JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2018 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (January - 2018 - R15)
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
What are the applications of stacks and queues?
Answer
Stacks are primarily used for function call management (recursion), expression evaluation and conversion (infix to postfix), syntax parsing in compilers, and undo mechanisms in editors. Queues are essential for CPU scheduling, disk scheduling, buffering in IO devices, breadth-first search (BFS) algorithms, and handling asynchronous data transfers where order of arrival must be preserved.
Discuss about Union and Find Algorithms.
Answer
Union and Find algorithms are used to manage disjoint sets. The Find operation determines which subset a particular element belongs to, typically returning the representative of the set. The Union operation merges two disjoint sets into a single set. Efficiency is improved using Path Compression during Find and Union by Rank/Size, which keeps the tree height minimal, resulting in nearly constant time complexity per operation.
Write down the differences between linear searching and binary searching.
Answer
Sign in to view the complete answer paper.
What are the advantages and disadvantages of Splay Trees?
Answer
Sign in to view the complete answer paper.
Formulate Job Sequencing with Deadlines problem and explain briefly.
Answer
Sign in to view the complete answer paper.
Part B
Find the upper bound of the recurrence relation:
Answer
Sign in to view the complete answer paper.
Write the pseudocode which inserts the element at the right end of an array representation of a linear list and give an example.
Answer
Sign in to view the complete answer paper.
Explain the single linked list operations with appropriate algorithms.
Answer
Sign in to view the complete answer paper.
Explain various operations of stack data structure with relative example.
Answer
Sign in to view the complete answer paper.
What is a priority queue? State the applications of priority queue.
Answer
Sign in to view the complete answer paper.
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.
Answer
Sign in to view the complete answer paper.
Write down the algorithm for DFS graph traversal technique and explain with an example.
Answer
Sign in to view the complete answer paper.
What is collision in Hashing? Explain various methods to resolve the collision.
Answer
Sign in to view the complete answer paper.
Sort the following numbers using Radix sort: 100, 300, 95, 60, 10, 900, 800 showing positions of various buckets.
Answer
Sign in to view the complete answer paper.
Mention the advantages and disadvantages of Radix sort.
Answer
Sign in to view the complete answer paper.
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.
Construct the binary search tree.
Answer
Sign in to view the complete answer paper.
Find the in-order, pre-order and post-order traversal of BST created.
Answer
Sign in to view the complete answer paper.
Explain insertion and deletion operations of an AVL Tree.
Answer
Sign in to view the complete answer paper.
Explain the problem of optimal binary search Tree construction and give the solution method by the dynamic programming formulation.
Answer
Sign in to view the complete answer paper.
Discuss the Knuth-Morris-Pratt pattern matching algorithm with an example.
Answer
Sign in to view the complete answer paper.