(SEM III) THEORY EXAMINATION 2017-18 DATA STRUCTURES

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.