JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year DATA STRUCTURES Previous Question Paper (February - 2024 - R15)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
Part A
What is sparse matrix? Show array representation of a sparse matrix.
Answer
A sparse matrix is a matrix in which the number of zero elements is significantly higher than the number of non-zero elements. It is represented using a 2D array of size (n+1) x 3, where the first row stores the total number of rows, columns, and non-zero values, and subsequent rows store the triplet (row_index, column_index, value) for each non-zero element.
What is amortized complexity? Discuss briefly.
Answer
Amortized complexity is the average time taken per operation over a worst-case sequence of operations. Unlike average-case analysis, which relies on probability, amortized analysis guarantees the average performance of each operation in the worst case, ensuring that occasional expensive operations are offset by a large number of cheap ones.
What is an ADT? Write stack ADT.
Answer
Sign in to view the complete answer paper.
What is Deque? Indicate how deque is represented in C.
Answer
Sign in to view the complete answer paper.
Define strictly binary tree. Give example.
Answer
Sign in to view the complete answer paper.
Explain adjacency matrix representation of a graph with example.
Answer
Sign in to view the complete answer paper.
What is Hash table?
Answer
Sign in to view the complete answer paper.
What is sorting? What is searching?
Answer
Sign in to view the complete answer paper.
Define AVL tree.
Answer
Sign in to view the complete answer paper.
What are splay trees?
Answer
Sign in to view the complete answer paper.
Part B
Give the node structure to create a linked list of integers and write C functions to perform the following:
Create a three node list with data 11, 22, and 33.
Answer
Sign in to view the complete answer paper.
Insert a node with data value 15 in between the nodes 11 and 22.
Answer
Sign in to view the complete answer paper.
Display the resulting singly linked list.
Answer
Sign in to view the complete answer paper.
Explain different types of linked lists with diagram.
Answer
Sign in to view the complete answer paper.
Write a C program to insert a node into a doubly linked list.
Answer
Sign in to view the complete answer paper.
Discuss the various exceptional conditions that should be handled while using stacks.
Answer
Sign in to view the complete answer paper.
Convert the following postfix expressions to infix expressions: i) A B C D E / * - F / G + + ii) a b c d g / * + +.
Answer
Sign in to view the complete answer paper.
Define stack and write functions for operations over stack.
Answer
Sign in to view the complete answer paper.
Write a C program to reverse a string using stack.
Answer
Sign in to view the complete answer paper.
Explain insertion and deletion from a Max Heap with examples.
Answer
Sign in to view the complete answer paper.
Write a C program to implement BFS.
Answer
Sign in to view the complete answer paper.
Write C functions for the following tree traversals: i) In order ii) Pre order iii) Post order.
Answer
Sign in to view the complete answer paper.
Apply heap sort on the following list of elements: {14, 12, 9, 8, 7, 10, 18, 20, 30}
Answer
Sign in to view the complete answer paper.
What is hash function? Explain different hash functions with example.
Answer
Sign in to view the complete answer paper.
Analyze input (371, 325, 163, 199, 344, 679, 989, 534, 448, 355) and the hash function is h(x) = x mod 10. Show the result using quadratic probing and double hashing h2(x) = 7 – (x mod 7).
Answer
Sign in to view the complete answer paper.
Construct a b-tree of order 3 for the following: {5, 3, 21, 9, 1, 13, 2, 7, 10, 12, 4, 8}
Answer
Sign in to view the complete answer paper.
Explain about Red-Black trees.
Answer
Sign in to view the complete answer paper.
Explain different types of AVL rotations with example.
Answer
Sign in to view the complete answer paper.