Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R17 2019 April-May 842AA Aprilmay Data Structures And Algorithms Previous Question Paper
R17
Code No: 842AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, April/May -2019
DATA STRUCTURES AND ALGORITHMS
Time: 3hrs
Max.Marks:75
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 ? 5 Marks = 25
1.a) What do you mean by time complexity? Discuss briefly.
[5]
b) Describe Job sequencing with deadlines.
[5]
c) Explain general method of backtracking.
[5]
d) Discuss about linear probing.
[5]
e) What are various types of trees? Explain.
[5]
PART - B
5 ? 10 Marks = 50
2.a) Describe pseudo code conventions of algorithms.
b) Write an algorithm for Quick sort.
[5+5]
OR
3.a) Explain about Strassen's matrix multiplication.
b) What are asymptotic notations? Explain with examples.
[5+5]
4.
Show that Prim's algorithm can like Kruskal's algorithm be implemented using
Heap. Show that it then takes a time in (a log n).
[10]
OR
5.a)
Explain Kruskal's algorithm for minimum-cost spanning trees.
b) Solve the Greedy Knapsack problem where
m=25, n=3, P = (25,24,17) and W = (16,14,9).
[5+5]
6.a) Analyze the time complexity of OBST.
b)
Explain in detail about Graph coloring problems?
[5+5]
OR
7.a) Explain about sum-of-subsets problem.
b) Differentiate between Greedy method and Dynamic Programming.
[5+5]
8.a) Write an algorithm of Heap sort.
b) Explain about double hashing? Illustrate with an example.
[5+5]
OR
9.
Give an example of selection sort.
[10]
10. 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
11.a) Explain deletion operation from an AVL search tree.
b) Describe Knuth- Morris-Pratt algorithm.
[5+5]
---ooOoo---
This post was last modified on 17 March 2023