(SEM IV) THEORY EXAMINATION 2017-18 DATA STRUCTURE

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.