Data Structure and Algorithms

This is the question set Data Structure and Algorithms Fall 2017, which was taken by Pokhara University.

Pokhara University – Data Structure and Algorithms Fall 2017

Level:  Bachelor	Semester –sixth	Year: 2017-Fall
Program: BCIS		Full Marks: 100
Course: Data Structure and Algorithms		Pass Marks: 45
		Time:  3hrs.

Section “A”

Very Short Answer Questions

Attempt all the questions.

1. What are the advantages of a circular queue over a linear queue?
2. Write any four applications of stack.
3. Find the postfix expression of a + b $ c / d * e.
4. What do you mean by the complete binary tree and strictly binary tree?
5. Define Hash collision and collision resolution.
6. Define the leftist heap with the leftist property.
7. What do you mean by adaptive and non-adaptive sorting?
8. How many edges are there in a complete graph having 10 vertices?
9. Where can we use the Divide and Conquer algorithm? Write any two examples?
10. What are the differences between Kruskal’s and Prim’s algorithm that finds MST?

Section “B”
Descriptive Answer Questions

Attempt any six questions
11. Explain Recursion and write a C-program to solve TOH for n number of disks.
12. What are the advantages, disadvantages, and applications of linked lists? Explain its types and operations.
13. Define AVL Tree. Create an AVL Tree from the following data and show the deletion of the root.
30, 55, 65, 60, 50, 62, 20, 15, 12, 25
14. What do you mean by priority queue? Create a min 2-heap for the following data:
10, 15, 7, 3, 12, 20, 4, 8, 10, 30, 1 and remove one element from this descending heap.
15. What do you mean by leftist heap? What is null path length? Create a leftist heap from the following data:
20, 10, 30, 25, 15, 40, 50, 35
16. Explain Quicksort in brief with an algorithm and suitable example.

17.                                                                                 Section”C”
                                                                                    Case Analysis
Read the following cases and answer the given questions:
a) The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand a vast amount of data items in a given collection.
Case Question:
How hashing facilitates searching and is better than binary searching and linear searching techniques? Explain.

b) In the case of a power grid and water network, vertices represent connection points and edges represent the wires or pipes between them. Graphs can be used to minimize the cost to build this infrastructure that matches the required demands.
Case Question:
Clarify the case by illustrating the concept of graph data structure with an example.