Hall Ticket No Question Paper Code: ACS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech I/II Semester Supplementary Examinations July, 2017
Regulation: IARE R16
DATA STRUCTURES
[Common for II Semester IT, ECE and
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. What is selection sort? State the process and sort the following set of elements using this
technique: 20,35,40,100,3,10,15.
Write a recursive algorithm for finding solution to the Tower's of Hanoi problem. Explain the
working of your algorithm (with 3 disks) with diagrams.
2. An array A contains n unique integers from the range x to y and y inclusive where
That is there is one member that is not in A. Design an time algorithm for finding that
number.
What are the characteristics of a good algorithm? What is the relation between the time and
space complexities of an algorithm?
UNIT II
3. Suppose a queue is housed in an array in circular fashion. Write a procedure ENQ to add a new
item into the above house. And also check whether the queue is full. Write another procedure
DEQ to delete an element from the queue after checking queue empty status.
Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following
postfix expression as your input: a b c d
4. Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis
or not.
Illustrate the steps for converting an infix expression into a postfix expression for the following
expression .
UNIT III
5. Implement a Queue using a singly linked list L. The operations INSERT and DELETE should
still take O time.
Write a function to reverse the links in a linked list such that the last node becomes the first and
the first becomes the last by traversing the linked list only once.
Page 1 of 2
6. If x is a pointer to a node in a doubly linked list, then prev is the pointer to the node before
it and x->next is the pointer to the node after it. What does this pair of statements, executed
in order, do?


If we then execute this pair of statements (after executing the first pair of statements), what
happens?


Visualize the both conditions using diagrammatic representation.
Let P be a pointer to a circularly linked list. Show how this list may be used as a queue. That
is, write algorithms to add and delete elements. Specify the value for P when the queue is empty
and show using diagrammatic representation.
UNIT IV
7. Draw a picture of the directed graph, Where graph G is defined as
G


Obtain the following for the above graph:
i. Adjacency matrix.
ii. Reachability matrix.
A binary tree T has 9 nodes. The in order and preorder traversals of T yield the following
sequence of nodes.
In Order: EACKFHDBG
Pre 0rder:FAEKCDHGB
Draw the tree T. Also give the yield of the Post Order traversal.
8. Explain various graph traversal schemes and write their merits and demerits.
What is a binary tree? Write an algorithm for the preorder traversal of a binary tree using stacks.

UNIT V
9. Suppose that a Binary Search Tree is constructed by repeatedly inserting distinct values in to
the tree. Argue that the number of nodes examined in searching for a value in the tree is one
plus the number of nodes examined when the value was first inserted in to the tree.
The following values are to be stored in a hash table
25, 42, 96, 101, 102, 162, 197, 201
Use division method of hashing with a table size of 11. Use sequential method of resolving
collision. Give the contents of array.
10. Create B-Tree of order 5 from the following list of data items:
20, 30, 35, 85, 10, 55, 60, 25.What will be the root note for the above B-Tree.
Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23,94, 11, 39, 20, 16
and 5 using the hash function h mod 11.