1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034 M.C.A.DEGREE EXAMINATION COMPUTER APPLICATIONS FIRSTSEMESTER APRIL 2017
16PCA1MC04- DATA STRUCTURES AND ALGORITHMS
Date: 05-05-2017 Dept. No. Max. 100 Marks
Time: 01:00-04:00 PART A Answer ALL Questions (10 X 2 20 Marks)
1. What are the advantages of linked list?
2. Define Stack .
3. Define RedBlack tree.
4. Create a search tree from the following list: 27, 15, 32, 45. 5. Define Graph?
6. What do you mean by Spanning tree?.
7. Define Big O notation.
8. State the problem of job sequencing with deadlines.
9. State 8-Queen Problem.
10. What is branch and bound problem?
PART B Answer ALL Questions(5 X 8 40 Marks)
11a. Write the algorithm for converting from an Infix expression to Postfix expression.
11b. Write a program to demonstrate the stack operations for pushing 52 and retrieving two elements.
12a. i. Construct the binary tree whose inorder and postorder traversals are as follows: Inorder: HDIBJEKAFCG Postorder: HIDJKEBFGCA ii. Represent the following prefix expression as binary tree and write the postfix form. ACD A BD
12b. Explain the operations performed on a heap structure. 13a. Write short notes on graph traversals.
13b. Write Dijkstra's algorithm to find shortest path between any two nodes in a graph.
2
14a. Define algorithm. List the criteria that an algorithm should satisfy. 14b. Give general algorithm for Greedy method and explain.
15a. Describe the general method of Backtracking algorithm.
15b. Explain Bicycle lock problem. PART C Answer any TWO Questions x 20 40 Marks)
16a. Write a program to create and append nodes in a single linked list. 16b. Discuss various methods of hashing
17a. Write a program for Bubble sort and illustrate it with an example.
17b. Using Dijkstra's algorithm, find the shortest path between vertex A and vertex F in the following graph.
B 5 D 2 2 A 2 1 F 3 4 C 5 E
18a. Discuss Knapsack problem and its solution in detail.
18b. What is Dynamic Programming problem. Explain using multistage graph.