# WBUT Previous Years Question Papers EE

## Data Structure And Algorithm  B Tech Sem 3rd Dec 2007

Time : 3 Hours ]

Full Marks : 70

GROUP-A (Multiple Choice Type Questions)

1. 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 in-degree 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

d) none of these.             ‘

v)              The Ackerman function, fdr all non-negative values of m and n is recursively defined as ,        ,  –

n + 1             ifm = 0

A ( m – 1, 1 )    if m ! = 0 but n = 0

A(m-l,A(m,n-l)) 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 in-order traversal a right NULL link of any node is replaced by the address Of its

 a) c)
 b) d)
 successor root
 predecessor own.

vii)           In a height balanced tree the heights of two sub-trees 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) (log2 n)

c)    0(2″)     d) O (nlog2n).

A linear list in which elements can be added or removed at either end but not in the middle is known as

 a) d
 b) d)
 deque tree.
 queue stack

GROUP-B ( Short Answer Type Questions)

Answer any three of the following.

Show that the function/( n) defined by:

/( 1 ) = 1 .

fin) -f (n-l) + ^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 non-empty 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

GROUP-C (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).

1. 9.              a) The in-order & pre-order traversal sequence of nodes in a binary tree are given

below :

In-order : EACKF HDBG Pre-order : FAEKCDHGB

Draw the binary tree. State briefly the logic used to construct the tree.

b)              Insert the following keys into a B-Tree 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 non-recursive algorithm for In-order traversal of a binary tree.

1. 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.

1. 11.                             a) How can a polynomial such as 5x 4 – 3x 2 + 9x – 11 be represented by a linked list ?                          2
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 non-recursive routines ? Justify your answer with example.