Jawaharlal Nehru Technological University Hyderabad
Jawaharlal Nehru Technological University Hyderabad B.Tech III Year DATA STRUCTURES Previous Question Paper (March - 2024 - R16)
Answer all questions from Part A. Answer any one question from each unit in Part B.
Part A
Define time complexity and space complexity.
Answer
Time complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input. It is typically expressed using asymptotic notation, such as Big O notation, to describe the growth rate of the execution time relative to the input size.
Space complexity is a measure of the amount of working storage (memory) an algorithm requires as a function of the input size. It includes both the space for the input data and the auxiliary space used by the algorithm during its execution.
Represent the following sparse matrix as a linked list.
Answer
A sparse matrix can be represented as a linked list by storing only the non-zero elements. Each node in the linked list contains four fields: row index, column index, value, and a pointer to the next non-zero element node. The list is typically headed by a header node that stores the total number of rows, total number of columns, and the total number of non-zero elements present in the matrix.
This representation is highly efficient in terms of memory usage because it avoids storing zero values, which are predominant in sparse matrices. The traversal of the matrix is performed by following the pointers from the head node through the sequence of non-zero nodes.
Write any four applications of stack.
Answer
Sign in to view the complete answer paper.
Find the value of the given postfix expression AB+C*DE-F/+G+ where A = 3, B = 2, C = 5, D = 4, E = 6, F = 9, G=12.
Answer
Sign in to view the complete answer paper.
Represent the following graph using adjacency matrix.
Answer
Sign in to view the complete answer paper.
Represent the following binary tree using array.
Answer
Sign in to view the complete answer paper.
What is collision? How collisions are handled in hashing?
Answer
Sign in to view the complete answer paper.
How many comparisons are required using linear search and binary search to search the key 46 in the following elements? 12, 32, 34, 36, 40, 46, 50, 52, 53
Answer
Sign in to view the complete answer paper.
Define Binary Search Tree and AVL Tree.
Answer
Sign in to view the complete answer paper.
Write in-order, pre-order, post-order traversal sequences for the following binary search tree.
Answer
Sign in to view the complete answer paper.
Part B
Write a function to insert an element at the end of the linked list.
Answer
Sign in to view the complete answer paper.
Write an algorithm to insert an element at the front of circular linked list.
Answer
Sign in to view the complete answer paper.
Write a function to add two sparse matrices.
Answer
Sign in to view the complete answer paper.
Write a function to find GCD of two numbers using recursion.
Answer
Sign in to view the complete answer paper.
Write the program to implement operations of stack using arrays.
Answer
Sign in to view the complete answer paper.
Write the program to convert given infix expression into postfix expression.
Answer
Sign in to view the complete answer paper.
Write the program to implement operations of queue using linked list.
Answer
Sign in to view the complete answer paper.
What is deque (Double ended queue)? Explain insert and delete operations of deque.
Answer
Sign in to view the complete answer paper.
Write a procedure to insert an element into max heap.
Answer
Sign in to view the complete answer paper.
Define Graph. Write a function to traverse the graph using BFS.
Answer
Sign in to view the complete answer paper.
Write a function to delete an element from binary tree.
Answer
Sign in to view the complete answer paper.
Differentiate between DFS and BFS.
Answer
Sign in to view the complete answer paper.
Create a hash table using the following values: 98, 73, 21, 58, 88, 14, 37, 77. The hash function is h(x) = x%7.
Answer
Sign in to view the complete answer paper.
Write a program to implement insertion sort.
Answer
Sign in to view the complete answer paper.
Use selection sort to sort the following elements: 23, 21, 11, 43, 32, 55, 2, 9. Show the array elements at each step.
Answer
Sign in to view the complete answer paper.
Write a program to search for an element using binary search.
Answer
Sign in to view the complete answer paper.
Write a function to insert an element into a binary search tree.
Answer
Sign in to view the complete answer paper.
Explain various rotations of the AVL tree.
Answer
Sign in to view the complete answer paper.
Write the process to insert and delete an element in B-Tree.
Answer
Sign in to view the complete answer paper.
Write an algorithm for The Knuth-Morris-Pratt algorithm.
Answer
Sign in to view the complete answer paper.