THEORY EXAMINATION (SEM–IV) 2016-17 DATA STRUCTURE

Subject: Data Structure (NEC401)

Exam Type: Theory
Semester: IV (4th Semester)
Time: 3 Hours
Maximum Marks: 100

Section A — Short Answer Questions (10 × 2 = 20 Marks)

This section focuses on fundamental concepts, basic operations, and definitions related to data structures

Topics covered include:

Address calculation in a 2D array (row-major order)       

Static vs. dynamic memory allocation

Advantages of doubly linked lists over singly linked lists

Recursion: its definition and properties (base case & recursive case)

Tree definitions: tree, level, and height of a node

Applications of queues (e.g., job scheduling, CPU task management)

Garbage collection and compaction

Sparse matrix: definition and storage method

Difference between linear and non-linear data structures

Adjacency matrix: definition and example

Section B — Descriptive / Algorithmic Questions (5 × 10 = 50 Marks)

This section includes algorithmic and implementation-based problems focusing on searching, sorting, graph traversal, and recursion

Key questions include:

Breadth-First Search (BFS) with example

Kruskal’s Algorithm for minimum spanning tree (MST) — with discussion on multiple MSTs

Converting postfix expressions to infix and prefix using a stack

Towers of Hanoi — recursive algorithm and explanation

Linked List implementation of stack in C — with all primitive operations

Merge Sort — perform sorting on {18, 25, 4, 26, 10, 15, 20, 5} and explain algorithm

Circular Queue: implementation with algorithms for all operations (enqueue, dequeue, display, etc.)

Binary Search Tree (BST): explanation, insertion, and tree formation for the sequence
{45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10}

Section C — Analytical / Long Questions (2 × 15 = 30 Marks)

This section includes complex problems and detailed explanations of tree structures and sorting techniques

Questions include:

Binary Tree Construction:                              Using given traversals —

Inorder: D J G B A E H C F I                               Preorder: A B D G J C E H F I

Draw the corresponding binary tree.                Explain threaded binary tree with an example.

Doubly Linked List:

Define and write a C program to create one.    Explain internal sorting techniques.

Short Notes (any three):                                 Huffman Algorithm (data compression)

Depth First Search (DFS)                                 Priority Queue

Abstract Data Type (ADT)

Major Topics Covered

Arrays and memory representation                    Linked lists (singly, doubly, circular)

Stack and queue operations                               Trees and binary trees

Sorting and searching algorithms (merge sort, binary search, etc.)

Graph algorithms (BFS, DFS, Kruskal’s)                Recursion and algorithm design

Memory management (garbage collection)

Purpose of the Paper

This exam evaluates your understanding of data structures and algorithm design, focusing on how data is stored, processed, and organized efficiently.
It combines theory, logic, and practical coding concepts — making it crucial for understanding core programming and algorithm fundamentals.