About this previous year paper
This examination evaluates the students’ understanding of fundamental data structure principles, algorithm design, memory representation, tree/graph operations, hashing techniques, and complexity analysis. The paper is structured across three sections to test conceptual clarity, algorithmic thinking, and problem-solving skills.
SECTION A — Short Answer Questions (14 Marks)
Seven questions × 2 marks each
This section checks the student's foundational knowledge of Data Structures and Algorithms.
Concepts Included:
1. Asymptotic Notations
Students recall Big-O, Big-Ω, Big-Θ, Little-o, Little-ω etc., used for analyzing algorithm efficiency.
2. Precedence in Infix vs Postfix Expressions
Why infix requires parentheses for unambiguous evaluation but postfix does not.
3. Quick Sort Pivot Choice
How selecting first/last/random/median pivot affects best, average, and worst time complexity.
4. Two Forms of Hashing
Open hashing and closed hashing; chaining, probing methods, etc.
5. Huffman Algorithm & Binary Trees
Binary tree is central to building optimal prefix codes.
6. Edges in Regular Graph
Formula:
Edges=nd2\text{Edges} = \frac{nd}{2}Edges=2nd
7. Algorithm for Connected Components
Using DFS/BFS to identify all components in graphs.
This section measures the student's fundamental clarity on core data structure concepts.
SECTION B — Medium-Level Analytical / Algorithmic Tasks (21 Marks)
Attempt any three × 7 marks
These questions assess algorithm-building, tracing, and implementation skills.
1. Concatenate Two Linked Lists
Write pseudocode with parameters as list heads; link last node of first list to start of second.
2. Infix → Postfix Conversion Algorithm
Use operator precedence, associativity rules, stack operations with full trace for expression:
A + B * C – D / F
3. Disadvantages of Linear Probing & Quadratic Probing Solution
Discuss clustering, primary/secondary clustering, and how quadratic probing reduces cluster formation.
4. Non-Recursive Postorder Traversal
Write C implementation using stack; no recursion allowed.
5. Dijkstra’s Algorithm
Apply it on the given graph to compute shortest paths from source.
This section examines algorithm writing, code correctness, and ability to trace operations.
SECTION C — Long Descriptive / High-Weightage Questions (35 Marks)
One question from each group × 7 marks
3. Array Address Calculations / Polynomial Linked List
Option A – Address Calculation
Given 2D array Data[20][50], element size = 4 bytes, base = 2000
Find address of Data[10][10] for both:
• Row major
• Column major
Option B – Polynomial Using Linked List
Explain node structure (coeff, power, next), creation, insertion, and representation with example.
4. Expression Evaluation Using Stack / Deque Implementation
Option A – Evaluate Arithmetic Expression
Algorithm to evaluate using stack and show step-by-step evaluation of:
3 * (5 – 3)
Option B – Deque Representation
Map deque onto 1D array and write C functions for:
• Insert Left
• Insert Right
• Delete Left
• Delete Right
5. Sorting / Binary Search
Option A – Selection Sort Program in C
Sort 100 integers; discuss worst-case complexity O(n²).
Option B – Binary Search Program
C code + explanation of average time complexity O(log n).
6. Tree Properties / Huffman Coding
Option A – External & Internal Path Length
Prove:
E=I+2nE = I + 2nE=I+2n
for a binary tree with n internal nodes.
Option B – Huffman Code Construction
Given probabilities (0.07, 0.09, 0.12, 0.22, 0.23, 0.27):
• Build Huffman tree
• Generate code for each symbol
• Calculate average code length
7. Minimum Spanning Tree / In-Degree & Out-Degree
Option A – Prim’s Algorithm
Apply MST algorithm to the given weighted graph, showing all steps.
Option B – Indegree & Outdegree Program in C
Given adjacency matrix → compute in-degree and out-degree for all vertices.
Purpose of This Examination
The paper ensures the student’s ability to:
Understand and analyze algorithm complexity
Perform stack/queue/linked list/tree/graph operations
Solve problems using hashing, sorting, and searching
Implement algorithms in C
Apply mathematical analysis to arrays, trees, and graphs
Reason about efficiency and correctness of solutions
This exam builds a strong foundation for advanced courses such as Algorithms, Operating Systems, Compiler Design, and Database Systems.