DATA STRUCTURES

[Link] (CSE, AI&ML) II Year I Sem (R22)

COURSE FILE

Department of Computer Science and Engineering

AURORA’S SCIENTIFIC AND TECHNOLOGICAL INSTITUTE

Aushapur, Ghatkesar, Hyderabad
 Aurora’s Scientific and Technological Institute

CONTENTS
[Link] Particulars Page No

1 Course Details 2

2 Course Introduction 3

3 Course Objectives 4

4 Course Outcomes 4

5 CO – PO/ PSO Mapping Matrix 4

6 Syllabus 5

7 Text Books & References 6

8 Session Plan 7

9 Lecture Notes/ Slides 9

10 Question Bank for Mid-Term Examinations 10

11 Question Bank for External Examination 25

12 Assignments 26

13 Seminars 28

1
 Aurora’s Scientific and Technological Institute

1. Course Details:
1 Course Code CS302PC
2 Course Title Data Structures
3 Course Abbreviation DS
4 Credits 3 (L:3-T:0-P:0)
5 Regulation R22
6 Academic Year 2025-26
7 Programme [Link]
8 Specialisation Computer Science and Engineering
9 Year – Semester II Year – I Semester
10 Course File Prepared by [Link] Kumar, Associate Professor, Department of CSE

2
 Aurora’s Scientific and Technological Institute

2. Course Introduction
The course Data Structures is designed to provide students with a comprehensive understanding of how
data can be organized, managed, and processed efficiently in computer memory. It builds upon the
foundational programming concepts learned in Programming for Problem Solving and introduces the
essential principles and techniques for designing efficient algorithms and data management solutions.

Students begin by exploring the concept of abstract data types (ADTs) and learning how different data
structures—such as lists, stacks, and queues—support efficient data manipulation and retrieval. They
study the underlying representations of these structures using arrays and linked lists, along with various
operations like insertion, deletion, and searching.

The course then advances to dictionaries and hashing techniques, which enable rapid data access and
storage. Students learn different hashing strategies and collision resolution mechanisms, such as linear
probing, chaining, and double hashing, which are fundamental to the implementation of efficient search
systems.

In subsequent units, the course delves into tree and graph data structures, which form the backbone of
many modern computing applications. Students study binary search trees, AVL trees, B-trees, and red-
black trees to understand how hierarchical data is maintained, balanced, and traversed efficiently. The
module on graphs introduces representation methods and traversal algorithms, enabling learners to model
and solve real-world problems such as network routing and dependency analysis.

Additionally, the course covers sorting algorithms like quick sort, heap sort, and merge sort, focusing on
both internal and external sorting techniques to handle large datasets. The final unit introduces pattern
matching and trie structures, emphasizing efficient text processing, searching, and data compression
techniques used in applications such as compilers, search engines, and bioinformatics.

Through a combination of theoretical concepts and practical implementation, students gain hands-on
experience in designing and implementing data structures using the C programming language. The
practical sessions reinforce analytical thinking, problem-solving, and coding proficiency.

Aligned with the Outcome-Based Education (OBE) framework, this course forms a crucial bridge
between basic programming and advanced topics such as Algorithms, Database Systems, and Software
Engineering. By mastering data structures, students develop the foundation required to design scalable,
optimized, and maintainable software solutions.

By the end of this course, students will be able to:

 Analyse computational problems and identify suitable data structures for their efficient resolution.
 Implement various linear and non-linear data structures using C.
 Apply data structure concepts to solve real-world problems efficiently.
 Evaluate and compare algorithmic efficiency and storage management techniques.

Key Highlights:
 Builds strong conceptual and practical understanding of linear and non-linear data structures.
 Emphasizes efficiency, optimization, and algorithmic design principles.
 Integrates hands-on programming exercises for each data structure.
 Strengthens the ability to select appropriate data structures for given problems.
 Prepares students for advanced courses in Algorithms, Database Systems, and Software Design.
3
 Aurora’s Scientific and Technological Institute

3. Course Objectives:
1. Exploring basic data structures such as stacks and queues.
2. Introduces a variety of data structures such as hash tables, search trees, tries, heaps, graphs.
3. Introduces sorting and pattern matching algorithms.

4. Course Outcomes (COs):

CO Bloom’s Mapped POs/
Statement
No. Level PSOs
Explain the basic concepts of data structures and PO1, PO2, PO3, PO4,
CO1 implement linear data structures such as lists, stacks, and L1, L2, L3 PO5, PO10, PO11,
queues. PO12, PSO1, PSO2
Apply hashing and dictionary techniques for efficient data PO1, PO2, PO3, PO4,
CO2 storage and retrieval. L3, L4 PO5, PO10, PO11,
PO12, PSO1, PSO2
Implement and analyse tree data structures such as BST, PO1, PO2, PO3, PO4,
CO3 AVL, and B-Trees. L3, L4 PO5, PO10, PO11,
PO12, PSO1, PSO2
Apply graph and sorting algorithms for solving PO1, PO2, PO3, PO4,
CO4 computational problems. L3, L4 PO5, PO10, PO11,
PO12, PSO1, PSO2
Use pattern matching and trie algorithms for string and PO1, PO2, PO3, PO4,
CO5 text processing applications. L3, L5 PO5, PO10, PO11,
PO12, PSO1, PSO2

Programme Outcomes (POs) – [Link] (CSE):

Graduates of the Computer Science and Engineering program will be able to:
PO/ PSO No./ Name Programme Outcome (NBA Graduate Attribute)
Apply the knowledge of mathematics, science, engineering
PO1: Engineering
fundamentals, and an engineering specialization to the solution of
Knowledge
complex engineering problems.
Identify, formulate, review research literature, and analyze complex
PO2: Problem Analysis engineering problems using first principles of mathematics, natural
sciences, and engineering sciences.
Design solutions for complex engineering problems and design system
PO3: Design/ Development of components or processes that meet the specified needs considering
Solutions public health and safety, and cultural, societal, and environmental
factors.
PO4: Conduct Investigations Use research-based knowledge and research methods including design
of of experiments, analysis and interpretation of data, and synthesis of
Complex Problems information to provide valid conclusions.
Create, select, and apply appropriate techniques, resources, and modern
PO5: Modern Tool Usage engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.
Apply reasoning informed by contextual knowledge to assess societal,
PO6: The Engineer and
health, safety, legal, and cultural issues and the consequent
Society
responsibilities relevant to the professional engineering practice.
PO7: Environment and Understand the impact of professional engineering solutions in societal

4
 Aurora’s Scientific and Technological Institute

and environmental contexts and demonstrate the knowledge of and need

Sustainability
for sustainable development.
Apply ethical principles and commit to professional ethics and
PO8: Ethics
responsibilities and norms of the engineering practice.
PO9: Individual and Team Function effectively as an individual, and as a member or leader in
Work diverse teams, and in multidisciplinary settings.
Communicate effectively on complex engineering activities with the
engineering community and with society at large — such as being able
PO10: Communication
to comprehend and write effective reports and design documentation,
make effective presentations, and give and receive clear instructions.
Demonstrate knowledge and understanding of the engineering and
PO11: Project Management management principles and apply these to one’s own work, as a member
and Finance and leader in a team, to manage projects and in multidisciplinary
environments.
Recognize the need for and have the preparation and ability to engage in
PO12: Life-Long Learning independent and life-long learning in the broadest context of
technological change.
Apply knowledge of computing, programming, and mathematics to
PSO1: Software Design
design, develop, and evaluate software systems and applications that
and Development
meet desired requirements using modern tools and technologies.
Analyze, design, and implement intelligent systems using data analytics,
PSO2: Data Analytics and
artificial intelligence, and machine learning techniques to solve real-
Intelligent Systems
world problems effectively.

Blooms Taxonomy:
Cognitive Skill Key Action Verbs
Leve Typical
Category (Student Learning (for Questions / COs /
l Question Type
Outcome) Assignments)
Recall previously learned Define, List, Name, State,
Objective /
L1 Remember facts, Identify, Label, Recall,
MCQs
terms, and basic concepts. Match
Explain, Describe, Discuss,
Explain ideas or concepts;
Summarize, Interpret, Short Answer /
L2 Understand interpret and summarize
Classify, Conceptual
information.
Distinguish
Program
Use learned knowledge in Apply, Use, Demonstrate,
Writing /
L3 Apply new Compute, Execute,
Application
situations to solve problems. Implement
Problems
Break down information into
Analyze, Compare, Contrast, Analytical
components; examine
L4 Analyze Differentiate, Examine, Questions /
patterns, relationships, or
Categorize, Organize Algorithm Design
causes.
Design
Make judgments based on Evaluate, Justify, Test,
Evaluation /
L5 Evaluate criteria; verify and justify Critique, Validate, Conclude,
Debugging /
solutions. Recommend
Validation
Generate new ideas, combine
Create, Design, Develop, Project / Case
elements, or design
L6 Create Construct, Formulate, Plan, Study / Open
innovative
Generate ended Problem
solutions.
5
 Aurora’s Scientific and Technological Institute

5. CO-PO Mapping Matrix (3-2-1 Scale):

CO \ PO PSO
PO1 PO2 PO3 PO4 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO2
PO/PSO 5 1
CO1 3 3 2 2 2 - - - - 1 1 2 3 2
CO2 3 3 3 2 2 - - - - 1 1 2 3 2
CO3 3 3 3 3 2 - - - - 1 1 2 3 2
CO4 3 3 3 3 3 - - - - 1 1 2 3 3
CO5 3 3 3 3 3 - - - - 1 1 2 3 3
Average 3 3 2.8 2.6 2.4 - - - - 1 1 2 3 2.4
Rounded
3 3 3 3 2 - - - - 1 1 2 3 2
Average
Scale: 3 = Strong, 2 = Moderate, 1 = Low, 0 = None (blank)

6
 Aurora’s Scientific and Technological Institute

6. Syllabus:
Unit Topics Hours
Introduction to Data Structures: Abstract data types, Linear list – singly linked list
implementation, insertion, deletion and searching operations on linear list,
I 12
Stacks: Operations, array and linked representations of stacks, stack applications,
Queues: Operations, array and linked representations.
Dictionaries: linear list representation, skip list representation, operations - insertion,
deletion and searching.
II Hash Table Representation: hash functions, collision resolution-separate chaining, 8
open addressing, linear probing, quadratic probing, double hashing, rehashing,
extendible hashing.
Search Trees: Binary Search Trees, Definition, Implementation, Operations-
Searching, Insertion and Deletion, B- Trees, B+ Trees, AVL Trees, Definition, Height
III 7
of an AVL Tree, Operations – Insertion, Deletion and Searching, Red –Black, Splay
Trees.
Graphs: Graph Implementation Methods. Graph Traversal Methods.
IV Sorting: Quick Sort, Heap Sort, External Sorting- Model for external sorting, Merge 8
Sort.
Pattern Matching and Tries: Pattern matching algorithms-Brute force, the Boyer –
V Moore algorithm, the Knuth-Morris-Pratt algorithm, Standard Tries, Compressed Tries, 10
Suffix tries.
Total Hours: 45

7
 Aurora’s Scientific and Technological Institute

7. Text Books & References:

7.1. Text Books:
1. Fundamentals of Data Structures in C, 2 nd Edition, E. Horowitz, S. Sahni and Susan Anderson Freed,
Universities Press.
2. Data Structures using C – A. [Link], Y. Langsam, and M.J. Augenstein, PHI/Pearson Education.

7.2. References:
1. Data Structures: A Pseudocode Approach with C, 2 nd Edition, R. F. Gilberg and [Link],
Cengage Learning.

7.3. Website References:

1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7. [Link]
8. [Link]
9. [Link]
10. [Link]
11. [Link]
12. [Link]
13. [Link]
14. [Link]
15. [Link]
16. [Link]
17. [Link]
18. [Link]
19. [Link]
20. [Link]
21. [Link]
22. [Link]
23. [Link]
24. [Link]
25. [Link]

8
 Aurora’s Scientific and Technological Institute

8. Session Plan:

Reference
[Link]. Unit Topic / Sub-Topic Teaching Methodology
(Books)
Introduction to Data Structures and
1 I Lecture + PPT + Example Programs TB1, Ch.1
Abstract Data Types
Linear Lists and Singly Linked List
2 I Lecture + PPT + Example Programs TB1, Ch.2
Concepts
3 I Linked List Insertion Operations Lecture + PPT + Example Programs TB1, Ch.3
4 I Linked List Deletion Operations Lecture + PPT + Example Programs TB1, Ch.4
5 I Linked List Searching Operations Lecture + PPT + Example Programs TB1, Ch.5
6 I Stacks - Definition and Operations Lecture + PPT + Example Programs TB1, Ch.6
7 I Stack Implementation using Arrays Lecture + PPT + Example Programs TB1, Ch.7
Stack Implementation using Linked
8 I Lecture + PPT + Example Programs TB1, Ch.8
Lists
9 I Applications of Stacks Lecture + PPT + Example Programs TB1, Ch.9
10 I Queues - Definition and Operations Lecture + PPT + Example Programs TB1, Ch.10
11 I Queue Implementation using Arrays Lecture + PPT + Example Programs TB1, Ch.11
Queue Implementation using Linked
12 I Lecture + PPT + Example Programs TB1, Ch.12
Lists
Dictionaries and Linear List
13 II Lecture + PPT + Example Programs TB1, Ch.1
Representation

14 II Skip List Representation and Operations Lecture + PPT + Example Programs TB1, Ch.2

Hash Table Concepts and Hash

15 II Lecture + PPT + Example Programs TB1, Ch.3
Functions

16 II Collision Resolution - Separate Chaining Lecture + PPT + Example Programs TB1, Ch.4

17 II Open Addressing - Linear Probing Lecture + PPT + Example Programs TB1, Ch.5
18 II Quadratic Probing and Double Hashing Lecture + PPT + Example Programs TB1, Ch.6
19 II Rehashing Techniques Lecture + PPT + Example Programs TB1, Ch.7
20 II Extendible Hashing Lecture + PPT + Example Programs TB1, Ch.8
21 III Binary Search Trees and Operations Lecture + PPT + Example Programs TB2, Ch.1
22 III B-Trees - Definition and Structure Lecture + PPT + Example Programs TB2, Ch.2
23 III B+ Trees - Structure and Applications Lecture + PPT + Example Programs TB2, Ch.3
24 III AVL Trees - Definition and Height Lecture + PPT + Example Programs TB2, Ch.4
25 III AVL Tree Operations - Insertion Lecture + PPT + Example Programs TB2, Ch.5
26 III Red-Black and Splay Trees Concepts Lecture + PPT + Example Programs TB2, Ch.6
27 III Deletion and Searching in Trees Lecture + PPT + Example Programs TB2, Ch.7
28 IV Graph Definitions and Representations Lecture + PPT + Example Programs TB2, Ch.1
29 IV Graph Implementation Techniques Lecture + PPT + Example Programs TB2, Ch.2
30 IV Graph Traversal - BFS and DFS Lecture + PPT + Example Programs TB2, Ch.3
31 IV Applications of Graphs Lecture + PPT + Example Programs TB2, Ch.4
32 IV Sorting - Quick Sort Lecture + PPT + Example Programs TB2, Ch.5

9
 Aurora’s Scientific and Technological Institute

33 IV Heap Sort Lecture + PPT + Example Programs TB2, Ch.6

External Sorting and Merge Sort
34 IV Lecture + PPT + Example Programs TB2, Ch.7
Concepts
35 IV Model for External Sorting Lecture + PPT + Example Programs TB2, Ch.8
36 V Pattern Matching - Introduction Lecture + PPT + Example Programs TB2, Ch.1
37 V Brute Force Algorithm Lecture + PPT + Example Programs TB2, Ch.2
38 V Boyer–Moore Algorithm Lecture + PPT + Example Programs TB2, Ch.3
39 V Knuth–Morris–Pratt Algorithm Lecture + PPT + Example Programs TB2, Ch.4
40 V Introduction to Tries Lecture + PPT + Example Programs TB2, Ch.5
41 V Standard Tries Lecture + PPT + Example Programs TB2, Ch.6
42 V Compressed Tries Lecture + PPT + Example Programs TB2, Ch.7
43 V Suffix Tries Lecture + PPT + Example Programs TB2, Ch.8
44 V Applications of Tries Lecture + PPT + Example Programs TB2, Ch.9
45 V Revision and Practice Problems Lecture + PPT + Example Programs TB2, Ch.10

TB1 – Fundamentals of Data Structures in C, 2nd Edition, E. Horowitz, S. Sahni, Susan Anderson Freed,
Universities Press.
TB2 – Data Structures using C, A. S. Tanenbaum, Y. Langsam, M. J. Augenstein, PHI/Pearson Education.
RB1 – Data Structures: A Pseudocode Approach with C, 2nd Edition, R. F. Gilberg, B. A. Forouzan,
Cengage Learning.

10
 Aurora’s Scientific and Technological Institute

9. Lecture Notes/ Slides:

Lectures Notes/Slides are included at the end of the Course File.

11
 Aurora’s Scientific and Technological Institute

10. Question Bank for Mid-Term Examinations:

The Part A of the mid-term examination shall be Objective/ Quiz Question Paper containing 20
questions with 10 MCQs, 5 Fill in the Blanks and 5 Match the Following Questions and shall be evaluated
for 10 marks. Each question in Part A carries 0.5 marks in the mid-term examination. Mid I shall be
conducted at the middle of the semester with questions from 2.5 units of syllabus and Mid II at the end of
the semester with questions from the remaining 2.5 units of syllabus.

The Part B of the mid-term examination shall be Descriptive Question Paper for 20 marks. The
descriptive paper shall contain 6 questions out of which, the student has to answer 4 questions, each
carrying 5 marks. The questions shall be as follows:

10.1. Unit-I: Part – A – Objective Questions:

Bloom's
[Link]. Type Question CO Answer
Level
What is a data structure?
(A) A programming language
1 MCQ (B) A way of organizing and storing data CO1 L1 B
(C) A type of algorithm
(D) A computer hardware component
Which of the following is NOT a linear data structure?
2 MCQ CO1 L1 D
(A) Array (B) Linked List (C) Stack (D) Tree
In a singly linked list, each node contains:
3 MCQ (A) Only data (B) Data and pointer to next node (C) Data and CO1 L1 B
two pointers (D) Only pointer
What is the time complexity of insertion at the beginning of a
4 MCQ singly linked list? CO1 L2 A
(A) O(1) (B) O(n) (C) O(log n) (D) O(n²)
Which operation is NOT permitted in a stack?
5 MCQ CO1 L2 D
(A) Push (B) Pop (C) Peek (D) Random access
A stack follows which principle?
6 MCQ CO1 L1 B
(A) FIFO (B) LIFO (C) Random (D) Priority based
In which condition does stack overflow occur?
(A) Stack is empty (B) Stack is full and push operation is
7 MCQ CO1 L2 B
attempted (C) Stack has one element (D) Pop operation on
empty stack
What is the output of postfix expression "5 6 2 + * 12 4 / -"?
8 MCQ CO1 L3 B
(A) 30 (B) 37 (C) 40 (D) 45
In a queue, insertion is performed at:
9 MCQ CO1 L1 B
(A) Front (B) Rear (C) Middle (D) Any position
Which of the following uses queue data structure?
10 MCQ (A) Recursion (B) BFS traversal (C) DFS traversal CO1 L2 B
(D) Function calls
What is an Abstract Data Type (ADT)?
(A) A data type with implementation details (B) A mathematical
11 MCQ CO1 L1 B
model with operations (C) A programming construct
(D) A hardware specification
12 MCQ The time complexity of searching an element in an unsorted CO1 L2 C
linked list is:
12
 Aurora’s Scientific and Technological Institute

(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)

Which data structure is best for implementing recursion?
13 MCQ CO1 L2 B
(A) Queue (B) Stack (C) Array (D) Tree
In circular queue, when rear = max-1, the next position of rear
14 MCQ will be: CO1 L2 A
(A) 0 (B) max (C) rear+1 (D) -1
What is the space complexity of a singly linked list with n
15 MCQ nodes? CO1 L1 C
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
Which operation in linked list requires traversing the list?
16 MCQ (A) Insertion at beginning (B) Deletion at beginning CO1 L2 C
(C) Insertion at end (D) Getting first element
The condition for queue empty in array implementation is:
17 MCQ (A) front = rear (B) front = rear = -1 (C) front > rear (D) Both CO1 L2 D
B and C
Which of the following applications uses stack?
18 MCQ (A) CPU scheduling (B) Printer spooling (C) Expression CO1 L2 C
evaluation (D) Breadth-first search
In a linked list, the NULL pointer in the last node indicates:
19 MCQ CO1 L1 B
(A) Beginning of list (B) End of list (C) Empty list (D) Error
What is the advantage of linked list over array?
20 MCQ (A) Random access (B) Dynamic size (C) Cache friendly (D) CO1 L2 B
Less memory usage
Infix expression "A + B * C" in postfix is:
21 MCQ CO1 L3 A
(A) ABC*+ (B) AB+C* (C) ABC+ (D) ABC+
Priority queue is implemented using:
22 MCQ CO1 L2 C
(A) Stack (B) Queue (C) Heap (D) Array
Double-ended queue is called:
23 MCQ (A) Priority queue (B) Circular queue (C) Dequeue (D) Simple CO1 L1 C
queue
The top of the stack is at index 5 and stack size is 10. How many
24 MCQ elements are in stack? CO1 L2 C
(A) 4 (B) 5 (C) 6 (D) 10
Which traversal method is used to visit all nodes in a linked list?
25 MCQ CO1 L1 C
(A) Inorder (B) Preorder (C) Linear traversal (D) Level order
Overflow condition in circular queue is:
26 MCQ (A) (rear+1)%max = front (B) front = rear (C) rear = max-1 CO1 L2 A
(D) front = 0
Which of the following is true about stack?
(A) Elements can be inserted at any position (B) Elements can
27 MCQ CO1 L2 C
be deleted from any position (C) Only top element can be
accessed (D) Random access is allowed
The auxiliary space complexity of converting infix to postfix
28 MCQ using stack is: CO1 L2 C
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
In linked implementation of queue, front and rear are: (A)
29 MCQ CO1 L1 B
Indices (B) Pointers (C) Values (D) Constants
Which operation is most efficient in linked list compared to
array?
30 MCQ CO1 L2 C
(A) Random access (B) Binary search (C) Insertion at
beginning (D) Cache performance
31 Fill A ___________is a collection of nodes where each node CO1 L1 linked list /
13
 Aurora’s Scientific and Technological Institute

singly
contains data and a link to the next node.
linked list
The operation of adding an element to the stack is called
32 Fill CO1 L1 push
________.
The operation of removing an element from a queue is called dequeue /
33 Fill CO1 L1
________. deque
dynamic /
34 Fill A stack that is implemented using linked list has ________ size. CO1 L1
variable
35 Fill In a queue, deletion occurs at ________ end. CO1 L1 front
36 Fill The condition top = -1 indicates that the stack is ________. CO1 L1 empty
37 Fill A data structure that follows FIFO principle is ________. CO1 L1 queue
The process of visiting each node in a linked list is called
38 Fill CO1 L1 traversal
________.
39 Fill In postfix expression, operators come ________ operands. CO1 L1 after
implementa
40 Fill An ADT defines operations without revealing ________ details. CO1 L1
tion
Match the Following:
1. LIFO
2. FIFO
3. Push operation
4. Front pointer
5. Head pointer
6. Postfix
1-b
7. Circular queue
2-a
8. Deque
3-d
9. Peek
4-j
10. Underflow
5-c
41 Match CO1 L2 6-i
Options:
7-h
(a) Queue
8-g
(b) Stack
9-f
(c) Linked list
10-e
(d) Add to stack
(e) Remove from empty structure
(f) View top element
(g) Both ends insertion/deletion
(h) Efficient space utilization
(i) Reverse Polish Notation
(j) Queue starting point

10.2. Unit-I: Part – B – Descriptive Questions:

[Link] Bloom's
Question CO
. Level
1 Define data structure. Explain various types of data structures with examples. CO1 L1
2 Explain the concept of abstract data type (ADT) with examples. CO1 L2
3 Describe array and linked representations of linear lists. CO1 L2

14
 Aurora’s Scientific and Technological Institute

4 Explain insertion and deletion operations in a singly linked list with algorithm. CO1 L3
5 Write an algorithm to search an element in a linked list. CO1 L3
6 Compare arrays and linked lists. CO1 L2
7 Explain stack operations (push, pop, peek) using array representation. CO1 L2
8 Explain linked representation of stacks with an example. CO1 L3
9 Discuss applications of stacks. CO1 L2
10 Write algorithms to convert infix expression to postfix using stack. CO1 L3
11 Explain queue operations (enqueue, dequeue) using array representation. CO1 L2
12 Describe linked representation of queues. CO1 L3
13 Explain circular queue and its advantages. CO1 L2
14 Discuss overflow and underflow conditions in stacks and queues. CO1 L2
15 Write an algorithm to reverse a string using stack. CO1 L3
16 Compare stacks and queues. CO1 L2
17 Explain priority queue and its applications. CO1 L2
18 Write an algorithm for insertion and deletion in a circular linked list. CO1 L3
19 Explain memory allocation and deallocation in linked lists. CO1 L3
20 Summarize the importance of linear data structures in programming. CO1 L2

10.3. Unit-II: Part – A – Objective Questions:

Bloom's
[Link]. Type Question CO Answer
Level
A dictionary is also known as:
1 MCQ CO2 L1 B
(A) Array (B) Map (C) Stack (D) Tree
What is the primary operation supported by dictionaries?
2 MCQ (A) Sorting (B) Key-value pair storage (C) Graph traversal (D) CO2 L1 B
Pattern matching
In a skip list, the bottom level contains:
3 MCQ (A) Few elements (B) All elements (C) Only keys (D) No CO2 L1 B
elements
What is the average time complexity of search in a skip list?
4 MCQ CO2 L2 B
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
A hash function maps: (A) Values to keys (B) Keys to indices
5 MCQ CO2 L1 B
(C) Indices to values (D) Keys to values
Collision in hashing occurs when:
6 MCQ (A) Hash table is full (B) Two keys hash to same index (C) CO2 L1 B
Hash function is null (D) Key is duplicate
Which collision resolution technique uses linked lists?
7 MCQ (A) Linear probing (B) Quadratic probing (C) Separate chaining CO2 L1 C
(D) Double hashing
In linear probing, the probe sequence is:
8 MCQ (A) h(k), h(k)+1, h(k)+2, ... (B) h(k), h(k)+1², h(k)+2², ... CO2 L2 A
(C) h(k), 2h(k), 3h(k), ... (D) Random
15
 Aurora’s Scientific and Technological Institute

The problem of primary clustering occurs in:

9 MCQ (A) Separate chaining (B) Linear probing (C) Double hashing CO2 L2 B
(D) Extendible hashing
In quadratic probing, the i-th probe is at position:
10 MCQ (A) (h(k) + i) mod m (B) (h(k) + i²) mod m (C) (h(k) * i) mod m CO2 L2 B
(D) (h(k) + 2i) mod m
Double hashing uses:
11 MCQ (A) One hash function (B) Two hash functions (C) Three hash CO2 L1 B
functions (D) No hash function
The load factor of a hash table is defined as:
12 MCQ CO2 L1 A
(A) n/m (B) m/n (C) n*m (D) m-n
Rehashing is performed when: (A) Collision occurs (B) Load
13 MCQ factor exceeds threshold (C) Hash table is empty (D) Key is not CO2 L2 B
found
What is the ideal load factor for good hash table performance?
14 MCQ CO2 L2 B
(A) 0.0 - 0.3 (B) 0.5 - 0.7 (C) 0.9 - 1.0 (D) Greater than 1.0
Extendible hashing is used in:
15 MCQ (A) Main memory (B) External storage/databases (C) Cache CO2 L2 B
memory (D) Registers
Which hash function is best for string keys?
16 MCQ (A) Division method (B) Multiplication method (C) Polynomial CO2 L2 C
accumulation (D) Modulo method
The time complexity of insertion in hash table with chaining is:
17 MCQ CO2 L2 A
(A) O(1) average (B) O(log n) (C) O(n) (D) O(n²)
Which technique provides best resistance to clustering?
18 MCQ (A) Linear probing (B) Quadratic probing (C) Double hashing CO2 L2 C
(D) All are equal
In skip list, the maximum level is typically:
19 MCQ CO2 L2 A
(A) log n (B) n (C) √n (D) n²
What happens during rehashing?
20 MCQ (A) Delete all elements (B) Create new table and reinsert all CO2 L2 B
elements (C) Sort the elements (D) Compress the table
The division method hash function is:
21 MCQ (A) h(k) = k mod m (B) h(k) = k / m (C) h(k) = k * m CO2 L1 A
(D) h(k) = k + m
Secondary clustering occurs in:
22 MCQ (A) Linear probing (B) Quadratic probing (C) Double hashing CO2 L2 B
(D) Separate chaining
What is the worst-case time complexity of search in hash table
23 MCQ with chaining? CO2 L2 C
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
A perfect hash function:
24 MCQ (A) Has no collisions (B) Is fastest (C) Uses least memory (D) CO2 L1 A
Is easiest to implement
Which data structure is used in separate chaining?
25 MCQ CO2 L1 B
(A) Array (B) Linked list (C) Tree (D) Graph
The space complexity of a hash table with n elements and load
26 MCQ factor α is: CO2 L2 B
(A) O(n) (B) O(n/α) (C) O(n*α) (D) O(n²)
In extendible hashing, the directory size:
27 MCQ (A) Is fixed (B) Can grow/shrink (C) Is always n CO2 L2 B
(D) Is always 1

16
 Aurora’s Scientific and Technological Institute

A good hash function should:

(A) Produce sequential values (B) Distribute keys uniformly
28 MCQ CO2 L2 B
(C) Always return 0 (D) Be complex

Linear list representation of dictionary has search time

29 MCQ complexity of: CO2 L1 C
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
Skip list is a:
30 MCQ (A) Deterministic data structure (B) Probabilistic data structure CO2 L1 B
(C) Sequential structure (D) Circular structure
dictionary /
31 Fill A ________ is a collection of key-value pairs with unique keys. CO2 L1
map
hash
32 Fill In hashing, the ________ maps keys to table indices. CO2 L1
function
When two keys hash to the same location, it is called a
33 Fill CO2 L1 collision
________.
________ chaining resolves collisions by storing colliding
34 Fill CO2 L1 Separate
elements in linked lists.
35 Fill The ratio of number of elements to table size is called ________. CO2 L1 load factor
36 Fill In ________ probing, we search for next empty slot sequentially. CO2 L1 linear
37 Fill ________ probing uses two hash functions to resolve collisions. CO2 L1 Double
multi /
38 Fill A skip list is a ________ layered linked list structure. CO2 L1
multiple
________ is the process of creating a larger hash table and
39 Fill CO2 L1 Rehashing
reinserting all elements.
40 Fill ________ hashing uses a directory structure for dynamic growth. CO2 L1 Extendible
Match the Following:
1. Linear probing
2. Separate chaining
3. Load factor
4. Skip list
5. Double hashing
6. Rehashing
1-d
7. Perfect hash
2-e
8. Division method
3-a
9. Primary clustering
4-f
10. Extendible hashing
5-b
41 Match CO2 L2 6-g
Options:
7-c
(a) n/ m ratio
8-h
(b) Two hash functions
9-i
(c) No collisions
10-j
(d) Sequential probe
(e) Linked lists at buckets
(f) Probabilistic structure
(g) Table resizing
(h) h(k) = k mod m
(i) Linear probing problem
(j) Dynamic directory

17
 Aurora’s Scientific and Technological Institute

10.4. Unit-II: Part – B – Descriptive Questions:

[Link] Bloom's
Question CO
. Level
1 Define dictionary and explain its applications. CO2 L1
2 Explain linear list representation of dictionaries with example. CO2 L2
3 Discuss the need for hashing and its advantages. CO2 L2
4 What is a hash function? Explain its properties. CO2 L2
5 Explain collision and its resolution techniques. CO2 L3
6 Differentiate between open addressing and separate chaining. CO2 L3
7 Describe linear probing with example. CO2 L2
8 Explain quadratic probing with example. CO2 L2
9 What is double hashing? How does it reduce clustering? CO2 L3
10 Describe rehashing and its purpose. CO2 L3
11 What is extendible hashing? Explain its working. CO2 L4
12 Compare static hashing and dynamic hashing. CO2 L3
13 Discuss performance analysis of hash tables. CO2 L4
14 Describe skip list representation of dictionary. CO2 L2
15 Explain insertion and deletion operations in a dictionary. CO2 L3
16 Write an algorithm for searching a key in a hash table. CO2 L3
17 What are the limitations of hashing? CO2 L2
18 Explain applications of hashing in real-world scenarios. CO2 L4
19 Differentiate between hashing and index-based searching. CO2 L3
20 Explain the concept of hash collision with a neat example. CO2 L2

10.5. Unit-III: Part – A – Objective Questions:

Bloom's
[Link]. Type Question CO Answer
Level
In a Binary Search Tree (BST), the left child is:
1 MCQ (A) Greater than parent (B) Less than parent (C) Equal to parent CO3 L1 B
(D) No relation
What is the time complexity of searching in a balanced BST?
2 MCQ CO3 L2 B
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
3 MCQ The worst-case time complexity of search in a skewed BST is: CO3 L2 C

18
 Aurora’s Scientific and Technological Institute

(A) O(1) (B) O(log n) (C) O(n) (D) O(n log n)

An AVL tree is a:
4 MCQ (A) Completely balanced tree (B) Height-balanced tree CO3 L1 B
(C) Weight-balanced tree (D) Unbalanced tree
In an AVL tree, the balance factor of a node is:
(A) Height of left - height of right (B) Height of right - height of
5 MCQ CO3 L1 A
left (C) Number of left - number of right (D) Weight of left -
weight of right
What are the possible balance factor values in an AVL tree?
6 MCQ CO3 L1 B
(A) 0, 1, 2 (B) -1, 0, 1 (C) -2, -1, 0, 1, 2 (D) Any integer
Which rotation is needed for LL imbalance in AVL tree?
7 MCQ (A) Single left rotation (B) Single right rotation (C) Left-right CO3 L2 B
rotation (D) Right-left rotation
The maximum height of an AVL tree with n nodes is
8 MCQ approximately: CO3 L2 B
(A) log n (B) 1.44 log n (C) n (D) √n
B-tree is used in:
9 MCQ (A) Main memory indexing (B) External storage/ database CO3 L2 B
indexing (C) Network routing (D) Graphics rendering
In a B-tree of order m, each node can have maximum:
10 MCQ CO3 L1 A
(A) m children (B) m-1 children (C) m keys (D) m-1 keys
In a B+ tree, data is stored in:
11 MCQ (A) All nodes (B) Only leaf nodes (C) Only internal nodes (D) CO3 L1 B
Root node only
The minimum number of keys in a non-root B-tree node of order

(A) ⌈m/2⌉ (B) ⌈m/2⌉ - 1 (C) m (D) m - 1

12 MCQ m is: CO3 L2 B

Red-Black tree ensures maximum height of:

13 MCQ CO3 L2 B
(A) log n (B) 2 log n (C) n (D) √n
In a Red-Black tree, the root is always:
14 MCQ CO3 L1 B
(A) Red (B) Black (C) Either color (D) No color
A Red-Black tree is a BST with:
15 MCQ (A) One additional bit (B) Two additional bits (C) No CO3 L1 A
additional storage (D) Height information
In Red-Black tree, no red node can have:
16 MCQ CO3 L1 B
(A) Black parent (B) Red child (C) Two children (D) Any child
Splay trees use which operation after every access?
17 MCQ CO3 L1 B
(A) Rotation (B) Splaying (C) Balancing (D) Recolouring
The amortized time complexity of operations in splay tree is:
18 MCQ CO3 L2 B
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
Which tree self-adjusts based on access patterns?
19 MCQ CO3 L2 C
(A) AVL tree (B) Red-Black tree (C) Splay tree (D) B-tree
The inorder traversal of a BST gives elements in:
20 MCQ (A) Random order (B) Sorted order (C) Reverse order CO3 L1 B
(D) Level order
What is the minimum height of a BST with n nodes?
21 MCQ CO3 L2 B
(A) 1 (B) log n (C) n (D) n-1
In B+ tree, leaf nodes are connected using:
22 MCQ (A) Parent pointers (B) Sibling pointers (C) Random pointers CO3 L2 D
(D) No connection
19
 Aurora’s Scientific and Technological Institute

Which tree requires rebalancing after every insertion?

23 MCQ CO3 L2 A
(A) AVL tree (B) BST (C) B-tree (D) All of these
24 MCQ The space complexity of Red-Black tree compared to BST is: CO3 L2 C
(A) Same (B) Double (C) Slightly more (1 bit per node)
(D) Half
25 MCQ In splay tree, the zig-zig operation requires: CO3 L2 B
(A) One rotation (B) Two rotations (C) Three rotations
(D) No rotation
26 MCQ The order of a B-tree refers to: CO3 L1 B
(A) Number of keys (B) Maximum number of children
(C) Height of tree (D) Number of levels
Which tree provides best worst-case guarantees?
27 MCQ CO3 L2 B
(A) BST (B) AVL tree (C) Splay tree (D) None
28 MCQ Deletion in BST with two children requires finding: CO3 L2 C
(A) Leftmost node (B) Rightmost node (C) Inorder successor or
predecessor (D) Parent node
29 MCQ B-tree splits occur when a node exceeds: CO3 L2 B
(A) Minimum keys (B) Maximum keys (C) Height limit
(D) Balance factor
Which tree is most commonly used in file systems?
30 MCQ CO3 L2 C
(A) AVL tree (B) Red-Black tree (C) B+ tree (D) Splay tree
In a BST, all elements in the left subtree are ________ than the smaller /
31 Fill CO3 L1
root. less
balance
32 Fill An AVL tree maintains balance using ________ and rotations. CO3 L1
factor
The balance factor of a node in AVL tree is the difference
33 Fill CO3 L1 heights
between ________ of left and right subtrees.
multi-way /
34 Fill B-tree is a ________ search tree optimized for disk access. CO3 L1
m-way
In a Red-Black tree, all paths from root to leaves have the same
35 Fill CO3 L1 black
number of ________ nodes.
A ________ tree moves frequently accessed elements closer to
36 Fill CO3 L1 splay
the root.
The minimum degree 't' of a B-tree determines that each node
37 Fill CO3 L1 t-1
has at least ________ keys.
In B+ tree, all keys appear in ________ nodes for easy sequential
38 Fill CO3 L1 leaf
access.
39 Fill CO3 L1 left, right /
An LR imbalance in AVL tree requires a ________ rotation
left-right /
followed by a ________ rotation.
double
The worst-case height of a Red-Black tree with n nodes is 2 / two
40 Fill CO3 L1
________ log n. times
41 Match Match the Following: CO3 L2 1-a
1. BST property 2-b
2. AVL tree 3-c
3. Red-Black tree 4-d
4. B-tree 5-j
5. B+ tree 6-e
6. Splay tree 7-f
7. Balance factor 8-g
8. Single rotation 9-h
9. Double rotation 10-i

20
 Aurora’s Scientific and Technological Institute

10. Inorder traversal

Options:
(a) Left < Root < Right
(b) Height balanced
(c) Color property
(d) External storage
(e) Self-adjusting
(f) Height difference
(g) LL or RR case
(h) LR or RL case
(i) Gives sorted output
(j) Data only in leaves

10.6. Unit-III: Part – B – Descriptive Questions:

[Link] Bloom's
Question CO
. Level
1 Define Binary Search Tree and explain its properties. CO3 L1
2 Explain the process of searching a key in a BST with example. CO3 L2
3 Describe insertion and deletion operations in a BST. CO3 L3
4 What are the advantages and disadvantages of BST? CO3 L2
5 Define AVL tree and explain balance factor with example. CO3 L2
6 Explain rotations in AVL tree with diagrams. CO3 L3
7 Describe insertion in an AVL tree. CO3 L3
8 Describe deletion in an AVL tree. CO3 L3
9 Explain structure and properties of B-Tree. CO3 L2
10 Discuss insertion and deletion operations in B-Tree. CO3 L3
11 Explain difference between B-Tree and B+ Tree. CO3 L2
12 Describe the balancing rules of Red-Black Tree. CO3 L3
13 Explain insertion algorithm in Red-Black Tree. CO3 L4
14 Explain deletion in Red-Black Tree. CO3 L4
15 Define splay tree and explain its working principle. CO3 L2
16 Discuss the advantages of self-balancing trees. CO3 L3
17 Compare AVL tree and Red-Black tree. CO3 L4
18 Write an algorithm for inorder traversal of BST. CO3 L2
19 Explain height balancing in AVL and B-Tree. CO3 L3
20 Discuss applications of tree data structures. CO3 L4

21
 Aurora’s Scientific and Technological Institute

10.7. Unit-IV: Part – A – Objective Questions:

Bloom's
[Link]. Type Question CO Answer
Level
A graph consists of:
1 MCQ (A) Nodes only (B) Edges only (C) Vertices and edges (D) CO4 L1 C
Trees
In an undirected graph with n vertices, maximum number of
2 MCQ edges is: CO4 L2 B
(A) n (B) n(n-1)/2 (C) n(n-1) (D) n²
Adjacency matrix representation requires space complexity of:
3 MCQ CO4 L1 C
(A) O(V) (B) O(E) (C) O(V²) (D) O(V+E)
Adjacency list representation requires space complexity of:
4 MCQ CO4 L1 D
(A) O(V) (B) O(E) (C) O(V²) (D) O(V+E)
Which graph traversal uses a queue?
5 MCQ CO4 L1 B
(A) DFS (B) BFS (C) Both (D) Neither
Which graph traversal uses a stack?
6 MCQ CO4 L1 A
(A) DFS (B) BFS (C) Both (D) Neither
The time complexity of BFS and DFS is:
7 MCQ CO4 L2 C
(A) O(V) (B) O(E) (C) O(V+E) (D) O(V*E)
Quick Sort uses which technique?
8 MCQ (A) Greedy (B) Divide and conquer (C) Dynamic programming CO4 L2 B
(D) Backtracking
What is the average time complexity of Quick Sort?
9 MCQ CO4 L2 B
(A) O(n) (B) O(n log n) (C) O(n²) (D) O(log n)
What is the worst-case time complexity of Quick Sort?
10 MCQ CO4 L2 C
(A) O(n) (B) O(n log n) (C) O(n²) (D) O(2ⁿ)
The pivot selection in Quick Sort affects:
11 MCQ (A) Correctness (B) Performance (C) Space complexity (D) CO4 L2 B
Nothing
Heap Sort uses which data structure?
12 MCQ CO4 L1 C
A) Stack (B) Queue (C) Binary heap (D) Graph
What is the time complexity of Heap Sort?
13 MCQ CO4 L2 B
(A) O(n) (B) O(n log n) (C) O(n²) (D) O(log n)
Heap Sort is:
14 MCQ CO4 L1 B
(A) Stable (B) Unstable (C) Adaptive (D) Online
External sorting is used when:
15 MCQ (A) Data fits in memory (B) Data doesn't fit in memory (C) CO4 L2 B
Data is sorted (D) Data is small
K-way merge sort is used in:
16 MCQ (A) Internal sorting (B) External sorting (C) Quick sort (D) CO4 L2 B
Heap sort
In external merge sort, the number of passes required is:
17 MCQ CO4 L2 B
(A) log₂ n (B) logₖ (n/M) (C) n (D) k
18 MCQ A directed graph is strongly connected if: CO4 L2 B
(A) Some vertices are reachable (B) All vertices are reachable
22
 Aurora’s Scientific and Technological Institute

from any vertex (C) Graph has cycles (D) Graph is weighted
Which sorting algorithm is best for external sorting?
19 MCQ (A) Quick Sort (B) Bubble Sort (C) Merge Sort (D) Insertion CO4 L2 C
Sort
The space complexity of Quick Sort is:
20 MCQ CO4 L2 B
(A) O(1) (B) O(log n) (C) O(n) (D) O(n²)
A complete binary tree is used in:
21 MCQ CO4 L1 B
(A) Quick Sort (B) Heap Sort (C) Merge Sort (D) Radix Sort
BFS finds:
22 MCQ (A) Longest path (B) Shortest path in unweighted graph (C) CO4 L2 B
Minimum spanning tree (D) Cycles
DFS can be used to detect:
23 MCQ (A) Shortest path (B) Cycles in graph (C) Minimum weight CO4 L2 B
(D) Maximum flow
In-place sorting means:
24 MCQ (A) Uses O(1) extra space (B) Uses O(n) extra space (C) Uses CO4 L1 A
no comparisons (D) Always stable
Quick Sort is preferred over Merge Sort when:
25 MCQ (A) Stability is required (B) Space is limited (C) Data is on disk CO4 L2 B
(D) Data is linked list
The build heap operation takes time:
26 MCQ CO4 L2 A
(A) O(n) (B) O(n log n) (C) O(n²) (D) O(log n)
In a graph, a path that visits every vertex exactly once is called:
27 MCQ (A) Euler path (B) Hamiltonian path (C) Shortest path (D) CO4 L1 B
Simple path
Which representation is better for dense graphs?
28 MCQ (A) Adjacency matrix (B) Adjacency list (C) Edge list (D) All CO4 L2 A
same
The partition function in Quick Sort:
29 MCQ (A) Merges arrays (B) Rearranges elements around pivot (C) CO4 L2 B
Builds heap (D) Creates tree
Multi-way merge in external sorting uses:
30 MCQ CO4 L2 B
(A) Stack (B) Min-heap (C) Max-heap (D) Queue
tree / acyclic
31 Fill A graph with no cycles is called a ________. CO4 L1 graph /
DAG
________ traversal explores as far as possible along each branch Depth-first /
32 Fill CO4 L1
before backtracking. DFS
________ traversal visits all neighbors before moving to next Breadth-first
33 Fill CO4 L1
level. / BFS
In Quick Sort, the element used to partition the array is called
34 Fill CO4 L1 pivot
________.
35 Fill Heap Sort first builds a ________ heap from the array. CO4 L1 max
The process of selecting and removing the root in Heap Sort is heapify /
36 Fill CO4 L1
called ________. extract-max
secondary
External sorting uses ________ for sorting data that doesn't fit in
37 Fill CO4 L1 storage /
main memory.
disk
In external merge sort, sorted runs are merged using ________ k-way /
38 Fill CO4 L1
merge. multi-way
39 Fill A graph where edges have direction is called a ________ graph. CO4 L1 directed

23
 Aurora’s Scientific and Technological Institute

40 Fill The ________ matrix stores 1 if edge exists, 0 otherwise. CO4 L1 adjacency
Match the Following:
1. BFS
2. DFS
3. Quick Sort
4. Heap Sort
5. External Sort
6. Adjacency matrix 1-b
7. Pivot 2-c
8. Heapify 3-a
9. Merge phase 4-j
10. Graph cycle 5-h
41 Match CO4 L2 6-e
Options: 7-f
(a) Divide and conquer 8-d
(b) Uses queue 9-i
(c) Uses stack 10-g
(d) Binary heap property
(e) O(V²) space
(f) Partition element
(g) DFS detection
(h) Disk-based sorting
(i) Combining sorted runs
(j) Complete binary tree

10.8. Unit-IV: Part – B – Descriptive Questions:

[Link] Bloom's
Question CO
. Level
Explain the different methods of graph representation: adjacency matrix,
1 CO4 L2
adjacency list, and edge list. Compare their space and time complexities.
Describe the Breadth-First Search (BFS) algorithm for graph traversal. Write the
2 CO4 L3
algorithm and trace its execution on a sample graph.
Explain the Depth-First Search (DFS) algorithm. Write both recursive and
3 CO4 L3
iterative implementations. Demonstrate with an example graph.
Compare BFS and DFS traversal methods in terms of implementation,
4 CO4 L2
applications, space complexity, and use cases.
Describe how DFS can be used to detect cycles in a directed graph. Write an
5 CO4 L3
algorithm and provide an example.
Explain how BFS can be used to find the shortest path in an unweighted graph.
6 CO4 L3
Provide an algorithm and example.
What is Quick Sort? Explain the partition algorithm in detail. Write the complete
7 CO4 L3
Quick Sort algorithm with an example showing all recursive calls.
Analyze the time complexity of Quick Sort for best, average, and worst cases.
8 CO4 L2
What factors affect its performance? How can worst-case be avoided?
Describe different pivot selection strategies in Quick Sort: first element, last
9 CO4 L2
element, median-of-three, and random. Compare their effectiveness.
What is Heap Sort? Explain the structure of a binary heap and its properties.
10 CO4 L2
Describe the heapify operation with examples.
Write detailed algorithms for building a max-heap and performing Heap Sort.
11 CO4 L3
Trace the execution on the array [4, 10, 3, 5, 1, 8, 7, 2].

24
 Aurora’s Scientific and Technological Institute

Compare Quick Sort and Heap Sort in terms of time complexity, space
12 complexity, stability, and practical performance. When would you prefer one CO4 L2
over the other?
What is external sorting? Why is it necessary? Explain the model for external
13 CO4 L2
sorting including concepts of runs, buffers, and I/O operations.
Describe the external merge sort algorithm in detail. Explain the process of
14 CO4 L3
creating sorted runs and merging them. How many passes are required?
Explain k-way merge in external sorting. How does it optimize the number of
15 CO4 L3
passes? Write an algorithm using a min-heap for k-way merge.
Discuss the applications of graph traversal algorithms in real-world problems
16 CO4 L2
such as social networks, web crawling, and network routing.
Explain topological sorting of a directed acyclic graph (DAG) using DFS.
17 CO4 L3
Provide an algorithm and example showing the topological order.
Describe how to find connected components in an undirected graph using BFS or
18 CO4 L3
DFS. Write an algorithm and provide an example.
Compare internal and external sorting. Discuss the challenges in external sorting
19 CO4 L2
and techniques to optimize disk I/O operations.
Explain the concept of replacement selection in external sorting. How does it
20 CO4 L2
help in creating longer initial runs?

10.9. Unit-V: Part – A – Objective Questions:

Bloom's
[Link]. Type Question CO Answer
Level
Pattern matching is used in:
1 MCQ (A) Text editors (B) Search engines (C) DNA sequencing (D) CO5 L1 D
All of these
In pattern matching, the text to be searched is called:
2 MCQ CO5 L1 C
(A) Pattern (B) String (C) Text (D) Substring
What is the time complexity of brute force pattern matching?
3 MCQ CO5 L2 C
(A) O(n) (B) O(m) (C) O(nm) (D) O(n+m)
The Boyer-Moore algorithm scans the pattern from:
4 MCQ (A) Left to right (B) Right to left (C) Middle to ends (D) CO5 L1 B
Random
The bad character heuristic is used in:
5 MCQ CO5 L1 C
(A) Brute force (B) KMP (C) Boyer-Moore (D) Rabin-Karp
What is the best-case time complexity of Boyer-Moore
6 MCQ algorithm? CO5 L2 A
(A) O(n/m) (B) O(n+m) (C) O(nm) (D) O(m)
KMP algorithm uses:
7 MCQ (A) Bad character table (B) Failure function/prefix table (C) CO5 L1 B
Good suffix table (D) Hash function
What is the preprocessing time complexity of KMP algorithm?
8 MCQ CO5 L2 A
(A) O(m) (B) O(n) (C) O(nm) (D) O(1)
What is the matching time complexity of KMP algorithm?
9 MCQ CO5 L2 B
(A) O(m) (B) O(n) (C) O(nm) (D) O(n+m)
The prefix function in KMP stores:
10 MCQ (A) Character positions (B) Length of longest proper prefix that CO5 L2 B
is also suffix (C) Pattern length (D) Text length
11 MCQ A trie is used for: CO5 L1 B
(A) Sorting numbers (B) String storage and retrieval (C) Graph
25
 Aurora’s Scientific and Technological Institute

traversal (D) Matrix operations

The root of a standard trie represents:
12 MCQ (A) First character (B) Last character (C) Empty string (D) CO5 L1 C
Longest string
What is the time complexity of searching a word of length m in a
13 MCQ trie? CO5 L2 B
(A) O(1) (B) O(m) (C) O(n) (D) O(nm)
How many children can a node have in a standard trie for
14 MCQ English alphabet? CO5 L1 B
(A) 10 (B) 26 (C) 52 (D) 256
Compressed trie is also known as:
15 MCQ (A) Standard trie (B) Suffix trie (C) Radix tree/Patricia trie (D) CO5 L1 C
B-tree
What does a compressed trie compress?
16 MCQ (A) Data values (B) Chains of single-child nodes (C) Multiple CO5 L2 B
words (D) Root node
A suffix trie stores:
17 MCQ (A) Prefixes of a string (B) All suffixes of a string (C) CO5 L1 B
Substrings of a string (D) Reversed string
Suffix tries are used in:
18 MCQ (A) Spell checking (B) Pattern matching (C) Auto-completion CO5 L2 D
(D) All of these
What is the space complexity of a standard trie with n strings of
19 MCQ average length m? CO5 L2 C
(A) O(n) (B) O(m) (C) O(nm) (D) O(n+m)
The advantage of compressed trie over standard trie is:
20 MCQ (A) Faster search (B) Reduced space (C) Easier implementation CO5 L2 B
(D) Better sorting
In Boyer-Moore, the good suffix rule is used when:
21 MCQ (A) Mismatch occurs (B) Match occurs (C) Pattern ends (D) CO5 L2 A
Text starts
Which algorithm doesn't require preprocessing?
22 MCQ (A) KMP (B) Boyer-Moore (C) Brute force (D) All require CO5 L1 C
preprocessing
Auto-complete feature in search engines uses:
23 MCQ CO5 L2 B
(A) Hash tables (B) Tries (C) Stacks (D) Queues
The worst-case complexity of Boyer-Moore algorithm is:
24 MCQ CO5 L2 C
(A) O(n/m) (B) O(n+m) (C) O(nm) (D) O(m)
KMP algorithm avoids:
25 MCQ (A) Character comparison (B) Unnecessary backtracking (C) CO5 L2 B
Pattern matching (D) Text scanning
A trie with n nodes has maximum height of:
26 MCQ CO5 L2 C
(A) log n (B) n (C) Length of longest string (D) √n
Which pattern matching algorithm is best for long patterns?
27 MCQ CO5 L2 C
(A) Brute force (B) KMP (C) Boyer-Moore (D) All same
Suffix trees are constructed from:
28 MCQ (A) Prefix trie (B) Suffix trie (C) Standard trie (D) Compressed CO5 L2 B
trie
The space overhead in KMP algorithm is:
29 MCQ CO5 L2 B
(A) O(1) (B) O(m) (C) O(n) (D) O(nm)
Which data structure is used for spell checkers?
30 MCQ CO5 L2 B
(A) Array (B) Trie (C) Stack (D) Graph
26
 Aurora’s Scientific and Technological Institute

The ________ algorithm compares pattern with text character by brute force /
31 Fill CO5 L1
character. naive
The ________ algorithm scans pattern from right to left but text Boyer-
32 Fill CO5 L1
from left to right. Moore
KMP algorithm uses a ________ function to avoid unnecessary failure /
33 Fill CO5 L1
comparisons. prefix / next
34 Fill A ________ is a tree-based data structure for storing strings. CO5 L1 trie
35 Fill In a trie, each ________ from root to leaf represents a string. CO5 L1 path
________ trie reduces space by merging nodes with single Compressed
36 Fill CO5 L1
children. / Radix
37 Fill A ________ trie stores all suffixes of a given string. CO5 L1 suffix
The time complexity of KMP algorithm is ________, where n is O(n+m) /
38 Fill CO5 L1
text length and m is pattern length. linear
Boyer-Moore algorithm uses ________ heuristic and good suffix bad
39 Fill CO5 L1
heuristic. character
string /
40 Fill Tries support efficient ________ operations like prefix matching. CO5 L1 lexicographi
c
Match the Following:
1. Brute force
2. Boyer-Moore
3. KMP
4. Standard trie
5. Compressed trie
6. Suffix trie
7. Failure function
1-a
8. Bad character
2-b
9. Auto-complete
3-c
10. DNA matching
4-d
41 Match CO5 L2 5-e
Options:
6-f
(a) O(nm) complexity
7-g 8-h
(b) Right to left scan
9-i
(c) Prefix table
10-j
(d) All string characters
(e) Radix tree
(f) All suffixes
(g) KMP preprocessing
(h) Boyer-Moore heuristic
(i) Trie application
(j) Pattern matching use

10.10. Unit-V: Part – B – Descriptive Questions:

[Link] Bloom's
Question CO
. Level
Explain the brute force pattern matching algorithm. Write the algorithm and
1 CO5 L3
analyze its time complexity. Demonstrate with an example.
Describe the Boyer-Moore pattern matching algorithm. Explain the bad character
2 CO5 L2
heuristic with examples. How does it improve over brute force?

27
 Aurora’s Scientific and Technological Institute

Explain the good suffix heuristic in the Boyer-Moore algorithm. How does it
3 CO5 L2
work in conjunction with the bad character heuristic?
Write a detailed algorithm for the Boyer-Moore pattern matching. Trace its
4 CO5 L3
execution on text "ABCABAABABCABA" with pattern "ABABC".
What is the Knuth-Morris-Pratt (KMP) algorithm? Explain how it avoids
5 CO5 L2
unnecessary character comparisons. Discuss its advantages over brute force.
Describe the construction of the failure function (prefix function) in the KMP
6 CO5 L3
algorithm. Write the algorithm and demonstrate with pattern "ABABCABAB".
Explain the complete KMP pattern matching algorithm with preprocessing and
7 CO5 L3
matching phases. Provide a detailed example with text and pattern.
Trace the KMP algorithm for text "ABABDABACDABABCABAB" and pattern
8 CO5 L3
"ABABCABAB". Show the failure function values and matching process.
Compare the three pattern matching algorithms: Brute Force, Boyer-Moore, and
9 KMP in terms of time complexity, preprocessing requirements, and practical CO5 L2
performance.
What is a trie (prefix tree)? Explain its structure and properties. How is it
10 CO5 L2
different from other tree structures like BST?
Describe the insertion and search operations in a standard trie. Write algorithms
11 CO5 L3
and demonstrate by inserting words: "the", "there", "their", "these", "this".
Explain the deletion operation in a trie. What are the different cases to consider?
12 CO5 L3
Provide an algorithm and example.
What is a compressed trie (radix tree or Patricia trie)? How does it differ from a
13 CO5 L2
standard trie? Explain with examples showing space savings.
Describe the construction of a compressed trie. Write the algorithm for
14 CO5 L3
compressing a standard trie and demonstrate with an example.
What is a suffix trie? Explain its construction for a given string. How is it useful
15 CO5 L2
in pattern matching and substring search problems?
Construct a suffix trie for the string "banana$". Show all suffixes and the
16 CO5 L3
resulting trie structure. Demonstrate how to search for pattern "ana".
Discuss the applications of tries in real-world scenarios such as auto-completion,
17 CO5 L2
spell checking, IP routing, and dictionary implementations.
Compare standard tries, compressed tries, and suffix tries in terms of space
18 CO5 L2
complexity, time complexity for operations, and use cases.
Explain how suffix tries can be used to find all occurrences of a pattern in a text
19 CO5 L3
in linear time. Provide an algorithm and example.
Describe the concept of longest common prefix using tries. Write an algorithm to
20 CO5 L3
find the longest common prefix among a set of strings using a trie.

28
 Aurora’s Scientific and Technological Institute

11. Question Bank for External Examination

11.1. Unit I
[Link] Reg/
Year Question Marks CO Bloom
. Suppl

29
 Aurora’s Scientific and Technological Institute

30
 Aurora’s Scientific and Technological Institute

12. Assignments
Assignments are part of Continuous Internal Evaluation (CIE) and are evaluated for 5 marks. Student
shall submit two assignments in a course and the average of 2 Assignments each for 5 marks shall be
taken. The first assignment should be submitted before the conduct of the first mid-term examination, and
the second assignment should be submitted before the conduct of the second mid-term.

12.1. Assignment-I (from first 50% of the Syllabus)

Bloom’
[Link]. Question CO
s Level
Write a C program to implement a singly linked list with insertion, deletion, and CO1 L3
1
display operations.
Develop a program to perform searching for a specific element in a singly linked CO1 L3
2
list.
Design a C program to reverse a singly linked list using iterative and recursive CO1 L5
3
methods.
Implement stack operations (push, pop, peek, display) using arrays. CO1 L3
4
Implement stack operations using linked list representation. CO1 L4
5
Apply stack concept to evaluate a postfix expression using C. CO1 L4
6
Write a C program to convert an infix expression to postfix using stack CO1 L4
7
operations.
Implement queue operations (enqueue, dequeue, display) using arrays. CO1 L3
8
Design a C program to implement a circular queue using arrays. CO1 L4
9
Implement a queue using linked list representation and perform enqueue and CO1 L4
10
dequeue operations.
Write a program to represent a dictionary using a linear list and perform CO2 L4
11
insertion and deletion operations.
Develop a program to implement a skip list and perform search operation CO2 L5
12
efficiently.
Design a C program to implement a hash table using separate chaining CO2 L5
13
technique.
Write a program to implement hash table using open addressing (linear CO2 L5
14
probing) for collision resolution.
Design a program to demonstrate quadratic probing and double hashing CO2 L6
15
collision resolution techniques.
Implement rehashing and extendible hashing in a hash table for dynamic CO2 L6
16
resizing.
Write a C program to construct a Binary Search Tree (BST) and perform CO3 L4
17
insertion and searching operations.
Implement deletion operation in a Binary Search Tree and display the tree after CO3 L5
18
each deletion.
Write a C program to construct a B-Tree and perform insertion operation. CO3 L5
19
Design and implement a B+ Tree for efficient search and indexing operations. CO3 L6
20
31
 Aurora’s Scientific and Technological Institute

12.2. Assignment-II (from remaining 50% of the Syllabus)

Bloom’
[Link]. Question CO
s Level
Write a C program to create an AVL Tree and perform insertion operations while CO3 L5
1
maintaining balance.
Implement deletion operation in an AVL Tree and display the tree after each deletion. CO3 L5
2
Develop a program to find the height of an AVL Tree using recursion. CO3 L4
3
Construct a Red-Black Tree from a given sequence of numbers and demonstrate CO3 L5
4
balancing after insertion.
Write a C program to perform searching in a Red-Black Tree. CO3 L4
5
Implement a Splay Tree and demonstrate splaying for access operations. CO3 L6
6
Compare the performance of AVL, Red-Black, and Splay Trees based on height and CO3 L6
7
rotation count.
Write a C program to represent a graph using adjacency matrix and adjacency list. CO4 L4
8
Implement Breadth-First Search (BFS) and Depth-First Search (DFS) traversals for a CO4 L4
9
given graph.
Design a C program to detect cycles in a directed graph using DFS. CO4 L5
10
Develop a program to find connected components in an undirected graph using CO4 L5
11
adjacency list representation.
Implement Quick Sort algorithm and analyze its performance for different input sizes. CO4 L5
12
Write a C program to perform Heap Sort and display intermediate heap states. CO4 L4
13
Design and implement Merge Sort for external files (External Sorting Model). CO4 L6
14
Compare the performance of Quick Sort, Heap Sort, and Merge Sort for large data CO4 L6
15
sets.
Implement the Brute-Force pattern matching algorithm for searching substrings in a CO5 L4
16
text file.
Write a C program to implement the Boyer–Moore pattern matching algorithm. CO5 L5
17
Develop a program to implement the Knuth–Morris–Pratt (KMP) algorithm for CO5 L5
18
efficient pattern matching.
Construct a Trie for a set of given strings and perform insert and search operations. CO5 L5
19
Design a program to build a Suffix Trie for text indexing and substring search CO5 L6
20
applications.

32
 Aurora’s Scientific and Technological Institute

13. Seminars:

Seminars are part of the Continuous Internal Evaluation and are evaluated for five marks. Seminars are to
be given by each learning group of three students on a topic in the concerned subject. This assessment
shall be completed before II Mid-Term Examination.

[Link]. Question Unit / Concept CO Bloom

Importance of Data Structures in Efficient Software Unit I – Introduction
1 CO1 L4
Development to Data Structures
Abstract Data Types and Their Role in Software Unit I – Abstract Data
2 CO1 L5
Modularity Types
Unit I – Lists and
3 Comparative Study of Static and Dynamic Data Structures CO1 L4
Arrays
Real-World Applications of Linked Lists in System
4 Unit I – Linear List CO1 L5
Programming
Stack Implementation and Its Role in Function Call Unit I – Stack
5 CO1 L4
Management Operations
Queue Data Structure and Its Application in Real-Time Unit I – Queue
6 CO1 L5
Systems Representations
7 Role of Dictionaries in Information Retrieval Systems Unit II – Dictionaries CO2 L4
Unit II – Skip List
8 Skip List and Its Advantage over Linear Lists CO2 L5
Representation
9 Hash Functions and Their Impact on Performance Unit II – Hashing CO2 L4
Collision Resolution Techniques and Their Practical Unit II – Collision
10 CO2 L5
Applications Resolution
Rehashing and Extendible Hashing: Concepts and Unit II – Advanced
11 CO2 L6
Implementation Hashing
Comparative Analysis of Hashing Techniques in Database
12 Unit II – Hash Tables CO2 L6
Indexing
13 Design and Analysis of Binary Search Trees Unit III – BST CO3 L4
Unit III – Balanced
14 Balancing Techniques in AVL and Red-Black Trees CO3 L5
Trees
15 Role of Splay Trees in Data Access Optimization Unit III – Splay Trees CO3 L5
Self-Balancing Trees and Their Role in Optimized Unit III – AVL and
16 CO3 L6
Searching Red-Black Trees
Graph Traversal Techniques and Their Applications in Unit IV – Graph
17 CO4 L4
Networks Traversal
Unit IV – Graph
18 Comparison of Graph Representation Methods CO4 L5
Implementations
19 Performance Comparison of Sorting Algorithms Unit IV – Sorting CO4 L5
Unit IV – External
20 External Sorting and Its Importance in Big Data Processing CO4 L6
Sorting

33
 Aurora’s Scientific and Technological Institute

Unit IV – Graph
21 Use of Graph Algorithms in Social Network Analysis CO4 L6
Applications
Pattern Matching Algorithms and Their Use in Text Unit V – Pattern
22 CO5 L5
Processing Matching
Trie and Suffix Trie Data Structures for Fast String
23 Unit V – Tries CO5 L6
Searching
Modern Applications of Trie Structures in Spell Checking Unit V – Tries and
24 CO5 L6
and Auto-completion Pattern Matching
Integrating Linear Structures, Trees, Graphs, Hashing, and Comprehensive – CO1–
25 L6
String Processing for Real-World Data Management Units I to V CO5

34