Tribhuvan University

Institute of Science and Technology

2080

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 questions.**

1

Explain queue as an ADT. Write a program to implement linear queue. Compare linear queue with circular queue.

2

Define hash table and hash function. What is collision in hashing? Explain linear probing and quadratic probing with suitable example.

3

Explain AVL tree with example. Also, explain balancing algorithm for this tree.

**Section B**

**Attempt any eight questions.**

4

What is asymptotic analysis? Explain theta notation with example.

5

Explain push and pop operations of stack. What are different applications of stack?

6

Explain tail recursion with example. Compare recursion with iteration.

7

Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11.

8

Explain binary search with an example. What is the time complexity of binary search?

9

Write Dijkstra’s algorithm to find shortest path between any two vertices of a graph.

10

Write a program to implement insertion sort.

11

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

12

Write short notes on:

a. Abstract data type

b. Circular linked list

HAMROCSIT.COM