(SEM III) THEORY EXAMINATION 2021-22 BASIC DATA STRUCTURE AND ALGORITHMS

This question paper belongs to the B.Tech (Semester III) course titled Basic Data Structures and Algorithms (Subject Code: KOE035). The paper is structured to thoroughly evaluate a student’s understanding of the fundamental concepts, logical reasoning, implementation skills, and analytical abilities required in Data Structures & Algorithms (DSA). The questions cover the entire syllabus in a balanced and comprehensive manner, ensuring that students are tested on both theory and practical application.

The paper is divided into three main sections: A, B, and C, each containing different types of questions — from short conceptual queries to full-length algorithmic explanations and coding implementations.

SECTION A – Short Answer Questions (20 Marks)

This section consists of ten brief questions, each designed to test basic understanding and definitions. Topics include:

Asymptotic notation and Big-O, used in analyzing time complexity.

Applications of sparse matrices in memory-efficient storage.

Conditions for a circular queue being full.

Advantages of circular linked lists over simple linked lists.

Difference between internal and external sorting with examples like Quick Sort and Merge Sort.

Tree vs graph concepts and structural differences.

Maximum number of nodes in a binary tree of height h.

Difference between Polish notation and Reverse Polish notation.

Advantages of B+ Trees in indexing, particularly in databases.

Pivot selection strategies for Quick Sort.

These questions check conceptual clarity, textbook definitions, and quick recall skills.

SECTION B – Descriptive / Analytical Questions (30 Marks)

Students must attempt any three out of five questions. These involve explanation, algorithm writing, and logical reasoning:

Static vs dynamic memory allocation with practical differences.

Algorithm to evaluate a postfix expression using a stack.

Deletion operation in a Binary Search Tree, along with an example of all three cases.

Dijkstra’s Algorithm explained step-by-step with a proper weighted graph.

Justification of why binary search is more efficient than linear search in terms of time complexity and search behaviour.

This section tests a student’s ability to explain concepts, write algorithms, and apply knowledge to solve logical problems.

SECTION C – Problem Solving & Programming (20 Marks)

Students must choose one part from two separate long questions. This section focuses on applying DSA knowledge in practical programming scenarios.

Question 3

Finding the memory location of a 2-D array element in both row-major and column-major order based on given base address and storage size.

OR

Writing a C program to reverse a singly linked list.

Question 4

Converting a complex infix expression to postfix using stack operations.

OR

Writing a C program to implement a queue with enqueue and dequeue operations.

These questions check a student's ability to perform computations, write C code, and work with stack/array addressing.

Higher-Order Questions – DSA Application & Algorithm Construction (30 Marks)

Question 5 – Binary Tree / B-Tree

Students need to either:

Construct a binary tree using given In-order and Post-order traversals and write the algorithm for In-order traversal.

OR

Build a B-Tree of order 5 step-by-step for a long sequence of keys.

Question 6 – Graphs / MST

Choice between:

Explaining Breadth-First Search (BFS) algorithm with an example graph.

OR

Explaining Minimum Cost Spanning Tree and demonstrating Kruskal’s Algorithm.

Question 7 – Quick Sort / Short Notes

Students must either:

Write the algorithm for Quick Sort and apply it to sort a sequence of ten numbers.

OR

Write short notes on Priority Queue and Threaded Binary Tree.

These questions focus on higher-order thinking, stepwise algorithm design, and complex DSA operations. They check how well a student can construct, trace, and explain algorithms programmatically.

Overall Summary

This 100-mark question paper is carefully designed to measure a student’s understanding of:

Core data structures (arrays, linked lists, queues, trees, graphs)

Searching and sorting techniques

Algorithm design and analysis

Memory allocation and addressing

Tree and graph traversal methods

Stack-based expression evaluation

Practical implementation using C language

Higher-order topics like B-Trees, BST operations, Dijkstra’s algorithm, and Minimum Spanning Trees

The paper ensures that students are well-prepared for advanced subjects like algorithms, operating systems, compiler design, and database management systems.