Hall Ticket No Question Paper Code: BCS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Regular) January/February, 2018
Regulation: IARE-R16
DATA STRUCTURES AND PROBLEM SOLVING
(Computer Science and Engineering)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Consider the code in Table 1 snippets. Derive the time complexity
Table 1
int count N 1000 int count N 1000
for (int i i for (int i i i
for (int j j for (int j j

Explain briefly stack data structure along with algorithms for push and pop operation.
2. Explain briefly array based internal representation of heap with a suitable example.
What is the space complexity of the following code? Justify your answer int sum(int int
int sum for(i i sum sum return sum;

UNIT II
3. Write algorithms for dictionary search and insertion using skip list.
Demonstrate the insertion of the keys 28, 19, 15, 20, 33, 12, 17, and 10 into a hash table with
collisions resolved by chaining. Let the table have 9 slots, and let the hash function be k
mod 9.

4. Describe linear probing and quadratic probing with suitable example.
Given the values 2341, 4234, 2839, 430, 22, 397, 3920, a hash table of size and hash function
x mod show the resulting tables after inserting the values in the given order with
each of these collision strategies: separate chaining, linear probing, quadratic probing and double
hashing
Page 1 of 2
UNIT III
5. Explain Depth First Search Method.
Assume that you have been given the following binary tree shown in Figure 1. Write Java function
to perform InOrder traversal of this tree using iterative and recursive approach.
Figure 1
6. Discuss Dijkstra's algorithm w.r.t data structure with a suitable example.
Use Kruskal's algorithm to find a minimum spanning tree of the given graph in Figure 2. Draw
the resulting spanning tree and list the edges in the order they are picked by Kruskal's algorithm.
Figure 2

UNIT IV
7. Outline the steps for searching an element in AVL tree.
Write two methods in Java to find the successor and predecessor of a given node. Assume that
a class Tree Node that represents nodes in the BST already exists.
8. Show result of inserting 7 into an empty AVL tree.
Design a class to find the Kth largest element in a Binary Search Tree.
UNIT V
9. What is B-Tree? List any four properties of B-Tree.
What is KNUTH-MORRIS-PRATT Algorithm? Outline the Algorithm
10. Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, and
8 into an initially empty red-black tree.
How text compression can be done using Huffman coding? Describe clearly.