Hall Ticket No Question Paper Code: BCS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Regular) February, 2017
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. Explain briefly Circular Queue along with algorithm for insert and delete operations.
Show that, if c is a positive real number, then c c2 cnis
i. ifc 1
ii. ifc 1
iii. ifc 1
2. What is circular linked list? How is different from linear linked list?
What is the time complexity of the following code snippet?
for i 1 to n do
for j i 1 to n do
for k j 1 to n do
z z 1
UNIT II
3. What is a dictionary? What are the typical operations that can be performed on dictionary?

Consider inserting the keys 10, 22, 31, 15, 28, 17, 88, and 59 into a hash table of length m=11
using open addressing with the primary hash function k mod m. Illustrate the result of
inserting these keys using linear probing, using quadratic probing with c1 1 and c2= and
using double hashing with 1 mod
4. Suppose we wish to search a linked list of length where each element contains a key k along
with a hash value Each key is a long character string. How might we take advantage of the
hash values when searching the list for an element with a given key?
Suppose a hash table with capacity M=31 gets to be over 3/4ths full. We decide to rehash. What
is a good size choice for the new table to reduce the load factor below .5 and also avoid collisions?

Consider a hash table of size 1000 and the hash function (kA (mod for
the notation refers to the largest integer at most x. For example [3.14]=3. Of
course, x (mod is the fractional part of x. Compute the locations to which the keys 61, 62, 63,
64, 65 are mapped.
Page 1 of 3
UNIT III
5. Write recursive functions to
i. compute the size of a binary tree rooted at node U
ii. compute the height of a node U
Bring out the need for threaded binary trees.
Discuss Graph data structure with suitable example. Explain the term Vertex
6. What is a binary tree? List any four properties of a binary tree?
Consider the following directed, weighted graph:
Figure 1
i. Even though the graph has negative weight edges, step through Dijkstra's algorithm to
calculate supposedly shortest paths from A to every other vertex. Show your steps in the
table.
ii. Dijkstra's algorithm found the wrong path to some of the vertices. For just the vertices
where the wrong path was computed, indicate both the path that was computed and the
correct path.
iii. What single edge could be removed from the graph such that Dijkstra's algorithm would
happen to compute correct answers for all vertices in the remaining graph?
UNIT IV
7. Discuss the Binary Search Tree ADT
What is an AVL tree? Insert the integers 50, 30, 75, 80, 20, 10, 60, 70, 72 to an initially empty
AVL tree in order. Draw the state of the AVL tree before and after each necessary rotation.

8. Design appropriate class(es) with suitable methods using C/Java to find the node with minimum
value in a Binary Search Tree. Write a test driver for the same.
List the steps involved in insert an element into AVL tree.
Page 2 of 3
UNIT V
9. What is R Tree? When is it preferable over B Tree?
Consider the following splay tree:
Figure 2
i. Perform a delete for the key 3 under the assumption that this is a bottom‐up splay tree.
Show each step
ii. Perform a split from the tree of Figure 2 (not the resulting tree of part for the key 6
under the assumption that this is a top‐down splay tree.
10. Show the red-black trees that result after successively inserting the keys 10, 15, 25, 20, and 30
into an initially empty red-black tree.
Discuss the two methods available for splitting the full nodes of R Trees.