Uttar Pradesh Technical University (UPTU) 2010-3rd Sem B.Tech Computer Science and Engineering -ester-Data Structures Using C - Question Paper

B.Tech
(IIIrd sem)Odd Semester Theory exam 2010-2011
Data Structures using 'C'
Total Time: three hours Total Marks: 100

1. Attempt any 4 parts: [Marks 5*4=20]
(i) Determine the formula to obtain the address location of an element in 3 dimensional array, suppose every element takes 4 bytes of space and elements are stored in column major order.
(ii) Write and discuss the algorithm to obtain the seventh smallest element in an array.
(iii) Write a program using C to create an array of 10 elements. Take 10 elements in the array pass them to a function which prints them in a reverse order.
(iv) Write an element to obtain out the location of an element in the linked list. Is the binary search suitable for this search? discuss the cause.
(v) How a polynomial formula can be represented through link list? discuss the method to add 2 polynomial formula using link list.
(vi) describe duoble link list. Write an algorithm to delete an element from the existing link list.

2. Attemt any 4 parts: [Marks 5*4=20]
(a) Write an algorithm to evaluate an expression provided in postfix notation.
(b) describe recursion. Write a recursive and non recursive program to compute the factorial of the provided number.
(c) What do you mean by priority queue? discuss the kinds to maintain the priority queue.
(d) What is circular queue? Write a C function to insert an element in the circular queue.
(e) What is the Tower of Hanoi problem? discuss the solution to Tower of Hanoi issue where number of disks are 4 and number of pegs are three.
(f) Convert the subsequent infix expression into postfix expression:
A*(B+D)/E-F*(G+H/K)
3. Attempt any 2 parts of the following: [Marks 10*2=20]
(a) (i) Determine in the terms of level one the maximum number of possible nodes at level one in binary tree, and also determine the maximum number of possible nodes in a binary tree is the root node is at level 1.
(ii) How a node can be deleted from a binary search tree?Explain the method.
(b) Write the function in C to insert and delete a node in the existing binary search tree.
(c) The preorder and inorder traversal of binary tree is provided beneath. Construct the tree.
Preorder: FAEKCDHGB
Inorder: EACKFHDBG

4. Attempt any 2 parts of the following: [Marks 10*2=20]
(a) Write and discuss the breadth 1st search and depth 1st graph traversal algorithm. elaborate their complexities?
(b) describe the spanning tree. Write the Prim's algorithm to obtain out the minimum cost spanning tree of the following:
Figure 1

(c)Write the Dijikstra's algorithm for finding shortest path with help of suitable example.

5. Attempt any 2 parts of the following: [Marks 10*2=20]
(a) Write the algorithm for bubble sort and insertion sort. discuss their best case and worst case complexities.
(b) Write the algorithm for merge sort. discuss it's complexity. Sort the subsequent using merge sort method:
75,10,20,70,80,90,100,40,30,50
(c) discuss the following:
(i) Heap sort
(ii) Radix sort

Attachment: uttar-pradesh-technical-university--uptu--2010-b-tech-computer-science-and-engineering-20588-1.kra uttar-pradesh-technical-university--uptu--2010-b-tech-computer-science-and-engineering-20588-2.JPG

Earning:   Approval pending.