WBUT Queston Papers EE
Data Structure And Algorithm B Tech Sem 3rd2006
Graph sheet is provided on Page No. 31.
Time : 3 Hours ]
[ Full Marks : 70
Group – A
(Multiple Choice Questions)
 Choose the correct alternatives of the following : 10 x 1 = 10
i) A graph G with n nodes bipartite if it contains
a) n edges
b) a cycle of odd length
c) no cycle of odd length
d) n^{2} edges.
ii) The postfix equivalent of the prefix * + abcd is
a) ab + cd *
b) abed + – *
c) ab + cd*
d) ab + – cd * .
iii) A sort which compares adjacent elements in a list and switches where necessary is
a) insertion sort
b) heap sort
c) quick sort
d) bubble sort.
iv) The following sequence of operations is performed on a stack: push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop. The sequence of popped out values are
a) 2, 2, 1, 1, 2
b) 2, 2, 1, 2, 2
c) 2, 1, 2, 2, 1
d) 2, 1, % 2, 2.
v) The initial configuration of queue Is a, b, c, d (‘a’ is at the front). To get the configuration d_{T}c,b, a one needs a minimum of
a) 2 deletions and 3 additions
b) 3 deletions and 2 additions
c) 3 deletions and 3 additions
d) 3 deletions and 4 additions. [
vi) Which of the following sorting techniques requires extra space, than the data to be stored ?
a) Selection sort
b) Bubble sort
c) Heap sort
d) None of these. ____
vii) Which of the following methods has the best average case complexity for searching ? ~
£0 Hashing ,
b) Sequential
c) Random
d) Binaiy.
viii) A binaiy search tree is generated by inserting in order the following integers :
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is
a) (4,7)
b) (7,4)
c) ( 8, 3 )
d) (3, 8). I



Ix) The tecnlque of linear probing for Collision Resolution can lead to
a) clustering
b) efficient storage utilization
c) overflow
d) underflow.
x) Inserting a new node after a given node in a doubly Linked list requires
a) four pointer exchanges
b) two pointer exchanges
c) one pointer exchanges
d) no pointer exchanges. ,
Group • B ( 8hort Answer Questions )
Answer any three questions.
 Prove that for any nonempty binary true T, if is the number of leaves and n_{2} be the
number of nodes having degree 2, then n_{0} = n_{2} + 1.
 Write an algorithm for inorder traversal of a threaded binary tree. ^{5}
 a) How can a polynomial such as 6x ^{6} + 4x ^{3} – 2x + 10 be represented by a linked
list ?
b) Suggest an algorithm to reverse the direction of all the links of a singly linked
list.
 a) Explain /( n) = O ( g ( n)).
b) What is the advantage of binary search over linear search ?
 Compare linked list with array in respect of both advantages and disadvantages. 5
Group – C ( Long Answer Questions )
Answer any three questions.
Define a directed graph. Provide an example.
Discuss about the following terminolgy
I) Indegree
II) Sink
III) Cycle
iv) Network.
Define adjacency matrix corresponding to a digraph.
Draw the graph corresponding to the following bit matrix :
0 0 0 1 10 11 10 0 1 0 0 10
What is path matrix ? 2
Count the total number of nodes of a binary tree having depth n. 1
Let a & b denotes positive integers. Suppose a function Q is defined as follows : 0 if a < b
Q ( a.b) = { Q ( a – b, b ) + 1 if b < = a }
Find the value of Q ( 2, 3 ) and Q ( 14. 3 ).
Transform the following expression to the expression In Postfix notation :
A*(B + D)/EP»(G + H/K)
Why is the Queue Data Structure called FIFO ?
Construct the following Queue of characters where Queue is a circular array which Is allocated six memory cells.
FRONT = 2 REAR = 4 QUEUE : _ . A, C, D________
Describe the Queue as the following operations take place :
I) F is added to the Queue
II) Two letters are from the Queue.
Hi) K.L.M are added to the Queue.
Iv) Two letters are deleted from the Queue.
v) R Is added to the Queue.
vi) One letter Is deleted from the Queue.
The inorder & preorder traversal sequence of nodes in a binary tree are given below :
Inorder: D G B A H E I C F
Preorder: ABDGCEHI F.
Draw the binary tree. State briefly the logic used to construct the tree.
Insert the following keys in the order given below to build them into an AVL tree. g, h, s, I e, m. t, u.
Clearly mention different rotations used and balance factor of each node.
What is 2way threading ? 6 + 6 + 3
What is BST ?
For the following Graph Find
I) BFS Traversal
II) DFS Traversal.
c) Explain with a suitable example the principles of operation of Heap sort.
d) Find the Time Complexity of the above algorithm.
 Write short notes on any three of the following :
a) AVL Tree
b) Tail Recursion
c) Collision Resolution using chaining
d) Dequeue — operation & application
e) Wars hall’s Algorithm.