Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R15 2018 June-July 821AF Data Structures And Algorithms Previous Question Paper
R15
Code No: 821AF
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, June/July - 2018
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) Explain about the Asymptotic notations.
[5]
b) Write an algorithm for DFS traversal.
[5]
c) Write an abstract algorithm of Divide and Conquer method.
[5]
d) What are the properties of Red- Black tree?
[5]
e) Explain about the Compressed trie with an example.
[5]
PART - B
5 ? 10 Marks = 50
2.a)
Explain the operations of Doubly linked list with an example.
b)
Write an algorithm to find whether the given number is a palindrome or not and also
compute the time complexity of the same.
[5+5]
OR
3.a)
Write an algorithm to convert the infix expression to postfix expression and also compute
the time complexity of the same.
b) Differentiate between stack and queue.
[5+5]
4.
Write a Non ? recursive algorithm of tree traversals and also compute the complexity of
the same.
[10]
OR
5.
Explain about the union and find algorithms with an example and also how to improve the
complexity of the same.
[10]
6.
Derive the time complexity of Quick sort in an average case.
[10]
OR
7.a)
Insert the following list of elements into the hash table by using Quadratic probing (size of
hash table is 10)
45, 67, 30, 89, 27, 37, 11, 76
b)
Explain about the Radix sort with an example.
[5+5]
8.a)
Construct the B-tree of order 4 of the following data
12, 40, 69, 34, 90, 22, 45, 89, 78, 56, 47, 36
b)
Write an algorithm to delete an element from the binary search tree.
[5+5]
OR
9.
What is Splay tree? Explain the Splaying operations of Splay tree with an example.[10]
10.
Consider the following text T and pattern P
Text: THIS IS AN EXAMPLE
Pattern: AMPLE
Apply the KMP algorithm and illustrate the intermediate steps.
[10]
OR
1
1
1
11.
Consider 4 elements al < a2 < a3 < a4 with q(0) = , q(1) =
, q(2) = q(3) = q(4) =
:
8
16
16
1
1
1
p(1) = , p(2) = , p(3) = p(4) =
. Construct the optimal binary search tree. [10]
4
8
16
---oo0oo---
This post was last modified on 17 March 2023