## Tribhuvan University | Faculty of Management

BIM / Third Semester / ITC 215: Data Structure and Algorithm

Year: 2071 (2014)

Full Marks: 40 | Time: 2 hrs

Candidates are required to answer all the question in their own words as far as practicable.

** Group “A” – 1. Brief Answer Questions: [10 X 1 = 10]**

i. Define graph as an Abstract Data Types.

ii. Compare binary search and sequential search with respect to their time complexity.

iii. Arrange the following expressions by their growth rate from slowest to fastest.

Log^{n},logn^{2},n!,n^{5}

iv. What is greedy approach?

v. Differentiate between complete binary tree and almost complete binary tree.

vi. Why do we need the concept of collision resolution?

vii. Write the relationship between the stack and recursion.

viii. What is heap tree?

ix. What are the advantages of circular queue over linear queue?

x. What will be the result if we perform the post order traversal of an expression tree?

** Group “B” – Short Answer Questions: [5 X 3 = 15]**

2. What is the advantage of AVL tree over binary search tree? Construct an AVL tree from the given set of data: 3, 3, 1, 4, 5, 6, 7, 16, 15, 9,14

3. What do you mean by Minimum Spanning Tree (MST)? Write Kruskal’s algorithm to construct MST with suitable example.

4. What is doubly linked list? Write an algorithm or C-function to insert a node at end of doubly linked list.

5. Write algorithm to solve problem of Tower of Hanoi.

6. Use stack to convert the expression into postfix expression and evaluate the value of postfix expression where assume A = 1, B = 2, C = 3, D = 4, E = 5, F =6

A+(B + C) * D$(E * F)

** Group “C” – Long Answer Questions: [3 X 5 = 15]**

7. What are the benefits of linked list over array? Write C-function or algorithm to perform insertion operation at the start and end of singly linked list. Illustrate it with suitable diagram.

8. What is sorting? Which sorting algorithm is used to sort data in linked list? Sort the following data using merge sort algorithm: 25, 37, 12, 48, 57, 33, 86, 92

9. Differentiate between hashing and sequential search. How the collision in hashing can be reduced? Explain any one technique.