Data Structure
BCS 301
30 Important Questions
Unit 1:
1. Explain Asymptotic Notations: Big-O, Big-Theta, and Big-Omega with
examples.
Session: 2022-23
2. Analyze the time complexity of the following code snippet:
Session: 2021-22
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
printf("*");
}
3. Illustrate the Time-Space Trade-off with an example.
Session: 2019-20 , 2020-21
4. Derive the formula to calculate the memory location of an element in Row
Major Order and Column Major Order.
Session: 2020-21
5. For a 3x3 array stored in Row Major Order, calculate the address of
element A[2][1]A[2][1], assuming the base address is 200 and each
element takes 4 bytes.
Session: 2020-21, 2022-23, 2023-24
6. Write the algorithm for create, insertion and deletion in a singly linked list
and doubly linked list.
Session: 2018-19 , 2022-22, 2022-23
7. Represent the polynomial 4x3+3x2+54x^3 + 3x^2 + 5 using a linked list.
Session: 2019-20 ,2022-23, 2023-24
8. Define the Abstract Data Type (ADT) of a stack.
Session: 2019-20
Unit 2:
9. Write algorithms for Push and Pop operations using arrays.
Session: 2022-23
[Link] the Tower of Hanoi problem for 3 disks.
Session: 2020-21
[Link] between normal queue, circular queue, and priority queue.
Session: 2018-19
[Link] algorithms for enqueue and dequeue operations in a circular queue.
Session: 2019-20
[Link] an algorithm to convert a valid arithmetic infix expression into an
equivalent prefix and postfix expression. Trace your algorithm for following
infix expression. 2021- 22, 2023-2024, 2022-23
A+B*C-D/F
Unit 3:
[Link] between sequential search and binary search.
Session: 2019-20, 2020-21
[Link] binary search to find the number 27 in the sorted array {10, 15,
20, 27, 30, 35}.
Session: 2020-21 , 2023-204
[Link] hashing and discuss any two collision resolution techniques.
Session: 2019-20 , 2022-23
[Link] the keys {10, 22, 31, 4, 15, 28} into a hash table of size 7 using
linear probing.
Session: 2021-22 , 2023-24.
[Link] algorithms of insertion sort. Implement the same on the following
numbers; also calculate its time complexity. 13, 16, 10, 11, 4, 12, 6, 7.
Session 2021-22
[Link] the array {23, 45, 12, 8, 67, 5} using Quick Sort. Session: 2021-22,
2022-23
Unit 4:
[Link] the following: Session: 2020-21
o Binary Tree
o Complete Binary Tree
o Strictly Binary Tree
[Link] a binary tree from the following traversals: Session: 2021-22,
2022-23
o Inorder: D B E A F C
o Preorder: A B D E C F
[Link] algorithms for inorder, preorder, and postorder traversal of a binary
tree.
Session: 2021-22
[Link] Huffman Coding and construct a Huffman tree for the following
character frequencies: Session: 2021-22, 2023-24
o A: 5, B: 9, C: 12, D: 13, E: 16, F: 45
[Link] the sequence {20, 10, 30, 5, 15, 25, 35} into an AVL tree. Perform
rotations wherever necessary. Session: 2019-20, 2022-23
[Link] is B-Tree? Write the various properties of B- Tree. Show the results of
inserting the keys F, S, Q, K ,C, L, H, T, V, W, M, R, N, P, A, B in order into a
empty B-Tree of order 5. . Session: 2021, 22, 2022-23
Unit 5:
[Link] the adjacency matrix and adjacency list representation of a graph.
Session: 2020-21
[Link] the algorithm for Prim's Algorithm and Kruskal’s and find the
Minimum Spanning Tree for the following graph: Session: 2021-22, 2022-
23, 2023-2024
o Vertices: {A, B, C, D}
o Edges with weights: {A-B: 1, B-C: 4, A-C: 2, C-D: 3}
[Link] the shortest path from vertex A to all other vertices using Dijkstra’s
algorithm for the following weighted graph: Session: 2021-22, 2022-23,
2023-24
o Vertices: {A, B, C, D, E}
o Edges and Weights:
A → B: 4
A → C: 2
B → C: 5
B → D: 10
C → D: 3
C → E: 2
D → E: 6
[Link] and explain the Floyd Warshall algorithm to find the all pair shortest
path. Use the Floyd Warshall algorithm to find shortest path among all the
vertices in the given graph: session 2022-23
[Link] an algorithm for Breadth First search (BFS) and explain with the help
of suitable example: Session 2020-21
