Download JNTUH MCA 2nd Sem R09 2017 August Data Structures And Algorithms Question Paper

FirstRanker.com

Code No: F3201 R09

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

--- Content provided by FirstRanker.com ---

MCA I Semester Examinations, August - 2017

DATA STRUCTURES AND ALGORITHMS

Time: 3hrs Max.Marks: 60

Answer any five questions

All questions carry equal marks

--- Content provided by FirstRanker.com ---

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. 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.

--- Content provided by FirstRanker.com ---

4. Make a comparison between the linear search and binary search. [6+6]
5. a) Construct an AVL tree with the following numbers: 25, 46, 13, 55, 15, 30, 58, 4, 6.
   b) Insert 50, 10 and 40, delete 25, 13 and 30 and rebalance the tree if necessary in each case.
6. Write insertion algorithm of red black tree. Also analyze its time complexity. [6+6]
7. a) Explain the Kruskal’s algorithm for minimum cost Spanning trees with an example.
   

   --- Content provided by FirstRanker.com ---

   b) Give a brief note on the Knuth-Morris-Pratt algorithm. [6+6]
8. a) Explain various collision resolution strategies in hashing.
   b) Compare and contrast exponential time complexity with polynomial time complexity. [6+6]
9. 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]

--- Content provided by FirstRanker.com ---

10. a) Consider a hash table of size 11 that uses open addressing with linear probing. Let h(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]

--00000--

FirstRanker.com

--- Content provided by FirstRanker.com ---