SECTION A: (Any 5)
(i) Define Abstract Data Type (ADT)?
ADT is a data structure that defines operations without specifying implementation, ensuring
data abstraction, encapsulation, and modularity for efficient algorithm design.
(ii) What is the postfix expression?
A postfix expression is a mathematical notation where operators follow operands, eliminating
parentheses and simplifying evaluation (e.g., 3 4 + instead of 3 + 4).
(iii) What is the concept of recursion?
Recursion is a technique where a function calls itself, solving complex problems by breaking
them into smaller subproblems until a base condition is met.
(iv) What is the difference between PUSH and POP?
PUSH inserts an element into a stack, while POP removes the top element, following the
LIFO (Last In, First Out) principle in stack operations.
(v) What is a linear linked list?
A linear linked list is a dynamic data structure where nodes are connected sequentially, each
pointing to the next, allowing efficient insertion and deletion.
(vi) What is the difference between linear search and binary search?
Linear search sequentially checks each element, while binary search divides a sorted list into
halves, reducing comparisons and improving efficiency.
(vii) How does the Bubble Sort work?
Bubble Sort compares adjacent elements and swaps them if in the wrong order, repeatedly
passing through the list until fully sorted.
(viii) What is a Binary Tree?
A binary tree is a hierarchical structure where each node has at most two children (left and
right), facilitating efficient searching and sorting.
(ix) What is an AVL Tree?
An AVL tree is a self-balancing binary search tree that maintains a height difference of at
most one between subtrees for optimized searching.
(x) Which data structures are used in BFS and DFS algorithms?
BFS uses a queue (FIFO) for level-wise traversal, while DFS uses a stack (explicit or
recursion) for depth-first exploration.
SECTION B: (Any 3)
Q2. Differentiate between Linear and Non-Linear Data Structures
Feature Linear Data Structure Non-Linear Data Structure
Definition Data arranged sequentially. Data connected hierarchically.
Feature Linear Data Structure Non-Linear Data Structure
Examples Array, Linked List, Stack, Queue Tree, Graph, Hash Table
Traversal Sequential (one by one). Multiple ways (DFS, BFS).
Memory Usage Uses contiguous/linked memory. Uses dynamic memory allocation.
Complexity Simpler operations. More complex structures and operations.
Algorithms:
• Linear: Linear Search, Stack (PUSH/POP), Queue (ENQUEUE/DEQUEUE).
• Non-Linear: DFS, BFS, Binary Search Tree (Insert/Delete/Search).
Q3. Different Types of Linked Lists
1. Singly Linked List:
o Nodes linked sequentially; each node points to the next.
o Example operations: Insertion, Deletion, Traversal.
2. Doubly Linked List:
o Each node contains two pointers (next and previous).
o Faster bidirectional traversal but requires extra memory.
3. Circular Linked List:
o Last node points to the first (forms a loop).
o Used in scheduling and memory management.
Algorithms:
• Insert at Beginning/End
• Delete a Node
• Reverse a Linked List
Q4. Binary Tree Traversal Methods
1. Inorder Traversal (LNR - Left, Node, Right):
o Visits left subtree → root → right subtree.
o Example: Sorting elements in BST.
2. Preorder Traversal (NLR - Node, Left, Right):
o Visits root → left subtree → right subtree.
o Used in creating tree copies.
3. Postorder Traversal (LRN - Left, Right, Node):
o Visits left subtree → right subtree → root.
o Used in deleting trees.
Algorithm Example (Inorder Traversal - Recursive):
void inorder(Node* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
Q5. C++ Program for Binary Search
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int key = 30, size = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, size - 1, key);
(result != -1) ? cout << "Element found at index " << result : cout << "Element not found";
return 0;
Q6. Graph Traversal Methods
1. Breadth-First Search (BFS):
o Uses a queue (FIFO) to explore neighbors first.
o Best for shortest path problems.
Algorithm:
o Start at a node, visit all adjacent nodes before moving deeper.
2. Depth-First Search (DFS):
o Uses a stack (or recursion) to explore as deep as possible before backtracking.
o Useful for cycle detection and pathfinding.
Algorithm:
o Visit a node → go deeper → backtrack when needed.
Algorithm Example (BFS - C++):
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void BFS(vector<int> adj[], int start, int n) {
vector<bool> visited(n, false);
queue<int> q;
[Link](start);
visited[start] = true;
while (![Link]()) {
int node = [Link]();
[Link]();
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
int main() {
vector<int> adj[5] = {{1, 2}, {0, 3, 4}, {0, 4}, {1}, {1, 2}};
BFS(adj, 0, 5);
return 0;
SECTION C: (Any 2)
Q7. Convert Infix Expression to Prefix and Postfix
Given Infix Expression:
(A+B)∗C/D+EF/G(A + B) * C / D + E^F / G(A+B)∗C/D+EF/G
Steps to Convert to Postfix:
1. Convert parentheses first.
2. Follow operator precedence: ^ > * / > + -.
3. Left to right for + - * /, right to left for ^.
Postfix Expression:
AB+C∗D/EFG/+A B + C * D / E F ^ G / +AB+C∗D/EFG/+
Steps to Convert to Prefix:
1. Reverse the infix expression.
2. Convert to postfix using the same precedence rules.
3. Reverse the result.
Prefix Expression:
EFG+ / * + A B C D / ^ E F G+/∗+ABCD/EFG
C++ Program to Convert Infix to Postfix
#include <iostream>
#include <stack>
using namespace std;
int precedence(char op) {
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
string infixToPostfix(string infix) {
stack<char> st;
string postfix = "";
for (char ch : infix) {
if (isalnum(ch))
postfix += ch;
else if (ch == '(')
[Link](ch);
else if (ch == ')') {
while (![Link]() && [Link]() != '(') {
postfix += [Link]();
[Link]();
[Link]();
else {
while (![Link]() && precedence([Link]()) >= precedence(ch)) {
postfix += [Link]();
[Link]();
}
[Link](ch);
while (![Link]()) {
postfix += [Link]();
[Link]();
return postfix;
int main() {
string infix = "(A+B)*C/D+E^F/G";
cout << "Postfix Expression: " << infixToPostfix(infix) << endl;
return 0;
}
Q8. C++ Program to Build a Linked List and Display Nodes
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
};
class LinkedList {
public:
Node* head;
LinkedList() { head = NULL; }
void insertEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
void display() {
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
};
int main() {
LinkedList list;
[Link](10);
[Link](20);
[Link](30);
cout << "Linked List: ";
[Link]();
return 0;
}
Q9. Properties of AVL Tree
An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference
between the left and right subtrees is at most 1 for every node.
Key Properties:
1. Balance Factor: Difference between left and right subtree heights must be -1, 0, or 1.
2. Rotations: Balancing is done using LL, RR, LR, and RL rotations when inserting
or deleting nodes.
3. Efficient Operations:
o Insertion, Deletion, and Search take O(log n) time.
o Better performance than unbalanced BSTs.
4. Self-Balancing: Ensures logarithmic height for faster operations.
Example AVL Tree:
markdown
30
/ \
20 40
/ \ \
10 25 50
Here, the balance factor for each node is within [-1,1], maintaining AVL tree properties.
Q10. Weighted Graph and Sub-Graph
Weighted Graph
A weighted graph is a graph where edges have weights (numerical values) representing cost,
distance, or time.
Example:
(A) --5-- (B)
| /
3 2
| /
(C)
Here, edges (A-B), (A-C), and (B-C) have weights 5, 3, and 2, respectively.
Applications:
• Shortest path problems (Dijkstra’s Algorithm).
• Network routing, transportation planning.
Sub-Graph
A sub-graph is a portion of a graph containing some of its nodes and edges.
Example:
If the original graph is:
A -- B -- C -- D
A sub-graph could be:
A -- B
It retains edges and nodes but is a smaller part of the original