Master in Data Science (SMS, TU) Data Structures and Algorithms Question Paper 2082 (Set page 21; 2082 board/final exam (IOST,TU)) Nepal

Compare data type with abstract data type. What are the benefits of using abstract data types? (1.5 + 1.5)

Define tail recursion. Write a recursive function for Tower of Hanoi problem. (1 + 2)

Compare singly linked list with doubly linked list. What is header node? (2 + 1)

Explain binary search in brief. What is its time complexity? (2 + 1)

Explain almost complete binary tree with example. (3)

What are different applications of stack? Convert $A + (B - C + D) * E / F$ to postfix using stack. (2 + 4)

OR

Compare linear queue with circular queue. How do you implement circular queue? (2 + 4)

How do you insert and remove nodes in a singly linked list? (6)

What is divide-and-conquer strategy. Trace the execution of quick sort algorithm with the array of numbers 35, 27, 71, 31, 55, 17, 26, 15, 81, and 11. (2 + 4)

OR

Trace the execution of heap sort algorithm with the array of numbers 35, 27, 71, 31, 55, 17, 26, 15, 81, and 11. (6)

What is double hashing? Suppose, the set of keys is $\{18, 22, 14, 20, 99, 48, 19, 50\}$, $m = 10$, and $h(x) = x \bmod 10$. Show the effect of successively inserting these keys using linear probing. (2 + 4)

What is AVL tree. Construct AVL tree for the sequence 23, 30, 39, 11, 7, 17, 28, and 18. (1 + 5)