Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R15 2018 January 821AF Data Structures And Algorithms Previous Question Paper
R15
Code No: 821AF
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, January - 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)
What are the applications of stacks and queues?
[5]
b) Discuss about Union and Find Algorithms.
[5]
c)
Write down the differences between linear searching and binary searching.
[5]
d)
What are the advantages and disadvantages of Splay Trees?
[5]
e) Formulate Job Sequencing with Deadlines problem and explain briefly.
[5]
PART - B
5 ? 10 Marks = 50
2.a)
Find the upper bound of the recurrence relation: T(n) = T(n/2) + T(2n/3) + 1.
b)
Write the pseudocode which inserts the element at the right end of an array representation
of a linear list and give an example.
[5+5]
OR
3.a)
Explain the single linked list operations with appropriate algorithms.
b)
Explain various operations of stack data structure with relative example.
[5+5]
4.a)
What is a priority queue? State the applications of priority queue.
b)
Show the result at each pass of inserting the following elements in to an empty min heap:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
[4+6]
OR
5.
Write down the algorithm for DFS graph traversal technique and explain with an example.
[10]
6.
What is collision in Hashing? Explain various methods to resolve the collision.
[10]
OR
7.a)
Sort the following numbers using Radix sort:
100, 300, 95, 60, 10, 900, 800 showing positions of various buckets.
b)
Mention the advantages and disadvantages of Radix sort.
[6+4]
8.
Suppose the following list of numbers is inserted in order into an empty binary search tree:
45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10.
a) Construct the binary search tree.
b) Find the in-order, pre-order and post-order traversal of BST created.
[4+6]
OR
9.
Explain insertion and deletion operations of an AVL Tree.
[10]
10.
Explain the problem of optimal binary search Tree construction and give the solution
method by the dynamic programming formulation.
[10]
OR
11.
Discuss the Knuth-Morris-Pratt pattern matching algorithm with an example.
[10]
---oo0oo---
This post was last modified on 17 March 2023