http://www.makaut.
com
Name : ……………………………………………………………
Roll No. : ………………………………………………………..
Invigilator’s Signature : ………………………………………..
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
2012
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 the following :
10 1 = 10
i) Inserting a new node after a given node in a doubly
linked list requires
a) four pointer exchanges
b) two pointer exchanges
c) one pointer exchanges
d) np pointer exchange.
3001 (O) [ Turn over
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
ii) A complete binary tree with n leaves contains
a) n nodes b) log 2 n nodes
c) 2n – 1 nodes d) 2 n nodes.
iii) A vertex of degree one is called
a) Isolated vertex b) Pendant vertex
c) Coloured vertex d) Null vertex.
iv) A sort, which iteratively passes through a list to
exchange the first element with any element less than it
and then repeats with a new first element, is called
a) Bubble sort b) Selection sort
c) Heap sort d) Quick sort.
v) The postfix equivalent of the prefix + ab – cd is
a) ab + cd – b) ab ± cd
c) ab + cd – d) abcd + – .
vi) A linear list that allows elements to be added or
removed at either end but not in the middle is called
a) stack b) queue
c) priority queue d) none of these.
3001 (O) 2
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
vii) Which of the following methods had the best average
case complexity for searching ?
a) Hashing b) Sequential search
c) Random search d) Binary search.
viii) The technique of linear probing for collision resolution
can lead to
a) clustering
b) efficient storage utilization
c) underflow
d) overflow.
ix) 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) successor b) predecessor
c) root d) own.
x) For a function f ( n ) = 1000 n log n + 500 n 4 + 0·52 n ,
we can say that f ( n ) is
a) O( n4) b) O ( n log n )
c) O(2n) d) none of these.
3001 (O) 3 [ Turn over
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
GROUP – B
( Short Answer Type Questions )
Answer any three of the following. 3 5 = 15
2. Discuss the advantages and disadvantages of linked list over
array as linear data structure and also write down the
function to insert an element into a sorted array of
descending order.
3. Define hashing. Explain with a suitable example the collision
resolution technique using linear probing with open
addressing.
4. Define big O notation. What is stack and why is this called
LIFO ?
5. Write the algorithm for in-order traversal of a threaded
binary tree.
6. Prove that for any non-empty binary tree T, if n 0 is the
number of leaves and n 2 be the number of nodes having
degree 2 then prove
n 0 = n 2 + 1.
7. Write an algorithm to delete a node from a doubly linked list,
where a node contains one data and two addresses
( previous and next ) portion.
3001 (O) 4
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
GROUP – C
( Long Answer Type Questions )
Answer any three of the following. 3 15 = 45
8. a) Write the algorithm of binary search and calculate the
complexity for best, worst and average cases.
b) Why is queue data structure called FIFO ?
c) Construct the following queue of characters where
queue is a circular array which is allocated six memory
cells.
FRONT = 2, REAR = 4 & QUEUE : …… , A, C, D, …… , ……
Describe the queue as the following operations take
place :
i) F is added to the queue.
ii) Two characters are deleted from the queue.
iii) K, L, M are added into the queue.
iv) R is added to the queue.
v) One character is deleted from the queue.
3001 (O) 5 [ Turn over
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
9. a) How can a polynomial such as
5x 8 + 600x 5 + 45x 2 – 5x + 56
be represented by a linked list.
b) Write the algorithm to reverse linked list.
c) What is dummy node in a linked list.
d) Write the function in c language to find the predecessor
of a node in linked list.
10. a) The in-order & pre-order traversal sequences of nodes
in a binary tree are given as follows :
In : D G B A H E I C F
Pre : A B D G C E H I F
Draw the binary tree. State the algorithm to construct
the tree.
b) Insert the following keys in order given below to build
them into an AVL tree :
g, h, s, l, e, m, t, u.
c) What is two-way threading ?
11. a) What is stack ?
b) Write the algorithm to evaluate postfix expression using
stack data structure, and hence evaluate following
postfix expression :
5 + 67 + –
c) Convert the following infix expression into equivalent
postfix expression :
a+b c+(d e+f) g.
3001 (O) 6
CS/B.TECH (CSE-OLD)/ IT (O),ECE (O), EE (O), EEE (O), ICE (O)/SEM-3/CS-302/2012-13
12. Write short notes on the following :
a) Quick sort
b) B-tree
c) Tail recursion
d) AVL Tree.
3001 (O) 7 [ Turn over
