# WBUT Question Papers EC

## Data Structure And Algorithm B Tech Third Sem 2010 – 2011

Time Allotted : 3 Hours

Full Marks : 70

The figures in the margin indicate full marks.

Candidates are required to give their answers in their own words

as far as practicable.

GROUP – A ( Multiple Choice Type Questions )

1. Choose the correct alternatives for the following :

10 x 1 = 10

i)         Which of the following is the best time for an algorithm?

 a) O(n) b) O (log 2 n) c) 0 ( 2″) d) O ( n log 2 n ). /

il) ‘the Ackerman function, for all non-negative values of m and h is recursively defined as

A ( m, n ) =

i)       n + 1               if m = 0

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

iii)    A(.m-l), A(m,n-1) if m ! = 0, n ! = 0 Therefore the value of A ( 1, 2 ) is

a)    4    b) 3

c) 5                d) 2.

iii)      The best case time complexity of Bubble sort technique

is

a)   O(n)  b) Q ( n 2 )

c) O ( n log n)     d) O (log n).

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

a)  queue     b) dequeue

c) stack            d) tree.

v)        Which of the following sorting procedures is the slowest ? –

a)  Quick sort    b) rieap sort

c) Merge sort    d) Bubble sort.

vi)       In array representation of Binary tree, if the index number of a child node is 6 then the index number of its parent node is

a)   2               b) 3

c) 4                d) 5.

vii)     Maximum number of edges in a n-node undirected graph without self loop is

, o n( n- 1 )

a)  n*——– b) ——g

‘ – ( n + 1 ) ( n) c) n – 2—- d)    g    •

viii)   Four algos do the same task. Which algo should execute the slowest for large values of n ?

a)      0[n2)              b) 0( n)

c) O (log 2 n)        d) O ( 2 n).

ix)      The adjacency matrix of an undirected graph is

a)   unit matrix b) asymmetric matrix

c) symmetric matrix d) none of these.

x)        BFS constructs

a)        a minimal cost spanning tree of a graph

b)        a depth first spanning tree of a graph

c)        a breadth first spanning tree of a graph

d)        none of these.

GROUP -B

( Short Answer Type Questions )

Answer any three of the following. 3×5= 15

1. a) Convert the following infix expression into equivalent

postfix expression using stack.

{A + B)*C-[D-E)/ (F+G).

b)

What is dequeue ?       4+1

1. a) How a polynomial such as 6xe + 4x3 – 2x + 10 can be

represented by a linked list ?

b)        What are the advantages and disadvantages of linked list over an array ? 2 + 3

1. Define Big O notation. Show that the function /( n) defined by

F( 1) = 1

F ( n ) =/( n – 1 ) + 1/n for n > 1 has the complexity O (log ri).       2 + 3

1. a) Write down the recursive definition for generation of

the Fibonacci sequence.

b)        Assuming Fib ( n ) is a recursive function, draw a

recursive tree for Fib ( 6 ).            ,                     2 + 3

1. What is the precondition of performing binary search in an

array ? Write the Binary Search algorithm.

3001

GROUP -C ( Long Answer Type Questions )

Answer any three of the following. 3×15 = 45

1. a) What is Circular queue ? Write ©-insert algorithm for the circular queue.       1+4

b)       Construct the expression tree for the following expression :   2

E = [ 2a + 5b ) [ x – 7y ) 4 .

c)        Write the recursive function for the problem of Tower of Hanoi problem.    3

d)       Write a C function for selection sort and also calculate the time complexity for selection sort.                                              3 + 2

1. a) Show the stages in growth of an order – 4 B-tree when the following keys are inserted in the order given : 5

74 72 19 87 51 10 35 18 39 60 76 58 19 45

b)       How do AVL trees differ from binary search tree ?

Insert the following keys in the order given below to build them into an AVL tree :

8 12 9 11 7 6

Clearly mention different rotations used and balance factor of each node.                              5

c)        Explain with suitable example the principle of operation of Quick sort.                             K

1. a) Given the preorder and inorder sequence and draw the

resultant binary tree and write its postorder traversal:

Pre-order : ABDGHEICFJK In-order : GDHBEIACJFK

b)        Write non-recursive algorithm for inorder traversal of a binary tree.         5

c)        Write an algoritm to search a node in a binary search tree.   5

1. a) Define‘Hashing’.                                                           2

b)        Explain with a suitable example the collision resolution scheme using linear probing with open addressing. 5

c)        What is index ? What are the various types of indexing ? State the advantages of using indexing over a

sequential file.                        5

d)        Discuss the differences between command file and executable file.                                        3

1. Write short notes on any three of the following :                          3×5