Spring 2024

Section “A” 

Very Short Answer Questions 

Attempt all the questions. [10×2] 

1. What is time complexity? 

2. What is tail recursion? 

3. Define Stack as an ADT. 

4. Define circular queue. 

5. Write a node class or struct with a data field and a link field. 

6. What is a binary tree?

7. What is an internal sorting? 

8. What is a collision in a hash table? 

9. What is a directed a cyclic graph? 

10. Define Big O notation. 

Section “B” 

Descriptive Answer Questions 

Attempt any five questions. [5×10] 

11. Write a recursive algorithm for Tower of Hanoi. 

12. Write the algorithm to convert an expression from infix to postfix. Convert ((A-(B+C/M))*D)$(E+F) to prefix. 

13. Explain the drawback of Linear queue. Write a program in C to insert and delete data in a circular queue. 

14. What is a Linked List? Write algorithms to insert a new node at the beginning and at the end of a singly linked list. 

15. 

a. Explain Selection sort with suitable example. 

b. Implement insertion sort using C code. 

16. Sort the following data using quick sort algorithm. 50, 40, 60, 35, 45, 55, 70, 30, 38, 42, 48, 53, 57, 65

Section “C” 

Long Answer Questions 

Attempt any two questions. [2×15] 

17. 

a. Define the terminologies: 

i. Undirected graph 

ii. Directed graph 

iii. Adjacency Matrix 2 of 2 

iv. Minimum Spanning Tree 

v. Adjacency list 

b. Find the sequence of edges in the MST in the order that Kruskal’s algorithm includes them. 

c. Find the sequence of edges in the MST in the order that Prim’s algorithm includes them. Start Prim’s algorithm from vertex A. 

18. 

a. What are the rotation algorithms? Why do you need them? Explain in brief. 

b. Construct an AVL tree from 15, 20, 24, 10, 13, 7, 30, 36, 25, 48. 

c. Traverse the constructed AVL tree in pre-order, post-order and in-order. 

19. Consider the arrival order of the data: 21,36,39,42,44,46,55,66,91,35. Also assume a hash function h(x)=x mod 10. 

Now answer the following: 

a. What is a hash system? Implement the given hash function in C code. 

b. Insert the given data into the hash table. Use the linear probing if a collision is occurred. 

c. Insert the given data i