H.T.No.
Code No: CT3505 SRGEC-R20
I B.Tech II Semester Supplementary Examinations, July 2024
DATA STRUCTURES
(Computer Science and Engineering, Artificial Intelligence and Data Science, Artificial
Intelligence and Machine Learning & Information Technology)
Time: 3 Hours Max. Marks: 70
Note: Answer one question from each unit.
All questions carry equal marks.
5 × 14 = 70M
UNIT-I
1. a) Describe insertion sort algorithm and trace the steps of insertion sort for sorting the list:
12, 19, 33, 26, 29, 35, 22, 37. Find the total number of comparisons made. (7M)
b) Design an algorithm for selection sort. Illustrate the working of selection sort on the
following array with 7 elements: 30, 45, 25, 32, 55, 60, 49. (7M)
(OR)
2. a) Develop a program for Selection sort for arranging n integers in an ascending order. (7M)
b) Apply recursive binary search algorithm to search for an element 54 and 100 in the
following list: 6,13, 27,45,51,54,59,69,81,91. (7M)
UNIT-II
3. a) Write an algorithm to insert new node at the beginning of a circular linked list. (7M)
b) Write an algorithm for traversing nodes in a doubly linked list. (7M)
(OR)
4. a) Develop a C program to create and delete first node from a singly linked list. (7M)
b) Elaborate the procedure to insert a node at specified location of the existing double linked
list. (7M)
List : 1,2,3,5,6
Element to be insert : 4 (in between 3 and 5)
UNIT-III
5. Write a non-recursive algorithm to convert the given infix expression into postfix expression
and Convert following expression X+(Y * Z) – ((N * M +O) /Q) in to postfix form. (14M)
(OR)
6. a) Consider the Queue with size 4, and suppose the following operations are performed on
the Queue in the order given (where enqueue(X) – inserts item X into Queue, dequeue() –
deletes an item from Queue); enqueue(Q), enqueue(W), enqueue(E), dequeue(),
enqueue(R), enqueue(T) and dequeue(). What is the content of Queue after performing
these operations? (7M)
b) Explain the prefix and postfix notation of (a + b) * (c + d) (7M)
Page 1 of 2
UNIT-IV
7. a) Explain in detail about creation of a binary search tree and insertion of a node into a binary
search tree with suitable example. (7M)
b) Consider the following list of elements: 10, 20, 15,6 5, 80, 55, 30, 40, 100. Construct a
min heap with these elements and delete the root. (7M)
(OR)
8. Create a binary search tree with the input given below: 98, 2, 48, 12, 56, 32, 4, 67, 23, 87, 23,
55, 46 (i) Insert 21, 39, 45, 54, and 63 into the tree (ii) Delete values 23, 56, 2, and 45 from
the tree . (14M)
UNIT-V
9. Illustrate with example the Open addressing and Chaining methods of collision resolution
techniques in hashing. (14M)
(OR)
10. a) Given a hash table of 100 locations, calculate the hash value using Division method for
keys 5678, 321, and 34567. (7M)
b) Consider a hash table of size 10. Using linear probing, insert the keys 72, 27, 36, 24, 63,
81, 92, and 101 into the table. (7M)
*****
Page 2 of 2
