B.Tech. / B.Tech. (Working Professional) III Semester
Examination, December 2024
Grading System (GS) / Working Professional
Max Marks: 70 | Time: 3 Hours
Note:
i) Attempt any five questions.
ii) All questions carry equal marks.
iii) In case of any doubt or dispute the English version question should be treated as final.
a) What is Data structure? Write a brief note on classification of data structure. (Unit 1)
b) What do you mean by algorithmic complexity? Explain Time complexity and space complexity in brief. (Unit 1)
a) How do you implement binary search recursively? (Unit 2)
b) How does the size of the input array affect the time complexity of linear search and binary search? (Unit 2)
a) Evaluate the post fix expression using stack:
$8 \quad 3 \quad 4 \quad + \quad - \quad 3 \quad 8 \quad 2 \quad / \quad + \quad * \quad 2 \quad \$ \quad 3 \quad +$ (Unit 3)
b) Explain and implement a singly linked list with an example? (Unit 4)
a) Suppose you have a queue with the following elements: [10, 20, 30, 40, 50]. What will be the result of dequeuing two elements from this queue, then enqueueing three new elements with the values of 60, 70 and 80, and finally dequeuing one more element? (Unit 3)
b) How can you implement a queue using two stacks, and what are the advantages and disadvantages of this approach? (Unit 3)
a) Explain Insertion sort in details. Write an algorithm for it. Discuss the complexity of insertion sort. (Unit 2)
b) What is max heap? Write an algorithm to perform heap sort. Give example. (Unit 2)
a) Suppose you have an array with the following elements: [22, 7, 2, 9, 8, 15, 13, 3, 11]. What will be the result of sorting this array using the quicksort algorithm with the first element as the pivot? (Unit 2)
b) Construct a binary tree whose preorder and post order traversal as follows (Unit 5)
i) Preorder- F, B, A, D, C, E, G, I, H, K, J
ii) Postorder- A, C, E, D, B, H, K, I, J, G, F
a) Insert the set of elements {30, 40, 24, 58, 48, 26, 11, 13} to construct a binary search tree starting from a null tree taking one element at a time from left to right. Draw a tree for each steps? (Unit 5)
b) Define the properties of circular queue. How will you check whether the circular queue is i) Full ii) Empty (Unit 3)
Write short note on any two:
i) Application of queue (Unit 3)
ii) BFS and DFS (Unit 4)
iii) Doubly circular linked list (Unit 5)
