Code: C-06 / T-06                          Subject: DATA STRUCTURES & ALGORITHM DESIGN

Time: 3 Hours                                                                              Flowchart: Alternate Process: December 2005                       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.  lg (n!) =____________

                                                                                                                                             

                  (A)  O (n)                                             (B)  O (lg n)

                  (C)  O (n2)                                           (D)  O (n lg n)                                       

                                                                                                                                                                 

b.      The result of evaluating the following postfix expression is

5, 7, 9, *, +, 4, 9, 3, /, +, -

 

                   (A)  50                                                (B)  65

(C)  61                                                (D)  69

 

             c.   A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are

 

                   (A)  more than n                                  (B)  more than n+1

(C)  more than (n+1)/2                        (D)  more than n(n-1)/2

                                                                                                                     

             d.   Out of the following, the slowest sorting procedure is

                  

                   (A)  Quick Sort                                   (B)  Heap Sort

                   (C)  Shell Sort                                     (D)  Bubble Sort

 

             e.   In ________, it is possible to traverse a tree without using stacks either implicitly or explicitly.

 

(A)     Threaded binary trees.                  (B)  AVL Tree

(C)  B+ tree                                         (D)  Heap

 

             f.    The order of a B-Tree with 2, 3, 4 or 5 children in every internal node is

 

(A)     2                                                  (B)  3

(C)  4                                                  (D)  5

 

             g.   The number of nodes that have no successors in a complete binary tree of depth 4 is

 

(A) 0                                                   (B)  8

(C) 16                                                 (D)  4

 

 

 

 

 

             h.   One can make an exact replica of a Binary Search Tree by traversing it in

     

(A)    Inorder                                         (B) Preorder

(C) Postorder                                      (D) Any order

 

             i.    A complete Binary Tree with 15 nodes contains________edges

 

(A)  15                                                (B)  30

(C)  14                                                (D)  16

 

             j.    The minimum number of comparisons required to find the largest number from 4 different numbers are

 

(A)  4                                                  (B)  3

(C)  5                                                  (D)  6

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

  Q.2     a.   What are the three different ways of representing a polynomial using arrays? Represent the following polynomials using any three different methods and compare their advantages and disadvantages.    

                   (i)

                  (ii)                                                                                         (8)

            

b.      Write an algorithm to evaluate the following polynomial. The number of additions and multiplications taken should be 5.                                        

                                                                                      (8)

 

  Q.3     a.   Let P be a pointer to a circularly linked list. Show how this list may be used as a queue. That is, write algorithms to add and delete elements. Specify the value for P when the queue is empty.     (10)

 

             b.   Give an algorithm for a singly linked list, which reverses the direction of the links.                (6)       

 

  Q.4     a.   Suppose that we have numbers between 1 and 1000 in a Binary Search Tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Explain your answer.

            

(i)                  2, 252, 401, 398, 330, 344, 397, 363

(ii)                924, 220, 911, 244, 898, 258, 362, 363

(iii)               925, 202, 911, 240, 912, 245, 363

(iv)              2, 399, 387, 219, 266, 382, 381, 278, 363

(v)                935, 278, 347, 621, 299, 392, 358, 363                                             (10)

 

 

 

             b.   Professor Banyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a BST ends up in leaf. Consider three sets (1) set A, the keys to the left of the search path, (2) set B the keys on the search path and (3) set C, the keys on the right of the search path. Professor Banyan claims that any three keys must satisy . Is his claim true? Otherwise give a counter example to the professor’s claim.                                 (3)

 

             c.   Draw BSTs of height 2 and 3 on the set of keys {1, 4, 5, 10, 16, 17, 21}.          (3)

 

  Q.5     a.   Why don’t we allow a minimum degree of t=1 for a B-tree?                                (2)

       

             b.   Show all legal B-Trees of minimum degree 3 that represent {1, 2, 3, 4, 5, 6}.                     (4)

 

             c.   Show the result of inserting the keys 4,19, 17, 11, 3, 12, 8, 20, 22, 23, 13, 18, 14, 16, 1, 2, 24, 25, 26, 5 in order in to an empty B-Tree of degree 3. Only draw the configurations of the tree just before some node must split, and also draw the final configuration.                                                (10)

 

  Q.6     a.   Write down the algorithm for quick sort.                                                             (8)

 

             b.   Show how quick sort sorts the following sequences of keys:

                   5, 5, 8, 3, 4, 3, 2                                                                                               (7)

 

             c.   On which input data does the algorithm quick sort exhibit its worst-cse behaviour?              (1)

 

  Q.7     a.   What do you mean by hashing? Explain any five popular hash functions.    (5)

                                                     

             b.   Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5 using the hash function h (i) = (2i+5) mod 11                                                      (7)

 

             c.   Explain any two methods to resolve collision during hashing.                                (4)

 

  Q.8     a.   Find out the minimum spanning tree of the following graph.                               (8)
 
 

 

 


                  

 

 

 

 

 

 

 

 

 

 

             b.   Give an algorithm to compute the second minimum spanning tree of a graph.                       (8)

 

  Q.9     a.   Define a threaded binary tree. Write an algorithm for inorder traversal of a threaded binary tree.                                                                 (6)

 

             b.   Give an algorithm to sort data in a doubly linked list using insertion sort.             (10)