Master in Data Science (SMS, TU) Data Structures and Algorithms Question Paper 2082 (Set page 10; Second Assessment 2082) Nepal

Compare data type with abstract data type. List some benefits of dynamic memory allocation. (2 + 1)

Why do you need circular queue? What is priority queue? (2 + 1)

Compare recursion with iteration. Write a recursive function to find $n^{th}$ Fibonacci number. (1.5 + 1.5)

Compare singly linked list with doubly linked list. What are the benefits of using doubly linked list over singly linked list? (1.5 + 1.5)

Define spanning tree and minimum spanning tree. (1.5 + 1.5)

Explain algorithm to convert an infix expression to postfix using stack. Use this algorithm to convert $A / (B + C - D) * E$ into postfix. (3 + 3)

OR

List some applications of stack. How do you implement stack using linked list? (1 + 5)

Trace the execution of heap sort algorithm with the array of numbers 34, 23, 17, 31, 45, 7, 21, 15, 8, and 1. (6)

OR

Explain quick sort. Trace the execution of quick sort algorithm with the array of numbers 34, 23, 17, 31, 45, 7, 21, 15, 8, and 1. (2 + 4)

Define collision in hashing. Suppose, the set of keys is $\{27, 22, 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 AVL tree. Construct AVL tree for the sequence 20, 26, 30, 9, 4, 14, 28, and 18. (1 + 5)

What is graph traversal? Explain depth first search (DFS) algorithm for traversing graphs with example. (1 + 5)