(SEM III) THEORY EXAMINATION 2019-20 DATA STRUCTURES

This document is the B.Tech Semester III (2019–20) Theory Examination question paper for DATA STRUCTURES (KCS301) under Dr. A.P.J. Abdul Kalam Technical University (AKTU).
The exam duration is 3 hours, carries 100 marks, and the question paper is divided into three sections only — SECTION A, SECTION B, and SECTION C.
The uploaded file contains two pages, each clearly showing questions, marks, and CO (Course Outcome) mapping.

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

Section A contains ten 2-mark questions, each checking quick conceptual understanding of core data structure topics.

The questions include:

Representing a sparse matrix in memory

Listing operations on linked lists

Applications of stack

Meaning of tail recursion

Defining priority queue and giving one application

Working of bubble sort

Explaining minimum cost spanning tree

Difference between adjacency matrix and adjacency list

Defining:

Extended binary tree

Full binary tree

Strictly binary tree

Complete binary tree

Meaning of threaded binary tree

All questions are arranged in a table format on Page 1, with each carrying 2 marks.

SECTION B — Descriptive Questions (Attempt Any 3 × 10 = 30 Marks)

(Page 1, lower section)

Section B contains five long questions, out of which students must attempt any three.

These questions cover:

Differences between iteration and recursion + recursive Tower of Hanoi

Array & linked representation of queue + meaning of dequeue

Warshall’s algorithm (with example)

Dijkstra’s algorithm for shortest path (with graph)

Determining the shortest path in a weighted graph

These questions require detailed explanation, writing algorithms, and applying graph algorithms.

SECTION C — Applied/Numerical/Theory (Q3–Q6, Each 1 × 10 Marks)

(Page 2 of the document)

Section C contains four groups of questions, numbered Q3 to Q6, and for each group the student must attempt one part (a or b).

Q3 — Linked List / Complexity & Notation

Doubly linked list definition, applications, and deletion of an element using C
OR

Short notes on:

Time complexity

Space complexity

Asymptotic notation

Big-O notation

Q4 — Recursion / Queue Representation

Difference between iteration and recursion + Tower of Hanoi recursive solution
OR

Array and linked representation of queue, and dequeue definition

Q5 — Sorting / Hashing

Why quicksort is called "quick"? Steps of quicksort for given numbers:
{25, 57, 48, 37, 12, 92, 86, 33}
(with first element as pivot)
OR

What is hashing? Characteristics of a hash function + collision-resolution techniques

Q6 — Graph Algorithms

Warshall’s algorithm with example
OR

Dijkstra’s algorithm for shortest path from vertex ‘S’

These questions focus on practical implementation and algorithmic understanding.

OVERALL SUMMARY OF THE DOCUMENT

The uploaded Data Structures (KCS301) question paper evaluates a student's understanding of:

Linear & non-linear data structures

Linked lists, stacks, queues

Trees and binary tree types

Graph representations

Sorting algorithms (especially quicksort)

Hashing & collision handling

Complexity analysis

Recursion and Tower of Hanoi

Graph algorithms (Warshall, Dijkstra)

Sparse matrices, spanning trees, priority queues

The structure follows the standard AKTU pattern:

SECTION A: Short conceptual recall

SECTION B: Medium-length descriptive questions

SECTION C: Applied, algorithmic, and numerical questions

The entire paper appears clearly on two pages in a tabular and well-structured format.