JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2019 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (April/May - 2019 - R13)
Part A is compulsory which carries 20 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 8 marks and may have a, b, c as sub questions.
PART - A
Write briefly about Abstract Data Type.
Answer
An Abstract Data Type (ADT) is a mathematical model for data types where the data type is defined by its behavior (operations) from the perspective of the user, rather than its implementation. It specifies what operations can be performed on the data and the constraints on those operations, without specifying how the data is stored or how the algorithms for the operations are implemented. This promotes abstraction and encapsulation, allowing the internal representation to change without affecting the code that uses the ADT.
Write a short note on Graph Representations.
Answer
Graphs are primarily represented in memory using two methods:
- Adjacency Matrix: A 2D array of size V x V where the cell [i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. It is efficient for dense graphs but requires O(V2) space.
- Adjacency List: An array of lists where each index represents a vertex and stores a list of all adjacent vertices. It is space-efficient for sparse graphs, requiring O(V + E) space.
When quick sort will take more time to sort the list? Give an example.
Answer
Sign in to view the complete answer paper.
Discuss briefly about B-Tree.
Answer
Sign in to view the complete answer paper.
Write about Knuth-Morris-Pratt algorithm.
Answer
Sign in to view the complete answer paper.
PART - B
Write an algorithm to convert a valid arithmetic Infix Expression into it equivalent Postfix Expression. Trace your algorithm for A-B/C+D*E+F.
Answer
Sign in to view the complete answer paper.
Explain the difference between Stack and Queue.
Answer
Sign in to view the complete answer paper.
Write an algorithm of operation of doubly linked list.
Answer
Sign in to view the complete answer paper.
Define Disjoint Set? Explain the Operations that are performed on Sets.
Answer
Sign in to view the complete answer paper.
What is Heap? Construct the man heap of the following list of elements 50,30,60,80,40,20,90.
Answer
Sign in to view the complete answer paper.
Explain about Merge Sort? Why Merge Sort is considered as External Sort.
Answer
Sign in to view the complete answer paper.
Discuss Radix Sort with suitable example.
Answer
Sign in to view the complete answer paper.
Explain about Red Black tree and AVL tree? Which is better AVL or Red Black Tree?
Answer
Sign in to view the complete answer paper.
Define Binary Search Tree? With example explain operations of Binary Search.
Answer
Sign in to view the complete answer paper.
Considered the following jobs: Job ID Deadline Profit. Find the Maximum Profit using Job Sequencing with Deadlines?
Answer
Sign in to view the complete answer paper.
Describe All Pair Shortest Path with suitable example?
Answer
Sign in to view the complete answer paper.