JNTUH
JNTUH MCA 2019 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (December 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
Define a single linked list, Write the structure of the linked list with neat sketch.
Answer
A singly linked list is a linear data structure where each element, called a node, contains a data field and a pointer (or reference) to the next node in the sequence. It allows for efficient insertion and deletion of elements as it does not require contiguous memory allocation.
The structure in C is:
Sketch representation: [Data|Next] -> [Data|Next] -> [Data|NULL]
Explain the representations of graphs.
Answer
Graphs are primarily represented using two methods:
- Adjacency Matrix: A 2D array of size V x V where matrix[i][j] = 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 linked lists where each index i represents a vertex and points to a list of all vertices adjacent to i. This is more space-efficient for sparse graphs, requiring O(V + E) space.
Write a program to sort an array of integers using selection sort.
Answer
Sign in to view the complete answer paper.
Insert 02, 36, 09, 06, 14, 27, 28 into BST.
Answer
Sign in to view the complete answer paper.
What is dynamic programming? When to apply it.
Answer
Sign in to view the complete answer paper.
Part B
Explain the Operations on Doubly Linked Lists.
Answer
Sign in to view the complete answer paper.
List and explain the applications of stack ADT.
Answer
Sign in to view the complete answer paper.
Write an algorithm to find the sum of n-numbers and also analyze its time complexity.
Answer
Sign in to view the complete answer paper.
Differentiate between BFS and DFS traversals. Take an example graph and implement the BFS traversal.
Answer
Sign in to view the complete answer paper.
Define tree and what are the properties of trees?
Answer
Sign in to view the complete answer paper.
Explain the different types tree traversals.
Answer
Sign in to view the complete answer paper.
Explain the worst-case time complexity in the quick sort.
Answer
Sign in to view the complete answer paper.
Explain the different types of Hash functions are used in hashing.
Answer
Sign in to view the complete answer paper.
Perform heap sort algorithm for (10 15 6 2 25 18 16 2 20 4).
Answer
Sign in to view the complete answer paper.
Define AVL trees. Explain the rotations involved in balancing an unbalanced AVL tree.
Answer
Sign in to view the complete answer paper.
Write the insertion algorithm of red-black tree. Also analyze its time complexity.
Answer
Sign in to view the complete answer paper.
What are properties of B-Tree.
Answer
Sign in to view the complete answer paper.
Compare the Standard Tries and Compressed Tries with an example.
Answer
Sign in to view the complete answer paper.
State and explain the Knuth-Morris-Pratt algorithm with an example.
Answer
Sign in to view the complete answer paper.