West Bengal Institute of Technology (WBIT) 2010 B.Tech Electronics and Communications Engineering 3rd SEMESTER,DATA STRUCTURES AND ALGORITHMS, -11,B-TECH,WBUT - Question Paper

DATA STRUCTURE AND ALGORITHMS--2010-11



GROUP-A
(Multiple option kind Questions)

1. select the accurate options for the following: 10*1=10

i) Which of the subsequent is the best time for an algorithm?
a) O(n)
b) O(log2 n)
c) O (2n)
d) O(n log two n).
ii) The Ackerman function, for all non-negative values of m and n is recursively
described as A (m,n)=
a) n+ 1 if m=0
b) A ( m-1, 1) if m! = 0 and n= 0
c) A ( m-1), 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) O( n2)
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 subsequent sorting procedures is the slowest ?
a) Quick sort
b) Heap sort
c) Merge sort
d) Bubble sort.
vi) In array representation odd Binary tree, if the index number of a child node is six
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
a) n2
b) n ( n-1)/2
c) n-2
d) ( n+1) (n)/2.
viii) 4 algos do the identical task. Which algo should execute the slowest for large
values of n ?
a) O (n^2)
b) O ( n)
c) O ( log two 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 1st spanning tree of a graph
c) a breath 1st spanning tree of a graph
d) none of these.

GROUP - B
( Short ans kind Questions)

ans any 3 of the subsequent. three * five =15

2. a) Convert the subsequent infix expression into equivalent postfix expression using stack.
( A + B)* c -( D - E)/ (F+ G).
b) What is dequeue ? four + 1

3. a) How a polynomial such as 6x6 + 4x3 - 2x +10 can be represented by a lnke list?
b) elaborate the advantages and disadvantages of linked list over an array ? two + 3

4. describe Big O notation . Show that the function f(n) described by
F(1)= 1
F(n) = f( n-1) + 1/n for n>1
has the complexity O ( log n).

5. a) Write down the recursive definition for generation of the Fibonacci sequence.
b) Assuming Fib (n) is recursive function, draw a recursive tree for Fib ( 6). 2+3

6 What is the precondition of performing binary search in an array? Write the Binary Search
algorithm . 5



GROUP-C
( Long ans kind Questions)
ans any 3 of the following: 3*15=45

7. a) What is Circular queue? Write Q-insert algorithm for the circular queue. one + 4
b) Construct the expression tree for the subsequent expression :
E= ( 2a + 5b) ( x- 7y)^4.
c) Write the recursive function for the issue of Tower of Hanoi issue. 3
d) Write a C function for selection sort and also compute the time complexity for selection
sort. three + 2

8. a) Show the stages in growth of an order -4 B-tree when the subsequent keys are inserted in
the order provided : 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 subsequent keys in the order provided beneath to build them into an AVL tree:
8 12 nine 11 seven 6
Clearly mention various rotations used and balance factor of every node. 5
c) discuss with suitable example the principle of the operation of Quick sort. 5

9. a) provided the preorder and inorder sequence and draw the resulting binary tree and write
its postorder traversal :
Preorder : A B D G H E I C F J K
Postorder: G D H B E I A C J F K
b) Write non- recursive algorithm for inorder traversal of a binary tree. 5
c) Write an algorithm to search a node in a binary search tree. 5

10. a) describe 'Hashing'. 2
b) discuss with a suitable example the collision resolution scheme using linear probing
with example addressing. 5
c) What is index ? elaborate the different kinds of indexing? State the advantages of using
indexing over a sequential file. 5
d) explain the differences ranging from command file and executable file. 3

11. Write short notes on any 3 of the following: three * 5

a) Radix sort
b) Index sequential file ordering
c) Tail recursion
d) Threaded binary tree
e) BFS vs DFS.

Earning:   Approval pending.