This course includes the basic foundations in of data structures and algorithms. This course covers concepts of various data structures like stack, queue, list, tree and graph. Additionally, the course includes idea of sorting and searching.
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.
Explain queue as an ADT. Write a program to implement linear queue. Compare linear queue with circular queue.
Define hash table and hash function. What is collision in hashing? Explain linear probing and quadratic probing with suitable example.
Explain AVL tree with example. Also, explain balancing algorithm for this tree.
Section B
Attempt any eight questions.
What is asymptotic analysis? Explain theta notation with example.
Explain push and pop operations of stack. What are different applications of stack?
Explain tail recursion with example. Compare recursion with iteration.
Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11.
Explain binary search with an example. What is the time complexity of binary search?
Write Dijkstra’s algorithm to find shortest path between any two vertices of a graph.
Write a program to implement insertion sort.
How can you use linked list to implement stack? Explain.
Write short notes on:
a. Abstract data type
b. Circular linked list