Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R092017 August Data Structures And Algorithms Previous Question Paper
R09
Code No:F3201
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, August - 2017
DATA STRUCTURES AND ALGORITHMS
Time: 3hrs
Max.Marks:60
Answer any five questions
All questions carry equal marks
- - -
1.a)
Explain an algorithm to implement insertion and deletion on a singly linked list.
b)
Analyze the best, average and worst case time complexities of linear search with an
example list of size n.
[6+6]
2.a)
What are the two different ways to represent a graph? Explain each of them.
b)
Differentiate between BFS and DFS traversals. Take an example graph and implement the
BFS traversal.
[6+6]
3.a)
Sort the following elements in ascending order by using Quicksort taking the last element
as pivot element? And show elements after each pass? 24, 47, 15, 8, 9, 4, 40, 30, 12, 17.
b) Make a comparison between the linear search and binary search.
[6+6]
4.a)
Construct an AVL tree with the following numbers:
25, 46,13,55,15,30,58,4,6.
Insert 50, 10 and 40, delete 25, 13 and 30 and rebalance the tree if necessary in each case.
b) Write insertion algorithm of red black tree. Also analyze its time complexity.
[6+6]
5.a)
Explain the Kruskal's algorithm for minimum cost Spanning trees with an example.
b)
Give a brief note on the Knuth-Morris-Pratt algorithm.
[6+6]
6.a)
Explain various collision resolution strategies in hashing.
b)
Compare and contrast exponential time complexity with polynomial time complexity.
[6+6]
7.a)
Write an algorithm to sort array of integers using exchange sort and find the time
complexity of exchange sort.
b) How do you perform searching operations in a B tree? Explain.
[6+6]
8.a)
Consider a hash table of size 11 that uses open addressing with linear probing. Let
n(k) = k mod 11 be the hash function used. Insert following elements into an initially
empty hash table? 45, 36, 92, 87, 11, 4, 71, 13, 4.
b) Explain the construction of Optimal Binary Search Trees.
[6+6]
--ooOoo--
This post was last modified on 17 March 2023