Tribhuvan University

Institute of Science and Technology

Model Set I

Bachelor Level / third-semester / Science

Computer Science and Information Technology( CSC206 )

Data Structure and Algorithm

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Group A

Attempts any TWO questions

1

Define queue as ADT. Describe its primitive operation on circular array implementation and singly linked list implementation.

2

Define Contiguous List as ADT. Write C program to implement the operation of Contiguous List.

3

What do you mean by MST. Explain Kruskal Algorithm with example.

Group B

Attempts any EIGHT questions

4

State relative merits and demerits of contiguous list and linked list?

5

What is Data Structure? Show the status of stack converting following infix expression to prefix

A+(B*C-(D/E^F)*G) [Note ^ is the power]

6

What is singly linked list? Write an algorithm to add  a node at the beginning and end of singly linked list.

7

What do you mean by breadth first search in graph? Explain with recursive tree.

8

Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursive tree.

9

What is AVL tree? Draw the AVL tree when input is 1,2,3,4,5,6,7.

10

State problem Tower of Hanoi. Explain the algorithm to solve problem.

11

What is insertion sort? Trace and sort the following data using the insertion sorting algorithm.

90, 56, 80, 10, 22, 21, 45, 9

12

What is hashing? Explain the different types to resolute collision?