1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034
M.C.A. DEGREE EXAMINATION COMPUTER APPLICATIONS
FIRST SEMESTER NOVEMBER 2017
17/16PCA1MC04 DATA STRUCTURES AND ALGORITHMS
Date: 10-11-2017 Dept. No. Max. 100 Marks
Time: 01:00-04:00
SECTION A
Answer All Questions (10X2=20)
1. Why stack is considered as an abstract data type?
2. What is the prefix form of
3. What is the difference between binary tree and binary search tree?
4. What is the principle of insertion sort?
5. Define graph
6. How Prim's Algorithm differs from Kruskal's algorithm?
7. What is external sorting? How it differs from internal sorting?
8. Define space complexity of algorithms
9. Define Dynamic programming
10. What is 0/1 knapsack problem?
SECTION B
Answer All Questions
11. Write an algorithm to insert elements in a list

Explain the evaluation of postfix algorithm with example
12. Explain the tree traversal algorithms with example

Explain bubble sort algorithm with an example
13. Explain breadth first traversal algorithm with an example.

What is topological sorting? Write down the algorithm and explain with an example.
14. Explain Merge Sort with an example.

What is Knapsack problem? Write a greedy algorithm to solve it.
15. Explain Queen's problem and the algorithm to resolve it.

Explain travelling salesman problem and solve it using branch and bound technique.
2
SECTION C
Answer any two questions (2X20=40)
16. Explain the basic operations on arrays with examples.
ii) Explain quick sort algorithm with example
17. Explain Dijkstra's algorithm with an example
ii) Explain Asymptotic Notations in finding the time complexity of algorithms
18. Find the minimum spanning path in the following Graph from A and H. through forward approach
and backward approach
ii) Explain hashing functions with example.