(SEM IV) THEORY EXAMINATION 2018-19 DATA STRUCTURE

SECTION–A — Short Questions Checking Fundamental DSA Concepts (14 Marks)

Section–A contains seven 2-mark questions, each touching the fundamental ideas of data structures and algorithms. The very first question asks students to compute the number of moves in Tower of Hanoi for n = 15 disks, which checks understanding of the classical recursive formula 2n−12^n - 12n−1.

The second question asks to explain AVL trees and list the rotation cases, ensuring that students understand height-balancing in binary search trees, with LL, RR, LR, and RL cases. The next question introduces priority queues, asking about their behavior and the condition of overflow, which helps check the student’s knowledge of abstract data types and heap-based implementation.

The fourth question focuses on Breadth First Search (BFS), a fundamental graph traversal technique using queues. The next question concerns the rules of infix to postfix conversion, testing understanding of precedence, associativity, and stack handling. Students are also asked to define data types and their types (primitive, derived, constructed, abstract), which is a core programming concept. The section ends with a comparison of complete binary trees versus full binary trees, ensuring clarity on tree structure constraints.

SECTION–B — Algorithm Design, Sorting, Queue Operations, MST, Expression Conversion (21 Marks)

Section–B requires students to attempt any three out of five long questions. Each of them evaluates algorithmic reasoning and practical understanding.

The first question asks for the algorithm of insertion sort, followed by a complete trace on the dataset (77, 33, 44, 11, 88, 22, 66, 55). This tests the student’s ability to apply sorting logic step by step.

The next question asks students to define an algorithm and list the parameters to judge efficiency, such as time complexity, space complexity, correctness, robustness, maintainability, etc.

Another question asks for the algorithm to insert an element in a queue, along with defining a deque and describing input- and output-restricted deques with diagrams, which tests understanding of advanced queue structures.

The next option deals with Minimum Spanning Trees (MST), asking students to explain Kruskal’s Algorithm with an example, testing graph-theory competency.

The last question asks to convert a very long infix expression into postfix notation:

AB−CD∗E$F+G/H−I+JA^B - C^D * E\$F + G/H - I + JAB−CD∗E$F+G/H−I+J

This tests precise step-handling of the Shunting Yard process.
 

SECTION–C — Heap Construction OR Binary Search Tree Construction (7 Marks)

This section requires choosing one of two detail-oriented structure-building tasks.

The first option asks to define heap, differentiate between max-heap and min-heap, and to build a Min-Heap using the sequence:
60, 33, 50, 22, 55, 40, 11, 22, 65, 30
This tests understanding of heapify operations and array-based heap representation.

The alternate option requires drawing the Binary Search Tree (BST) obtained by inserting the ordered elements:
50, 48, 35, 44, 80, 70, 10, 55, 11, 85
This question checks whether students can apply BST insertion rules correctly and represent the final structured tree.
 

SECTION–D — Tower of Hanoi OR AVL Rotations (7 Marks)

Section–D focuses on recursive thinking and balanced tree design.

The first choice asks to explain Tower of Hanoi using a proper tree representation for n = 3 disks and towers A, B, C. Students must illustrate the recursive subproblem division: moving n-1 disks, shifting the largest disk, and repeating.

The alternate question requires inserting the keys 12, 22, 17, 20 into an AVI tree and showing proper rotations required to maintain its height balance. This tests the student’s understanding of imbalance detection and correction (LL, RR, LR, RL rotations).

SECTION–E — Circular Queue OR Doubly Linked List (7 Marks)

Section–E asks students to select one of two data-structure design questions.

The first option asks: What is a Circular Queue? and requires full algorithms for inserting and deleting an item. This tests boundary condition management, including front/rear wrapping and overflow/underflow handling.

The alternative option asks for explanation of Doubly Linked List representation with an example, ensuring that students understand two-way pointer usage and node-based dynamic storage.

SECTION–F — Dijkstra’s Algorithm OR DFS & BFS (7 Marks)

This section covers graph traversal and shortest-path algorithms.

The first option requires describing Dijkstra’s Algorithm, followed by a full step-by-step working for the given graph (the graph is printed on page 2). Students must relax edges, update distance tables, and identify final shortest paths.

The second option asks for algorithms of DFS and BFS, along with illustrative examples, testing comprehension of stack-based and queue-based graph exploration.

SECTION–G — Memory Mapping OR Hash Table Construction (7 Marks)

The final section tests computational implementation of arrays and hashing.

The first question gives a 2D array A[20][50], with base = 2000 and element size = 4 bytes. Students must compute the location of A[10][10] using both Row-Major and Column-Major addressing formulas. This tests the ability to map multi-dimensional arrays into linear memory.

The alternate question provides keys:
11, 31, 32, 49, 55, 27, 60, 50, 77, 25
and asks to place them in a hash table of size 15 using:
open addressing
chaining
This evaluates collision-handling techniques and hashing proficiency.

FINAL SUMMARY — Complete Descriptive Overview of the Exam Paper

The DATA STRUCTURE & ALGORITHM (RCS-406) question paper is comprehensive and evaluates conceptual clarity, algorithmic logic, problem-solving ability, and efficient data-handling techniques. Section–A tests core definitions and structures. Section–B challenges students to write algorithms, trace them, and convert expressions. Sections C–G cover trees, heaps, recursion, queues, linked lists, shortest-path algorithms, memory addressing, and hashing.

The paper ensures students demonstrate both theoretical understanding and practical implementation skills across the full DSA syllabus.