Code: DC-08 Subject: DATA STRUCTURES

Time: 3 Hours Max. Marks: 100

NOTE: There are 11 Questions in all.

Question 1 is compulsory and carries 16 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

Any required data not explicitly given, may be suitably assumed and stated.

Q.1 Choose the correct or best alternative in the following: (2x8)

a. In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order?

(A) left, root, right (B) root, left, right

(C) right, root, left (D) right, left, root

b. The equivalent prefix expression for the following infix expression (A+B)-(C+D*E)/F*G is

(A) -+AB*/+C*DEFG (B) /-+AB*+C*DEFG

(C) -/+AB*+CDE*FG (D) -+AB*/+CDE*FG

c. The number of nodes in a complete binary tree of depth d is

(A) (B)

(C) (D)

d. Ackermans function is defined on the non-negative integers as follows

a (m,n) = n+1 if m=0

= a (m-1, 1) if m0, n=0

= a (m-1, a(m, n-1)) if m0, n0

The value of a (1, 3) is

(A) 4. (B) 5.

(C) 6. (D) 7.

e. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is

(A) 600. (B) 350.

(C) 650. (D) 588.

f. The worst case of quick sort has order

(A) O(n²) (B) O(n)

(C) O(n log₂n) (D) O(log₂n)

g. For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is

(A) ne (B) 2n

(C) 2e (D) eⁿ

h. The time required to delete a node x from a doubly linked list having n nodes is

(A) O (n) (B) O (logn)

(C) O (1) (D) O (n logn)

PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2 a. What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine. (4)

b. Explain any three methods of representing polynomials using arrays. Write which method is most efficient for representing the following polynomials.

(i) 8x¹⁰⁰+10x+6

(ii) 8x³-7x²+5x+15

Write an algorithm to add two polynomials using any one of your representations. (10)

Q.3 a. Let X = (X1, X2, X3,.Xn) and Y= (Y1, Y2, Y3,.Xm) be two linked lists. Write an algorithm to merge the lists together to obtain the linked list Z such that Z = (X1, Y1, X2, Y2,.Xm, Ym,Xm+1.Xn) if m<=n or Z = (X1, Y1,X2,Y2.Xn,Yn,Yn+1.Ym) if m>n. (7)

b. Devise a representation for a list where insertions and deletions can be made at either end. Such a structure is called a Deque (Double ended queue). Write functions for inserting and deleting at either end. (7)

Q.4 a. Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not. (7)

b. Implement a stack using linked list. Show both the PUSH and POP operations. (7)

Q.5 a. Write binary search algorithm and trace it to search element 91 in following list:

What are the limitations of Binary Search? (7)

b. What are the two phases in heap sort algorithm? Sort the following data

using heap sort and show all the intermediate steps.

88, 12, 91, 23, 10, 36, 45, 55, 15, 39, 81 (7)

Q.6 a. What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.

45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92 (7)

b. Traverse the Binary Search Tree created above in Preorder, Inorder and Postorder. (7)

PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7 a. What is a sparse matrix? How is it stored in the memory of a computer? Write a function to find the transpose of a sparse matrix using this representation. (8)

b. What do you understand by row-major order and column-major order of arrays? Derive a formula for calculating the address of an array element in terms of the row number, column number and the base address of the array. (6)

Q.8 a. Write an algorithm for converting an infix expression into a postfix expression using stack. Illustrate the steps for the following expression. (((a+b)*c) / (d+e)) (7)

b. Write an algorithm for finding solution to the Towers of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams. (7)

Q.9 a. Suppose we have divided n elements in to m sorted lists. Explain how to produce a single sorted list of all n elements in time O (n log m)? (7)

b. Define hashing. Describe any two commonly used hash functions. Describe one method of collision resolution. (7)

Q.10 a. A Binary tree has 9 nodes. The inorder and preorder traversals of the tree yields the following sequence of nodes:

Inorder :	E	A	C	K	F	H	D	B	G
Preorder:	F	A	E	K	C	D	H	G	B

Draw the tree. Explain your algorithm. (7)

b. What are B-trees? Construct a B-Tree of order 3 for the following set of

input data:

69, 19, 43, 16, 25, 40, 132, 100, 145, 7, 15, 18 (7)

Q.11 a. What is the difference between Prims algorithm and Kruskals algorithm for finding the minimum-spanning tree of a graph? Execute both Prims and Kruskals algorithms on the following graph. (8)