Code: AC06 /
AT06
Subject: DATA STRUCTURES & ALGORITHM DESIGN
Time: 3 Hours 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. To implement Sparse matrix dynamically, the following data structure is used
(A) Trees (B) Graphs
(C) Priority Queues (D) Linked List
b. The depth dn, of complete binary tree of n nodes, where nodes are labeled from 1 to n with root as node 1 and last leaf node as node n is
(A) 
(B) 
(C) 
(D) 
c. The balance factor for an AVL tree is either
(A) 0,1 or –1 (B) –2,–1 or 0
(C) 0,1 or 2 (D) All the above
d. Applications of Linked List are
(A) Simulation , event driven systems
(B) Postfix and prefix manipulations
(C) Dictionary systems, polynomial manipulations
(D) Fixed block storage allocation, garbage collection
e. AVL trees have LL, LR, RR, RL rotations to balance the tree to maintain the balance factor (LR : Insert node in Right sub tree of Left sub tree of node A, etc). Among rotations the following are single and double rotations
(A) LL, RL and LR, RR (B) LL, RR and LR, RL
(C) LR, RR and LL, RL (D) LR, RL and LR, RL
f. Hashing collision resolution techniques are
(A) Huffman coding, linear hashing (B) Bucket addressing, Huffman coding
(C) Chaining, Huffman coding (D) Chaining, Bucket addressing
g. The running time of the following sorting algorithm depends on whether the partitioning is balanced or unbalanced
(A) Insertion sort (B) Selection sort
(C) Quick sort (D) Merge sort
h. Graphs are represented using
(A) Adjacency tree (B) Adjacency linked list
(C) Adjacency graph (D) Adjacency queue
i. The average case complexity of Insertion Sort is
(A) O(2n) (B) O(n3)
(C) O(n2) (D) O(2n)
j. Infinite recursion leads to
(A) Overflow of run-time stack (B) Underflow of registers usage
(C) Overflow of I/O cycles (D) Underflow of run-time stack
Answer any FIVE Questions out of EIGHT Questions.
Each question carries 16 marks.
Q.2 a. What is an Abstract data type (ADT)? Explain with an example. (4)
b. Consider a list of numbers 9, 20, 6, 10, 14, 8, 60, 11 given. Sort them using Quick Sort. Give step wise calculation. (8)
c. What is a sparse matrix? Explain an efficient way of storing a sparse matrix in memory. (4)
Q.3 a. Evaluate the following prefix expressions (9)
(i) + * 2 + / 14 2 5 1
(ii) – * 6 3 – 4 1
(iii) + + 2 6 + – 13 2 4
b. (i) Give four properties of Big –O Notations. (4)
(ii) Give the graphical notations of Big-O estimations for the following functions:
, n , 
, n2,
n3, 2n
(3)
Q.4 a. Write an algorithm to insert an element k in double linked list at (8)
(i) Start of linked list
(ii) After a given position P of list
(iii) End of linked list.
b. Write an algorithm to add two polynomials using linked list. (8)
Q.5 a. Write modules to perform the following operation on Binary tree (8)
(i) count number of leaf nodes
(ii) find height of tree
b. Create B-Tree of order 5 from the following list of data items: (8)
20, 30, 35, 85, 10, 55, 60, 25
Q.6 a. Write an algorithm to insert an element k into binary search tree. Give the analysis and example. (8)
b. Fill in the following table, showing the number of comparisons necessary to either find a value in the array DATA or determine that the value is not in the array. (8)
DATA
|
26 |
42 |
96 |
101 |
102 |
162 |
197 |
201 |
243 |
[1] [2] [3] [4] [5] [6] [7] [8] [9]
Number of Comparisons
|
Value |
Sequential Ordered Search |
Binary Search |
|
26 |
|
|
|
2 |
|
|
|
103 |
|
|
|
244 |
|
|
Q.7 a. Explain the functionality of linear and quadratic probing with respect to hashing technique. (8)
b. The following values are to be stored in a hash table
25, 42, 96, 101, 102, 162, 197, 201
Use division method of hashing with a table size of 11. Use sequential method of resolving collision. Give the contents of array. (8)
Q.8 a. Write Kruskal’s algorithm and give the analysis. Compare it with Dijkstra’s method. (8)
b. Write algorithm for Breadth First Search (BFS) and give the complexity. (8)
Q.9 a. A binary tree T has 10 nodes. The inorder and preorder traversals of T yield the following sequence of nodes:
Inorder : D B H E A I F J C G
Preorder : A B D E H C F I J G
Draw the tree T. (8)
b. Construct AVL tree from the following set of elements
{ March, May, November, August, April, January, December, July } (8)