(SEM IV) THEORY EXAMINATION 2022-23 BASIC DATA STRUCTURE & ALGORITHMS

This “What Description” explains what the question paper contains, what each section demands, and how students are expected to answer.
It is written in a formal exam-style explanation, easy to understand and detailed.

WHAT DESCRIPTION – COMPLETE DETAILED EXPLANATION

1. About the Question Paper

This question paper is based on Data Structures and Algorithms (DSA).
It is divided into three major sections – A, B and C, along with additional internal choices.
The paper tests both conceptual understanding and problem-solving skills, such as algorithms, data structures, graph theory, sorting techniques, trees, hashing, recursion, etc.

The total marks are 100, and the duration is 3 hours, so students must manage time efficiently.

2. Section A – Short, Conceptual Questions

Section A contains 10 short questions, each requiring a brief yet clear explanation.
Each question is of 2 marks, covering fundamental concepts of DSA.

The topics include:

● Complexity Analysis

Students must explain time and space complexity, comparing efficiency of algorithms.

● Queue Conditions

Syntax to check full or empty circular queue using front and rear indices.

● Expression Tree

Drawing a binary tree for a given arithmetic expression.

● Data Structure Advantages

Advantages of linked list over array, such as dynamic memory allocation, efficient insertion/deletion, etc.

● Transitive Closure

Definition of reachability in graphs using adjacency matrix.

● Sorting Algorithm

Writing bubble sort algorithm and its time complexity.

● Applications of Linked List

Practical uses: stacks, queues, memory management, polynomial representation, etc.

● BFS Algorithm

Algorithm for Breadth First Search using queue.

● Types of Sorting

Difference between internal and external sorting based on memory usage.

● Recursion

Data structure used for recursion: Stack.

This section checks whether the student is strongly familiar with basic DSA terminology.

3. Section B – Long, Analytical Questions

This section contains five questions, out of which any three must be answered.
Each question carries 10 marks, requiring detailed explanation, steps, working, or algorithm.

Topics include:

● Multi-dimensional Array Calculation

Finding:                                                    Dimension lengths

Total number of elements                        Address calculation formula (row-major order)

Students must compute address of a specific element in memory.

● Stack Definition & C Program

Explaining stack concept and writing array-based implementation (push, pop, display).

● Insertion Sort

Writing algorithm and sorting a given list step by step.

● Dijkstra’s Algorithm

Finding shortest path in weighted graph with example.

● Huffman Coding

Constructing a Huffman tree, assigning codes, and writing binary code for the word AHEAD.

This section focuses on computation, algorithm tracing, and understanding of core data structures.

4. Section C – Application-Based Questions

Student must attempt one question from each part.

Part 3 – Linked List Applications

Questions include:                                              Representing polynomials using linked lists

C-program to add two polynomials      OR        Algorithm to insert a node after a given node in a singly linked list

It checks student’s ability to use pointers and dynamic memory in practical problems.

5. Part 4 – Expression Conversion OR Queues

Choice between:

● Infix to Postfix Conversion

Students must:            Write algorithm

Trace the conversion of the given complex expression into postfix form

OR

● Short Notes

Priority queue             Circular queue

This evaluates understanding of different queue structures.

6. Part 5 – Hashing or Quick Sort

Students must answer either:

● Hashing Methods

Explain:             Mid-square method            Digit-folding method
with examples.

OR

● Quick Sort

Write algorithm and trace the given sequence.

This section checks algorithm design and problem execution capability.

7. Part 6 – Spanning Trees or All-Pairs Shortest Path

Students choose between:

● Minimum Spanning Tree

Explanation + Kruskal’s algorithm on the given graph.

OR

● Floyd–Warshall Algorithm

Use it to compute all-pairs shortest paths.

This section focuses on graph algorithms and optimization techniques.

8. Part 7 – Tree Structures

Choice between:

● B-Tree Construction

Explain:                     Definition                                 Properties

Insert the given sequence in a B-tree of a specific order

OR

● Short Notes

Internal & external sorting

B+ tree

This part checks understanding of advanced tree data structures.

FINAL SUMMARY (WHAT THIS DESCRIPTION MEANS)

This “What Description” clearly explains:

What the question paper consists of

What each section demands

What concepts are being tested

What type of answers are expected

Which algorithms and data structures the student must know

It is designed to help students understand the structure, purpose, and requirements of the exam in a complete and descriptive manner.