Deemed University 2011 B.Tech Computer Science and Engineering University: Lingayas University Term: V Title of the : Data Structures

Roll No. ..

 

Lingayas University

B.Tech. 2^nd Year (Term V)

Examination Feb 2011

Data Structures & Algorithms (CS - 201)

 

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: All questions carry equal marks. Attempt five questions in all. Question no. 1 is compulsory. Select two questions from Section B and two questions from Section C.

Section A

Q-1. Part - A

Select the correct answer of the following multiple choice questions. (10x1=10)

(i) Given two sorted list of size m and n respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be

(a) m x n (b) maximum of m, n

(c) minimum of m, n (d) m + n 1

(ii) The depth of a complete binary tree with n nodes is (Log is to the base two)

(a) log (n + 1) 1 (b) log (n)

(c) log (n 1) + 1 (d) log (n) + 1

(iii) The average successful search time taken by binary search on a sorted array of 10 items is

(a) 2.6 (b) 2.7

(c) 2.8 (d) 2.9

(iv) The number of possible binary trees with 4-nodes is

(a) 12 (b) 13

(c) 14 (d) 15

(v) Sorting is useful for

(a) Report generation

(b) Making searching easier and efficient

(c) Responding to queries easily

(d) All of above

(vi) Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?

(a) Heap sort (b) Quick sort

(c) Insertion sort (d) Selection sort

(vii) The order of the binary search algorithm is

(a) n (b) n²

(c) nlog(n) (d) log(n)

(viii) A binary tree has n leaf nodes the number of degree 2 in this tree is

(a) log₂n (b) n 1

(c) n (d) 2ⁿ

(ix) The minimum number of edges in a connected cyclic graph on n vertices is

(a) n 1 (b) n

(c) n + 1 (d) none of above

(x) The maximum number of values stored in an array A[-1 .m, 1 m] is

(a) m+1 (b) m(m+1) (c) m (d) m (m+2)

 

Part B

(a) Evaluate the following expression into prefix form

A * (b + c) + (b/d) * a + z * u (5)

(b) Evaluate the following expression into postfix form

a + ((b + c) * (d + e) + f / g) (5)

 

Section B

Q-2. (a) Define data structures. Name and explain them briefly. Also discuss various operations of the data structures.

(b)Write an algorithm to delete an item from the sorted array? (2x10=20)

Q-3. (a) What is recursion? Give the suitable example to represent recursion?

(b) What is the complexity of an algorithm? Discuss asymptotic notations to represent the complexity. (2x10=20)

 

Q-4. (a) Write a C program to implement the linear queue. The program must contain different functions for enqueue, dequeue and display operations. (10)

(b) Why queue overflow condition is not checked when the queue is implemented using link list? (5)

(c) Evaluate the following postfix expression using a stack.

20 4 3 * 6 3/1 3 * - 2 * + (5)

 

Section C

Q-5. (a) Suppose that P is the reference to start node in a linked list with 15 nodes. Write an algorithm that will make a new copy of the list. Your algorithm should have X pointing to the start of newly created link list.

(b) Give the advantages & disadvantages of link list over arrays. Also write an algorithm for deleting a node from the beginning of the link list? (2x10=20)

 

Q-6. (a) Prove that the maximum height of the binary tree is n and the minimum height of the binary tree is log₂(n+1).

(b) For a binary tree T, the in-order and P re-order traversal sequences are as follows:

pre-order : DCKEAHBQJI

in-order : DKECHQJIBA (2x10=20)

Q-7. (a) Define hasing. Also discuss different hash function. What are the advantages of hashing over other searching techniques?

(b) Write the algorithm for BFS and DFS and specify the data structure used for these implementation. (2x10=20)

 

Q-8. (a) Explain bubble sort with algorithm. Calculate the run time complexity of this algorithm.

(b) Explain selection sort with algorithm. Give the run time complexity of this algorithm. (2x10=20)