(SEM IV) THEORY EXAMINATION 2018-19 DATA STRUCTURE

SECTION–A — Short, Conceptual Questions Covering Core DSA Fundamentals (14 Marks)

Section–A contains seven brief questions, each worth 2 marks, but they collectively cover the most fundamental ideas of Data Structures and Algorithms. The first question asks for the definition of asymptotic notation and an explanation of Big-O notation, testing whether students understand how algorithm performance is expressed mathematically in terms of input size.

The second question moves into memory mapping and asks for the address calculation of a 2D array A[–100:100, –5:50] using row-major order, a base address of 10, and 4 bytes per element. This checks the mathematical understanding of array storage in contiguous memory.

The third question provides inorder and preorder traversals of a binary tree and requires reconstruction of the complete tree. This tests tree construction skills based solely on traversal sequences.

Next, the section asks to evaluate a postfix expression, which ensures students understand stack-based expression evaluation.

The question on collision resolution in hashing checks the conceptual clarity of chaining, open addressing, rehashing, and similar techniques. The sixth question demands a recursive solution to Tower of Hanoi, reinforcing recursive thinking. Finally, the comparison between complete binary tree and full binary tree checks clarity on structural constraints of binary tree types.

SECTION–B — Long, Analytical Questions on Lists, Sorting, Huffman Coding & Graph Algorithms (21 Marks)

Section–B requires the student to attempt any three out of five 7-mark questions, each evaluating deeper analytical ability.

The first question requires converting a complex infix expression into postfix using a stack, forcing students to apply operator precedence, associativity rules, and proper use of a stack.

The second question asks: What is a doubly linked list? and then requires an algorithm to insert a node at the beginning of a singly linked list, testing conceptual distinctions and pointer manipulation skills.

A major question in this section asks to construct a Huffman Tree for eight characters (A, B, C, D, E, F, G, H) with given frequencies 22, 5, 11, 19, 2, 11, 25, 5 respectively. After building the tree, the student must provide the binary Huffman code of the word “HEAD” — a practical application of lossless coding.

Another question asks to apply Dijkstra’s Algorithm to find the shortest paths from source S to all other vertices. This requires relaxation steps and building a distance table.

The final option asks students to apply Heap Sort on a specific sequence {8, 5, 45, 24, 36, 11, 43, 21}, covering heap construction and repeated deletion of max/min elements.
 

SECTION–C — Time–Space Trade-Off OR Circular Linked List (7 Marks)

Section–C provides two choices. The first asks to explain the time–space trade-off, and then requires describing how time complexity is analysed in best, average, and worst cases. This question checks the student’s ability to reason about algorithm efficiency.

The alternate option asks: What is a circular linked list? and then requires writing an algorithm to delete a node from the beginning of a singly linked list. This tests understanding of pointer updates and special cases like empty/single-node lists.

SECTION–D — Priority Queues OR Prefix Conversion Algorithm (7 Marks)

This section again offers two choices.

The first option asks what a priority queue is and requires explaining the various ways it can be maintained in memory — using sorted arrays, unsorted arrays, binary heaps, and sometimes Fibonacci heaps.

The second option requires writing the algorithm for converting an infix expression into prefix notation, which is more complex than postfix conversion because it requires reversing the expression, handling parentheses, and applying stack operations carefully.

SECTION–E — Binary Tree Construction OR Threaded Binary Tree (7 Marks)

In this section, students must choose one of two tree-based questions.

The first option provides preorder and postorder traversals of a binary tree and asks the student to reconstruct the complete tree. This is more challenging because reconstruction is not always unique; however, the given data is chosen in such a manner that a unique tree emerges.

The alternate option asks: What is a threaded binary tree? and requires explanation of two-way inorder threading, where left-null and right-null pointers are replaced with previous and next pointers to facilitate non-recursive traversal.

SECTION–F — Floyd–Warshall Algorithm OR Transitive Closure (7 Marks)

This section tests graph algorithms.

The first option asks students to implement Floyd–Warshall Algorithm on a given graph. This requires understanding dynamic programming, distance matrix updates, and triple nested loop execution.

The second option asks to explain transitive closure of a graph and list the steps used to compute it — usually using Warshall’s Algorithm or repeated BFS/DFS.

SECTION–G — AVL Tree OR B-Tree Insertion (7 Marks)

The final section focuses on advanced tree structures.

The first option asks the student to describe an AVL tree and then requires constructing an AVL tree by inserting the elements:
{60, 2, 15, 20, 12, 115, 90, 88}
This involves detecting imbalances and performing the appropriate LL, RR, LR, or RL rotations.

The alternate option asks to show the results of inserting the keys
F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B
in order into an initially empty B-Tree of order 5, requiring multiple splits and promotion steps.

FINAL SUMMARY — Full Descriptive Overview of the Exam Paper

The DATA STRUCTURES (RCS-405) question paper is comprehensive and examines every major concept taught in the course. Section–A covers asymptotic notations, arrays, trees, hashing, recursion, and tree types. Section–B tests sorting, linked lists, Huffman coding, graph algorithms, and heap operations. Sections C–G explore deeper analytical concepts such as time–space complexity, linked lists, priority queues, tree construction, Floyd–Warshall, transitive closure, AVL rotations, and B-Tree insertion.

Overall, the paper assesses whether the student can reason about algorithms, manipulate data structures, perform correct calculations, and build logical programs with solid theoretical grounding.