CSIT 3rd Semester
Data Structure And Algorithms Board Question Paper 2082

CSC 211-2082 ✡
Tribhuvan University
Institute of Science and Technology
2082
✡
Bachelor Level/Second Year/Third Semester/Science
Computer Science Information Technology (CSC 211)
(Data Structure And Algorithms)
(New Course)
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 Answer Questions
Attempt any Two question.
[2x10=20]
1.

Distinguish between data type and abstract data type. List any three characteristics of algorithm. Evaluate the postfix expression 33 + 2 * 40 -, using stack.

2.

Define height, depth and level of the tree. Find the minimum spanning tree of the following weighted graph using Kruskal and Prims algorithm.
Weighted graph with nodes

3.

Define queue as ADT and discuss about primitive operations in queue. Trace the output generated by following recursive function for the statement TOH(4,1,3).
TOH(n, s, d)
{
if (n == 1)
{
printf(" move the top disk from rod %d to rod %d",s,d)
}
else
{
TOH (n- 1, s, 6- s- d)
printf(" move the top disk from rod %d to rod %d",s,d)
TOH (n- 1, 6- s- d, d)
}
}

Section B

Attempt any Eight questions

[8x5=40]
4.

Why do we need algorithms for searching? Trace the binary search operation for the key = 6, in the set {3, 6, 8, 12, 67, 89, 90, 100}

5.

How do you implement single linked list using stack? Explain.

6.

Trace the merge sort algorithm for the input {8, 7, -4, 19, 3, 45, 12}.

7.

Explain about any three hash collision resolution techniques.

8.

Describe the process of deleting the node at start, end and specified position of singly linked list.

9.

Write the algorithm of Quick sort with its efficiency analysis.

10.

Why do we always prefer the worst case for algorithm analysis? Describe the insertion and deletion operation in BST.

11.

Define overflow and underflow. Discuss the advantages and limitations of circular queue.

12.

What are the advantages of circular queue over linear queue? Sort the array {4, 7, 3, 2, 1} using insertion sort.