(SEM III) THEORY EXAMINATION 2023-24 DATA STRUCTURE

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.