Code: DC08                                                                                  Subject: DATA STRUCTURES

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 A*B+C/D  is

(A) *AB/CD+                                  (B) AB*CD/+

(C) A*BC+/D (D) ABCD+/*

b. Let the following circular queue can accommodate maximum six elements with the following data

                       front = 2                             rear = 4

                       queue = _______;              L, M, N, ___, ___

                                                                 What will happen after ADD O operation takes place?

(A)   front = 2                    rear = 5

        queue = ______;       L, M, N, O, ___

(B)   front = 3                    rear = 5

        queue = L, M, N, O, ___

(C) front = 3                    rear = 4

        queue = ______;       L, M, N, O, ___

(D) front = 2                    rear = 4

        queue = L, M, N, O, ___

             c.   A binary tree of depth “d” is an almost complete binary tree if

(A) Each leaf in the tree is either at level “d” or at level “d–1”

(B)  For any node “n” in the tree with a right descendent at level “d” all the left descendents of “n” that are leaves, are also at level “d”

(C)  Both (A) & (B)

(D)  None of the above

             d.   A linear collection of data elements where the linear node is given by means of pointer is called

(A)  linked list                                     (B)  node list

(C)  primitive list                                 (D)  None of these

             e.   Representation of data structure in memory is known as:

(A)  recursive                                      (B)  abstract data type

(C)  storage structure                           (D)  file structure

             f.    If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2 bytes then the array has been stored in _________ order.

(A)  row major                                    (B)  column major

(C)  matix major                                  (D)  none of these

g. An adjacency matrix representation of a graph cannot contain information of :

(A) nodes                                           (B)  edges

(C)  direction of edges                         (D)  parallel edges

             h.   Quick sort is also known as

(A) merge sort                                    (B)  heap sort

(C)  bubble sort                                   (D)  none of these 

             i.    One of the major drawback of B-Tree is the difficulty of traversing the keys sequentially.

(A)  True                                             (B)  False

j. O(N) (linear time) is better than O(1) constant time.

(A)  True                                             (B)  False

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Define data type and abstract data type. Comment upon the significance of both.                (8)

     b.   Write a procedure to reverse a singly linked list.                                                  (8)

Q.3     a.   Write an algorithm to convert an infix expression to a postfix expression. Execute your algorithm with the following infix expression as input

(8)

             b.   A double ended queue is a linear list where additions and deletions can be performed at either end. Represent a double ended queue using an array to store elements and write modules for additions and deletions.                                             (8)

Q.4     a.   Enumerate various operations possible on ordered lists and arrays. Write procedures to insert and delete an element in to array.                              (8)

b.   By taking an example show how multidimensional array can be represented in one dimensional array.                                                           (8)

Q.5     a.   Write an algorithm for bubble sort. Show the various passes of this sorting on an unsorted list 11, 15, 2, 13, 6                                                                                                                       (8)

     b.   Compare and contrast various sorting techniques with respect to memory space and computing time.                                                                     (8)

  Q.6     a. What do you mean by hash clash? Explain in detail any one method to resolve hash collisions.                                                                    (8)

             b.   Describe the concept of binary search technique? Is it efficient than sequential search?                    (8)

Q.7     a.   Prove the hypothesis that “A tree having ‘m’ nodes has exactly (m–1) edges or branches”.              (8)

b.   What do you understand by tree traversal? Write a procedure for traversing a binary tree in preorder and execute it on the following tree.            (8)

Q.8     a.   Write a procedure to insert a node into a linked list at a specific position and draw the same by taking any example?                                             (8)

             b    Explain insertion into a B-tree.                                                                           (8)

Q.9     a.   Define adjacency matrix and make the same for the following undirected graph.                  (8)

             b.  Show the linked representation of the above graph.                                              (8)