This document contains the complete B.Tech Semester III – Theory Examination 2017–18 question paper for the subject Data Structures (RCS-305). It consists of 2 printed pages, carries 70 marks, and evaluates a student’s understanding of core data structure concepts, algorithms, complexity analysis, and tree/graph operations.
Section A — Short Theoretical Questions (14 Marks)
Section A contains basic conceptual questions designed to test fundamental knowledge. The questions include:
Definition of Data Structure, and examples of linear and non-linear structures with applications
Understanding of successor and predecessor in Binary Search Trees
Converting an infix expression to postfix
Explanation of circular queue and its overflow condition
Number of moves in Tower of Hanoi for n = 10
Types of graph representations
Concept of height-balanced trees and rebalancing cases
These questions test the student’s clarity on essential data structure concepts and their real-world relevance.
Section B — Descriptive & Analytical Questions (21 Marks)
In Section B, students must attempt any three out of five questions. These require deeper understanding, algorithmic thinking, and problem-solving:
Explanation of time-space trade-off with best, worst, and average-case analysis
Sorting a list using Quick Sort and analyzing its stability
Constructing a Minimum Spanning Tree using Prim’s Algorithm
Definitions of tree, binary tree, complete binary tree, and full binary tree, with traversal algorithms (inorder, preorder, postorder)
Construction of a B-tree (order 3) for a given sequence of inputs
These questions assess the student’s ability to implement algorithms, analyze complexity, and design trees/graphs.
Section C — Advanced Data Structure Problems (28 Marks)
Section C contains several long-answer questions. Students must attempt one part from each question group. Topics include:
1. Algorithm Analysis & Linked Lists
Asymptotic notations with emphasis on Big-O
Algorithm to insert a node at the end of a circular linked list
2. Stacks & Recursion
C program to reverse a string using a stack
Recursive and non-recursive programs for factorial
3. Trees & AVL Rotations
Drawing a binary tree from given traversals
Inserting new nodes into an AVL tree with proper rotations
4. Threaded Binary Trees & Algorithms
Concept and advantages of Threaded Binary Trees
Dijkstra’s Algorithm for shortest path with step-by-step working
5. Hashing & Sorting
Short notes on Hashing Techniques and Garbage Collection
Explanation of Heap Sort and Radix Sort
These questions measure a student's depth of understanding, algorithmic logic, implementation skills, and capability to handle complex data structure operations.
Summary
This exam paper comprehensively evaluates key areas of Data Structures including:
Time & space complexity
Searching & sorting algorithms
Stacks, queues, linked lists
Trees: BST, AVL, B-tree, threaded tree
Graphs & shortest path algorithms
Hashing and storage mechanisms
It integrates theory with practical implementation, making it an essential academic resource for understanding core concepts of data structures.
