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. Which of the following data structure may give overflow error, even though the current number of elements in it, is less than its size
(A) simple queue (B) circular queue
(C) stack (D) none of these
b. In a binary tree, the number of leaf nodes are 10. The number of nodes with two children are
(A) 9 (B) 11
(C) 15 (D) none of these
c. Which of the following is a hash function:
(A) quadratic probing (B) chaining
(C) open addressing (D) folding
d. In an undirected graph of ‘n’ vertices and ‘e’ edges, the sum of degree of all vertices is 2e
(A) True (B) False
e. To store a diagonal square matrix of size nXn in one dimensional array, the minimum size of the array should be
(A) n2 (B) n
(C) n2–1 (D) n/2
f. The smallest number of keys that will force B-tree of order 3 to have a height 3 is
(A) 12 (B) 10
(C) 7 (D) none of these
g. Number of “ADD” and “REMOVE” operations required to access n/2th element of a queue of ‘n’ elements so that the original queue remains the same after the access is _______. Another queue can be considered for any help required.
(A) 4*n (B) 2
(C) 8*n–1 (D) 2*n
h. A stack cannot be used to
(A) evaluate an arithmetic expression in postfix form
(B) implement push and pop functions
(C) convert infix to postfix form of an expression
(D) allocate resources by operating system
i. ___________ can be used to find the shortest distance between given two nodes in the graph.
(A) BFS (B) DFS
(C) FIFO (D) stack
j. Adjacency matrix for a digraph is
(A) unit matrix (B) symmetric
(C) asymmetric matrix (D) none of these
Answer any FIVE Questions out of EIGHT Questions.
Each question carries 16 marks.
Q.2 a. Give mathematical background of “GRAPH” by explaining path, degree, and incidence. (8)
b. What do you understand by searching? Explain keys and records. What are internal and external searching? (8)
Q.3 a. Explain Selection Sort. Write a procedure to implement Selection Sort. (8)
b. Using Merge Sort algorithm sort the following list in an ascending order:
85, 76, 46, 92, 30, 41, 12, 19, 93, 3, 50, 11 (8)
Q.4 a. Give brief details about linked list by showing it diagrammatically. (8)
b. Write a program to construct a linear linked list of n numbers and to display the list in FIFO method. (8)
Q.5 a. Explain popping a node from a linked stack, with neat diagram. (8)
b. Write a program to create a binary tree. Write modules to display the contents of the tree using inorder tree traversal method. (8)
Q.6 a. Execute
BFS and DFS on the following graph with vertex E as the Starting Vertex. (6)
b. Construct a directed weighted graph on which Dijkstra’s algorithm to find the shortest path will fail. (5)
c. Compare the two
functions 
and
for
various values of n. Determine when the second becomes larger than the first. (5)
Q.7 a. Take any binary tree. Draw the mirror image of this binary tree. (4)
b. Write an algorithm for converting an infix expression to a postfix expression. Execute your algorithm on the following expression as the input
(12)
Q.8 a. Write down the algorithm for Binary Search. What is the complexity of Binary Search? (8)
b Explain the concept of adding two polynomials and also write the steps involved for adding two polynomials. (8)
Q.9 a. Write a procedure to handle collision in hashing using open addressing/rehashing method. (10)
b. Consider the following binary search tree. Describe the tree when
(i) the node O is deleted
(ii) the node P is also deleted (6)
