DSA Model Question 4

Group A

Very Short Answer Questions

Attempt all the questions. Give your answer in few lines.[10*2=20]

1. What is an ADT?

2. Why do we need a base case in recursion? Example. 

3. Write down four applications in the queue. 

4. What is a data field and linked field in a linked list?

5. Define a "complete binary tree.".

6. Why do collisions occur?

7. Define Hash function and Hash Table. 

8. Name two real-world applications of graphs.

9. What is the purpose of asymptotic notations in algorithm analysis?

10. What is a primary limitation of a simple (linear) queue regarding space utilization?

Section “B”

Descriptive Answer Questions

Attempt any five questions. [5×10=50]

1. What is tail recursion?  Write a recursive algorithm for the Tower of Hanoi.

2. Write a program for push and pop operation on stack using arrays with full and empty conditions.

3. Why is Queue called FIFO in data structure? Write an algorithm for enqueue and dequeue operation on queue.

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

5. Explain Selection sort with suitable examples.

6. Implement insertion sort using C code.

7. Describe different AVL tree rotations techniques with examples.

8. What is asymptotic notation? Explain its type in detail.

Section C

Attempt any two questions. [2×15=30]

1. A. Define the terminologies: 

i. Undirected graph

ii. Directed graph

iii. BFS and DFS

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

2. Define singly linked list. Write full code used to perform the following operation in a single linked list:

A. To insert a new node at the end of the list 

B. To remove a first node from the list. 

C. To display the data from the linked list.

3. 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. Insert the given data into the hash table. Use the chaining if a collision is occurred.

B. Insert the given data into the hash table. Use linear probing if a collision occurs.

C. Insert the given data into the hash table. Use quadratic probing if a collision occurs.