Code: AC-06 / AT-06                    Subject: DATA STRUCTURES & ALGORITHM DESIGN Flowchart: Alternate Process: JUNE 2007

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.  The postfix form of the following infix notation is :

                                                                                                                                                                                                                                                                            

                  (A)                       (B)  

                  (C)                    (D)                        

                                                                                                        

b.      The number of nodes in a complete binary tree of depth d (with root at      depth 0) is

 

                   (A)                                        (B)  

(C)                                        (D) 

 

             c.   The average case of quick sort has order

 

                   (A)                                            (B)  

(C)                                     (D) 

                                                          

             d.   Inorder to get the information stored in a BST 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

 

             e.   Every internal node in a B-tree of minimum degree 2 can have

 

(A)     2, 3 or 4 children                          (B)  1, 2 or 3 children

(C)  2, 4 or 6 children                          (D)  0, 2 or 4 children

 

             f.    Which sorting algorithm is the best if the list is already in order?

 

                   (A)  Quick sort                                    (B)  Merge sort

                   (C)  Insertion sort                                (D)  Heap sort

 

             g.   In _________ the difference between the height of the left sub tree and height of right sub tree, for each node, is not more than one

 

(A)    BST                                             (B)  Complete Binary Tree

(C)  AVL-tree                                     (D)  B-tree

             h.   The number of comparisons required to sort 5 numbers in ascending order using bubble sort is  

           

(A)    7                                                  (B)  6

(C) 10                                                 (D)  5       

 

             i.    The complexity of adding two matrices of order m*n is

 

(A)  m + n                                           (B)  mn

(C)  max(m, n)                                     (D)  min(m, n)

 

             j.    The second largest number from a set of n distinct numbers can be found in

 

(A)  O(n)                                             (B)  O(2n)

(C)                                            (D)  O(log n)

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

  Q.2     a.   What is the smallest value of n such that an algorithm whose running time is  runs faster than an algorithm whose running time is  on the same machine? Justify your answer.                   (6)      

            

b.      Define a sparse matrix.  Explain an efficient way of storing sparse matrix in the memory of a computer.  Write an algorithm to find the transpose of sparse matrix using this representation.       (10)          

 

  Q.3     a.   What do you understand by row-major order and column-major order of arrays?  Derive their formulae for calculating the address of an array element in terms of the row-number, column-number and base address of array.                                                                                                                (8)

 

             b.   Using stacks, write an algorithm to determine whether an infix expression has balanced parenthesis or not.                                                              (8)

 

  Q.4     a.   How will you represent a max-heap sequentially?  Explain with an example.  Write an algorithm to insert an element to a max-heap that is represented sequentially.                                       (8)

 

             b.   Construct an expression tree for the expression .  Show all the steps and give pre-order, in-order and post-order traversals of the expression tree so formed.        (8)  

 

  Q.5     a.   Write an algorithm to find solution to the Towers of Hanoi problem.  Explain the working of your algorithm (with 3 disks) with diagrams.                (10)

       

             b.   What is recursion? A recursive procedure should have two properties.  What are they?  What type of recursive procedure can be converted in to iterative procedure without using stack?  Explain with example.                                                           (6)

       

  Q.6     a.   Give an  time non-recursive procedure that reverses a singly linked list of n nodes.  The procedure should not use more than constant storage beyond that needed for the list itself.                   (8)

 

             b.   Device 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.   (8)

 

  Q.7     a.   The height of a tree is the length of the longest path in the tree from root to any leaf.  Write an algorithmic function, which takes the value of a pointer to the root of the tree, then computes and prints the height of the tree and a path of that length.                                                                               (8)

 

             b.   Two Binary trees are similar if they are both empty or if they are both non-empty and left and right subtrees are similar.  Write an algorithm to determine if two binary trees are similar.           (8)

            

  Q.8     a.   Write an algorithm for Binary search.  What are the conditions under which sequential search of a list is preferred over binary search?                 (7)

 

             b.   Work through Binary Search algorithm on an ordered file with the following keys {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.  Determine the number of key comparisons made while searching for keys 2, 10 and 15.                             (9)

 

  Q.9     a.   Consider the following undirected graph:
 
 


               

                       

(i)                  Find the adjacency list representation of the graph.

(ii)                Find a depth-first spanning tree starting at A.

(iii)               Find a breadth-first spanning tree starting at A.

(iv)              Find a minimum cost spanning tree by Kruskal’s algorithm.       (4 x 3 = 12)

 

             b.   Suppose that a graph has a minimum spanning tree already computed.  How quickly can the minimum spanning tree be updated if a new vertex and incident edges are added to G?                          (4)