(SEM IV) THEORY EXAMINATION 2017-18 DATA STRUCTURE & ALGORITHMS

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.