Code: DC-08                                                                                Subject: DATA STRUCTURES

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.       The searching technique that takes O (1) time to find a data is 

 

                   (A)  Linear Search                               (B)  Binary Search

(C)    Hashing                                       (D)  Tree Search

                                                          

b.      A mathematical-model with a collection of operations defined on that model is called

 

(A)    Data Structure                              (B)  Abstract Data Type

(C)  Primitive Data Type                      (D)  Algorithm

            

             c.   The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is

                                                                            

(A) 6                                                   (B)  5

(C) 7                                                   (D)  8

                                                               

             d.   The postfix form of the expression  is

                  

(A)                   (B) 

(C)               (D)         

       

             e.   The complexity of multiplying two matrices of order m*n and n*p is

                  

(A)     mnp                                             (B)  mp

(C)  mn                                               (D)  np

 

             f.    Merging 4 sorted files containing 50, 10, 25 and 15 records will take____time

 

(A)     O (100)                                       (B) O (200)

(C)  O (175)                                       (D  O (125)

             g.   For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to

 

(A)     2n                                                (B)  (2n-1)/2

(C) 2e                                                 (D)  e2/2

 

             h.   In worst case Quick Sort has order

 

(A) O (n log n)                                    (B)  O (n2/2)

(C) O (log n)                                       (D)  O (n2/4)

 

             i.    A full binary tree with 2n+1 nodes contain

 

(A) n leaf nodes                                   (B)  n non-leaf nodes

(C) n-1 leaf nodes                               (D)  n-1 non-leaf nodes

 

             j.    If a node in a BST has two children, then its inorder predecessor has

 

(A) no left child                                    (B)  no right child

(C) two children                                  (D)  no child

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

  Q.2     a.   Define the term array. How are two-dimensional arrays represented in memory? Explain how address of an element is calculated in a two dimensional array.                                                                 (8)

       

             b.   An, array, A contains n unique integers from the range x to y (x and y inclusive where n=y-x). That is, there is one member that is not in A. Design an O(n) time algorithm for finding that number. (8)

 

  Q.3     a.   Draw the expression tree of the following infix expression. Convert it in to Prefix and Postfix expressions.   

                                                                                        (9)

 

             b.   Write an algorithm to evaluate postfix expression.                                               (7)

                  

  Q.4     a.   Implement a Queue using a singly linked list L. The operations INSERT and DELETE should still take O (1) time.                                                    (6)

 

             b.   Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.                                                                                                                (10)

 

  Q.5     a.   Two Binary Trees are similar if they are both empty or if they are both non-empty and left and right sub trees are similar. Write an algorithm to determine if two Binary Trees are similar.          (8)

       

             b.   The degree of a node is the number of children it has. Show that in any binary tree, the number of leaves are one more than the number of nodes of degree 2.                                                                (8)

 

  Q.6     a.   Write an algorithm to test whether a Binary Tree is a Binary Search Tree.            (4)

 

             b.   Write the non-recursive algorithm to traverse a tree in preorder.                          (8)

 

c.       Give the adjacency matrix for the following graph:                                               (4)
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


                                                                               

  Q.7     a.   Draw the complete undirected graphs on one, two, three, four and five vertices. Prove that the number of edges in an n vertex complete graph is n(n-1)/2.                                                                 (8)   

 

             b.   Apply BFS and DFS to the complete graph on four vertices. List the vertices in the order they would be visited.                                                 (8)

 

  Q.8     a.   Bubble sort algorithm is inefficient because it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comparisons in the best and worst cases are the same. Modify the algorithm in such a fashion that it will not make the next pass when the array is already sorted.                                                              (12)

 

             b   Which sorting algorithm is easily adaptable to singly linked lists? Explain your answer.                      (4)

 

  Q.9     a.   Sort the following sequence of keys using merge sort.

                   66, 77, 11, 88, 99, 22, 33, 44, 55                                                                     (8)

 

             b.   Draw a B-tree of order 3 for the following sequence of keys:

 

                   2, 4, 9, 8, 7, 6, 3, 1, 5, 10                                                                                 (8)