Data Structures & Algorithms – Complete Exam Guide 2025 | GATE, IBPS, SSC, UPSC

💻 Computer Science · Competitive Exam 2025

Data Structures &
Algorithms Master Guide

Array · Linked List · Stack · Queue · Tree · Graph · Hashing · Sorting · Searching · Big-O Notation · 50 MCQs with Explanations — for GATE, IBPS, SSC, UPSC, NDA & Campus Placements

GATE CSIBPS PO/ClerkSSC CGLUPSC GS-III NDA/CDSRBI Grade BCampus PlacementsBank Internal

📋 Table of Contents

1. What is a Data Structure? 2. Linear Data Structures 3. Non-Linear Data Structures 4. Comparison Table 5. Big-O & Complexity 6. Searching Algorithms 7. Sorting Algorithms 8. Tree Traversal Methods 9. Hashing 10. DS Operations Complexity 11. Banking & Real-World Apps 12. MCQ Practice (50 Qs) 13. Quick Revision Cards

📚

FoundationWhat is a Data Structure?

A Data Structure is a method of organising and storing data in a computer so it can be accessed and modified efficiently. Choosing the right data structure directly impacts the speed and memory usage of programs.

Term	Meaning	Example
Data	Raw facts (numbers, text, values)	Account number: 12345678
Structure	Organised format for storage	Rows and columns
Data Structure	Way to store and manage data efficiently	Array of account numbers
Algorithm	Step-by-step solution procedure	Sorting customer names A–Z
ADT	Abstract Data Type — defines behaviour without implementation	Stack, Queue are ADTs

⚡ Core Exam Facts

Data Structures are classified as Linear (sequential) and Non-Linear (hierarchical/networked)
Stack and Queue are ADTs (Abstract Data Types) — keyboards and integers are NOT
Data structures are stored in RAM (main memory) during execution
Wrong data structure = slower programs + excess memory usage
Used in: banking software, OS, databases, networking, AI — essentially all software

➡️

Data Arranged SequentiallyLinear Data Structures

📦

Array

Linear · Fixed Size

Collection of same-type elements stored in continuous memory. Access any element instantly using its index. Size fixed at declaration.

Access

O(1) by index

Insert/Delete Middle

O(n) — shifting needed

Memory

Continuous/contiguous

Size

Fixed at compile time

🔗

Linked List

Linear · Dynamic Size

Nodes connected via pointers. 10 → 20 → 30 → NULL. Types: Singly, Doubly, Circular. No continuous memory needed.

Insert at Head

O(1)

O(n) — traverse

Memory

Non-contiguous

Size

Dynamic

📚

Stack

LIFO — Last In, First Out

Like a stack of plates — last placed, first removed. Operations: Push (add) and Pop (remove). Peek to see top without removing.

Push/Pop

O(1)

O(n)

Overflow

top = maxSize−1

Underflow

top = −1 or NULL

🚶

Queue

FIFO — First In, First Out

Like a bank counter line — first to arrive, first to be served. Enqueue (insert at rear), Dequeue (remove from front). Variants: Circular, Priority, Deque.

Enqueue/Dequeue

O(1)

Insert at

Rear

Delete at

Front

Uses

BFS, scheduling, printing

🎯 Linear DS — Exam Key Points

LIFO → Stack | FIFO → Queue — most tested one-liner
Stack uses: Undo/Redo, recursion, DFS, expression evaluation, parentheses matching
Queue uses: BFS, printer scheduling, bank token system, OS scheduling
Last node of singly linked list has next pointer = NULL
Circular linked list: last node’s next points to Head
Doubly linked list: each node has prev + next pointers (traversal both ways)
Array first index = 0 in most programming languages

🌳

Data Arranged Hierarchically / NetworkedNon-Linear Data Structures

🌳

Tree

Hierarchical · Non-Linear

Nodes connected in parent-child hierarchy. Root (top), Leaf (no children). Binary Tree: max 2 children per node. BST: left < root < right.

Root

Topmost node

Leaf

Node with no children

BST Search

O(log n) balanced

Tree with n nodes

n−1 edges

🌐

Graph

Network of Nodes & Edges

Nodes (vertices) connected by edges. Can be directed/undirected, weighted/unweighted. A Tree is a special case of Graph (connected, acyclic).

BFS uses

Queue

DFS uses

Stack/Recursion

Adj. Matrix

O(n²) space

Adj. List

O(n+e) space

🔑

Hash Table

Key-Value · Fast Search

Stores data as key-value pairs. A hash function maps key → index. Average O(1) for search, insert, delete. Collision = two keys map to same index.

Search avg

O(1)

Search worst

O(n) — many collisions

Collision fix

Chaining, Linear probing

Used in

Databases, passwords

⛰️

Heap

Complete Binary Tree · Priority

Max Heap: largest element at root. Min Heap: smallest at root. Used to implement Priority Queue. Insert + Delete = O(log n).

Max Heap root

Largest element

Min Heap root

Smallest element

Insert/Delete

O(log n)

Priority Queue

Implemented via Heap

Term	Meaning	Exam Trigger
Root	Topmost node of tree	“Top of tree” = Root
Leaf	Node with no children	“No children” = Leaf
Height	Longest path from root to leaf	Single node height = 0 (most conventions)
BST property	Left < Root < Right	Inorder BST = sorted ascending order
Directed Graph	Edges have direction (→)	Also called Digraph
Undirected Graph	Edges have no direction (—)	Social network friendships
Weighted Graph	Edges have values (cost/distance)	Railway route map
AVL Tree	Self-balancing BST (balance factor −1, 0, 1)	Always balanced, O(log n) operations
B-Tree / B+ Tree	Multi-way balanced tree	Used in databases and file systems

⚖️

Most Tested TableData Structures Comparison

Feature	Array	Linked List	Stack	Queue
Type	Linear	Linear	Linear (restricted)	Linear (restricted)
Size	Fixed	Dynamic	Dynamic	Dynamic
Access	O(1) by index	O(n) traverse	Only top	Only front/rear
Memory	Continuous	Non-continuous	Either	Either
Logic	Index	Pointer	LIFO	FIFO
Insert middle	O(n) — shift	O(1) after node	Not applicable	Not applicable
Real-life	Book rack	Train coaches	Stack of plates	Bank queue

📊

Big-O Notation — Most TestedAlgorithm Complexity

Time Complexity = how long an algorithm takes as input size (n) grows. Space Complexity = how much memory it uses. Big-O notation describes the worst-case upper bound.

Complexity Order — Best to Worst

O(1)

Constant

O(log n)

Logarithmic

O(n)

Linear

O(n log n)

Linearithmic

O(n²)

Quadratic

O(2ⁿ)

Exponential

O(n!)

Factorial

Notation	Name	Meaning	Exam Focus
`O (Big-O)`	Upper bound	Worst case — maximum time taken	⭐⭐⭐⭐⭐ Most asked
`Θ (Theta)`	Tight bound	Average / exact growth rate	⭐⭐⭐
`Ω (Omega)`	Lower bound	Best case — minimum time	⭐⭐

Complexity	Example Algorithm/Operation	Exam Example
`O(1)`	Array access by index, Stack push/pop, Hash table access	arr[5] = value
`O(log n)`	Binary Search, BST balanced search	Search in sorted 1000 items = ~10 steps
`O(n)`	Linear Search, Linked List traversal	Find element in unsorted array
`O(n log n)`	Merge Sort, Quick Sort (average), Heap Sort	Best efficient sorting for large data
`O(n²)`	Bubble Sort, Selection Sort, Insertion Sort	Basic/naive sorting algorithms
`O(2ⁿ)`	Recursive Fibonacci, subset enumeration	Exponential — avoid for large n

🔍

Two Key AlgorithmsSearching Algorithms

Algorithm	Prerequisite	Best Case	Average Case	Worst Case	Banking Use
Linear Search	None — works on unsorted data	O(1) — first element	O(n/2)	O(n)	Search transaction in unsorted log
Binary Search	Data must be sorted	O(1) — middle element	O(log n)	O(log n)	Search customer by account no. in sorted file

📌 Searching — Exam Key Points

Binary Search requires sorted data — if unsorted, must use linear search
Binary Search worst case = O(log n) — much better than O(n) for large datasets
In 1000 elements: Linear Search = up to 1000 comparisons | Binary Search = up to 10 comparisons
Binary Search works on arrays (random access) NOT on linked lists (no O(1) access)
Symbol for array element access: arr[index] — uses [ ] brackets

🔢

Know Complexities — Very Frequently TestedSorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Stable?	Type
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes	Comparison
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌ No	Comparison
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes	Comparison
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ Yes	Divide & Conquer
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ No	Divide & Conquer
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ No	Heap-based

🎯 Sorting — Exam Key Points

Bubble/Selection/Insertion = O(n²) — basic, slow for large data
Merge/Quick/Heap = O(n log n) average — efficient for large data
Quick Sort worst case = O(n²) (when pivot is always min/max)
Merge Sort = Divide and Conquer | Always O(n log n) — most stable and reliable
Stable sort = maintains relative order of equal keys (Bubble, Insertion, Merge)
Heap Sort = uses heap data structure | Space O(1) in-place

🌳

All 4 Methods — Exam FavouriteTree Traversal Methods

Preorder

Root → Left → Right

Memory: Root comes PRE (before children). Used for: prefix expression, copying tree

Inorder

Left → Root → Right

Gives sorted order for BST. Most tested. Used for: sorted output of BST

Postorder

Left → Right → Root

Root comes POST (after children). Used for: postfix expression, deleting tree

Level Order

Level by level (top to bottom)

Uses a Queue (BFS). Visits all nodes at each depth before going deeper

🎯 Traversal — Exam Memory Tricks

Inorder BST = sorted ascending — most asked single fact about BST traversal
Preorder = Root FIRST | Inorder = Root MIDDLE | Postorder = Root LAST
Level order traversal uses Queue (BFS); DFS uses Stack/recursion
Preorder → prefix expression | Inorder → infix | Postorder → postfix
BST with keys [5, 10, 15]: Inorder = 5, 10, 15 (sorted!) — always verify this

🔑

Fast O(1) LookupHashing & Hash Tables

Hashing = technique to map a key to an array index using a hash function, enabling O(1) average search. A Hash Table stores data as key-value pairs. Banking example: customer roll no. → customer name.

Term	Meaning	Example
Hash Function	Maps key → index in hash table	hash(101) = 101 % 10 = 1
Collision	Two different keys get the same hash index	hash(101) = hash(201) = 1
Chaining	Each index stores a linked list of colliding entries	Index 1 → [101: Ravi, 201: Priya]
Linear Probing	On collision, try next available slot	Index 1 taken → try index 2, 3…
Load Factor	No. of entries / table size — ideally < 0.7	Too high = many collisions

⚡

All Operations — Must MemoriseDS Operations Complexity Summary

Data Structure	Access	Search	Insert	Delete	Notes
Array	`O(1)`	O(n)	O(n) middle	O(n) middle	Fast access, slow middle ops
Linked List	O(n)	O(n)	`O(1)` head	O(1) given node	Fast insert/delete at head
Stack	O(n)	O(n)	`O(1)` push	`O(1)` pop	LIFO — only top accessible
Queue	O(n)	O(n)	`O(1)` enqueue	`O(1)` dequeue	FIFO — front/rear only
BST (balanced)	O(log n)	`O(log n)`	O(log n)	O(log n)	Skewed BST = O(n)
Hash Table	O(1) avg	`O(1)` avg	O(1) avg	O(1) avg	Worst case O(n) with many collisions
Heap (Max/Min)	O(n)	O(n)	O(log n)	O(log n) root	Root access = O(1)

🏦

Real-World & Banking ApplicationsDS & Algorithms in Real Life

📦

Array

Monthly balance for 12 months, IFSC codes list, marks table (2D), interest rate slabs

🔗

Linked List

Bank transaction logs (frequent add/remove), browser forward/backward history, adjacency list for graphs

📚

Stack

Undo/Redo in banking software, recursion, DFS traversal, expression evaluation, parentheses matching

🚶

Queue

Bank token/counter system, printer job scheduling, BFS, OS round-robin scheduling, call centre

🌳

Tree

Bank branch hierarchy (HO→Zone→Region→Branch), menu structures, BST for sorted account numbers

🌐

Graph

ATM/branch network routing, fraud detection patterns, shortest path algorithms, social networks

🔑

Hash Table

Customer record indexing, password storage, database indexing, cache systems

⛰️

Priority Queue/Heap

VIP customer service first, ATM cash denomination selection, CPU job scheduling

🏗️

B-Tree / B+ Tree

Core banking database indexing on disk, file system organisation (used in Oracle, MySQL)

🔄

Circular Queue

Round-robin CPU scheduling, circular token systems, ring buffer for real-time data

↔️

Deque

Browser history (back/forward), sliding window algorithms, input-restricted queue systems

🔍

Binary Search

Find customer by account number in sorted file, lookup in sorted price tables

Scenario / Question	Best Data Structure / Algorithm
Undo/Redo in bank transaction entry	Stack (two stacks)
Bank counter customer token system	Queue
Hierarchical branch network (HO→Branch)	Tree
ATM/branch route optimisation	Graph + Dijkstra
Customer indexing for fast lookup	Hash Table
Serving VIP customers first	Priority Queue (Max Heap)
Searching sorted account records	Binary Search
Database indexing on disk	B-Tree / B+ Tree
Fraud pattern detection in accounts	Graph analytics
Fixed list of 12 months’ balances	Array
BFS in graph / Level order in tree	Queue
DFS in graph	Stack / Recursion

📝

Tap Any Option to Reveal AnswerMCQ Practice — 50 Questions (5 Chapters)

Score: 0 / 0

CH.1Basics, Arrays & ComplexityQ.01–Q.12

Q.01Basics🔥 Most Asked

A data structure is primarily used to:

✔ Correct: B

A Data Structure is a method of organising and storing data so it can be accessed and used efficiently. Choosing the right one improves program speed and reduces memory usage.

Q.02Classification🔥 Most Asked

Which of the following is a NON-LINEAR data structure?

✔ Correct: D — Tree

Linear DS: Array, Linked List, Stack, Queue (sequential). Non-Linear DS: Tree and Graph (hierarchical/networked). Tree has parent-child hierarchy — not a straight sequence.

Q.03Complexity🔥 Most Asked

In Big-O notation, O(1) means:

✔ Correct: A — Constant time

O(1) = constant time. The operation takes the same time regardless of n. Examples: array access by index, stack push/pop, hash table lookup (average). Best possible complexity.

Q.04Complexity🔥 Most Asked

Which time complexity is BEST (most efficient)?

✔ Correct: B — O(1) is best

Complexity order from best to worst: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). O(1) is constant — always the fastest regardless of data size.

Q.05Array🔥 Most Asked

Accessing any element in an array by its index takes:

✔ Correct: A — O(1) constant time

Arrays store elements in contiguous memory. Since each element’s address = base_address + (index × size), any element can be accessed in constant time O(1) — this is the biggest advantage of arrays.

Q.06Array🔥 Most Asked

Inserting an element in the MIDDLE of an array is slow because:

✔ Correct: B — Elements must be shifted

To insert in the middle of an array, all elements from the insertion point to the end must be shifted one position right — O(n) time. Similarly, deletion in the middle requires shifting left.

Q.07Array

Index of the first element in an array in most programming languages is:

✔ Correct: B — Index 0

Most programming languages (C, Java, Python, JavaScript) use 0-based indexing. The first element is at index 0, last element at index n−1 for an array of n elements.

Q.08Complexity🔥 Most Asked

Big-O notation (O) represents which case of an algorithm?

✔ Correct: C — Worst case (upper bound)

Big-O (O) = worst case / upper bound. This is the most asked notation in exams. Θ (Theta) = average. Ω (Omega) = best case (lower bound). O is used most because it guarantees the worst outcome.

Q.09ADT🔥 Most Asked

Which of the following is an example of an Abstract Data Type (ADT)?

✔ Correct: C — Stack

An ADT (Abstract Data Type) defines operations and behaviour without specifying implementation. Stack (push/pop), Queue (enqueue/dequeue), Tree are ADTs. Integer, Float are primitive types. Keyboard is hardware.

Q.10Complexity🔥 Most Asked

Which of the following is the correct ordering from BEST to WORST complexity?

✔ Correct: A

The correct order is: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Constant is best; factorial is worst. This chain is one of the most tested facts in CS exams.

Q.11Array

What is stored in a 2D array?

✔ Correct: B — Table/matrix (rows and columns)

A 2D array stores data in rows and columns — like a matrix or table. Example: marks of 5 students in 3 subjects → 5×3 = 2D array. Used widely in banking for multi-dimensional data.

Q.12Array

A fixed-size list of 12 months for storing monthly account balances is best stored in:

✔ Correct: A — Array

When the size is fixed and known (12 months), an array is ideal. Access balance[5] = June balance in O(1). Arrays are best for fixed-size, index-based access.

CH.2Linked List, Stack & QueueQ.13–Q.26

Q.13Linked List🔥 Most Asked

In a singly linked list, each node contains:

✔ Correct: C — Data + pointer to next node

Singly linked list: each node = data + next pointer. Doubly linked list: each node = data + prev + next. Last node’s next = NULL. Head pointer stores address of first node.

Q.14Linked List🔥 Most Asked

Which is NOT an advantage of linked list over array?

✔ Correct: C — Random access is NOT possible in O(1)

Linked lists do NOT support O(1) random access. To reach the k-th element, you must traverse k nodes = O(k). Arrays support O(1) access. This is the biggest disadvantage of linked lists.

Q.15Linked List🔥 Most Asked

In a circular linked list, the last node’s next pointer points to:

✔ Correct: C — Head node

In a circular linked list, the last node’s next points back to the head, forming a circle. Used for: round-robin scheduling, circular token systems.

Q.16Linked List

Which linked list is BEST for browser forward/backward history navigation?

✔ Correct: B — Doubly linked list

Doubly linked list allows traversal in BOTH directions (prev and next pointers). Perfect for browser history — go back (prev pointer) or forward (next pointer) easily.

Q.17Stack🔥 Most Asked

A stack works on which principle?

✔ Correct: B — LIFO (Last In, First Out)

Stack = LIFO. The last element pushed is the first popped. Like a stack of plates — the plate you put on top last is the first one you take. Memory trick: Stack of plates = LIFO.

Q.18Stack🔥 Most Asked

If elements 1, 2, 3, 4 are pushed in this order, which element is removed first by pop?

✔ Correct: D — 4 is popped first

LIFO principle: push 1, 2, 3, 4 → stack (bottom to top): [1, 2, 3, 4]. Pop removes 4 first (top element). Next pop removes 3, then 2, then 1.

Q.19Stack🔥 Most Asked

Which data structure is used for function call management and recursion?

✔ Correct: B — Stack

Function calls use a call stack. When function A calls function B, B is pushed on the stack. When B completes, it’s popped. Recursion also uses the stack — each recursive call is pushed and popped in LIFO order.

Q.20Stack🔥 Most Asked

Undo operation in a text editor or banking software is best implemented using:

✔ Correct: B — Stack

Each action is pushed onto the stack. When Undo is pressed, the last action is popped and reversed (LIFO). For Undo+Redo, two stacks are used.

Q.21Queue🔥 Most Asked

A queue works on which principle?

✔ Correct: A — FIFO (First In, First Out)

Queue = FIFO. First customer to join the bank queue is first to be served. Operations: Enqueue (insert at rear), Dequeue (remove from front).

Q.22Queue🔥 Most Asked

In a queue, insertion happens at which end?

✔ Correct: A — Rear end

Queue: Insert at Rear (Enqueue) | Delete from Front (Dequeue). Remember: Join a queue at the back, served from the front — FIFO.

Q.23Queue🔥 Most Asked

Which data structure is used to implement BFS (Breadth First Search)?

✔ Correct: B — Queue

BFS = Queue | DFS = Stack/Recursion. BFS visits all nodes at current depth before going deeper — Queue ensures this level-by-level order. Also used for Level Order tree traversal.

Q.24Queue

A circular queue is also known as:

✔ Correct: B — Ring buffer

A circular queue is also called a Ring Buffer. The rear index wraps around: rear = (rear + 1) % size. Solves the “false overflow” problem of simple linear queues.

Q.25Queue🔥 Most Asked

A deque (Double-Ended Queue) allows:

✔ Correct: C — Both ends

A Deque (Double-Ended Queue) = insert/delete from BOTH front AND rear. More flexible than simple queue. Best implemented using a doubly linked list.

Q.26Bank App🔥 Most Asked

In a bank’s token-based customer service system, customers join and are served using:

✔ Correct: B — Queue (FIFO)

Bank token systems use a Queue. Customer joins → Enqueue (add to rear). Customer served → Dequeue (remove from front). First come, first served = FIFO principle.

CH.3Trees, BST & HeapsQ.27–Q.38

Q.27Tree🔥 Most Asked

The topmost node in a tree is called:

✔ Correct: B — Root

Tree terminology: Root = topmost node. Leaf = node with no children. Internal node = has at least one child. Degree = number of children of a node.

Q.28BST🔥 Most Asked

In a Binary Search Tree (BST), the left child key is:

✔ Correct: B — Less than the parent

BST property: Left child < Parent < Right child. This property enables efficient O(log n) search in a balanced BST — compare key with root, go left or right accordingly.

Q.29BST Traversal🔥 Most Asked

Inorder traversal of a BST produces elements in:

✔ Correct: B — Sorted ascending order

Inorder traversal (Left → Root → Right) of a BST always produces elements in sorted ascending order. This is the most tested property of BST. BST [5,10,15]: Inorder = 5, 10, 15.

Q.30Traversal🔥 Most Asked

Preorder traversal visits nodes in which sequence?

✔ Correct: C — Root → Left → Right

Traversal sequences: Preorder = Root-Left-Right (Root FIRST) | Inorder = Left-Root-Right | Postorder = Left-Right-Root (Root LAST).

Q.31Traversal🔥 Most Asked

Level Order traversal (BFS on tree) uses which data structure?

✔ Correct: B — Queue

Level order traversal visits all nodes at each depth before going deeper — this is BFS on a tree. Uses a Queue: enqueue root, then dequeue and enqueue its children, level by level.

Q.32Tree

A tree with n nodes has how many edges?

✔ Correct: B — n − 1 edges

A tree with n nodes always has exactly n − 1 edges. This is a fundamental property of trees (connected acyclic graphs). Example: 5 nodes → 4 edges.

Q.33BST🔥 Most Asked

Average time complexity for search in a BALANCED BST is:

✔ Correct: B — O(log n)

Balanced BST search = O(log n). Each comparison eliminates half the remaining nodes (similar to binary search). Unbalanced/skewed BST degrades to O(n) — like a linked list.

Q.34Tree Types🔥 Most Asked

Which tree is widely used in DATABASE INDEXING and FILE SYSTEMS?

✔ Correct: C — B-Tree / B+ Tree

B-Tree and B+ Tree are multi-way balanced trees specifically designed for disk storage. Oracle, MySQL, file systems all use B+ Trees for indexing — they minimise disk reads by keeping more data per node.

Q.35Heap🔥 Most Asked

In a MAX Heap, the largest element is at:

✔ Correct: B — The root

Max Heap: largest element is always at the root. Min Heap: smallest element at root. Heaps are complete binary trees. Used to implement Priority Queues.

Q.36Heap🔥 Most Asked

Priority Queue is most commonly implemented using:

✔ Correct: B — Heap

Heap is the standard implementation of Priority Queue. Max Heap → dequeue always gives highest priority. Banking use: serving VIP customers first, ATM cash denomination selection.

Q.37AVL🔥 Most Asked

An AVL tree is a:

✔ Correct: B — Self-balancing BST

AVL Tree = self-balancing BST where balance factor (left height − right height) = {−1, 0, 1} for every node. Guarantees O(log n) operations always (unlike plain BST which can degrade to O(n)).

Q.38Bank App🔥 Most Asked

In banking, to represent the hierarchical structure HO → Zones → Regions → Branches, which DS is used?

✔ Correct: C — Tree

A hierarchical parent-child relationship (HO is parent, Zones are children, Regions are grandchildren, Branches are leaves) is naturally represented by a Tree. HO = Root node.

CH.4Graphs, Hashing & SortingQ.39–Q.46

Q.39Graph🔥 Most Asked

BFS (Breadth First Search) traversal of a graph uses which data structure?

✔ Correct: B — Queue

BFS = Queue. Explores all neighbours at current depth before going deeper. DFS = Stack/Recursion. Memory trick: BFS = Broad first (level by level) = Queue. DFS = Deep first = Stack.

Q.40Graph🔥 Most Asked

A Tree is a special case of a Graph that is:

✔ Correct: B — Connected and acyclic

A Tree is a special graph that is: connected (every node is reachable) and acyclic (no cycles). n nodes → n−1 edges. If you add one more edge to a tree, it creates a cycle and becomes a general graph.

Q.41Graph🔥 Most Asked

For a SPARSE graph (few edges), which representation is more memory-efficient?

✔ Correct: B — Adjacency List for sparse graphs

Adjacency Matrix = O(n²) space (wastes space when few edges). Adjacency List = O(n+e) — only stores existing edges. For sparse graphs (few edges), adjacency list is much more efficient.

Q.42Hashing🔥 Most Asked

Collision in a hash table means:

✔ Correct: A — Two keys get same index

Collision = two different keys map to the same index in the hash table. Solved by: Chaining (linked list at each index) or Open Addressing (linear probing, quadratic probing).

Q.43Hashing🔥 Most Asked

Average time complexity for search in a well-designed hash table is:

✔ Correct: A — O(1) average

Hash table average search = O(1). The hash function directly maps key to index — no traversal needed. Worst case = O(n) when many collisions. Good hash function + proper table size keeps average at O(1).

Q.44Sorting🔥 Most Asked

Which sorting algorithms have worst-case O(n²) complexity?

✔ Correct: A — Bubble, Selection, Insertion

Basic/naive sorts = O(n²) worst case: Bubble, Selection, Insertion. Efficient sorts = O(n log n): Merge, Heap (always), Quick (average). Quick Sort worst case = O(n²) when pivot is always min/max.

Q.45Sorting🔥 Most Asked

Merge Sort uses which algorithm design technique?

✔ Correct: B — Divide and Conquer

Merge Sort = Divide and Conquer. Divides array into halves, sorts each half, then merges. Always O(n log n). Stable sort. Requires O(n) extra space. Quick Sort also uses Divide and Conquer.

Q.46Sorting

A “stable sort” means:

✔ Correct: A — Maintains relative order of equal keys

Stable sort = preserves the relative order of elements with equal keys. Stable: Bubble, Insertion, Merge. Unstable: Selection, Quick, Heap. Important when sorting records on multiple keys.

CH.5Applied & Banking ApplicationsQ.47–Q.50

Q.47Applied🔥 Most Asked

Which mapping is CORRECT?

✔ Correct: A

Essential mappings: LIFO → Stack (plates) | FIFO → Queue (bank line) | Priority → Heap (VIP service). These three are the most tested data structure classification facts.

Q.48Applied🔥 Most Asked

For real-time fraud detection in banking using suspicious transaction PATTERNS between accounts, the best data structure is:

✔ Correct: C — Graph

Fraud detection involving relationships between accounts (A sends money to B who sends to C…) = Graph problem. Graph algorithms detect suspicious cycles, clusters, and patterns in financial networks.

Q.49Applied🔥 Most Asked

For core banking DATABASE INDEXING on disk (like MySQL, Oracle), which tree is preferred?

✔ Correct: C — B-Tree / B+ Tree

B-Tree and B+ Tree are the standard for database and filesystem indexing. They store more keys per node (minimising disk reads), handle large datasets efficiently, and stay balanced automatically.

Q.50Applied🔥 Most Asked

Which statement is MOST accurate about data structures in banking technology?

✔ Correct: C

Data Structures are everywhere in banking: Array (monthly data), Queue (token system), Stack (undo/redo), Tree (org hierarchy, DB indexes), Graph (fraud detection, routing), Hash (customer lookup), Heap (priority). All DS are relevant!

⚡

Last-Minute PrepQuick Revision Flash Cards

📦 Array

Fixed size, continuous memory
Access by index = O(1)
Insert/delete middle = O(n) (shifting)
First index = 0
Best for: fixed-size indexed data

🔗 Linked List

Nodes + pointers, dynamic size
Insert at head = O(1)
Search/access = O(n)
Singly: next only | Doubly: prev+next | Circular: last → head
Best for: frequent inserts/deletes

📚 Stack

LIFO = Last In, First Out
Push/Pop = O(1)
Overflow: top = maxSize−1 | Underflow: top = −1
Uses: Undo, recursion, DFS, expression eval

🚶 Queue

FIFO = First In, First Out
Enqueue (rear), Dequeue (front) = O(1)
Uses: BFS, bank tokens, scheduling
Circular Queue = Ring Buffer

🌳 Tree / BST

Root = top, Leaf = no children
n nodes → n−1 edges
BST: Left < Root < Right
Inorder BST = sorted output
Balanced BST = O(log n) all ops

🌳 Tree Traversal

Preorder = Root → L → R
Inorder = L → Root → R (sorted for BST)
Postorder = L → R → Root
Level order = uses Queue (BFS)

🌐 Graph

Vertices + Edges (directed/undirected)
BFS → Queue | DFS → Stack
Sparse graph → Adjacency List
Dense graph → Adjacency Matrix
Tree = connected + acyclic graph

🔑 Hashing

Hash function → key to index
Search avg = O(1)
Collision = same index for 2 keys
Fix: Chaining or Linear Probing

📊 Big-O Order

O(1) < O(log n) < O(n)
< O(n log n) < O(n²)
< O(2ⁿ) < O(n!)
Big-O = worst case

🔍 Searching

Linear Search = O(n) — any data
Binary Search = O(log n) — sorted only
Binary on 1000 items ≈ 10 steps

🔢 Sorting

Bubble/Selection/Insertion = O(n²)
Merge/Quick avg/Heap = O(n log n)
Quick Sort worst = O(n²)
Merge Sort = Divide & Conquer, stable

🏦 Banking DS Map

Queue → bank token system
Stack → Undo/Redo operations
Tree → HO → Branch hierarchy
Graph → fraud detection, routing
B+ Tree → database indexing
Hash → customer lookup

📌 Must-Know Keywords

LIFO = StackFIFO = Queue Inorder BST = SortedBFS = Queue DFS = StackO(1) = Best Binary Search = O(log n)Merge Sort = O(n log n) B+ Tree = Database IndexHash Table = O(1) avg AVL = Self-Balancing BSTHeap = Priority Queue

📚 Exam Focus: Array=O(1) access · Linked List insert head O(1), search O(n) · Stack=LIFO (push/pop O(1)) · Queue=FIFO (enqueue rear, dequeue front) · BFS=Queue, DFS=Stack · BST Left<Root<Right, Inorder=sorted · Preorder=Root-L-R, Inorder=L-Root-R, Postorder=L-R-Root · Heap=priority queue (Max root=largest) · B+Tree=database indexing · Hash O(1) avg, collision=chaining · Big-O worst case: O(1)<O(log n)<O(n)<O(n log n)<O(n²) · Binary Search=O(log n) sorted only · Bubble/Selection/Insertion=O(n²) · Merge/Heap=O(n log n) always · Quick Sort avg O(n log n), worst O(n²) · Tree n nodes = n−1 edges · Graph=vertices+edges, fraud patterns · AVL=self-balancing BST

© GyanDesk — Data Structures & Algorithms | GATE · IBPS · SSC · UPSC · NDA · Bank Exams 2025

Data Structures and Algorithms

FoundationWhat is a Data Structure?

Data Arranged SequentiallyLinear Data Structures

Array

Linked List

Stack

Queue

Data Arranged Hierarchically / NetworkedNon-Linear Data Structures

Tree

Graph

Hash Table

Heap

Most Tested TableData Structures Comparison

Big-O Notation — Most TestedAlgorithm Complexity

Two Key AlgorithmsSearching Algorithms

Know Complexities — Very Frequently TestedSorting Algorithms

All 4 Methods — Exam FavouriteTree Traversal Methods

Fast O(1) LookupHashing & Hash Tables

All Operations — Must MemoriseDS Operations Complexity Summary

Real-World & Banking ApplicationsDS & Algorithms in Real Life

Array

Linked List

Stack

Queue

Tree

Graph

Hash Table

Priority Queue/Heap

B-Tree / B+ Tree

Circular Queue

Deque

Binary Search

Tap Any Option to Reveal AnswerMCQ Practice — 50 Questions (5 Chapters)

Last-Minute PrepQuick Revision Flash Cards

📦 Array

🔗 Linked List

📚 Stack

🚶 Queue

🌳 Tree / BST

🌳 Tree Traversal

🌐 Graph

🔑 Hashing

📊 Big-O Order

🔍 Searching

🔢 Sorting

🏦 Banking DS Map