Hall Ticket No Question Paper Code: ACS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech II Semester End Examinations (Regular/Supplementary) May, 2018
Regulation: IARE R16
DATA STRUCTURES
Time: 3 Hours (Common to CSE IT ECE EEE) 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. Trace the insertion sort algorithm with the given set of 8 numbers 15, 20, 10, 30, 50, 18, 45 by
showing the passes and position moved. Mention the Worst case and Best case running time of
Insertion sort.
What is the result of mystery Given positive integers a and discuss what
mystery(a, does.
int mystery(int int

if
return
else if 2
return mystery(a b
else
return mystery(a b

2. Consider an array of elements 34, 76, 123, 234, 567, 677 and 986 and read a number X.
Write a function which will return such that (ai if x is not in the array then return
(which means "Not Found"). Then the function should return 6 (because 123 is at position 6
binary search algorithm).
Write a function using recursion for multiplication operation using positive integers a and b as
parameters, by using or operators.
UNIT II
3. Write an algorithm to insert an element into double ended queue at rear and front end.
Convert the given INFIX expression B to POSTFIX expression using
stacks.
4. Given the following numbers into a circular queue. Consider the size as 5. Perform
the following operations <enqueue, enqueue, enqueue, enqueue, enqueue, dequeue, dequeue,
enqueue, enqueue, What is the final Front and Rear element?
Write a function to dequeue() an element and enqueue() an element into a queue using array.

Page 1 of 3
UNIT III
5. Write an algorithm to reverse the elements in a singly linked list?
Input Consider the following linked list

Output Linked list should be changed to,

Write an algorithm to insert the element at any position in a doubly linked list?
6. Write an algorithm to delete the element from middle for a circular linked list?
Write a function to enqueue an element and dequeue an element into a queue using single linked
list.
UNIT IV
7. Show the result of inserting into an initially empty binary search tree.
Show the result of deleting the root.
Explain how queue is useful to traverse a graph using breadth first search using the graph shown
in Figure 1.
Figure 1
8. Which data structure is useful to traverse a graph using depth first search. Examine the possible
order of visiting the nodes of the following graph in Figure 2.
Figure 2
Page 2 of 3
Write the binary tree traversals for the diagram shown in Figure 3. Write the function to perform
inorder traversal.
Figure 3
UNIT V
9. Show the result of inserting these keys into an initially empty AVL tree: 34, 56, 74, 23, 19, 83,
23, 12, 96.
Show the B-tree that results when deleting then deleting V and then deleting P from the
B-tree shown in Figure 4 with a minimum branching factor of t=2.
Figure 4
10. Given the input 76,93,40,47,10,55 a fixed table size of 7 and a hash function X mod
show the result after performing linear probing.
Load the keys 23, 13, 21, 14, and 15 in this order, in a hash table of size 7 using quadratic
probing with i2 and the hash function: h(key) key 7.