Hall Ticket No Question Paper Code: BCS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (supplementary) July, 2018
Regulation: IARE-R16
DATA STRUCTURES AND PROBLEM SOLVING

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 how insertions and deletions are done in a circular linked list.
Explain the concept of ADT with the example of the priority queue ADT.
2. Describe the Big Oh, Omega and Theta notations with an example.
Explain the operations of insertion and deletion into a max heap with an example.
UNIT II
3. What is double hashing? Insert the keys 76,93,40,47,10,55 into a hash table of seven elements
using double hashing, using the second hash function Hash2(key) 5 key 5 and show the
contents of the hash table at each stage.
Explain with an example how hash table collisions are resolved using linear probing.
4. What is rehashing? When is rehashing done?
Explain the linear list representation of dictionaries. Also explain how insertion and search
operations are done in such dictionaries.
UNIT III
5. How is non-recursive traversal of a binary tree done? Explain with an example
With an example, trace the working of the Djikstra's algorithm for single source shortest path
problem.
6. What are threaded binary trees? Give an example.
Write the algorithm for finding the minimum cost spanning tree proposed by Kruskal.
UNIT IV
7. Write an algorithm for insertion of an element into a binary search tree.
Create a binary search tree by repeated insertion of the following elements 50, 70, 20, 10, 30,
67, 89, 12, 14. Now, delete element 20 and draw the resultant tree.
Page 1 of 2
8. How do you find the smallest and largest numbers in a binary search tree?
What is an AVL tree? Describe when and how an RR rotation is performed in an AVL tree.

UNIT V
9. Illustrate Huffman coding for compression with an example.
What is a red-black tree? Explain the insertion operation into a red-black tree with an example.

10. What are the B trees and write any three applications of B trees?
Explain the working of the nearest neighbor query in an R tree.