M.Sc. DEGREE EXAMINATION, NOVEMBER 2017
First Semester
Computer Science
DATA STRUCTURE AND ALGORITHMS
(CBCS 2016 onwards)
Time 3 Hours Maximum 75 Marks
Part A (10 x 2 20)
Answer all questions.
1. What are the possible ways available to represent the two
dimensional array?
2. Write the advantages of linked list.
3. What is the maximum number of nodes in a binary tree
of depth
4. Define Hashing.
5. What is the worst-case complexity of insertion sort?
6. What are the two ways available to maintain a graph in
the memory of a computer?
7. Define time complexity.
8. What are the criteria to be satisfied by an algroithm?
Sub. Code
551102
RW-978
2
Sp4
10. What do you mean by back tracking?
Part B x 5 25)
Answer all questions choosing either or
11. Describe the different types of data structure.
Or
Write an algorithm to insert a node at the front of
the linked list.
12. What is threaded binary tree? Briefly explain its
applications.
Or
Write about AVL Tree.
13. Describe the selection sort procedure.
Or
Explain the depth first search algorithm with an
example.
14. Classify the rate of growth of an algorithm and
explain.
15. Describe the Kruskal algorithm to find the
minimum spanning tree.
Or
Explain the travelling sales person problem.
Part C x 10 30)
Answer any three questions.
16. What is stack? What are the operations that can be
performed on stack? Explain.
17. Describe the applications of binary trees.
18. Use radix sort to sort the numbers
310, 213, 023, 130, 013, 301, 222, 032, 201
111, 323, 002, 330, 102, 231, 120.
Also explain and write an algorithm for the same.
19. What are the major criteria available for judging the
performance of an algorithm? Explain them with an
example.
20. Explain the 8 queens problem.