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. If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
(A) less than 1. (B) less than n.
(C) less than m. (D) less than n/2.
b. Let A be an adjacency matrix
of a graph G. The 
entry in the matrix 
, gives
(A) The number of paths of length K from vertex Vi to vertex Vj.
(B) Shortest path of K edges from vertex Vi to vertex Vj.
(C) Length of a Eulerian path from vertex Vi to vertex Vj.
(D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
c. The OS of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called
(A) Concatenation (B) Garbage collection
(C) Collision (D) Dynamic Memory Allocation
d. What is the following code segment doing?
void fn( ){
char c;
cin.get(c);
if (c != ‘\n’) {
fn( );
cout.put(c);
}
}
(A) The string entered is printed as it is.
(B) The string entered is printed in reverse order.
(C) It will go in an infinite loop.
(D) It will print an empty line.
e. You have to sort a list L consisting of a sorted list followed by a few “random” elements. Which of the following sorting methods would be especially suitable for such a task?
(A) Bubble sort (B) Selection sort
(C) Quick sort (D) Insertion sort
f. B Trees are generally
(A) very deep and narrow (B) very wide and shallow
(C) very deep and very wide (D) can not say
g. A technique for direct search is
(A) Binary Search (B) Linear Search
(C) Tree Search (D) Hashing
h. If a node having two children is deleted from a binary tree, it is replaced by its
(A) Inorder predecessor (B) Inorder successor
(C) Preorder predecessor (D) None of the above
PART I
Answer any THREE Questions. Each question carries 14 marks.
Q.2 a. What is an algorithm? What are the characteristics of a good algorithm? (4)
b. How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example. (5)
c. Compare
two functions 
and
for
various values of n. Determine when second becomes larger than first. (5)
Q.3 a. Explain an efficient way of storing a sparse matrix in memory. Write a module to find the transpose of a sparse matrix stored in this way. (10)
b. Explain an efficient way of storing two symmetric matrices of the same order in memory. (4)
Q.4 a. Write
an algorithm to evaluate a postfix expression. Execute your algorithm using
the following postfix expression as your input : a b + c d +*f 
. (7)
b. What are circular queues? Write down routines for inserting and deleting elements from a circular queue implemented using arrays. (7)
Q.5 a. How do you represent polynomials using linked lists? Write a procedure for adding two polynomials using your representation. (7)
b. Two linked lists contain information of the same type in ascending order.
Write a module to merge them to a single linked list that is sorted. (7)
Q.6 a. What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.
45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48
Traverse the tree in Preorder, Inorder and postorder. (8)
b. What are expression trees? Represent the following expression using a tree. Comment on the result that you get when this tree is traversed in Preorder, Inorder and postorder. (a-b) / ((c*d)+e) (6)
PART II
Answer any THREE Questions. Each question carries 14 marks.
Q.7 a. How do you rotate a Binary Tree? Explain right and left rotations with the help of an example. (8)
b. Taking a suitable example explain how a general tree can be represented as a Binary Tree. (6)
Q.8 a. What are the different ways of representing a graph? Represent the following graph using those ways. (6)
|
b. Show the result of running BFS and DFS on the directed graph given below using vertex 3 as source. Show the status of the data structure used at each stage. (8)
|
Q.9 a. Write an algorithm for finding solution to the Tower’s of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams. (5)
b. Reverse the order of elements on a stack S
(i) using two additional stacks.
(ii) using one additional queue.
(iii) using one additional stack and one variable. (9)
Q.10 a. What do you understand by hashing? Explain any three popular hashing functions. How collisions are resolved in hashing? (7)
b. A hash table contains 100 slots indexed from 1 to 100. The elements stored in the table have keys that range in value from 1 to 9999. Which, if any, of the following hash functions would work correctly? Explain your answer.
(i) Key MOD 1000
(ii) (Key+1) MOD 999
(iii) (Key MOD 1000) + 1 (7)
Q.11 Write short notes on any FOUR:-
(i) B Tree.
(ii) Time Complexity, Big O notation.
(iii) Merge Sort.
(iv) Threaded Binary Tree.
(v) Depth First Traversal. (3.5 x 4 = 14)