POKHARA UNIVERSITY

Level: Bachelor                                  Semester: Spring                                   Year: 2023

Programme: BBA/BI/TT/BCIS/BHCM/BHM                                              Full Marks: 100

Course: Data Structure and Algorithms                                                         Pass Marks: 45

Time: 3 hrs. 

                                                          Section "A"

                                            Very Short Answer Questions

      Attempt all the questions. [102]

1. Differentiate between linear and non-linear data structure. 

2. What do you mean by Time Space Tradeoff?

3. What is a queue and how does it work?

4. How do AVL trees differ from binary search trees?

5. What is a collision in a hash table?

6. How does a priority queue differ from a regular queue?

7. How does a merge sort algorithm work?

8. Differentiate BFS and DFS.

9. Define dynamic programming.

10. What is the lower bound for comparison based sorting algorithms?

                                                        Section "B"

                                           Descriptive Answer Questions

Attempt any six questions. [6×10] 

11. What is the advantage of postfix notation and Convert the infix expression a+b*c+(d*e+f)*g into postfix expression. 

12. Construct AVL Tree for the following sequence of numbers-

        50, 20, 60, 10, 8, 15, 32, 46, 11 and 48 

13. Create a binary min heap from a given set of data and demonstrate the deletemin( )operation on it.

       62, 71, 69, 26, 31, 85, 93, 58, 47, 99, 21, 36, 39, 42

14. Sort following data using quick sort algorithm:

       25,10, 30, 15, 20 and 28

15. Define a minimum spanning tree. Write and explain kruskal's algorithm to find the minimum spanning tree with an example.

16. Define backtracking algorithm. Write and explain one algorithm that uses this technique to solve a problem.

17. Write an algorithm to perform a merge sort. Show various stages in merge sorting over the data: 11, 2, 9, 13, 57, 25, 17, 1, 90, 3.

                                                        Section "C

                                                       Case Analysis

18. Read the case situation given below and answer the questions that follow [20]

a) A doubly linked list is a linear data structure where each node contains a reference to both the previous and next nodes in the list. This allows for efficient traversal in both directions, making it useful in scenarios where forward and backward navigation is required. In a doubly linked list, each node holds two pointers: one pointing to the previous node and another pointing to the next node. This bidirectional linkage facilitates operations like insertion and deletion, as it provides easy access to neighbouring nodes.

i. How would you insert a new node after a specified node?

ii. How would you delete a node after a specified node?

 b) Define Hash Function and Load Factor. For the input (59, 100, 617, 99,  344, 199, 87, and 73) into hash table of size 10, show the resulting in

i. Separate chaining hash table

ii. Open addressing hash table using both linear and quadratic probing