(SEM III) THEORY EXAMINATION 2021-22 DATA STRUCTURE

This question paper belongs to B.Tech (Semester III) for the subject Data Structure (KCS301). It is a 100-mark, 3-hour examination designed to assess a student's understanding of fundamental and advanced topics in data structures. The entire paper is divided into three sections—A, B, and C—each testing different cognitive levels: basic recall, analytical thinking, and applied problem-solving.

SECTION A – Short Conceptual Questions (20 Marks)

Section A contains 10 short questions, each carrying 2 marks, covering core concepts of data structures.

Topics include:

Converting infix to postfix expressions

Ranking time complexities

Constructing a binary search tree from given insertions

Understanding recursive functions and their output

Sparse matrix definition and efficient representation

Advantages of doubly linked lists

Stable vs unstable sorting techniques

AVL tree advantages over BST

Tail recursion with example

Memory representations of graphs

This section checks fundamentals, definitions, properties, and quick conceptual applications.
 

SECTION B – Analytical & Algorithmic Questions (30 Marks)

Students must attempt any 3 out of 5, each of 10 marks.

Topics include:

Advantages & disadvantages of linked lists vs arrays

Writing C function to create a new list from alternate nodes

Insertion sort algorithm, dry-run and time-complexity

DFS vs BFS and constructing BFS tree

Linear vs binary search, writing recursive binary search

Maintaining threads in a threaded BST and insertion algorithm

This section evaluates the student's ability to differentiate, write algorithms, analyze operations, and apply concepts to specific cases.

 SECTION C – Long Answer & Problem-Solving (50 Marks)

This section contains 5 main questions, each with two alternatives, and students must attempt one part from each question (5 × 10 = 50 marks).

Q3 – Arrays / Polynomial Using Linked List

Students must either:

Compute size and explain row-major & column-major order for a 3D array

Or represent polynomials using linked lists and write C functions to add them

Q4 – Sorting / Hashing

Apply merge sort & quick sort with full step-wise execution

Or perform hashing with open addressing & differentiate probing techniques

Q5 – Dijkstra & Prim

Students must solve:

Dijkstra’s shortest path from a given graph

Or Prim’s Minimum Spanning Tree for the given weighted graph
(Both graphs shown visually on Page 2: 

Q6 – BST / Recursion

Write iterative BST search + disadvantages of recursion

Or write recursive + non-recursive factorial programs

Q7 – B-Tree / Stacks

Construct a full B-Tree of order 5 with many insertions + deletions

Or design 2 stacks in one array + reverse a string using a stack

This section tests deep understanding of data structures, algorithmic thinking, C programming, tree construction, searching, sorting, hashing, and graph algorithms.

 Overall Summary

The Data Structure (KCS301) question paper is a complete syllabus-coverage exam including:

Expression conversion

Complexity analysis

Trees (BST, AVL, Threaded BST, B-Tree)

Searching & sorting

Linked lists (single, double, polynomial)

Graph algorithms (DFS, BFS, Dijkstra, Prim)

Hashing

Recursion & memory layouts

It evaluates both theoretical clarity and practical implementation skills, essential for understanding advanced algorithmic subjects in later semesters.