(SEM III) THEORY EXAMINATION 2024-25 BASICS DATA STRUCTURE & ALGORITHMS

BASICS OF DATA STRUCTURE & ALGORITHMS (BOE306)

Time: 3 Hours | Maximum Marks: 70

This question paper comprehensively assesses a student’s knowledge and practical understanding of data structures, algorithmic techniques, memory organization, recursion, sorting methods, tree traversal, and graph-based computations. The design of the paper ensures a balanced evaluation of theoretical clarity, programming ability, analytical reasoning, and problem-solving skills. The paper is divided into three sections, each targeting a different level of understanding.

SECTION A – Short Answer Questions (14 Marks)

This section examines foundational knowledge related to basic definitions, key concepts, and introductory data structure operations. Students must answer all seven questions, each requiring concise yet conceptually accurate responses.

The questions cover:

Meaning, purpose, and necessity of data structures

Difference between static and dynamic memory allocation

Fundamental concepts of Stack (LIFO)

Working principle of Queue (FIFO)

Role of recursion and its relationship with the system stack

Properties of Minimum Spanning Tree (MST)

Conceptual differences between a Tree and a Graph

This section tests the student's basic conceptual clarity.

SECTION B – Algorithmic & Programming Questions (21 Marks)

Students must attempt any three questions. This section evaluates practical skills—designing algorithms, writing C programs, and performing step-wise execution of logic.

Topics included:

• Singly Linked List Insertion

Algorithm/program to insert nodes at the beginning using pointer manipulation.

• Fibonacci Series (Recursive & Non-Recursive)

Comparison of recursion vs iteration through C implementation.

• Stack Using Linked List

Dynamic implementation of push/pop operations.

• Quick Sort Algorithm + Full Tracing

Divide-and-conquer partitioning, pivot strategy, and sorting given numbers.

• Dijkstra’s Algorithm

Detailed shortest path computation from source 'S' to all vertices.

This section measures the student's ability to write algorithms, trace programs, and apply data structures to solve computational problems.

SECTION C – Long Descriptive / Analytical Questions (35 Marks)

This section contains five sub-sections, and the student must attempt one question from each subsection. These questions involve deeper analysis, computation, and complete algorithmic demonstration.

C1 – Arrays & Complexity

Option A: Address calculation in Row-Major order (2D array indexing formula).
Option B: Explanation of Asymptotic Notations with examples (O, Ω, Θ, o, ω).

C2 – Expressions & Queues

Option A: Complete algorithm for Infix → Postfix conversion with traced example.
Option B: Enqueue(x) algorithm using Linked List implementation.

C3 – Circular Queue & Heap Sort

Option A: Circular queue insertion logic with circular indexing.
Option B: Heap Sort algorithm and stepwise sorting of the given sequence.

C4 – Recursion & Tower of Hanoi

Option A: Concept + recursive algorithm of Tower of Hanoi.
Option B: Explanation of Tail Recursion + factorial algorithm using recursion.

C5 – Trees & Graph Algorithms

Option A: Construction of a Binary Tree from Inorder & Postorder traversals + Preorder result.
Option B: Concept of Spanning Tree, Prim’s algorithm, and solving the MST for the given graph.

Overall Purpose of the Question Paper

This examination is designed to ensure that students:

Grasp the fundamentals of data representation and manipulation

Understand and apply commonly used data structures (arrays, linked lists, stacks, queues, trees, graphs)

Develop skills to write and analyze efficient algorithms

Solve computational problems involving sorting, searching, path-finding

Perform recursion, tree traversal, and graph-based computations

Clearly understand memory organization, notation, and complexity

Gain practical experience in tracing, debugging, and designing algorithms

The paper integrates both theoretical and practical components, aligning with the learning outcomes expected at the B.Tech (CS/IT) level.