AMIETE –
CS/IT (OLD SCHEME)
Code: AC06 / AT06 Subject: DATA STRUCTURES &
ALGORITHM DESIGN
Time: 3 Hours
Max. Marks: 100
NOTE: There are 9 Questions in all.
· Question 1
is compulsory and carries 20 marks. Answer to Q.1 must be written in the space
provided for it in the answer book supplied and nowhere else.
· Out of the
remaining EIGHT Questions answer any FIVE Questions. Each question carries 16
marks.
· Any
required data not explicitly given, may be suitably assumed and stated.
Q.1 Choose the correct or the best alternative
in the following: (2
10)
a. The
number of movements needed to solve the
(A) 8 (B)
10
(C) 15 (D) 63
b. An algorithm is made up of two independent
time complexities f (n)
and g (n).
Then the complexities of the algorithm is in the order of
(A) f(n) g(n) (B) Min (
f(n),g(n))
(C) Max (f(n),g(n)) (D) f(n) + g(n)
c. The
worst case time complexity of Quick sort algorithm is
(A) 
(B)
(C) 
(D) 
d. Evaluate the prefix expression: +*2+/14251
(A) 25 (B) 15
(C) 37 (D) 23
e. Which of
the following algorithms should execute the slowest for large values of N
(A)
O(√N) (B) O(N)
(C) O(log N) (D) None
of these
f. The
time complexity of applying merge sort on an array which is already sorted is
(A) (B) 
(C) (D)
g. A linked list contains integers stored in sorted
order. Time complexity of searching for an integer is
(A)
(B)
(C) (D) 
h. The maximum degree of any vertex in a simple
graph with n vertices is
(A)
n–1 (B) n+1
(C) 2n–1 (D)
n
i. A
hash table has space for 100 records. Then the probability of collision before
the table is 10% full, is
(A)
0 .5 (B)
0.1
(C) 0.45 (D) 0.9
j. The processing of accessing data stored in
a tape is similar to manipulating data on a
(A) list (B)
stack
(C) heap (D)
queue
Answer any
FIVE Questions out of EIGHT Questions.
Each
question carries 16 marks.
Q.2 a. What
is a binary search tree? Mention advantage over a linked list for storing data records with a key and data
fields? Mention any inefficiency that could arise and a possible solution. Draw the binary tree which results
from inserting the keys 13,18, 14, 15, 11, 12 into an
initially empty tree. (8)
b.
Write the recursive algorithm
for the binary search method using an array
implementation for an array A of size N.
(8)
Q.3 a.
Write a function to reverse a linked
list.
(8)
b. Convert the following Infix expression to postfix form using a stack.
A+B*C+ (P*Q+R)*S, Follow usual precedence rule and assume
that the expression is legal. (8)
Q.4 a. You
are given an array of (decimal) integers, where different integers may have
different number of digits, but the total number of digits over all the
integers in the array is n. Show how the array can be sorted in O(n) time. Your answer should
include a high-level description of the algorithm, a proof of its correctness
and an analysis to show that its (worst-case) running time is O(n). (8)
b. Show that the second smallest of n elements can be found using at most n
+ [log2 n] − 2
comparisons. You may assume that all the n elements are distinct. Your answer
must include an algorithm for finding the second smallest value, a proof of its
correctness and a proof that the number of comparisons used by the algorithm is
at most n + [log n]
− 2. (8)
Q.5 a. Consider the following undirected graph in
Fig.1.
Fig. 1
(i) Write
the adjacency list representation of the graph.
(ii) Find the depth first spanning tree starting at
A.
(iii)
Find the breadth first spanning tree
starting at A.
(iv)
Find minimum cost spanning tree by
Kruskal’s algorithm. (10)
b. Write a recursive and efficient function to
compute 
where a and n are both
integers. (6)
Q.6 a. The
inorder and preorder traversals of binary search tree produces the following
sequences (8)
|
Inorder: |
D |
B |
F |
E |
G |
H |
I |
A |
C |
|
Preorder: |
A |
B |
D |
E |
F |
G |
H |
I |
C |
Construct the tree.
b. Work out the average and worst time complexity
of Quick sort. (8)
(6)
Q.7 a. The sequence of characters A B C D E is read once, character-by-character
from left to right. Each character read may be first placed in a
temporary memory or sent directly to the output. The reading operations may be
interleaved with operations removing characters from the memory and sending
them to the output. In this way we obtain at the output a permutation of the
input sequence (the left-most character of the permutation is the character sent
first to the output). Consider the permutations A C E D B and B C E A D. For
each of them check whether it is possible to obtain it if the temporary memory
is
(i)
Stack
(ii) Queue
If
the answer is “yes" show the sequence of the respective operations
performed to obtain it. If the answer is “no" explain why no sequence of
the operations can generate the required permutation. (8)
b. Given the array [26 5 77
1 6 1 11 59 15] construct a heap tree.
Show how the array can be sorted using Heap sort. (8)
Q.8 a. Put
the following elements on an AVL tree.
Whenever the tree is unbalanced, draw the balanced tree and indicate the
rotation used.40, 30, 50, 60, 55, 20. (8)
b. Write an algorithm which returns if two binary
trees A and B are similar. The trees are similar if they are both empty and the
left and right sub-trees are similar. (8)
Q.9 a. Give Dijkstra’s shortest path algorithm. (8)
b. Explain
any two collision resolution
methods in Hashing. (8)