Code: DC-08                                                                                Subject: DATA STRUCTURES 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 data structure required to check whether an expression contains balanced parenthesis is   

 

                   (A)  Stack                                           (B) Queue

(C)  Tree                                             (D) Array

                                                          

b.      The complexity of searching an element from a set of n elements using Binary search algorithm is

 

(A)    O(n)                                             (B) O(log n)

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

    

             c.   The number of leaf nodes in a complete binary tree of depth d is

                                                                                                                                                                                                                                                                                                                                                                                     

(A) 2d                                                  (B) 2d–1+1

(C) 2d+1+1                                           (D) 2d+1

 

 

             d.   A node having two children is deleted from a binary search tree is replaced by its

 

(A)      Inorder Predecessor                   (B)  Inorder Successor

(C)  Preorder Predecessor                  (D)  Preorder Successor   

      

             e.   Which of the following sorting methods would be most suitable for sorting a list which is almost sorted

                                                                                                                                                                                                                                                                                                                                                                                     

(A) Bubble Sort                                   (B) Insertion Sort

(C) Selection Sort                                (D) Quick Sort

 

             f.    A B-tree of minimum degree t can maximum _____ pointers in a node.

 

(A)  t–1                                               (B)  2t–1

(C)  2t                                                 (D)  t

 

             g.   The searching technique which takes constant amount of time to find a data is

 

(A) Linear Search                                (B) Tree Search  

(C) Binary Search                                (D) Hashing

 

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

 

(A)    greater than n–1                           (B)  less than n(n–1)

(C)  greater than n(n–1)/2                    (D)  less than n2/2

 

i.         A  BST is traversed in the following order recursively:

                                                                       Right, root, left

                   The output sequence will be in

(A)   Ascending order                           (B)  Descending order

(C) Bitomic sequence                          (D)  No specific order

 

             j.    The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum

 

(A)    Three nodes                                 (B)  Two nodes

(C)  One node                                     (D)  Any number of nodes 

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

  Q.2     a.   What is an algorithm? What are the characteristics of a good algorithm?              (5)

 

             b.   Time and space complexities are inversely proportional. Is it true? Justify your answer.                    (4)

 

             c.   What are stacks? How can stacks be used to check whether an expression is correctly parenthized or not.  For eg(()) is well formed but (() or )()( is not.                                                                     (7)

                                                                             

  Q.3     a.   What is a linear array? Explain how two dimensional arrays are represented in memory.                  (8)

 

             b.   Write an algorithm to merge two sorted arrays into a third array. Do not sort the third array.                                                                      (8)                                                             

                  

  Q.4     a.   Write a complete programme in C to create a single linked list. Write functions to do the following operations

(i)   Insert a new node at the end

(ii)  Delete the first node                                                                                    (8)

 

             b.   Explain how polynomials can be represented using linked lists. Write a programme in C to add two polynomials using your representation.  (8)

 

  Q.5     a.   Write an algorithm to convert an infix expression to a post fix expression. Execute your algorithm with the following infix expression on your input

                                                                                    (8)

 

             b.   Devise a representation for a list where insertions and deletions can be made at either end. Such a structure is called Deque (Double ended queue). Write functions for inserting and deleting at either end.            (8)

 

  Q.6     a.   Write an algorithm and the corresponding C Programme for Quick Sort. Execute your algorithm on the following data till two key values are placed in their position 12,34,45,15,4,11,7,8,5,14,35,89,43,21.                                                           (8)

 

             b.   Define Hashing. How do collisions happen during hashing. Explain the different techniques resolving of collision.                                              (8)

 

  Q.7     a.   What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.

                   45,32,90,34,68,72,15,24,30,66,11,50,10

                   Traverse the BST created in Pre-order, Inorder and Postorder.                          (8)   

 

             b.   What is a Binary Tree? What is the maximum number of nodes possible in a Binary Tree of depth d. Explain the following terms with respect to Binary trees

                   (i) Strictly Binary Tree    (ii) Complete Binary Tree    (iii) Almost Complete Binary Tree                  (8)

 

  Q.8     a.   What is a Spanning tree of a graph? What is minimum spanning tree? Execute Prism’s Kruskal’s algorithm to find the minimum spanning tree of the following graph.                                                       (10)

 

 

             b  What are B-trees? Draw a B-tree of order 3 for the following sequence of keys.

                   3,5,11,10,9,8,2,6,12                                                                                        (6)

 

  Q.9     a.   Show the result of running BFS and DFS on a directed graph given below using vertex 1 as source. Show the status of the data structure used at each stage.                                                              (10)

 

 

  

 

 

             b.  Construct a complete binary tree with depth 3 for this tree which is maintained in memory using linked representation.  Make the adjacency list and adjacency matrix for this tree.         (6)