Hall Ticket No Question Paper Code: BCS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Supplementary) July, 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. Differentiate between linear and non-linear data structures with an example each.
Explain the queue ADT by using arrays.
2. How do you analyze the space complexity of an algorithm?
Illustrate the steps to delete a given element from a doubly linked list.
UNIT II
3. How is collision resolution done using separate chaining in hash tables?
Explain with suitable example how hash table collisions are resolved using quadratic probing.

4. Explain the usage of hash tables to represent a dictionary.
What is open addressing? Explain with an example.
UNIT III
5. Explain the binary tree ADT. Write different tree traversals with an example.
What is a threaded binary tree? Give an example.
6. What is a graph? Explain any three graph representations.
Write an algorithm for the breadth first search of a graph.
UNIT IV
7. What is the difference between a binary search tree and a binary tree? How do you find the
parent of a given node in a binary search tree?
How do you find the smallest and largest numbers in a binary search tree?
8. What is an AVL tree? Explain different rotations involved in it.
Create an AVL tree by repeated insertion of the following elements
50, 20, 21,15, 35.
Page 1 of 2
UNIT V
9. Illustrate the KMP algorithm with an example.
Draw the Huffman code tree for the following data source with five symbols:
Symbol Frequency
A 24
B 12
C 10
D 8
E 8
What is the length of the data source before and after coding consider 3 bits per character
10. What is a B tree? Explain the insertion operation into a B tree with an example.
Explain the working of join and range queries in an R tree.