DATA STRUCTURE – B.Tech (Semester IV), RCS-405
This is a 3-hour, 70-mark theory examination designed to assess a student’s fundamentals and applied understanding of data structures, including stacks, queues, trees, graphs, hashing, recursion, linked lists, and algorithmic reasoning.
The paper is divided into three sections, testing conceptual clarity, medium-length analytical answers, and complete programming/algorithmic questions.
SECTION A — Short Conceptual Questions (2 × 7 = 14 Marks)
This section contains 7 brief questions designed to test quick recall and basic understanding.
Topics include:
Queue operations – minimum enqueue/dequeue operations
Structure of BST and threaded binary tree Activity network (definition + example)
Minimum nodes in AVL tree of height 8 Recursive C program for multiplication
Priority queue – definition Transitive closure
These questions cover theoretical concepts, definitions, and small computations/programs.
SECTION B — Descriptive / Medium-Length Questions (7 × 3 = 21 Marks)
Attempt any 3 out of 5 questions.
Topics include:
(a) Address Calculation — Row & Column Major
A 2D array DSUC[50][60] stored in row-major order
Address calculation for DSUC[34][56] given base of DSUC[12][34]
(b) Short notes on:
Activity network
Garbage collection & compaction
(c) Stack –
Definition + example
Reverse a string using stack in C
Push/pop function implementation
(d) Convert infix → postfix:
(a + b^c^d) * (e + f/d)
(e) Hashing –
Any three hash functions with examples
Insert keys 37, 38, 72, 48, 98, 11, 56 using H(key) = key % 7 with linear probing
Location of key 11
Total collisions
This section checks problem-solving, C programming, stack/queue logic, hashing, and array memory mapping.
SECTION C — Long / Analytical Questions (7 marks each)
Each question contains choice (a or b) and tests deep understanding, diagrammatic representation, and algorithm writing.
Q3 – Linked Lists / Infix to Postfix
Advantages of linked lists over arrays
Implement doubly circular linked list + insert at given position
OR
Convert infix to postfix for:
a + b × c - d ^ e ^ f
Q4 – Huffman Coding / Floyd–Warshall
Build Huffman tree for given frequencies
Decode a long bitstream
Calculate average bits/message
OR
Write Floyd–Warshall algorithm + example
Q5 – Binary Tree Operations / Prim’s Algorithm
Write C functions:
Count total nodes
Compute height of binary tree
OR
Prim’s Algorithm + find MST for given graph
Q6 – Tree Construction / Binary Search
Construct binary tree from preorder & inorder sequences
Draw neatly
OR
Explain Binary Search, complexity, and C implementation
Q7 – DFS / Expression Tree
Data structure used for DFS
DFS algorithm + traverse given graph from node A
OR
Expression tree for:
(−b+√(b2–4ac))/2a( -b + √(b^2 – 4ac) ) / 2a(−b+√(b2–4ac))/2a
Provide preorder/inorder/postorder traversals
This section evaluates tree construction, linked lists, graph traversal, dynamic structures, and classical algorithms.
OVERALL PURPOSE OF THE EXAM
The question paper tests whether the student can:
Understand and apply classical data structures
Write and analyze C programs involving recursion, stacks, queues, trees
Perform address calculations for multidimensional arrays
Work with hashing and collision resolution
Convert expressions (infix ↔ postfix)
Construct trees, perform traversals
Use algorithms like DFS, Floyd-Warshall, Prim’s
Implement linked lists and use them for dynamic data management
It focuses heavily on problem-solving, implementation, and deep conceptual understanding essential for advanced computer science.
