Document information: This past examination paper is identified as an IOE/TU academic document and was cataloged from a public Google Drive archive. This independent website did not create the examination paper and is not affiliated with TU or IOE.
Rights holders can request correction or removal by emailing subeshgaming@gmail.com with this page URL and supporting details.
Most Frequently Asked Questions
Top recurring IOE board exam questions for Data Structure and Algorithum with verified mark schemes, formula notation, and recurrence frequency.
Showing 30 of 30 top repeated questions
Introduction
3 Questions
#1Repeated 6 Times[4 Marks]Introduction
What do you mean by asymptotic notations? Define Big-O, Omega (Ω), and Theta (Θ) notations with their mathematical definitions and graphical diagrams. Explain how time and space complexity of an algorithm are analyzed.
Appeared in:2082 Kartik2080 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#2Repeated 5 Times[4 Marks]Introduction
Define data structure and Abstract Data Type (ADT). Briefly explain why Stack, Queue, and List are called Abstract Data Types with suitable examples demonstrating abstraction and encapsulation.
Appeared in:2082 Kartik2080 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh
#3Repeated 2 Times[6 Marks]Introduction
Define Abstract Data Type (ADT). Explain asymptotic notations (Big-O, Big-Omega $\Omega$, Big-Theta $\Theta$) used in algorithm analysis with mathematical definitions and graphical plots.
Appeared in:2082 Kartik2081 Chaitra
Stack and Recursion
2 Questions
#1Repeated 6 Times[8 Marks]Stack and Recursion
Explain how recursion uses the stack data structure with an illustrative call stack diagram. Write an algorithm to solve the Tower of Hanoi (TOH) problem for n disks and draw the recursion tree for 3 disks.
Appeared in:2082 Kartik2080 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#2Repeated 2 Times[8 Marks]Stack and Recursion
Explain the principle of Divide and Conquer. Write a recursive function to solve the Tower of Hanoi problem for $N$ disks and analyze its time complexity.
Appeared in:2082 Kartik2081 Chaitra
Linked List
8 Questions
#1Asked in 7 Exam Sessions[8 Marks]Linked List
Define stack. Write an algorithm for converting an infix expression to a postfix expression. Convert the given infix expression to postfix showing the status of the stack after every step: A * (B + C) - (B ^ D) * A + E / F or (A * B * (((C ^ X + D ^ Y) + E / Z) * F)).
Appeared in:2082 Kartik2080 Chaitra2079 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#2Repeated 5 Times[6 Marks]Linked List
Differentiate between linear queue and circular queue with suitable diagrams. Write down conditions for queue full and queue empty in a circular queue. Write algorithms for enqueue and dequeue operations in a circular queue.
Appeared in:2082 Kartik2079 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#3Repeated 5 Times[10 Marks]Linked List
Explain how linked lists are used to represent and add/subtract two polynomial equations. Write an algorithm and program to implement addition of two polynomials using singly linked lists.
Appeared in:2080 Chaitra2078 Chaitra2076 Bhadra2074 Ashwin2072 Kartik
#4Repeated 5 Times[8 Marks]Linked List
Explain operations of stack and queue using linked lists. Write an algorithm to insert a node at the k-th position of a doubly linked list and delete the n-th node from a singly linked list.
Appeared in:2080 Chaitra2077 Chaitra2076 Baisakh2074 Ashwin2072 Kartik
#5Repeated 4 Times[5 Marks]Linked List
Evaluate the given postfix expression using a stack showing the stack status at each operand and operator token: A B C * + D E ^ / F G * - where A = 2, B = 3, C = 10, D = 5, E = 2, F = 4, and G = 6.
Appeared in:2080 Chaitra2076 Baisakh2074 Ashwin2071 Chaitra
#6Repeated 2 Times[8 Marks]Linked List
Explain circular queue and its advantages over linear queue. Write C functions for `enqueue()` and `dequeue()` operations on a circular queue implemented using an array.
Appeared in:2082 Kartik2080 Chaitra
#7Repeated 2 Times[8 Marks]Linked List
What is a doubly linked list? Write an algorithm or C function to insert a new node at a given position and delete a node with a specific value from a doubly linked list.
Appeared in:2081 Chaitra2079 Chaitra
#8Repeated 2 Times[6 Marks]Linked List
Evaluate the postfix expression: $12, 7, 3, -, /, 2, 1, 5, +, *, +$ showing the status of the stack at each step.
Appeared in:2082 Shrawan2078 Bhadra
Tree
6 Questions
#1Asked in 7 Exam Sessions[8 Marks]Tree
Describe an AVL tree. Construct an AVL balanced tree showing balance factors and rotation operations (LL, RR, LR, RL) after each insertion for the following sequence of data: 15, 20, 24, 10, 13, 7, 30, 36, 25 (or 18, 27, 9, 11, 36, 54, 81, 63, 72).
Appeared in:2082 Kartik2080 Chaitra2079 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#2Repeated 5 Times[6 Marks]Tree
Construct a Huffman code tree for the given set of symbols with their frequencies: A (35), B (18), C (10), D (20), E (9), F (8). Determine the binary code word for each symbol and calculate the average code length.
Appeared in:2080 Chaitra2078 Chaitra2075 Ashwin2073 Shrawan2070 Ashad
#3Repeated 5 Times[8 Marks]Tree
Explain deletion of a node having two children in a Binary Search Tree (BST) using in-order predecessor or in-order successor. Describe insertion and node-splitting operations in a B-tree with an example.
Appeared in:2079 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra2072 Kartik
#4Repeated 2 Times[8 Marks]Tree
What is a Binary Search Tree (BST)? Write an algorithm to insert a node, delete a node with two children, and search for a given key in a BST.
Appeared in:2082 Kartik2080 Chaitra
#5Repeated 2 Times[8 Marks]Tree
Define B-Tree of order $M$. Construct a B-Tree of order 4 (2-3-4 tree) by inserting the keys: $5, 12, 8, 22, 15, 30, 25, 18, 40, 35$.
Appeared in:2081 Chaitra2079 Chaitra
#6Repeated 2 Times[8 Marks]Tree
Explain tree traversal algorithms (Inorder, Preorder, Postorder). Construct a binary tree whose Inorder and Preorder traversals are: Inorder: D, B, H, E, A, I, F, J, C, G; Preorder: A, B, D, E, H, C, F, I, J, G.
Appeared in:2082 Kartik2078 Bhadra
Graphs
4 Questions
#1Repeated 6 Times[8 Marks]Graphs
Define Minimum Spanning Tree (MST). Explain Kruskal's algorithm to find the MST of a weighted connected graph. Construct the MST for the given graph showing each intermediate edge selection step and calculate total cost.
Appeared in:2082 Kartik2080 Chaitra2079 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh
#2Repeated 5 Times[6 Marks]Graphs
Define Breadth First Search (BFS) and Depth First Search (DFS) graph traversal algorithms. Illustrate both traversals on a given directed/undirected graph with 6 vertices showing the traversal order and tree edges.
Appeared in:2080 Chaitra2077 Chaitra2076 Bhadra2073 Shrawan2071 Chaitra
#3Repeated 2 Times[8 Marks]Graphs
Explain Breadth First Search (BFS) and Depth First Search (DFS) graph traversal algorithms. Write their algorithms and trace BFS and DFS on a given directed graph starting from vertex 1.
Appeared in:2082 Kartik2080 Chaitra
#4Repeated 2 Times[8 Marks]Graphs
Explain Dijkstra's Single Source Shortest Path algorithm. Trace Dijkstra's algorithm to find the shortest distance from source vertex A to all other vertices in a weighted graph.
Appeared in:2081 Chaitra2078 Bhadra
Sorting Algorithms
5 Questions
#1Repeated 5 Times[8 Marks]Sorting Algorithms
Create a max-heap showing each insertion step for data: 28, 24, 50, 36, 42, 58, 22, 56, 46. Use the same heap tree to sort the data in ascending order showing all intermediate heapify and deletion steps.
Appeared in:2082 Kartik2078 Chaitra2077 Chaitra2076 Bhadra2073 Chaitra
#2Repeated 5 Times[8 Marks]Sorting Algorithms
Write an algorithm for Quick Sort. Trace the quick sort algorithm step-by-step to sort the following numbers: 30, 25, 79, 19, 48, 28, 21, 44, and 110.
Appeared in:2080 Chaitra2078 Chaitra2076 Baisakh2074 Ashwin2071 Chaitra
#3Repeated 2 Times[8 Marks]Sorting Algorithms
Explain Merge Sort algorithm with a Divide and Conquer approach. Trace the algorithm for sorting the list: $38, 27, 43, 3, 9, 82, 10$ and prove its time complexity is $O(N \log N)$.
Appeared in:2082 Kartik2081 Chaitra
#4Repeated 2 Times[8 Marks]Sorting Algorithms
Explain Quick Sort algorithm. Trace Quick Sort for partitioning the array $[25, 57, 48, 37, 12, 92, 86, 33]$ with the first element as pivot. Discuss best-case, average-case, and worst-case time complexities.
Appeared in:2081 Chaitra2080 Chaitra
#5Repeated 2 Times[8 Marks]Sorting Algorithms
Explain Heap Sort algorithm. Build a Max-Heap from the array $[15, 30, 8, 45, 20, 50, 10]$ and sort it using Heap Sort.
Appeared in:2082 Kartik2079 Baishakh
Searching Algorithms
2 Questions
#1Asked in 7 Exam Sessions[8 Marks]Searching Algorithms
What is collision in hashing? What are the techniques used for collision resolution? Insert the keys: 62, 37, 36, 44, 67, 91, 82, and 31 into a hash table of size 10 using quadratic probing (or linear probing) where hash function h(key) = key % 10.
Appeared in:2082 Kartik2080 Chaitra2079 Chaitra2078 Chaitra2077 Chaitra2076 Baisakh2076 Bhadra
#2Repeated 2 Times[8 Marks]Searching Algorithms
Compare linear search and binary search. Explain open addressing (linear probing, quadratic probing, and double hashing) vs separate chaining for collision resolution in hash tables.