Hall Ticket No Question Paper Code: ACS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech II Semester End Examinations (Regular) May, 2017
Regulation: IARE R16
DATA STRUCTURES
(Common for CSE/IT/ECE/EEE)
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 the method to calculate the address of an element in an array. A 254 matrix array
DATA is stored in memory in 'row-major order'. If base address is 200 and 4 words per
memory cell. Calculate the address of DATA .
Bubble sort algorithm is inefficient because it continues execution even after an array is sorted
by performing unnecessary comparisons. Therefore, the number of comparisons in the best and
worst cases are the same. Modify the algorithm in such a fashion that it will not make the next
pass when the array is already sorted.
2. Describe insertion sort and its time complexity.
What are the characteristics of a good algorithm? What is the relation between the time and
space complexities of an algorithm?
UNIT II
3. Explain how to implement two stacks in one array A[1..n] in such a way that neither stack
overflows unless the total number of elements in both stacks together is n. The PUSH and POP
operations should run in time.
Suppose a queue is maintained by a circular array QUEUE with N 12 memory cells. Find the
number of elements in QUEUE if
i. Front Rear =8.
ii. Front 10, Rear 3.
iii. Front Rear 6 and then two elements are deleted.
4. Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis
or not.
Define double ended queue and its types and give its applications in real time scenario.
UNIT III
5. Two linked lists contain information of the same type in ascending order. Write a module to
merge them to a single linked list that is sorted.
Write an algorithm to count number of nodes in the circular linked list.
Page 1 of 3
6. Write an algorithm and show diagrammatic representation to insert an element k in double linked
list at
i. Start of linked list
ii. After a given position P of list
iii. End of linked list.
Write an algorithm that will split a circularly linked list into two circularly linked lists.
UNIT IV
7. Consider the following undirected graph and answer the following questions.
Figure 1
Assume that the edges are ordered alphabetically (i.e. when facing with alternatives, choose the
edges in alphabetical order)
i. List the nodes (cities) of the graph by depth first search starting from Varanasi.
ii. List the nodes (cities) of the graph by breadth first search starting from Calcutta.
What are priority Queues? How can priority queues be implemented? Explain in brief.
8. Describe Kruskal's algorithm to find minimum spanning trees. Apply Kruskal's algorithm from
node a for the below figure 2.
Figure 2
What is a binary tree? Write an algorithm for the preorder traversal of a binary tree using stacks.

Page 2 of 3
UNIT V
9. What do you mean by hash clash? Explain in detail any one method to resolve hash collisions.

What is a height balanced tree? Explain how the height is balanced after addition/deletion of
nodes in it?
10. Define hashing. Describe any two commonly used hash functions. Describe one method of
collision resolution.
Draw a B-tree of order 3 for the following sequence of keys:
10