Data Structures & Algorithms
💻 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 SizeCollection of same-type elements stored in continuous memory. Access any element instantly using its index. Size fixed at declaration.
🔗
Linked List
Linear · Dynamic SizeNodes connected via pointers. 10 → 20 → 30 → NULL. Types: Singly, Doubly, Circular. No continuous memory needed.
📚
Stack
LIFO — Last In, First OutLike a stack of plates — last placed, first removed. Operations: Push (add) and Pop (remove). Peek to see top without removing.
🚶
Queue
FIFO — First In, First OutLike a bank counter line — first to arrive, first to be served. Enqueue (insert at rear), Dequeue (remove from front). Variants: Circular, Priority, Deque.
🎯 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-LinearNodes connected in parent-child hierarchy. Root (top), Leaf (no children). Binary Tree: max 2 children per node. BST: left < root < right.
🌐
Graph
Network of Nodes & EdgesNodes (vertices) connected by edges. Can be directed/undirected, weighted/unweighted. A Tree is a special case of Graph (connected, acyclic).
🔑
Hash Table
Key-Value · Fast SearchStores 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.
⛰️
Heap
Complete Binary Tree · PriorityMax Heap: largest element at root. Min Heap: smallest at root. Used to implement Priority Queue. Insert + Delete = O(log n).
| 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)
CH.1Basics, Arrays & ComplexityQ.01–Q.12
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.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.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.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.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.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.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.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.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.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.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.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
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.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.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.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.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.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.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.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.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).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.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.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.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.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
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.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.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.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).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.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.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.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.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.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.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)).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
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.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.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.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).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).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.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.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
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.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.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.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
Related notes
More free study notes in Information Technology — all part of the GyanDesk study library.