Download JNTUH MCA 2nd Sem R17 2019 April-May 842AA Aprilmay Data Structures And Algorithms Question Paper

FirstRanker.com
Firstranker's choice

FirstRanker.com

--- Content provided by‌ FirstRanker.com ---

Code No: 842AA

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, April/May -2019
DATA STRUCTURES AND ALGORITHMS
Time: 3hrs Max.Marks:75

--- Content provided by FirstRanker.com ---

Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b, c as sub questions.

PART - A

5 x 5 Marks =25

1. a) What do you mean by time complexity? Discuss briefly. [5]

--- Content provided by FirstRanker.com ---

2. b) Describe Job sequencing with deadlines. [5]
3. c) Explain general method of backtracking. [5]
4. d) Discuss about linear probing. [5]
5. e) What are various types of trees? Explain. [5]

PART -B

--- Content provided by​ FirstRanker.com ---

5 x 10 Marks =50

1. a) Describe pseudo code conventions of algorithms.
2. b) Write an algorithm for Quick sort. [5+5]

OR

3. a) Explain about Strassen’s matrix multiplication.

--- Content provided by‍ FirstRanker.com ---

4. b) What are asymptotic notations? Explain with examples. [5+5]
5. Show that Prim’s algorithm can like Kruskal’s algorithm be implemented using Heap. Show that it then takes a time in-0(a log n). [10]

OR

6. a) Explain Kruskal’s algorithm for minimum-cost spanning trees.
7. b) Solve the Greedy Knapsack problem where
   

   --- Content provided by⁠ FirstRanker.com ---

   m=25, n=3, P =(25,24,17).and W = (16,14,9). [5+5]
8. a) Analyze the time complexity of OBST.
9. b) Explain in detail about Graph coloring problems? [5+5]

OR

10. a) Explain about sum-of-subsets problem.

--- Content provided by‍ FirstRanker.com ---

11. b) Differentiate between Greedy method and Dynamic Programming. [5+5]
12. a) Write an algorithm of Heap sort.
13. b) Explain about double hashing? Illustrate with an example. [5+5]

OR

14. Give an example of selection sort. [10]

--- Content provided by‌ FirstRanker.com ---

15. Start with an empty Red-Black tree and insert the following keys in the given order: 20, 10, 5, 30, 40, 57, 3, 2.4, 35, 25, 18, 22, 21.
    Draw the figures depicting the tree immediately after each insertion and following the rebalancing rotation or colour change (if any). Label all nodes with their colour and

identify their rotation types(if any) that is done. [10]

OR

16. a) Explain deletion operation from an AVL search tree.

--- Content provided by‌ FirstRanker.com ---

17. b) Describe Knuth- Morris-Pratt algorithm FirstRanker.com [5+5]