Download JNTUH MCA 2nd Sem R17 2019 December 842AA Data Structures And Algorithms Question Paper

Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R17 2019 December 842AA Data Structures And Algorithms Previous Question Paper


R17

Code No: 842AA















JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

MCA II Semester Examinations, December - 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

S 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) How can we measure an algorithm's running time?







[5]

b) Discuss minimum cost spanning tree.











[5]

c) State the Travelling sales person problem.









[5]

d) What is the purpose of a Hash function in Hashing?







[5]

e) Give the properties of red black tree.











[5]



PART - B

















5 ? 10 Marks = 50

2.a)

Solve the recurrence: T(n)=4T(n/2)+n, Where n 1 and is a power of 2.

b)

Write an algorithm for the finding the GCD of two numbers and also find the time
complexity of the same.















[5+5]

OR

3.a)

Show that the bestcase running time of Quicksort on a sequence of size n with distinct
elements is 0(nlogn).

b)

Explain the strassen's matrix multiplication.









[5+5]


4.a)

Describe UNION and FIND algorithms.

b)

What is the solution generated by using job sequencing with deadlines when n=7, (P1,
P2, P3 .....P7) = (3, 5, 20, 18, 1, 6, 30), and (d1, d2,.....d7 ) = (1, 3, 4, 3, 2, 1, 2). [5+5]

OR

5.

Explain an algorithm for generating minimum cost Spanning tree and list some
applications of it.

















[10]


6.a)

Discuss the general method for the dynamic programming.

b)

How the reliability of the system can be increased?







[5+5]

OR

7.a)

Write an algorithm of m-coloring problem.

b)

Solve the 4-queens problem using backtracking.









[5+5]


8.

Create the heap to sort the following list of numbers. 5, 18, 20, 9, 4, 15, 10, 30, 8, 45, 2,
22, 55, 63, 14, 72, 17.















[10]

OR

9.a)

What are the major advantages of extendible hashing over other hashing techniques?

b)

Write a function double hash to resolve collisions using double hashing.

[5+5]


10.a) How a node can be deleted from the binary search tree? Explain the methods.

b) Construct the B-tree of order 4 for the following list of elements {K, L, T, A, G, H, P,

W, R, U, Z, C, Y, B, J, M, E}













[5+5]

OR

11.

Elucidate Brute Force pattern matching algorithm with an example.



[10]

---ooOoo---

This post was last modified on 17 March 2023