Tribhuvan University

Institute of Science and Technology

2081

Bachelor Level / third-semester / Science

Computer Science and Information Technology( CSC211 )

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.

SECTION A

Attempt any TWO question.

1

Define circular queue. How queue differ from stack. Write a program to implement linear queue.

2

What is AVL tree? How heap differ from tree? Construct an AVL tree for data 24,12,8,15,35,30,57,40,45 and 78.

3

Define list. How can you use linked list to implement stack? Explain circular linked list.

SECTION B

Attempt any EIGHT question.

4

Explain big oh notation in brief. Find big oh of the following function:

f(x) = 5x4 + 9x2 + 7x + 9.

5

Convert the infix expression

A+(((B-C)*(D-E)+F)/G)\$(H-I)   into post expression using stack.

6

Write a program to find GCD of two numbers using recursion.

7

What is the application of spanning tree? Draw a MST of a graph containing any 8 vertices and 11 edges with arbitrary edge costs.

8

Sort the number {82, 73, 12, 39, 26, 88, 2, 9, 60, 41} using shell sort.

9

What is hashing? how do you apply linear probing and rehashing explain with example.

10

What is the algorithm for node insertion and deletion from specified position from doubly linked list.

11

What is linear queue? Why do we need circular queue? Explain.

12

Write short notes on:

1. Breadth First traversal of graph
2. TOH