S.A. ENGINEERING COLLEGE, CHENNAI-77.

(An Autonomous Institution, Affiliated to Anna University)

QUESTION BANK
ODD SEMESTER, 2024- 2025
B.E. COMPUTER SCIENCE AND ENGINEERING
COMMON TO IT, CSBS, CYBER SECURITY, AI&DS
SUBJECT CODE : CS1301A
SUBJECT TITLE : DATA STRUCTURES
COURSE CO-ORDINATOR : Ms.L.Sudha
SEM/YEAR : III SEM/II YEAR
UNIT I - LINEAR DATA STRUCTURES – LIST
Abstract Data Types (ADTs) – List ADT – array-based implementation – linked list implementation ––
singly linked lists-doubly-linked lists – circularly-linked list-applications of lists –Polynomial
Manipulation
PART-A
S.NO QUESTIONS CO BLT COMPETENCE
LEVEL
1. Define ADT. Give any two examples. CO1 BTL-1 Remember
2. Define Data Structure. How are data structures classified? CO1 BTL-1 Remember
3. List the disadvantages of linked lists over arrays. CO1 BTL-1 Remember
4. What are common operations that can be performed on a data CO1 BTL-1 Remember
structure? List out the applications of data structures.
5. State the difference between arrays and linked lists CO1 BTL-2 Understand
implementation.
6. Distinguish between linear data structure and non-linear data CO1 BTL-2 Understand
structure.
7. Represent the following polynomial expression using an array CO1 BTL-2 Understand
and linked list. P(X) = 8X6+6X3+4X2+3X+5
8. Compare a singly linked list with a circular linked list. CO1 BTL-2 Understand
9. State the use of a linked list with an example. CO1 BTL-2 Understand
10. Write the representation of a node. Specify the use of Header CO1 BTL-1 Remember
node in a linked list.
PART-B
1. Consider the SLL which contains the following elements 42, CO1 BTL-3 Apply
78, 95, and 100. Insert 56 at the beg, insert 125 at the end,
insert 29 between 78 and 95, delete at the beginning, delete at
the end, and delete 95. Perform the above operations, represent
the list accordingly, and Illustrate SLL routines for each
category of insertion, deletion, search, and traverse.
2. Illustrate the ADT operations for linked list implementation of CO1 BTL-3 Apply
Polynomial addition. Represent the following polynomial
expression using an array and linked list.
P(X1) = 10X5+8X4+2X2+4X+6
P(X2) = 5x3+4x2+3x+2
3. Illustrate the various methods for inserting nodes into a doubly CO1 BTL-3 Apply
linked list, including insertion at the beginning, end, and a
specific position. Provide algorithms for each method,
explaining how pointers are managed to maintain the list's
integrity. Illustrate each algorithm with examples
demonstrating the insertion process in a practical context.
4. Demonstrate step-by-step procedure to insert and delete nodes CO1 BTL-3 Apply
at both the beginning and end of a circular linked list. Include
a detailed example demonstrating these operations,
highlighting how the circular nature affects traversal and
manipulation of pointers or references.
5. Consider an array A [1: n] Given a position, write an CO1 BTL-3 Apply
algorithm to insert an element in the Array. If the position is
empty, the element is inserted easily. If the position is already
occupied the element should be inserted with the minimum
number of shifts. (Note: The elements can shift to the left or
to the right to make the minimum number of moves).
6. Illustrate an algorithm for inserting and deleting an element CO1 BTL-3 Apply
from the singly linked list with its representations. Explain the
procedures in detail, highlighting how each operation modifies
the list's structure.
7. Formulate an algorithm to perform the following operations in CO1 BTL-3 Apply
a doubly linked list. Insert a node at the beginning and end of
the list and delete the first and last node in the list.
8. Sketch the ways to insert a node in a linked list? Write an CO1 BTL-3 Apply
algorithm for inserting a node as the first node in a linked
list, the last node in a linked list, and before a given node in
a linked list.
9. Infer in detail how operations commonly associated with lists, CO1 BTL-3 Apply
such as insertion, deletion, and traversal, are implemented
using arrays as the underlying data structure.
 10. Compare and contrast the insertion and deletion operations in CO1 BTL-4 Analyze
circular linked lists and doubly linked lists. Provide a detailed
explanation of how these operations differ in terms of
implementation, efficiency, and handling of pointers or
references within each data structure.

UNIT II - LINEAR DATA STRUCTURES – STACKS, QUEUES

Stack ADT – Operations – Evaluating arithmetic expressions- Other Applications-Conversion of Infix to
postfix expression – Queue ADT – Operations – Circular Queue –Double Ended Queues – applications
of queues
PART-A
S.NO QUESTIONS CO BT COMPETENCE
LEVEL
1. State the advantage of representing a stack using a linked list CO2 BTL-2 Understand
rather than an array.
2. Point out the rules followed during the infix to postfix CO2 BTL1 Remember
conversions.
3. Write the routine to push an element into a stack. CO2 BTL-2 Understand
4. Sketch representation of queue as an array? Enlist the queue CO2 BTL1 Remember
operations.
5. For railway reservations, the queue data structure is preferred CO2 BTL-2 Understand
–Justify.
6. What are priority queues? List out its application. CO2 BTL1 Remember
7. List any five applications of stack. CO2 BTL2 Understand
8. Describe how the following "infix" expression is evaluated CO2 BTL1 Remember
with the help of the help of Stack: 12 + 3 * 14 – (5 * 16) +7.
9. Define double ended queue. CO2 BTL1 Remember
10. Why circular queue is better than a standard linear queue? CO2 BTL2 Understand
11. How the queue is implemented by a linked list? CO2 BTL2 Understand
PART-B
 1. Interpret about Stack ADT using an array-based CO2 BTL-3 Apply
implementation with example representation.
2. Sketch an algorithm to convert an infix expression to a CO2 BTL-3 Apply
postfix expression. Trace the algorithm to convert the
following infix expression to a postfix expression.
i. A+(B*C-(D/E^F)*G)*H
ii.((A-(B+C)*D)$(E+F))
3. Infer how Stack operations are implemented using a linked CO2 BTL-3 Apply
list implementation.
4. Illustrate in detail about Queue ADT using linked list CO2 BTL-3 Apply
implementation.
5. Demonstrate insertion and deletion operations performed on a CO2 BTL-3 Apply
circular queue. Outline the routines in detail.
6. Sketch an algorithm to implement queue operations using CO2 BTL-3 Apply
arrays and show the operations with relevant examples.
7. Develop an algorithm to perform the four operations in a CO2 BTL-3 Apply
double ended queue that is implemented as an array.
8. Convert the following infix expression to a postfix expression CO2 BTL-3 Apply
with a neat sketch using stacks (A/(B-C+D))(E-A)*C).
Outline the algorithm for evaluating a postfix expression
using the stack data structure. Evaluate the postfix expression
A-2,B-3,C-4,D-2,E-3
9. Perform the following operations in the given order on an CO2 BTL-3 Apply
empty stack of size 5. Display the stack after each operation.
Mention the top of the stack, push (20), push (72), push (68),
pop (), push (84), push (10), pop. Sketch the stack operations
routines.
10. Show the procedure for performing enqueue(), dequeue(), CO2 BTL-3 Apply
isempty(), isfull() operations in a queue data structure with
example data representation.

UNIT III - NON LINEAR DATA STRUCTURES – TREES

Introduction to Tree ADT – Implementations of trees- Binary Tree ADT -tree traversals -expression trees ––
binary search tree ADT –Threaded Binary Trees- AVL Trees –Multi-way Search Trees-B-Tree – B+ Tree- Heap-
Priority Queue
PART-A
S.NO QUESTIONS CO BT COMPETENCE
LEVEL
1. Number the following binary tree to traverse it in
CO3 BTL-2 Understand
i.Preorder ii.Inorder

2. Give the pre & postfix form of the expression (a +

CO3 BTL-2 Understand
((b*(c-e))/f).

3. Express tree traversal for the following tree. CO3 BTL-2 Understand

4. Define balance factor of AVL tree. How do we

calculate the balance factor for each node in an AVL CO3 BTL-2 Understand
tree?
5. Discuss with respect to following tree: CO3 BTL-2 Understand
a)List the siblings for node E.
b)Compute the height

6.
What are threaded binary trees? Give its advantage CO3 BTL-2 Understand
7.
Define a heap and show how it can be used to represent CO3 BTL 1 Remember
a priority queue.
8.
How binary search tree differ from binary tree? List out CO3 BTL-2 Understand
the applications of trees.
9.
What are the rules to be followed to construct a binary CO3 BTL-2 Understand
search tree? why binary search cannot be performed on
a linked list.
10.
Define a full binary tree and complete binary tree. Give CO3 BTL-2 Understand
an example.
PART-B
1. Examine BST for the following elements, 7,5,1,8, CO3 BTL-4 Analyze
3,6,10,9,4,2. Write an algorithm for preorder, in order
and postorder traversal of a binary tree. Compute the
tree traversal for the above tree.
2. Inspect the various methods in which a binary tree can
CO3 BTL-4 Analyze
be represented.
Draw B – Tree for order m = 5 for the keys {K, O, S,
V, M, F, B, G, T, U, W}
Delete the keys K and G in order.
3. Compare B trees with B+ trees. Construct B+ tree of
CO3 BTL-4 Analyze
order 5 for the following data: 7,10,1,23, 5,15,17, 9,11,
39,35,8,40,25
4. i. Show the result of inserting 10,14,9,16,8,4,7,3,1,2
CO3 BTL-3 Apply
one at a time into an initially empty binary min heap
and max heap.
ii. Show the result of performing three delete min
operations in the final binary min heap obtained.

5. Construct an empty AVL search tree, insert the

CO3 BTL-3 Apply
following elements in the given
order:5,12,10,9,8,14,23,29,28,17. Explain each step
with its algorithm. Delete the following elements
14,9,28.
6. i) Interpret the construction of expression tree
CO3 BTL-3 Apply
with example.
ii)List the applications of trees.
7. Consider the binary search tree given below.
CO3 BTL3 Apply
Find the result of in-order, pre-order, and
post-order traversals. Show the deletion of the
root node
Insert 11, 22, 33, 44, 55, 66, and 77 in the tree
 8. i)Inference a B+ tree for (1, 4, 7, 10, 17, 21, 31,
CO3 BTL-4 Analyze
25, 19, 20, 28, 42) with n=4 and delete the
following keys after construction 10,19.
Perform the tree traversals for the final tree.
ii) Infer the max heap algorithm. Construct a max heap
with the following set of numbers
10,5,14,7,12,18,15,13.Perform the deletion 3 times in
the final heap.
9. i) Convert the given binary tree into threaded binary
CO3 BTL-3 Apply
tree using single threaded binary tree method and
double threaded binary tree method.

ii)Do the following operations in binary search tree,

insert(root,5), insert(root,1), insert(root,15),
insert(root,9), insert(root,7), insert(root,12),
insert(root,30), insert(root,25), insert(root,40), insert
(root, 45), insert (root, 42), in order(root), delete (root,
1), delete(root,9), delete(root,30). Perform tree traversal
after the construction of the tree.
10. Interpret an algorithm for inserting and deleting a node
CO3 BTL-3 Apply
in a binary search tree.
11. i) Construct an expression tree for the expression
CO3 BTL-3 Apply
(a + b * c)+((d * e + 1) * g). Give the outputs when you
apply pre order, in order and post order traversals.
ii) Explain AVL tree ADT in detail.
12. Explain B+trees with an algorithm to insert a node into
CO3 BTL-3 Apply
a B+tree. Explain the min heap insertion and deletion
operation in detail with example data.

UNIT IV - GRAPHS AND HASHING

Graph and their representations-Graph Traversal Techniques: Breadth First Search (BFS) and Depth First Search
(DFS)-Topological Sort- Hashing- Hash Functions – Collision in hashing-Separate Chaining – Open
Addressing-Rehashing-Applications of Hashing
PART-A
S.NO QUESTIONS CO BT COMPETENCE
LEVEL
1. What are the advantage and disadvantage of separate CO4 BTL-1 Understand
chaining and linear probing?
2. Express how a graph differs from a spanning tree with CO4 BTL-2 Understand
an example.
3. State the uses of topological sort. CO4 BTL-1 Remember
4. CO4 BTL-2 Understand
How do you calculate the in-degree and out-degree of
each node in the given graph?

5. Illustrate the steps in the construction of adjacency CO4 BTL-2 Understand

matrix for the following graph

6. Write the graph representation for the following graph, CO4 BTL-2 Understand

7. Define hashing? List out the properties of good hash CO4 BTL-1 Remember
function.
8. Differentiate cyclic and acyclic graph. What is meant CO4 BTL-1 Remember
by strongly connected and weakly connected in a
graph?
9. List out various types of graph. List out two CO4 BTL-1 Remember
applications of graph.
10. What is the degree of vertex 4 and 7? CO4 BTL-2 Understand
 PART-B
1. Let the size of the hash table be 10.The index of the CO4 BTL – 3 Apply
hash table varies from 0 to 9.Consider the keys
43,24,57,12,10,64,19,82,36,39 in the order. Show how
the keys are occupied. Use chaining method, linear
probing and quadratic probing method to avoid
collisions.
2. Apply BFS and DFS on the below graph and explain CO4 BTL-3 Apply
its algorithm with its routines.

3. Given input {4371, 1323, 6173, 4199, 4344, 9679, CO4 BTL-3 Apply
1989} and a hash function h(x)=x(mod 10), show the
resulting
i. Open hash table
ii. Closed hash table using linear probing
iii. Closed hash table using quadratic probing

4. Explain in detail about graph traversal techniques with CO4 BTL-3 Apply
its routines. Write the BFS algorithm and traverse it
starting from the vertex 1 showing various stages. For
the same graph compute DFS.
5. Outline about the common collision resolution CO4 BTL-4 Analyze
strategies used in closed hashing system.
6. Examine a hash table with 9 slots. The hash function is CO4 BTL-4 Analyze
h(k) = k mod 9. The following keys are inserted in the
order 5, 28, 19, 15, 20, 33, 12, 7, 10. Draw the contents
of the hash table when the collisions are resolved by
i) Chaining ii) Linear Probing iii) Double Hashing.
The second hash function h2(x) = 7 – (x mod 7)
7. Compare and Contrast Breadth First and Depth First CO4 BTL-4 Analyze
traversal of a graph. List the order in which the
nodes of the undirected graph shown below are
visited by a i) Breadth first Traversal that starts from
vertex A and ii) Depth First Traversal that starts
from vertex D.

8. Illustrate topological sort with an algorithm. Construct CO4 BTL-3 Apply

the topological sort for the given graph.
 UNIT V - SEARCHING AND SORTING
Searching- Linear Search – Binary Search. Sorting – Bubble Sort – Selection Sort – Insertion Sort –
Quick Sort-Merge Sort-Shell Sort – Radix Sort-Heap Sort.
PART-A
S.NO QUESTIONS CO BT COMPETENCE
LEVEL
1. What is Divide and Conquer? State an example which CO5 BTL-1 Remember
uses the same strategy in sorting.
2. State the difference between linear search and binary CO5 BTL-2 Understand
search.
3. What is meant by internal and external sorting? Give CO5 BTL-1 Remember
examples of each type.
4. Which type of searching is best? Why? CO5 BTL-2 Understand
5. Select the best sorting method out of the following – CO5 BTL-2 Understand
insertion sort, quick sort and merge sort and give
justification.
6. Predict the fastest sorting algorithm, justify. CO5 BTL-2 Understand
7. Distinguish which sorting technique are in-place sort CO5 BTL-2 Understand
and which are not.
8. Give the time complexities of bubble sort and quick CO5 BTL-2 Understand
sort.
9. Identify the advantage of shell sort over insertion sort. CO5 BTL-1 Remember
10. What is sorting? CO5 BTL-1 Remember
PART-B
1. (i)Explain how the binary search technique is applied CO5 BTL-3 Apply
to the following list in step by step manner with an
algorithm. Find element 23 in the given elements in
the list 2, 5,8,12,16,23,38,56,72,91 using binary
search.
(ii)Sort the list using the selection sort technique: 10,
15, 87, 42, 24, 22, 7, 56, 65, and 50.
2. (i)Apply Quick sort for the following elements and CO5 BTL-3 Apply
write the procedure for the same
45,20,70,14,60,61,97,35
(ii) Sort the following numbers using radix sort:
77,12,8,39,27,21,44,18,6,427,117,237,5671 and 600.

3. i) Distinguish between linear search and binary CO5 BTL-4 Analyze

search. State and explain the algorithms for both the
search with example.
ii) Illustrate explain Heap sort. Sort the elements
using Heap sort 1 5 3 4 10
4. i) Write the routine for Insertion sort. Sort the CO5 BTL-3 Apply
following sequence using Insertion sort.
12,19,33,26,29,35,22.
ii)Demonstrate Bubble sort for the following elements
15,45,10,11, 9,12,67,4,

5. Interpret sorting for the following elements CO5 BTL-3 Apply

respectively
Radix sort - 326, 453,608,835,751,435,704,690
Shell sort – 9,8,34,70,5,6,4,1,12,82,3,7

COURSE CO ORDINATOR EVALUATOR HOD/CSE