# UPTU Previous Year Exam Papers

# B Tech 3rd Semester

# Data Structure Using C 2009-10

**Note : Attempt all questions.**

**1 Attempt any four parts : **

(a) Explain the different ways of analyzing algorithm.

(b) Write an efficient algorithm to find the k^{th} element in a sequence of n elements.

(c) Write an algoritlim which obtains the transpose of nxn sequence matrix onto itself

(d) Write the traversing algorithm for a linear array.

(e) Write an algorithm and a C function to reverse a single linked list.

(f) What is double linked list ? What are the advantage and disadvantage of double linked list ?

**2. Attempt any four parts : **

(a) Write deletion algorithm for a steak. What is its complexity

(b) Write an efficient algorithm which converts in-fix expressions into port fix expression.

(c) How can you reverse a string using stack ^{0} Give one example and show how you can reverse a given string using stack.

(d) Write a C program to implement a queue using linked list.

(e) Give short notes one :

(i) Dequeue

(ii) Priority Queues.

(f) What is recurrsione ? Write a C program to solve Tower of Hanoi problem.

**3. Attempt any two parts : **

(a) (i) If the in-order traversal of a binary tree is B, I, D, A, C, G E. H, F and its port – order traversal is I, D, B, G C, H, F, F, A. Determine the binary tree.

(ii) Write an algorithm to convert a forest in to a binary tree.

(b) What is a binary search tree ? Write a C program to insert new notes to a binary search tree and delete a given node from a binary search tree.

(c) Write shorts notes one :

(i) Height balance tree

(ii) Thread binary tree.

**4. Attempt any two parts : **

(a) (i) Obtain the minimum number of entries

that can be made in a B-tree of order m and of levels /.

(ii) Use merge – sort algorithm to sort the following elements 15, 10, 5, 20, 25, 30, 40, 35.

(b) How can you find shortest path between two nodes in a graph by Dijkstra’s algorithm^{9} Explain by suitable diagram and algorithm

(c) What is a graph ^{9} Differentiate between

(i) uncorrected and directed graph (ii) Cycle and Hamiltonian cycle.

**5 . Attempt any two questions : **

(a) Write down the algorithm for bubble sort and explain how you can sort an unsorted array of integers by using quick – sort. Find out the time complxity of your algorithm.

(b) Define hash function. State different types, of hash function. Give their algorithm and explain them by suitable diagram.

(c) Write shorts notes on :

(i) B+ Tree

(ii) Garbage collection.