Master in Data Science (SMS, TU) Data Structures and Algorithms Question Paper 2079 Nepal

Define asymptotic notation. Explain theta ($\theta$) notation with example. (1 + 2)

Explain circular queue. What are the benefits of using circular queue over linear queue? (1 + 2)

Explain tail recursion with suitable example. (3)

How do you implement queue using linked list? (3)

Explain binary search algorithm with example. (3)

Explain algorithm to evaluate the value of postfix expression using stack with suitable example. (6)

OR

Compare linear queue with circular queue. How do you implement enqueue and dequeue operations in queue? Explain. (2 + 4)

Compare singly linked list with doubly linked list. How do you insert and remove nodes in a doubly linked list? (2 + 4)

OR

Explain shell sort. Trace the shell sort algorithm with the array of numbers 34, 13, 16, 13, 45, 71, 21, 15, 8, and 1. (2 + 4)

Starting with empty binary search tree, show the effect of successively adding the following numbers as keys: 20, 23, 10, 21, 30, 15, 5, 22 and 40. Also, traverse this tree in preorder and postorder. (4 + 2)

Explain quadratic probing. Suppose, the set of keys is $\{7, 12, 14, 10, 49, 58, 9, 50\}$, $m = 10$, and $h(x) = x \bmod 10$. Show the effect of successively inserting these keys using quadratic probing. (2 + 4)

Define spanning tree and minimum spanning tree. Explain Kruskal's algorithm to find minimum spanning tree with suitable example. (2 + 4)