TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2083 B.S.
Candidates are required to give their answers in their own words as far as practicable.
Group A
Long Answer QuestionsAttempt any Two questions.
- 1Differentiate between singly, doubly and circular linked list. How do you insert a new element at the beginning, at the specified position and at the end of doubly linked list? Explain.
- 2Is bubble sort internal sort or external sort? Give reason. Apply Quick sort on the data set {12, 7, 9, 24, 8, 2, -8, 11, 4, 3, 14, 5, 6, -6} to keep them in ascending order.
- 3When does the binary search algorithm perform the worst case? Assume the size of hash table be 7 and the hash function as $h(k)=k\text{ MOD }7$ Now resolve the collisions using Linear probing, Quadratic probing and Double hashing while inserting the elements 17, 8, 24, 11, 15.
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Differentiate between ADT and data structure. Why do we always do worst case analysis of an algorithm? Justify.
- 5Convert $X+Y\times Z-(A/B)$ to postfix, using stack.
- 6Assume a circular queue of size 5 and then enqueue 4, 9, 5 and then dequeue two elements and enqueue 11.
- 7When do we prefer tail recursion? Demonstrate a program to find the factorial value of given positive integer using tail recursion.
- 8How do you measure efficiency of a sorting algorithm? How do you create a node for circular linked list?
- 9What is the problem with binary search tree? List the primitive operations on queue.
- 10Create an AVL tree for the data {35, 15, 5, 20, 25}.
- 11Find the minimum spanning tree of following graph using Prims algorithm. [diagram/image to be added manually]
- 12Write the algorithm for merge sort.