AMRITA VISHWA VIDYAPEETHAM, NAGERCOIL

SCHOOL OF COMPUTING

QUESTION BANK

Degree / Branch: [Link]. / CSE

Year / Semester: II / III

Course Code / Name: 23CSE203 / Data Structures and Algorithm

Syllabus

Introduction to Data Structures: Need and Relevance - Abstract Data Types and Data
Structures - Principles, and Patterns. Basic complexity analysis – Best, Worst, and Average
Cases - Asymptotic Analysis -Analyzing Programs – Space Bounds, recursion- linear, binary,
and multiple recursions. Arrays, Linked Lists and Recursion: Using Arrays - Lists - Array
based List Implementation – Linked Lists – LL ADT – Singly Linked List – Doubly Linked
List – Circular Linked List Stacks and Queues: Stack ADT - Array based Stacks, Linked
Stacks – Implementing Recursion using Stacks, Stack Applications. Queues - ADT, Array
based Queue, Linked Queue, Double-ended queue, Circular queue, applications.

[Link]. Question Marks CO Bloom’s

Level

1 Define an abstract data type (ADT). How does it differ from a data 2 CO1 L1
structure?

2 Explain the concept of recursion with an example. 2 CO1 L2

3 What is the difference between singly linked list and circular linked 2 CO1 L2
list?

4 Compare stack and queue based on their principle of operation. 2 CO1 L2

5 Write the time and space complexity for linear search and binary 2 CO2 L1
search.

6 Explain the term asymptotic notation and give an example of Big-O 2 CO2 L2
analysis.

7 Describe the process of implementing a stack using a linked list. 3 CO1 L3

8 Write the logic to check if a string is a palindrome using a stack. 3 CO2 L3

9 Implement an algorithm to merge two sorted linked lists into a single 4 CO2 L3
sorted list.

10 Given a circular queue with front=4 and rear=2, demonstrate enqueue 4 CO2 L3
and dequeue operations step-by-step for 5 elements.

11 Write Python functions to perform insertion and deletion at both ends 4 CO1 L3
of a doubly linked list.

12 Demonstrate how recursion is implemented using stacks in memory. 5 CO1 L3

13 Design a program to reverse the order of words in a sentence using a 5 CO2 L4

queue.

14 Differentiate between linear recursion and binary recursion with 5 CO2 L2

examples.

15 Describe how a circular queue can be used to manage CPU scheduling 5 CO4 L3
tasks.

Unit 2

Trees: Tree Definition and Properties – Tree ADT - Basic tree traversals - Binary tree - Data
structure for representing trees – Linked Structure for Binary Tree – Array based
implementation. Priority queues: ADT – Implementing Priority Queue using List – Heaps.
Maps and Dictionaries: Map ADT – List based Implementation – Hash Tables - Dictionary
ADT. Skip Lists - Implementation - Complexity.

[Link]. Question Marks CO Bloom’s

Level

16 Define a binary tree and list its properties. 2 CO2 L1

17 What are the advantages of using linked representation for binary 2 CO2 L1
trees?

18 Explain how a heap differs from a binary search tree. 2 CO3 L2

19 Define a hash function. What are the desirable properties of a good 2 CO3 L1
hash function?

20 Construct a binary tree for the preorder sequence A, B, D, E, C, F 3 CO2 L3

and inorder sequence D, B, E, A, F, C.

21 Explain the process of inserting elements into a max-heap. 3 CO3 L3

22 Compare open addressing and separate chaining in hash tables. 3 CO3 L2

23 Discuss the structure and working of a skip list. 4 CO4 L2

24 Implement a hash table to store employee data using linear 4 CO3 L4

probing.

25 Design a priority queue using a list. Demonstrate insertion and 5 CO3 L3

deletion operations with complexity.

26 Illustrate the creation of a min-heap using the elements {10, 4, 15, 5 CO3 L3
20, 8, 7}.

27 Write a short note on dictionary ADT and its operations. 5 CO3 L2

28 Analyze the complexity of skip list insertion and deletion 5 CO4 L4

operations.

Unit 3

Search trees – Binary search tree, AVL tree and its rotation– Segment Trees - B-Trees.
Implementation. External Memory Sorting and Searching. Graphs: ADT- Data structure for graphs
- Graph traversal- Transitive Closure- Directed Acyclic graphs - Weighted graphs – Shortest Paths
- Minimum spanning tree – Greedy Methods for MST.

Persistent data structures, fusion trees, Bloom filter, Game Trees (Case Study)

[Link]. Question Marks CO Bloom’s

Level

29 Define an AVL tree. Why is balancing required? 2 CO3 L1

30 What is a segment tree? Mention its application. 2 CO4 L1

31 Differentiate between directed and undirected graphs. 2 CO3 L2

32 Construct a binary search tree using {60, 40, 80, 20, 50, 70, 90}. 8 CO3 L3
Show inorder traversal.

33 Explain the steps to delete a node with two children in a binary 4 CO3 L3
search tree.

34 Demonstrate insertion of nodes in an AVL tree that causes an RR 8 CO4 L4

rotation.

35 Discuss Prim’s algorithm in detail and apply it to find the minimum 5 CO4 L4
spanning tree for a given weighted graph. Show all intermediate
steps.

36 Construct a B-Tree of order 3 using the sequence {5, 8, 12, 15, 18, 8 CO3 L5
 22, 30, 35, 40}. Show all splits.

37 Compare the complexity and applications of BST, AVL, and B- 8 CO3 L4

Trees.

38 Explain Kruskal’s algorithm for MST and demonstrate with an 10 CO4 L3

example graph.

39 Write short notes on: (a) Fusion Trees (b) Persistent Data Structures 10 CO4 L5
(c) Bloom Filters (d) Game Trees