Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2080

Bachelor Level / Second Year / Third Semester / Science

B.Sc in Computer Science and Information Technology (CSC211)

(Data Structures and Algorithms)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

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

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
Define hash table and hash function. What is collision in hashing? Explain linear probing and quadratic probing with suitable example.[10]
2.
Explain AVL tree with example. Also, explain balancing algorithm for this tree.[10]
3.
Explain queue as an ADT. Write a program to implement linear queue. Compare linear queue with circular queue.[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Explain push and pop operations of stack. What are different applications of stack? [5]
5.
Explain tail recursion with example. Compare recursion with iteration. [5]
6.
Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11. [5]
7.
Explain binary search with an example. What is the time complexity of binary search? [5]
8.
Write Dijkstra's algorithm to find shortest path between any two vertices of a graph. [5]
9.
Write a program to implement insertion sort. [5]
10.
How can you use linked list to implement stack? Explain. [5]
11.
What is asymptotic analysis? Explain theta notation with example. [5]
12.
Write short notes on: a. Abstract data type b. Circular linked list [5]