West Bengal Institute of Technology (WBIT) 2010 B.Tech Computer Science and Engineering WBUT Data Structures And Algorithms, CS-302 - Question Paper

2010
DATA STRUCTURE AND ALGORITHMS

Time Allotted : three Hours Full Marks : 70

The figures in the margin indicate the marks. Candidates are needed to provide their answers in their own words
as far as practicable.

GROUP-A

( Multiple option kind ques. )

1. select the accurate options for the subsequent :
[10 X one = 10]


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

a) 0( n)
b) 0 (log two n)
c) 0 ( n log two n )
d) 0(log2^n)



ii)the Ackerman function, for all non-negative values of m and n recursively described as

A(m,n)=

i) n + 1 if m = 0

ii) A ( m - 1, one ) if m t = 0 and n = 0

iii) A ( m- one ), A ( m. n- one ) if m t = 0, n ! = 0

Therefore the value of A ( 1, two ) is


a) 4

c) 5

b) 3

d) 2


iii) The best case time complexity of Bubble son technique is

a) 0 ( n) b) 0 ( n two )

c) 0 ( nlog n) d) 0 (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 of 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)


c) n-2 d) (n+.1)(n)


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


a) 0 ( n two )

c) 0 ( log two n)

b) 0 ( n)

d) 0 ( two 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 spanlling tree of a graph
c) a breadth 1st spanning tree df a graph
d) none of these.

GROUP-B

( Short ans kind ques. )
Answer any 3 of the subsequent. [3 X five = 15]

2.
a)Convert the subsequent infix expression postfix expression using •stack.
into equivalent

( A + B ) * C- ( D-E) I ( F + G ).

b)What is dequeue ? [4 + 1]

3.
a)How a polynomial• such as 6x six + 4x three - 2x + 10 can be represented by a linked list ?

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

4.Define Big 0 notation. Show that the function f ( n ) described by

F(1)=1

F ( n ) = f ( n - one ) + 1In for n > 1

has the complexity 0 (log n ) [2+3]

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

b)the Fibonacci sequence.

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

recursive tree> ( six ). [2+3]

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

array ? Write the Binary Search algorithm.

GROUPC

( Long ans kind ques. )
ans any 3 of the subsequent. [3 X 15 = 45]

7.
a) What is Circular queue ? Write Q-insert algorithm for the circular queue. [1 + 4]

b)Construct the expression tree for the subsequent expression : [2]
E = ( 2a + 5b ) ( x - 7y ) four •

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. [3+2]

8.
a)Show the stages in growth of an order- four 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 btnruy 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 ention various rotations used d balance factor of every node. [5]

c)Explain with suitable example the principle of operation of Quick sort. [5]




9.
a) provided the preorder and inorder sequence and draw the
resulting binary tree and write its postorder traversal. [5]


Pre-order: ABDGHEICFJK In-order: GDHBEIACJFK

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) Define 'Hashing'. [2]


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

c) What is index ? elaborate the different kinds of ind xing ? 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 subsequent :

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

Earning:   Approval pending.