WBUT Previous Years Question Papers EE
Data Structure And Algorithm B Tech Sem 3rd Dec 2007
Time : 3 Hours ]
Full Marks : 70
GROUPA (Multiple Choice Type Questions)
 1. Choose the correct alternatives of the following : 10 x 1 = 10
1) The vertex, removal of which makes a graph disconnected is called
a) pendant vertex b) bridge
c) articulation point d) colored vertex. _{(} •
ii) Stability of Sorting Algorithm is Important for
a) Sorting records on the basis of multiple keys
b) Worst case performance of sorting algorithm
c) Sorting alpha numeric keys as they are likely to be the same
d) None of these. „ 1
111) A vertex of indegree zero in a directed graph is called
a) articulation point b) sink
c) isolated vertex d) root vertex. 
iv) The ratio of Items present in the. hash table, to the total table size is called
b) load factor
d) none of these. ‘
v) The Ackerman function, fdr all nonnegative values of m and n is recursively defined as , , –
n + 1 ifm = 0
A ( m – 1, 1 ) if m ! = 0 but n = 0
A(ml,A(m,nl)) if m ! = 0 and n ! = 0
Therefore the value of A ( 1, 2 ) is
a) 4 b) ‘ 3
c) 5
2.
If a binary tree is threaded for inorder traversal a right NULL link of any node is replaced by the address Of its







vii) In a height balanced tree the heights of two subtrees of every node never differ by more than
a)
c)
viii) Adjacency matrix of a digraph is
a) identity matrix
c) asymmetric matrix
b) 0
d) I.
1?) symmetric matrix
d) none of these.
ix) Which of the following is the best time for an algorithm ?
a) O(n) b) (log_{2} n)
c) 0(2″) d) O (nlog_{2}n).
A linear list in which elements can be added or removed at either end but not in the middle is known as







GROUPB ( Short Answer Type Questions)
Answer any three of the following.
Show that the function/( n) defined by:
/( 1 ) = 1 .
fin) f (nl) + ^forn>l
has the complexity O (log n).
Define Big – O, Q, 0 notations. 2 + 3 = 5
Let the size of the elements stored in an 8 x 3 matrix be 4 bytes each. If the base address of the matrix is 3500, then find the address of A [ 4, 2, 1 for both row major & column major cases. What Is sparse matrix ? 2 + 2 + 1 = 5
Write an algorithm to Insert a node In a BST. 5
Write an algorithm to solve the Tower of Hanoi problem. Also calculate the time complexity of your algorithm. 5
Prove that, for any nonempty binary tree T, If n _{0} be the number 6f leaves and n i be the number of nodes of degree 2, then n _{0} = n j + 1. 5
GROUPC (Long Answer Type Questions)Answer any three questions. ’ 3×15 = 45
Write an algorithm of Merge Sort and explain with an example.
Compare the complexity of selection sort & Insertion sort.
Explain with a suitable example, the principal operation of Quick sort.
Find the complexity of Quick sort algorithm. 5 + 3 + 5 + 2=15
Write an algorithm to add two polynomials.
Write the recursive function for the Tower of Hanoi problem Also draw the recursion tree for any set of initial values.
What is hashing ? Explain Linear Probing & Quadratic Probing with example.
Derive values related to the average case and worst case behavior of Bubble Sort algorithm. Also, confirm that the best case behavior is O ( n).
 9. a) The inorder & preorder traversal sequence of nodes in a binary tree are given
below :
Inorder : EACKF HDBG Preorder : FAEKCDHGB
Draw the binary tree. State briefly the logic used to construct the tree.
b) Insert the following keys into a BTree of order 3 : p. q. r. d. h, m, I s. k, n.
c) Construct an expression tree for the expression E = ( 2x + y )* ( 5a – b ) ^{3}.
d) Write a nonrecursive algorithm for Inorder traversal of a binary tree.
 10. a) Write the difference between stack and queue and implement the operations of
priority queue.
b) Explain spanning tree and create a spanning from the following graph. 2 + 2
c) Write the key features of circular linked list and state why It Is important In case
of Josephus problem.
 11. a) How can a polynomial such as 5x ^{4} – 3x ^{2} + 9x – 11 be represented by a linked list ? 2
 b) Explain the advantages of binary search over sequential search. 3
c) Write an algorithm to delete a node from a doubly linked list, where a node contains one data and two address (prev & next) portion. 5
d)
Are recursive routines more efficient than nonrecursive routines ? Justify your answer with example. 