DATA STRUCTURE & ALGORITHMS – B.Tech (Semester IV), RCS-406
This is a 3-hour, 70-mark theory examination designed to evaluate a student's understanding of abstract data types, stacks, queues, trees, graphs, recursion, hashing, searching, sorting, and algorithmic design/analysis.
The paper is divided into three sections, containing conceptual questions, medium-length problems, and full analytical/programming questions.
SECTION A — Short Answer / Conceptual Questions (2 × 7 = 14 Marks)
This section contains 7 brief questions to test basic theoretical understanding.
Topics include:
Abstract Data Type (ADT) Internal vs external sorting + examples
Recursive C program for multiplication Priority queue definition
Threaded binary tree (definition + advantage) Transitive closure
Insertion function for circular queue
These questions assess definitions, differences, basic operations, and small programs.
SECTION B — Descriptive / Medium-Length Questions (7 × 3 = 21 Marks)
Attempt any 3 out of 5.
This section includes derivations, algorithms, C programs, and numerical hashing examples.
Topics include:
(a) Lower Triangular Matrix (LTM) –
Derive formulas for row-major and column-major address calculation.
(b) Tower of Hanoi –
Recursive algorithm
Total number of function calls for n disks
(c) Stack –
Define stack, reverse a string using stack, push & pop implementation in C.
(d) Convert infix → postfix for the expression:
(a + b^c^d) * (e + f/d)
(e) Hashing –
Explain three hash functions
Perform linear probing with H(key) = key % 7
Insert: 37, 38, 72, 48, 98, 11, 56
Determine location of key 11
Count total collisions
This section tests algorithmic understanding + implementation skills.
SECTION C — Long/Analytical/Programming Questions (7 marks each)
Each question offers choice (a or b) and requires deep explanation, design, or full program.
Q3 – Linked Lists & Expression Conversion
Advantages of linked lists over arrays
Implement doubly circular linked list & insert at a given position
OR
Postfix conversion of:
a + b × c - d ^ e ^ f
Q4 – Huffman Coding / Floyd–Warshall
Construct Huffman tree for given symbols & decode bitstream, find average bits/message
OR
Floyd–Warshall algorithm + example
Q5 – Binary Tree Operations / Prim’s Algorithm
C functions to count total nodes & compute height of binary tree
OR
Prim’s algorithm + find Minimum Spanning Tree (graph provided)
Q6 – Tree Construction / Binary Search
Construct binary tree from given preorder & inorder sequences
OR
Explain binary search, time complexity, and C implementation
Q7 – DFS / Expression Tree
Data structure for DFS, DFS algorithm, traverse given graph
OR
Construct expression tree for (−b+b2−4ac)/2a(-b + \sqrt{b^2 - 4ac}) / 2a(−b+b2−4ac)/2a
Give pre-order, in-order, post-order traversals
This section checks tree construction, graph traversal, MST, expression evaluation, recursion-based logic, and binary tree properties.
OVERALL PURPOSE OF THE EXAM
This examination evaluates a student's ability to:
Understand abstract data types & core DSA concepts
Implement stacks, queues, linked lists, trees & graphs
Apply recursion to real problems (Hanoi, multiplication, traversals)
Perform hashing, collision handling & address calculations
Translate infix ↔ postfix expressions
Construct trees & perform traversals
Apply shortest path, MST, DFS algorithms
Understand searching and sorting fundamentals
The paper combines theory, algorithms, programs, and mathematical derivations, building strong foundations for advanced computer science subjects.
