[Link]

com

Name : ……………………………………………………………
Roll No. : ………………………………………………………..
Invigilator’s Signature : ………………………………………..
CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10
2009
DATA STRUCTURE & ALGORITHMS
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 any ten of the following :
10 × 1 = 10

i) The time complexity of binary search is

2
a) 0(n ) b) 0(n)

c) 0 ( log n ) d) 0 ( n log n ).

ii) The fastest sorting algorithm for an almost already

sorted array is

a) quick sort

b) merge sort

c) selection sort

d) insertion sort.

33101 [ Turn over

CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

iii) The ratio of items present in a hash table to the total

size is called

a) balance factor b) load factor

c) item factor d) weight factor.

iv) The Linear Probing Technique for collision resolution

can lead to

a) Primary clustering

b) Secondary clustering

c) Overflow

d) Efficient storage utilization.

v) A height balanced binary tree is a binary tree in which

the height of two subtrees of every mode never differ
by more than

a) 1 b) 2

c) 3 d) none of these.

vi) Which tree structure is used for efficient access of

records residing in disc memory ?

a) AVL Tree b) B Tree

c) 2-3 Tree d) Binary Tree.

vii) Any connected graph with x vertices must have at least

a) x + 1 edges b) x – 1 edges

c) x edges d) x/2 edges.

33101 2
 CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

viii) Which of the following is essential for converting an

infix expression to postfix notation ?

a) A parse tree

b) An operand stack

c) An operator stack

d) None of these.

ix) The values in a BST can be sorted in ascending order

by using which of the following traversals ?

a) Pre-order b) In-order

c) Post-order d) Level-order.

x) The prefix expression for the infix expression

a ✳ ( b + c ) / e – f is

a) / ✳ a + bc – ef

b) – / ✳ + abcef

c) – / ✳ a + bcef

d) None of these.

xi) In C language, malloc( ) returns

a) integer pointer

b) structure pointer

c) null pointer

d) void pointer.

33101 3 [ Turn over

CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

xii) Fibonacci function fib ( n ) = fib ( n –1 ) + fib ( n – 2 ) is

an example of

a) Linear Recursion b) Binary Recursion

c) Non-linear Recursion d) Mutual Recursion.

xiii) A linear list in which elements can be added or removed

at either end but not in the middle is known as

a) Stack b) Queue

c) Dequeue d) Heap.

GROUP – B
( Short Answer Type Questions )

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

2. Prove that
O ( f ( x ) ) + O ( g ( x ) ) = O ( max ( f ( x ) , g ( x ) ).
3. a) Convert the following infix expression into equivalent
postfix expression using stack :
( A + B ) ✳ C – ( D – E ) ) / ( F + G ).
b) What is a Max Heap ? 4+1
4. What is a priority queue ? Mention the different design
options for priority queue. 2+3
5. “Binary search technique cannot be implemented using
Linked list.” — Justify the validity of the statement.
6. Show how the following integers can be inserted in an empty
binary search tree in the order they are given :
50, 30, 10, 90, 100, 40, 60, 20, 110, 5.
Draw the tree in each step.

33101 4
 CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

GROUP – C
( Long Answer Type Questions )
Answer any three of the following. 3 × 15 = 45

7. a) Prove that, the height of a binary tree that contains n

elements, n ≥ 0, is at most n and at least

[ log ( n + 1 ) ].

b) The order of nodes of a binary tree in Preorder and in

order traversal are as under :

In order : D B F E G H I A C

Pre-order : A B D E F G H I C

Draw the corresponding binary tree.

c) How does static allocation differ from dynamic allocation

of memory ? 5+5+5

8. a) What is a Stack ADT ?

b) Write a C function for popping an element from a stack

implemented using linked list.

c) Explain three uses of stack data structure. 5+5+5

9. a) Explain with a suitable example the principle of

operation of QuickSort algorithm.

b) In which cases, QuickSort becomes a ‘SlowSort’ ? What

is the remedy in those cases ?

c) Compare the performance and operation of BubbleSort

and SelectionSort. 5+5+5

33101 5 [ Turn over

CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

10. a) Show the steps in creation of a height balanced binary

AVL TREE using insertion of items in the following
order — show the balanceing steps required.

( March, May, November, August, April, January,

December, July, February, June, October,
September )

b) What do you mean by a B-Tree and what are the uses

of such a tree in data structures ?

c) Consider a B-Tree of order 5 as shown below — insert

the elements 4, 5, 58, 6 in this order in the B-Tree.

dia

8+2+5

33101 6
 CS/[Link] (EE/CSE/IT/ECE/EEE/ICE)/SEM-3/CS-302/2009-10

11. a) Compare BFS and DFS. Discuss the two different ways
of representing a graph.

b) Draw the minimum cost spanning tree for the graph

given below and also find its cost.

dia

c) What is a complete graph ? Show that the sum of

degree of all the vertices in a graph is always even.

5+5+5

33101 7 [ Turn over