Code: DC-08 Subject: DATA STRUCTURES
Time: 3 Hours June 2006 Max. Marks: 100
NOTE: There are 9 Questions in all.
· Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.
· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.
· Any required data not explicitly given, may be suitably assumed and stated.
Q.1 Choose the correct or best alternative in the following: (2x10)
a. A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as
(A) full binary tree. (B) AVL tree.
(C) threaded tree. (D) complete binary tree.
b. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a
(A) queue. (B) stack.
(C) tree. (D) linked list.
c. What is the postfix form of the following prefix expression
-A/B*C$DE
(A) ABCDE$*/- (B) A-BCDE$*/-
(C) ABC$ED*/- (D) A-BCDE$*/
d. A full binary tree with n leaves contains
(A)
n
nodes. (B) 
nodes.
(C) 2n –1 nodes. (D)
nodes.
e. A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
(A) insertion sort. (B) selection sort.
(C) heap sort. (D) quick sort.
f. Which of the
following sorting algorithms does not have a worst case running time of 
?
(A) Insertion sort (B) Merge sort
(C) Quick sort (D Bubble sort
g. An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?
(A) O (n) (B) O (e)
(C) O (e+n) (D)
O 
h. Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer?
(A) O (1) (B)
O 
(C) O (n) (D)
O 
i. The smallest element of an array’s index is called its
(A) lower bound. (B) upper bound.
(C) range. (D) extraction.
j. In a circular linked list
(A) components are all linked together in some sequential manner.
(B) there is no beginning and no end.
(C) components are arranged hierarchically.
(D) forward and backward traversal within the list is permitted.
Answer any FIVE Questions out of EIGHT Questions.
Each question carries 16 marks.
Q.2 a. What do you mean by complexity of an algorithm? Explain the meaning of worst case analysis and best case analysis with an example. (8)
b. Explain
the method to calculate the address of an element in an array. A 
matrix array DATA
is stored in memory in ‘row-major order’. If base address is 200 and 
words per memory
cell. Calculate the address of DATA [12, 3] . (8)
Q.3 a. What is the difference between a grounded header link list and a circular header link list? (3)
b. Write an algorithm to insert a node in the beginning of the linked list. (7)
c. Explain
how the two polynomials 
and 
be added using linked lists. (6)
Q.4 a. Write an algorithm that deletes an element from a queue and assigns it to a variable ITEM. (8)
b. Convert the following infix expressions into its equivalent postfix expressions;
(i) 
(ii)
(8)
Q.5 a. What is quick sort? Sort the following array using quick sort method.
24 56 47 35 10 90 82 31 (7)
b. How many key comparisons and assignments an insertion sort makes in its worst case? (4)
c. Create a heap with following list of keys:
8, 20, 9, 4, 15, 10, 7, 22, 3, 12 (5)
Q.6 a. The following values are to be stored in a hash table
25, 42, 96, 101, 102, 162, 197
Describe how the values are hashed by using division method of hashing with a table size of 7. Use chaining as the method of collision resolution. (8)
b. Write an algorithm INSERT that takes a pointer to a sorted list and a pointer to a node and inserts the node into its correct position in the list. (8)
Q.7 a. Write a non recursive algorithm to traverse a binary tree in inorder. (8)
b. Describe insertion sort with a proper algorithm. What is the complexity of insertion sort in the worst case? (8)
Q.8 a. Which are the two standard ways of traversing a graph? Explain them with an example of each. (8)
b Consider the following specification of a graph G
(i) Draw an undirected graph.
(ii) Draw its adjacency matrix. (8)
Q.9 Write short notes on the following:
(i) B-tree.
(ii) Abstract data type.
(iii) Simulation of queues. (5+6+5)