Sign Up Sign Up


Have an account? Sign In Now

Sign In Sign In


Forgot Password?

Don't have account, Sign Up Here

Forgot Password Forgot Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.


Have an account? Sign In Now

You must login to ask a question.


Forgot Password?

Need An Account, Sign Up Here

You must login to add post.


Forgot Password?

Need An Account, Sign Up Here

Please briefly explain why you feel this question should be reported.

Please briefly explain why you feel this answer should be reported.

Please briefly explain why you feel this user should be reported.

RTSALL Logo RTSALL Logo
Sign InSign Up

RTSALL

RTSALL Navigation

  • Home
  • Tutorials
    • All Subjects & Branches (90+)
    • C Programming MCQs
    • Python Programming MCQs
    • Data Structures MCQs
    • DBMS & SQL MCQs
    • Computer Networks MCQs
    • Operating Systems MCQs
    • Quantitative Aptitude MCQs
  • Interview
    • Interview Preparation Portal
    • Web API & REST API
    • SQL Server
    • System Design
    • C# (.NET 8/9)
    • ASP.NET MVC & Core
    • DSA (Data Structures)
    • Cyber Security
    • Burp Suite (AppSec)
  • Tools
    • Run Code
    • JSON Beautifier
    • Regex Tester
    • Diff Checker
    • JWT Decoder
    • UUID Generator
    • .htaccess Generator
    • YAML/JSON Converter
    • SQL Formatter
    • Cron Generator
    • JSON to CSV/Excel
    • System Design Estimator
    • Chmod Calculator
    • Duplicate Line Remover
  • DSA
    • All DSA Problems
    • Online C++ Runner
    • Arrays, Strings & Cache
    • Two Pointers & Sliding Window
    • Linked Lists & Custom Allocators
    • Stacks, Queues & Ring Buffers
    • Trees, BSTs & Indexes
    • Tries & Prefix Search
    • Heaps & Priority Schedulers
    • Hashing & Collision Resolution
    • Graphs & Network Topologies
    • Dynamic Programming
    • Advanced Bitmask & Tree DP
    • Greedy & Resource Allocation
    • Binary Search & State Spaces
    • Bit Manipulation & Low-Level
    • System-Scale & Probabilistic
  • AI Utilities
    • Token Counter
    • JSON Schema Compiler
    • Fine-Tuning JSONL Converter
    • Vector RAG Playground
    • Prompt Optimizer & Architect
    • LLM GPU VRAM Calculator
    • .NET AI Roadmap
  • Finance Tools
    • Compound Interest Calculator
    • SIP Calculator
    • Simple Interest Calculator
    • EMI Calculator
    • Present Value (PV) Calculator
    • Compound Interest Calculator
    • Future Value (FV) Calculator
    • NPV Calculator
    • IRR Calculator
    • CAGR Calculator
    • Dividend Income Calculator
    • Yield on Cost Calculator
    • Dividend Payout Ratio
    • WACC Calculator
    • CAPM & Cost of Equity
    • Cost of Debt Calculator
    • DCF Valuation Calculator
    • Enterprise Value Calculator
  • About Us
  • Blog
  • Contact Us
Search
Ask A Question

Mobile menu

Close
Ask a Question
  • Home
  • Tutorials
    • All Subjects & Branches (90+)
    • C Programming MCQs
    • Python Programming MCQs
    • Data Structures MCQs
    • DBMS & SQL MCQs
    • Computer Networks MCQs
    • Operating Systems MCQs
    • Quantitative Aptitude MCQs
  • Interview
    • Interview Preparation Portal
    • Web API & REST API
    • SQL Server
    • System Design
    • C# (.NET 8/9)
    • ASP.NET MVC & Core
    • DSA (Data Structures)
    • Cyber Security
    • Burp Suite (AppSec)
  • Tools
    • Run Code
    • JSON Beautifier
    • Regex Tester
    • Diff Checker
    • JWT Decoder
    • UUID Generator
    • .htaccess Generator
    • YAML/JSON Converter
    • SQL Formatter
    • Cron Generator
    • JSON to CSV/Excel
    • System Design Estimator
    • Chmod Calculator
    • Duplicate Line Remover
  • DSA
    • All DSA Problems
    • Online C++ Runner
    • Arrays, Strings & Cache
    • Two Pointers & Sliding Window
    • Linked Lists & Custom Allocators
    • Stacks, Queues & Ring Buffers
    • Trees, BSTs & Indexes
    • Tries & Prefix Search
    • Heaps & Priority Schedulers
    • Hashing & Collision Resolution
    • Graphs & Network Topologies
    • Dynamic Programming
    • Advanced Bitmask & Tree DP
    • Greedy & Resource Allocation
    • Binary Search & State Spaces
    • Bit Manipulation & Low-Level
    • System-Scale & Probabilistic
  • AI Utilities
    • Token Counter
    • JSON Schema Compiler
    • Fine-Tuning JSONL Converter
    • Vector RAG Playground
    • Prompt Optimizer & Architect
    • LLM GPU VRAM Calculator
    • .NET AI Roadmap
  • Finance Tools
    • Compound Interest Calculator
    • SIP Calculator
    • Simple Interest Calculator
    • EMI Calculator
    • Present Value (PV) Calculator
    • Compound Interest Calculator
    • Future Value (FV) Calculator
    • NPV Calculator
    • IRR Calculator
    • CAGR Calculator
    • Dividend Income Calculator
    • Yield on Cost Calculator
    • Dividend Payout Ratio
    • WACC Calculator
    • CAPM & Cost of Equity
    • Cost of Debt Calculator
    • DCF Valuation Calculator
    • Enterprise Value Calculator
  • About Us
  • Blog
  • Contact Us
Home/RTSALL Educational Academy: Subject MCQs, Practice Tests & Detailed Explanations/Data Structures: 5-Chapter Comprehensive Practice & 75 Verified MCQs

Data Structures: 5-Chapter Comprehensive Practice & 75 Verified MCQs

Home / Learning Platform / Computer Science & IT / Data Structures MCQs
Computer Science & IT 🟢 75 Verified MCQs • 5 Complete Chapters Active ⭐ Interview & Exam Grade

Data Structures: 5-Chapter Comprehensive Practice & 75 Verified MCQs

Master Data Structures with our complete 5-chapter question bank. Each verified MCQ provides four distinct options, verified solution keys, step-by-step technical rationale, and high-yield conceptual rules.

Curriculum Roadmap & Chapters Covered (All Live & Unlocked):
✓ Chapter 1: Linear Data Structures (Stacks & Queues) (Q1 – Q15)
✓ Chapter 2: Singly, Doubly & Circular Linked Lists (Q16 – Q30)
✓ Chapter 3: Binary Trees, BSTs & AVL Self-Balancing (Q31 – Q45)
✓ Chapter 4: Heaps, Priority Queues & Hash Tables (Q46 – Q60)
✓ Chapter 5: Graphs, BFS, DFS & Shortest Path Algorithms (Q61 – Q75)
📝 Total Questions: 75 Verified MCQs
📚 Modules: 5 Complete Chapters
⏱️ Est. Practice Time: ~90 minutes
🎯 Target Benchmark: 80% (60/75 Correct)
Select Chapter to Practice:
Interactive Practice Dashboard
Answered: 0 / 75 Correct: 0 Accuracy: 0% Streak: 🔥 0
Currently Displaying: All 75 Questions across Chapters 1 to 5. Click any option for instant evaluation and in-depth explanations.
Curriculum Track • Module 1 of 5
Chapter 1: Linear Data Structures (Stacks & Queues) (Q1 – Q15)
Question 1 of 75 Chapter 1
Which data structure operates on a Last-In, First-Out (LIFO) principle and is fundamentally used for function call runtime stacks?
A. Queue
B. Stack
C. Binary Search Tree
D. Hash Map
✔ Correct Answer: Option B
Detailed Explanation: A stack enforces a Last-In, First-Out (LIFO) discipline where the most recently inserted item is the first one retrieved. Compilers and OS kernels utilize the call stack to manage stack frames, local variables, and return addresses during nested function calls.
🎯 Key Learning Point: Both push() and pop() operations on a stack execute in strict O(1) constant time.
Question 2 of 75 Chapter 1
What is the equivalent postfix notation (Reverse Polish Notation) for the infix expression: (A + B) * (C – D)?
A. A B + C D – *
B. A B C D + – *
C. * + A B – C D
D. A + B * C – D
✔ Correct Answer: Option A
Detailed Explanation: In infix notation, parentheses dictate order. (A + B) converts to ‘A B +’, and (C – D) converts to ‘C D -‘. Multiplying the two sub-expressions places the operator at the end: ‘A B + C D – *’.
🎯 Key Learning Point: Postfix notation completely removes ambiguity without requiring parentheses, making it ideal for single-pass stack evaluation by calculators and virtual machines.
Question 3 of 75 Chapter 1
In a circular queue implemented using a fixed-size array of capacity N, what formula computes the next insertion index for the 'rear' pointer?
A. rear = (rear + 1) / N
B. rear = (rear + 1) % N
C. rear = rear + N % 1
D. rear = (rear * 2) % N
✔ Correct Answer: Option B
Detailed Explanation: The modulo arithmetic ‘rear = (rear + 1) % N’ ensures that once the rear pointer reaches the end of the array (index N – 1), incrementing it wraps around smoothly to index 0, enabling full reuse of deallocated space from earlier dequeues.
🎯 Key Learning Point: Circular queues prevent false overflow conditions that plague plain linear array queue implementations.
Question 4 of 75 Chapter 1
What is the time complexity of detecting a cycle in a singly linked list using Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)?
A. O(1) time and O(N) space
B. O(N) time and O(1) auxiliary space
C. O(N log N) time and O(1) space
D. O(N^2) time and O(N) space
✔ Correct Answer: Option B
Detailed Explanation: Floyd’s algorithm uses two pointers moving at different speeds: a slow pointer (1 node per step) and a fast pointer (2 nodes per step). If a loop exists, the relative distance between them decreases by 1 on every iteration, guaranteeing they meet in at most O(N) steps while requiring only O(1) extra memory pointers.
🎯 Key Learning Point: Floyd’s algorithm eliminates the need for hash sets to track visited node addresses, conserving space.
Question 5 of 75 Chapter 1
Why does iterating through an array generally exhibit significantly faster wall-clock execution time than iterating through an identical length linked list on modern CPU hardware?
A. Array memory addresses require fewer bits to store.
B. Contiguous array memory leverages CPU cache lines and spatial locality, whereas linked lists trigger frequent cache misses due to pointer chasing across scattered heap allocations.
C. Linked lists cannot be executed on superscalar processors.
D. Operating systems disable virtual memory for arrays.
✔ Correct Answer: Option B
Detailed Explanation: CPUs fetch data from main memory into L1/L2/L3 caches in blocks called cache lines (typically 64 bytes). Because arrays are contiguous, fetching one element pre-loads adjacent elements. Linked lists allocate individual nodes dynamically on the heap, scattering memory across random addresses and causing costly CPU pipeline stalls on cache misses.
🎯 Key Learning Point: Spatial and temporal cache locality makes contiguous arrays drastically faster in practice than pointer-based data structures despite identical O(N) theoretical complexity.
Question 6 of 75 Chapter 1
What is the minimum number of queues required to implement a functional Last-In, First-Out (LIFO) Stack?
A. 1 (using recursion or rotation) or 2 standard FIFO queues
B. Exactly 3 queues
C. 4 queues
D. Stacks cannot be simulated with queues under any conditions
✔ Correct Answer: Option A
Detailed Explanation: A stack can be implemented using two FIFO queues by either making push costly (enqueuing into an auxiliary queue, transferring all items from the primary queue, and swapping) or making pop costly. It can also be implemented using a single queue by rotating elements (dequeuing and re-enqueuing size – 1 times).
🎯 Key Learning Point: Dual-structure simulation illustrates the theoretical symmetry between LIFO stacks and FIFO queues.
Question 7 of 75 Chapter 1
In a doubly linked list, what operations are required to delete a given node 'curr' (assuming curr is neither head nor tail)?
A. curr.prev.next = curr.next; curr.next.prev = curr.prev; free(curr);
B. curr.next = curr.prev; free(curr);
C. curr.prev = NULL; curr.next = NULL;
D. free(curr.next);
✔ Correct Answer: Option A
Detailed Explanation: To bypass ‘curr’, the node before it (‘curr.prev’) must link its next pointer to the node after it (‘curr.next’). Simultaneously, the node after it (‘curr.next’) must update its prev pointer back to ‘curr.prev’. Finally, curr’s allocated memory is safely released.
🎯 Key Learning Point: Deleting a node in a doubly linked list takes O(1) time when the node reference is already in hand, compared to O(N) in a singly linked list to find the preceding node.
Question 8 of 75 Chapter 1
What is the optimal worst-case time complexity of finding the 'Next Greater Element' for all elements in an array of size N using a Monotonic Stack?
A. O(N^2)
B. O(N log N)
C. O(N)
D. O(2^N)
✔ Correct Answer: Option C
Detailed Explanation: A monotonic decreasing stack maintains elements in order. While iterating through the array, each element is pushed onto the stack exactly once, and popped at most once. Because the total number of push and pop operations across the entire algorithm is bounded by 2N, the amortized time complexity is strictly linear O(N).
🎯 Key Learning Point: Monotonic stacks reduce brute-force O(N^2) span and boundary queries into linear O(N) operations.
Question 9 of 75 Chapter 1
What is the primary operational advantage of a Double-Ended Queue (Deque) over a standard Queue?
A. Deques allow insertion and deletion at both the front and rear ends in O(1) time.
B. Deques sort elements automatically on insertion.
C. Deques consume half the memory of an array.
D. Deques allow random access in O(1) time without indexes.
✔ Correct Answer: Option A
Detailed Explanation: A deque (double-ended queue) supports four primary operations: push_front, pop_front, push_back, and pop_back—all operating in O(1) constant time. This flexibility enables algorithms like sliding window minimum/maximum.
🎯 Key Learning Point: Deques can function seamlessly as both FIFO queues and LIFO stacks.
Question 10 of 75 Chapter 1
When evaluating the postfix expression '5 3 + 8 2 – *' using an operand stack, what is the final evaluated result?
A. 48
B. 40
C. 24
D. 18
✔ Correct Answer: Option A
Detailed Explanation: 1) Push 5, push 3. 2) Encounter ‘+’: pop 3 and 5, compute 5 + 3 = 8, push 8. 3) Push 8, push 2. 4) Encounter ‘-‘: pop 2 and 8, compute 8 – 2 = 6, push 6. 5) Encounter ‘*’: pop 6 and 8, compute 8 * 6 = 48. Final result = 48.
🎯 Key Learning Point: For binary operators in postfix evaluation, the first popped element is the right operand, and the second popped element is the left operand.
Question 11 of 75 Chapter 1
In a singly linked list, which operation cannot be performed in O(1) time even if a pointer to the target node is provided?
A. Deleting the last node (tail) of the list
B. Inserting a new node immediately after the target node
C. Updating the value of the target node
D. Deleting the head node
✔ Correct Answer: Option A
Detailed Explanation: Even with a direct pointer to the tail node, updating the list requires setting the second-to-last node’s next pointer to NULL. Because singly linked lists have only unidirectional links, finding the preceding node demands an O(N) traversal from head.
🎯 Key Learning Point: Maintaining both head and tail pointers allows O(1) insertion at tail, but tail deletion remains O(N) in a singly linked list.
Question 12 of 75 Chapter 1
What problem occurs when implementing a queue using a simple, non-circular array where 'front' and 'rear' continuously increment?
A. Memory fragmentation occurs in the CPU cache.
B. False overflow: the queue appears full because rear reaches the array end, even if front has advanced leaving empty slots at the beginning.
C. Items are automatically reversed in order.
D. Compilers refuse to allocate static memory.
✔ Correct Answer: Option B
Detailed Explanation: In a linear array queue, every dequeue increments ‘front’, and every enqueue increments ‘rear’. Once ‘rear == capacity – 1’, no new items can be added despite unused memory at indices before ‘front’. This is ‘false overflow’, solved completely by circular queues.
🎯 Key Learning Point: Circular arrays eliminate false overflow by utilizing modulo arithmetic: index = (index + 1) % size.
Question 13 of 75 Chapter 1
How does reversing a singly linked list iteratively in O(N) time and O(1) space operate?
A. It swaps values between the first and last elements iteratively.
B. It maintains three pointers (prev, curr, next), redirecting curr.next to prev at each step.
C. It allocates a secondary array to collect addresses.
D. It invokes a binary heap to sort pointer addresses.
✔ Correct Answer: Option B
Detailed Explanation: The standard iterative reversal uses three pointers: ‘prev’ (initialized to NULL), ‘curr’ (initialized to head), and ‘next’. In each iteration, ‘next = curr.next’ saves the remainder of the list, ‘curr.next = prev’ reverses the link, ‘prev = curr’ advances the previous pointer, and ‘curr = next’ advances to the next node.
🎯 Key Learning Point: Pointer-reversal modifies memory links directly without copying data payloads, maintaining true O(1) space.
Question 14 of 75 Chapter 1
What data structure is ideally suited to check for balanced brackets and nested parentheses in compilers and syntax linters?
A. Priority Queue
B. Stack
C. Circular Queue
D. B+ Tree
✔ Correct Answer: Option B
Detailed Explanation: Because brackets must close in reverse order of opening (the innermost bracket closes first), a stack perfectly models nested parentheses: opening brackets (‘(‘, ‘[‘, ‘{‘) are pushed onto the stack, and closing brackets pop the top element to verify matching bracket types.
🎯 Key Learning Point: If a closing bracket fails to match the top of the stack, or if the stack is non-empty at end of file, a syntax error is flagged.
Question 15 of 75 Chapter 1
What is the auxiliary space complexity of recursively reversing a singly linked list of N nodes?
A. O(1)
B. O(N) due to call stack frames
C. O(N log N)
D. O(N^2)
✔ Correct Answer: Option B
Detailed Explanation: Although recursive reversal requires no explicit auxiliary collections, the runtime call stack allocates a stack frame for every recursive call until reaching the base case (the last node). For a list of N elements, N frames reside on the stack, consuming O(N) auxiliary space.
🎯 Key Learning Point: For large linked lists (e.g., 100,000+ nodes), recursive reversal risks stack overflow errors; iterative reversal with O(1) space is safer in production.
Curriculum Track • Module 2 of 5
Chapter 2: Singly, Doubly & Circular Linked Lists (Q16 – Q30)
Question 16 of 75 Chapter 2
In a singly linked list with head pointer only, what is the time complexity to insert a new node at the beginning vs at the end?
A. O(1) at beginning, O(N) at end
B. O(N) at beginning, O(1) at end
C. O(1) for both
D. O(N) for both
✔ Correct Answer: Option A
Detailed Explanation: Inserting at head requires updating the new node’s next pointer and head in O(1) time. Inserting at end without a tail pointer requires traversing all N nodes from head to reach the last node, taking O(N) time.
🎯 Key Learning Point: Maintaining a tail pointer reduces insertion at end to O(1) time.
Question 17 of 75 Chapter 2
What is the primary architectural feature of a Circular Singly Linked List?
A. Nodes are stored in a circle in RAM.
B. The next pointer of the last node points back to the head node instead of holding NULL.
C. Nodes have two next pointers.
D. It cannot be traversed.
✔ Correct Answer: Option B
Detailed Explanation: In a circular linked list, no node points to NULL; the final node links back to the head. This enables continuous cyclical round-robin scheduling algorithms.
🎯 Key Learning Point: Traversal termination checks ‘curr->next != head’ rather than ‘curr != NULL’.
Question 18 of 75 Chapter 2
What is the memory overhead of a Doubly Linked List node compared to a Singly Linked List node on a 64-bit architecture?
A. No extra overhead.
B. 8 additional bytes per node for the backward (prev) pointer.
C. 4 bytes per node.
D. Doubles the data size.
✔ Correct Answer: Option B
Detailed Explanation: Each node in a doubly linked list stores an additional ‘prev’ pointer (8 bytes on 64-bit CPUs), allowing bidirectional traversal at the expense of increased memory footprint.
🎯 Key Learning Point: XOR linked lists eliminate this overhead by storing (prev XOR next) in a single pointer field.
Question 19 of 75 Chapter 2
How does Floyd's Cycle Detection algorithm identify the starting node of a cycle after detecting that a loop exists?
A. By reversing the list.
B. Reset one pointer to head and advance both pointers at 1 step per iteration; their meeting point is the exact cycle start.
C. By counting the nodes in the list.
D. By hashing memory addresses.
✔ Correct Answer: Option B
Detailed Explanation: Mathematically, the distance from head to cycle start equals the distance from the initial meeting point to cycle start along the perimeter. Moving one pointer to head and stepping both at speed 1 guarantees they meet at the cycle entry node.
🎯 Key Learning Point: Floyd’s algorithm finds cycle presence and cycle entry in O(N) time and O(1) space.
Question 20 of 75 Chapter 2
What is a 'Skip List' data structure?
A. A list that skips every second element.
B. A probabilistic hierarchy of linked lists layered with express lanes that achieves O(log N) search, insertion, and deletion.
C. A hardware cache structure.
D. A queue with priority levels.
✔ Correct Answer: Option B
Detailed Explanation: Invented by William Pugh, Skip Lists layer linked lists with probabilistic promotion. Higher levels skip over multiple items, providing O(log N) expected search and update performance comparable to balanced trees, with simpler concurrent locking (used in Redis Sorted Sets).
🎯 Key Learning Point: Redis uses Skip Lists for its ZSET datatype.
Question 21 of 75 Chapter 2
What is the time complexity to merge two sorted singly linked lists containing M and N elements respectively into a single sorted list?
A. O(M * N)
B. O(M + N)
C. O(log(M + N))
D. O(M log N)
✔ Correct Answer: Option B
Detailed Explanation: Merging requires comparing the current heads of both lists and advancing the smaller element’s pointer. Every element is examined once, yielding O(M + N) linear time with O(1) auxiliary pointer space.
🎯 Key Learning Point: Merge sort on linked lists achieves optimal O(N log N) time and O(1) auxiliary pointer space because splicing nodes requires no data array copying.
Question 22 of 75 Chapter 2
What is the advantage of using a Sentinel (Dummy) Head Node in linked list implementations?
A. Halves memory consumption.
B. Eliminates special-case edge handling for operations at the head of the list (e.g. inserting or deleting the first node).
C. Accelerates CPU clock frequency.
D. Prevents pointer arithmetic.
✔ Correct Answer: Option B
Detailed Explanation: A dummy head node ensures that every real data node has a preceding node, eliminating conditional checks like ‘if (head == NULL)’ or ‘if (curr == head)’.
🎯 Key Learning Point: Dummy nodes significantly simplify linked list code in production systems.
Question 23 of 75 Chapter 2
How can you find the middle element of a singly linked list in a single pass without computing total length first?
A. Use a stack.
B. Use two pointers (slow and fast); advance fast by 2 nodes and slow by 1 node; when fast reaches the end, slow is at the middle.
C. Divide pointer addresses by 2.
D. It is mathematically impossible in one pass.
✔ Correct Answer: Option B
Detailed Explanation: Because the fast pointer moves at twice the speed of the slow pointer, when the fast pointer reaches the end (NULL or last node), the slow pointer has traversed exactly half the distance, landing on the middle element in O(N) time and O(1) space.
🎯 Key Learning Point: The fast/slow pointer paradigm is fundamental for finding list midpoints, cycle detection, and palindrome verification.
Question 24 of 75 Chapter 2
What happens if you attempt to traverse a circular linked list using standard 'while (ptr != NULL)' loop condition?
A. Loop terminates at the tail.
B. Infinite loop because the tail node points to head and never evaluates to NULL.
C. Segmentation fault immediately.
D. Program terminates after 100 iterations.
✔ Correct Answer: Option B
Detailed Explanation: Because a circular linked list has no NULL terminator, ‘ptr != NULL’ is always true, trapping execution in an infinite traversal loop.
🎯 Key Learning Point: Always test against head: ‘do { ptr = ptr->next; } while (ptr != head);’.
Question 25 of 75 Chapter 2
In an unrolled linked list, what does each node store?
A. A single integer.
B. An array of multiple elements (e.g. 16 or 32 items) and a next pointer, combining cache locality of arrays with flexible allocation of linked lists.
C. Binary tree nodes.
D. File descriptors.
✔ Correct Answer: Option B
Detailed Explanation: Unrolled linked lists store a small array of elements in each node. This dramatically improves CPU cache performance by keeping data contiguous while preserving O(1) node insertion/deletion.
🎯 Key Learning Point: Unrolled linked lists strike an optimal trade-off between array cache locality and list flexibility.
Question 26 of 75 Chapter 2
What is the time complexity of deleting a node at index K from a singly linked list of size N?
A. O(1)
B. O(K) to traverse to the K-th node
C. O(N^2)
D. O(log N)
✔ Correct Answer: Option B
Detailed Explanation: Finding the (K-1)th node requires traversing K steps from head, which takes O(K) time. Once reached, updating the link takes O(1) time.
🎯 Key Learning Point: Linked lists provide O(1) deletion ONLY when the pointer to the preceding node is already available.
Question 27 of 75 Chapter 2
What is an XOR Linked List?
A. A list that encrypts data with XOR.
B. A memory-efficient doubly linked list where each node stores the bitwise XOR of the previous and next node memory addresses in a single pointer field.
C. A list that stores boolean values only.
D. A hash table.
✔ Correct Answer: Option B
Detailed Explanation: In an XOR linked list, ‘node->npx = prev ^ next’. When traversing forward, ‘next = prev ^ node->npx’; traversing backward, ‘prev = next ^ node->npx’. This halves pointer memory consumption.
🎯 Key Learning Point: XOR linked lists cannot be used with modern garbage collectors because GC cannot trace XORed addresses.
Question 28 of 75 Chapter 2
How do you detect if two singly linked lists intersect and merge into a common tail?
A. Compare their head values.
B. Traverse both lists to their tails; if the tail node pointers are identical, they intersect; calculate length difference to find intersection node.
C. Sort both lists.
D. Sum their values.
✔ Correct Answer: Option B
Detailed Explanation: If two lists intersect, they share the identical tail node pointer. By computing lengths L1 and L2 and advancing the longer list by |L1 – L2| steps, advancing both pointers simultaneously will meet at the exact intersection node.
🎯 Key Learning Point: Intersection detection runs in O(L1 + L2) time with O(1) space.
Question 29 of 75 Chapter 2
What is the space complexity of reversing a linked list of size N using an iterative approach?
A. O(N)
B. O(1)
C. O(log N)
D. O(N^2)
✔ Correct Answer: Option B
Detailed Explanation: Iterative reversal uses three pointer variables (prev, curr, next) to reverse links in-place, requiring strictly O(1) auxiliary space.
🎯 Key Learning Point: Recursive reversal requires O(N) stack space; iterative requires O(1).
Question 30 of 75 Chapter 2
Can binary search be implemented efficiently on a standard singly linked list?
A. Yes, runs in O(log N) time.
B. No, because linked lists do not support O(1) random access; finding the midpoint takes O(N) time, making the overall search O(N).
C. Yes, if elements are sorted.
D. Yes, using bitwise pointers.
✔ Correct Answer: Option B
Detailed Explanation: Binary search relies on O(1) random indexing to jump to midpoints. In a linked list, locating the middle node requires linear traversal, making binary search O(N), offering no asymptotic improvement over linear search.
🎯 Key Learning Point: To get O(log N) search on linked nodes, use a Skip List or balanced Binary Search Tree.
Curriculum Track • Module 3 of 5
Chapter 3: Binary Trees, BSTs & AVL Self-Balancing (Q31 – Q45)
Question 31 of 75 Chapter 3
What is the maximum number of nodes in a binary tree of depth (height) H (where a tree with 1 node has H = 1)?
A. 2^H
B. 2^H – 1
C. 2^(H – 1)
D. H^2
✔ Correct Answer: Option B
Detailed Explanation: Level 1 has 2^0 = 1 node; level 2 has 2^1 = 2 nodes; level H has 2^(H-1) nodes. Summing the geometric series 1 + 2 + 4 + … + 2^(H-1) yields (2^H – 1) nodes.
🎯 Key Learning Point: A complete binary tree of height H has 2^H – 1 nodes.
Question 32 of 75 Chapter 3
Which binary tree traversal algorithm visits nodes in strictly ascending sorted order when applied to a Binary Search Tree (BST)?
A. Pre-order Traversal (Root, Left, Right)
B. In-order Traversal (Left, Root, Right)
C. Post-order Traversal (Left, Right, Root)
D. Level-order Traversal (BFS)
✔ Correct Answer: Option B
Detailed Explanation: In a BST, all keys in the left subtree are smaller than the root, and all keys in the right subtree are greater. In-order traversal visits Left -> Root -> Right, which naturally outputs keys in ascending sorted order.
🎯 Key Learning Point: In-order traversal of a BST sorts the keys in O(N) time.
Question 33 of 75 Chapter 3
What is the balance factor of a node in an AVL Tree, and what are its permitted values?
A. Height(Left) * Height(Right); permitted values: 0, 1, 2
B. Height(Left Subtree) – Height(Right Subtree); permitted values: -1, 0, +1
C. Number of left nodes minus right nodes; permitted values: any integer
D. Depth of root node
✔ Correct Answer: Option B
Detailed Explanation: An AVL tree is a strictly self-balancing BST where the balance factor of every node is defined as Height(Left) – Height(Right). If balance factor deviates from {-1, 0, +1}, tree rotations (LL, RR, LR, RL) restore balance.
🎯 Key Learning Point: AVL trees guarantee strict O(log N) lookup, insertion, and deletion times.
Question 34 of 75 Chapter 3
What is the worst-case time complexity of searching for an element in an unbalanced (degenerate) Binary Search Tree?
A. O(log N)
B. O(N) when the tree degenerates into a linear linked list
C. O(1)
D. O(N log N)
✔ Correct Answer: Option B
Detailed Explanation: If elements are inserted in already sorted order (e.g. 1, 2, 3, 4, 5), an unbalancing BST degenerates into a skewed line of right nodes, making search degrade to linear O(N) scanning.
🎯 Key Learning Point: Self-balancing trees (AVL, Red-Black) prevent skewing by enforcing height bounds of O(log N).
Question 35 of 75 Chapter 3
What tree rotation is performed when an AVL tree becomes unbalanced due to an insertion into the right subtree of the left child (LR Case)?
A. Single Right Rotation
B. Left-Right Double Rotation (Left rotation on left child, then Right rotation on root)
C. Single Left Rotation
D. Triple rotation
✔ Correct Answer: Option B
Detailed Explanation: The LR imbalance is resolved with a double rotation: first a Left rotation on the left child node converts the shape to LL, followed by a Right rotation on the parent node.
🎯 Key Learning Point: AVL rotations: LL -> Right; RR -> Left; LR -> Left then Right; RL -> Right then Left.
Question 36 of 75 Chapter 3
What is a 'Full Binary Tree'?
A. A tree where every node has either 0 or exactly 2 children.
B. A tree where all leaves are at the same depth.
C. A tree where all nodes have 1 child.
D. A tree filled with integers.
✔ Correct Answer: Option A
Detailed Explanation: A full (or strictly) binary tree is a tree in which every node has either zero or two children. No node has exactly one child.
🎯 Key Learning Point: In any full binary tree, Number of Leaf Nodes = Number of Internal Nodes + 1.
Question 37 of 75 Chapter 3
In a Red-Black Tree, what is the maximum possible height of a tree with N internal nodes?
A. log2(N)
B. 2 * log2(N + 1)
C. N / 2
D. N
✔ Correct Answer: Option B
Detailed Explanation: Red-Black properties mandate that no red node can have a red child and every path from root to leaf has the same black-height. This ensures the longest path is at most twice the shortest path: Height <= 2 * log2(N + 1).
🎯 Key Learning Point: Red-Black trees require fewer rotations during insertion/deletion than AVL trees, making them standard for C++ std::map and Java TreeMap.
Question 38 of 75 Chapter 3
How can you reconstruct a unique binary tree given its traversal sequences?
A. Pre-order and Post-order traversals alone are always sufficient.
B. In-order traversal paired with either Pre-order or Post-order traversal is required.
C. Any single traversal is sufficient.
D. Traversals cannot reconstruct trees.
✔ Correct Answer: Option B
Detailed Explanation: In-order traversal is mandatory because it separates the left subtree from the right subtree. Pre-order (or Post-order) identifies the root node. Together, In-order and Pre-order uniquely reconstruct any binary tree.
🎯 Key Learning Point: Without In-order, Pre-order and Post-order cannot distinguish left children from right children in single-child nodes.
Question 39 of 75 Chapter 3
What is the Lowest Common Ancestor (LCA) of two nodes u and v in a Binary Search Tree?
A. The root node always.
B. The first node encountered during top-down traversal whose key value lies between u and v (min(u,v) <= key <= max(u,v)).
C. The leaf node below u.
D. The node with the largest key.
✔ Correct Answer: Option B
Detailed Explanation: In a BST, starting from root: if both u and v are smaller than curr, LCA is in left subtree; if both are greater, LCA is in right subtree. The first node where the paths diverge (one on left, one on right, or curr equals u or v) is the LCA in O(H) time.
🎯 Key Learning Point: BST LCA takes O(H) time without storing parent pointers or paths.
Question 40 of 75 Chapter 3
What is a 'Trie' (Prefix Tree) primarily optimized for?
A. Storing floating point numbers.
B. Fast retrieval and prefix-matching of strings with O(L) search time where L is string length, independent of the number of keys stored.
C. Sorting integers.
D. Network routing packets.
✔ Correct Answer: Option B
Detailed Explanation: A Trie stores strings character by character along edges. Looking up a string of length L takes O(L) time regardless of whether the Trie holds 100 or 10,000,000 words, making it ideal for autocomplete and spell checkers.
🎯 Key Learning Point: Tries trade memory for extreme prefix search speed.
Question 41 of 75 Chapter 3
What is the diameter of a binary tree?
A. The depth of the root node.
B. The length of the longest path between any two nodes in the tree (which may or may not pass through the root).
C. The total number of leaf nodes.
D. The circumference of the tree.
✔ Correct Answer: Option B
Detailed Explanation: The diameter (width) of a tree is the maximum number of edges (or nodes) on the longest path between any two leaf nodes in the tree. It is computed in O(N) using post-order depth calculations.
🎯 Key Learning Point: Diameter at node = max(Left_Depth + Right_Depth, max(Left_Diameter, Right_Diameter)).
Question 42 of 75 Chapter 3
What is a B-Tree, and why is it preferred over BSTs for database storage engines on disk?
A. B-Trees are binary trees with red nodes.
B. B-Trees are self-balancing multi-way search trees with high branching factor (fan-out), minimizing slow disk I/O seeks by fitting thousands of keys into single disk blocks.
C. B-Trees store data in memory only.
D. B-Trees don't support range searches.
✔ Correct Answer: Option B
Detailed Explanation: Disk seeks take milliseconds, while CPU cycles take nanoseconds. B-Trees have broad fan-out (e.g. 512–1024 children per node), keeping tree height very low (3–4 levels for billions of rows) so each search needs only 3–4 disk block reads.
🎯 Key Learning Point: B+Trees store all data in leaf nodes linked sequentially, making range scans exceptionally fast.
Question 43 of 75 Chapter 3
What is the in-order successor of a node in a Binary Search Tree?
A. The parent node.
B. The node with the smallest key strictly greater than the given node (the leftmost child in its right subtree).
C. The right child always.
D. The left child always.
✔ Correct Answer: Option B
Detailed Explanation: If the node has a right subtree, the in-order successor is the minimum node in that right subtree (walk right, then walk left as far as possible). If no right subtree exists, it is the lowest ancestor whose left child is also an ancestor of the node.
🎯 Key Learning Point: In-order successor deletion is the standard technique when removing a BST node with two children.
Question 44 of 75 Chapter 3
What is a Segment Tree used for in algorithmic programming?
A. Storing text segments in editors.
B. Answering range queries (e.g. range sum, range minimum) and performing point updates in O(log N) time.
C. Memory segmentation in operating systems.
D. Generating random numbers.
✔ Correct Answer: Option B
Detailed Explanation: A Segment Tree stores precomputed intervals in a binary tree hierarchy, allowing arbitrary range queries (sum, min, max, gcd) and updates in O(log N) time on arrays of size N.
🎯 Key Learning Point: Lazy propagation allows Segment Trees to perform range updates in O(log N) time as well.
Question 45 of 75 Chapter 3
What is a Fenwick Tree (Binary Indexed Tree)?
A. A tree with binary leaves.
B. An array-backed structure that computes prefix sums and updates elements in O(log N) time using bitwise operations (i & (-i)).
C. An AVL tree.
D. A balanced heap.
✔ Correct Answer: Option B
Detailed Explanation: A Fenwick tree stores cumulative frequencies in an array where index isolation using the lowest set bit ‘(i & -i)’ enables prefix sum queries and point updates in O(log N) time with minimal O(N) space and low constant factors.
🎯 Key Learning Point: BIT uses less code and lower memory overhead than a full Segment Tree for prefix sum problems.
Curriculum Track • Module 4 of 5
Chapter 4: Heaps, Priority Queues & Hash Tables (Q46 – Q60)
Question 46 of 75 Chapter 4
In a zero-indexed array representation of a binary heap, what are the index formulas for the left child, right child, and parent of element at index i?
A. Left: 2*i + 1, Right: 2*i + 2, Parent: (i – 1) // 2
B. Left: 2*i, Right: 2*i + 1, Parent: i // 2
C. Left: i + 1, Right: i + 2, Parent: i – 1
D. Left: i * 2, Right: i * 4, Parent: i / 2
✔ Correct Answer: Option A
Detailed Explanation: Zero-indexed binary heap array layout: parent of i is at (i – 1) // 2; left child is at (2 * i + 1); right child is at (2 * i + 2). This allows complete binary trees to be stored in contiguous arrays without pointer overhead.
🎯 Key Learning Point: One-indexed heaps use Left: 2*i, Right: 2*i + 1, Parent: i // 2.
Question 47 of 75 Chapter 4
What is the time complexity to build a binary heap from an arbitrary unsorted array of N elements using the bottom-up heapify algorithm?
A. O(N log N)
B. O(N) linear time
C. O(N^2)
D. O(log N)
✔ Correct Answer: Option B
Detailed Explanation: Bottom-up heap construction runs heapify starting from the lowest internal nodes up to the root. Summing the work across all levels: N/4*(1) + N/8*(2) + N/16*(3) … converges mathematically to O(N) linear time, unlike inserting N elements one-by-one which takes O(N log N).
🎯 Key Learning Point: Building a heap in O(N) is the foundation of the Heapsort algorithm.
Question 48 of 75 Chapter 4
What is the time complexity of extracting the minimum element (extract_min) from a Min-Heap of size N?
A. O(1)
B. O(log N)
C. O(N)
D. O(N log N)
✔ Correct Answer: Option B
Detailed Explanation: Reading the min element takes O(1) time at root (index 0). But replacing the root with the last leaf and running sift-down (heapify) to restore heap order takes O(log N) time proportional to tree height.
🎯 Key Learning Point: Peek takes O(1); extract_min takes O(log N).
Question 49 of 75 Chapter 4
What collision resolution technique in hash tables chains colliding elements into a linked list or tree attached to each bucket?
A. Linear Probing
B. Separate Chaining
C. Quadratic Probing
D. Double Hashing
✔ Correct Answer: Option B
Detailed Explanation: Separate Chaining maintains an independent linked list (or balanced tree, as in Java 8 HashMap) at each bucket index. Colliding keys are simply appended to the list at that bucket.
🎯 Key Learning Point: Separate Chaining handles load factors greater than 1.0 gracefully, unlike open addressing.
Question 50 of 75 Chapter 4
What is 'Primary Clustering' in open-addressing hash tables, and which probing technique is most vulnerable to it?
A. Data clustering on disks; affects separate chaining.
B. The tendency for occupied hash slots to form long contiguous blocks, increasing average probe sequence lengths; caused by Linear Probing.
C. Memory fragmentation in heaps.
D. Sorting keys into clusters.
✔ Correct Answer: Option B
Detailed Explanation: Linear probing checks slots sequentially: (h(k) + i) % m. As occupied slots cluster together, any key hashing into the cluster extends it further, dramatically degrading lookup time to O(N).
🎯 Key Learning Point: Quadratic probing and double hashing mitigate primary clustering by introducing non-linear step sizes.
Question 51 of 75 Chapter 4
What is the 'Load Factor' (α) of a hash table, and what typical threshold triggers dynamic resizing?
A. α = Total Buckets / CPU speed; threshold = 100
B. α = Number of stored keys (n) / Number of allocated buckets (m); threshold typically 0.70 to 0.75
C. Memory size in megabytes; threshold = 1GB
D. Number of collisions; threshold = 10
✔ Correct Answer: Option B
Detailed Explanation: Load Factor α = n / m measures how full the table is. When α exceeds 0.75 in open addressing or separate chaining, the table allocates a doubled capacity array and rehashes all elements to maintain O(1) average lookup speed.
🎯 Key Learning Point: Rehashing takes O(N) time but occurs infrequently, giving O(1) amortized insertion time.
Question 52 of 75 Chapter 4
What is a 'Bloom Filter' data structure?
A. A graphical filter for image processing.
B. A space-efficient probabilistic data structure that tests set membership: it can return false positives, but NEVER returns false negatives.
C. A self-balancing tree.
D. A lossless compression algorithm.
✔ Correct Answer: Option B
Detailed Explanation: A Bloom filter uses a bit array and k independent hash functions. If any hashed bit is 0, the item is definitely NOT in the set (no false negatives). If all bits are 1, the item is PROBABLY in the set (possible false positive due to hash overlaps).
🎯 Key Learning Point: Bloom filters prevent expensive database disk lookups for non-existent keys (used in Cassandra, Bigtable, Google Chrome).
Question 53 of 75 Chapter 4
What is 'Consistent Hashing', and where is it fundamentally utilized?
A. Consistent font rendering in browsers.
B. A hashing technique where keys and nodes are mapped to a circular ring, minimizing key remapping to K/N items when servers are added or removed in distributed caches.
C. Standard hash maps in C++.
D. CRC32 error correction.
✔ Correct Answer: Option B
Detailed Explanation: In standard modulo hashing ‘hash(k) % N’, adding a server invalidates nearly all cached keys. Consistent Hashing maps both keys and servers to a 360-degree ring (0 to 2^32-1), so adding or removing a node reallocates only keys belonging to adjacent partitions.
🎯 Key Learning Point: Consistent hashing with virtual nodes is the backbone of Amazon DynamoDB, Apache Cassandra, and CDN edge routing.
Question 54 of 75 Chapter 4
What is a 'Fibonacci Heap' and what is its theoretical asymptotic advantage over a Binary Heap?
A. It stores Fibonacci numbers.
B. It supports decrease-key and insert operations in O(1) amortized constant time (compared to O(log N) in binary heaps), speeding up Dijkstra's shortest path algorithm to O(E + V log V).
C. It uses less memory than an array.
D. It operates without trees.
✔ Correct Answer: Option B
Detailed Explanation: Fibonacci heaps delay tree consolidation until extract_min is called. This lazy structure allows insert, union, and decrease-key to execute in O(1) amortized time, improving Dijkstra’s algorithm to O(E + V log V).
🎯 Key Learning Point: Due to high constant factor overhead in pointer manipulation, binary heaps are still preferred in practice over Fibonacci heaps for small/medium graphs.
Question 55 of 75 Chapter 4
How does Double Hashing compute the probe sequence for collision resolution?
A. hash1(k) + hash2(k)
B. (hash1(k) + i * hash2(k)) % TableSize (for i = 0, 1, 2…)
C. hash1(hash2(k))
D. hash1(k)^2
✔ Correct Answer: Option B
Detailed Explanation: Double hashing uses two independent hash functions: hash1 computes the initial index, and hash2 computes the step size. Because the step size depends on the key value, it avoids both primary and secondary clustering.
🎯 Key Learning Point: hash2(k) must evaluate to a non-zero value coprime to TableSize (achieved by making TableSize prime).
Question 56 of 75 Chapter 4
What is the worst-case time complexity of Heapsort on an array of N elements?
A. O(N^2)
B. O(N log N)
C. O(N)
D. O(log N)
✔ Correct Answer: Option B
Detailed Explanation: Building the heap takes O(N) time. Then N extract_max operations are performed, each taking O(log N) time to sift down. Total time is strictly O(N log N) in all cases (best, average, worst) with O(1) in-place auxiliary space.
🎯 Key Learning Point: Unlike Quicksort (which has O(N^2) worst-case), Heapsort guarantees O(N log N) worst-case in O(1) space.
Question 57 of 75 Chapter 4
What data structure does an LRU (Least Recently Used) Cache combine to achieve O(1) get() and O(1) put() operations?
A. Binary Search Tree and Array
B. Hash Map and Doubly Linked List
C. Stack and Queue
D. Heap and Set
✔ Correct Answer: Option B
Detailed Explanation: The Hash Map maps keys to nodes in O(1) time. The Doubly Linked List maintains usage order: accessing or adding an item moves its node to the head in O(1) time; evicting the least recently used item removes the tail node in O(1) time.
🎯 Key Learning Point: Java’s LinkedHashMap and Python’s OrderedDict use this exact architecture.
Question 58 of 75 Chapter 4
What is a 'Cuckoo Hash Table'?
A. A hash table that plays bird sounds.
B. An open-addressing structure with 2 hash functions that achieves guaranteed O(1) worst-case lookup time by displacing existing keys to alternate locations.
C. A recursive tree.
D. A cryptographic hash algorithm.
✔ Correct Answer: Option B
Detailed Explanation: Cuckoo hashing uses two hash functions h1 and h2. A key is stored in either h1(k) or h2(k). If both slots are occupied, the newly inserted key evicts the existing occupant to its alternate slot (like a cuckoo bird pushing eggs). Lookups check at most 2 locations, guaranteeing O(1) worst-case search.
🎯 Key Learning Point: Cuckoo hashing guarantees O(1) worst-case lookup time, making it valuable in network routing tables.
Question 59 of 75 Chapter 4
In a Max-Heap, where is the minimum element located?
A. At index 0 (root).
B. In one of the leaf nodes (indices ⌊N/2⌋ to N – 1).
C. In the left child of the root.
D. Max-heaps cannot contain minimum values.
✔ Correct Answer: Option B
Detailed Explanation: In a Max-Heap, every parent is greater than or equal to its children. Therefore, the minimum element cannot have children and must reside in one of the leaf nodes, which occupy indices from ⌊N/2⌋ to N – 1.
🎯 Key Learning Point: Finding the minimum in a Max-Heap takes O(N) linear time to scan the leaf nodes.
Question 60 of 75 Chapter 4
What property must a cryptographic hash function satisfy to prevent pre-image attacks?
A. It must be reversible.
B. Given a hash value h, it must be computationally infeasible to find any message m such that hash(m) = h (One-way property).
C. It must produce outputs under 8 bits.
D. It must be linear.
✔ Correct Answer: Option B
Detailed Explanation: Pre-image resistance (one-wayness) ensures that given an output hash, reversing it to discover the original input is computationally impossible.
🎯 Key Learning Point: Cryptographic hash functions require: Pre-image resistance, Second pre-image resistance, and Collision resistance.
Curriculum Track • Module 5 of 5
Chapter 5: Graphs, BFS, DFS & Shortest Path Algorithms (Q61 – Q75)
Question 61 of 75 Chapter 5
What is the time complexity of Breadth-First Search (BFS) and Depth-First Search (DFS) on a graph with V vertices and E edges represented using an Adjacency List?
A. O(V^2)
B. O(V + E)
C. O(V * E)
D. O(E log V)
✔ Correct Answer: Option B
Detailed Explanation: In an adjacency list representation, BFS and DFS visit every vertex once (O(V)) and inspect each directed edge once (or undirected edge twice) (O(E)). Total time complexity is strictly linear: O(V + E).
🎯 Key Learning Point: If represented using an Adjacency Matrix, both BFS and DFS take O(V^2) time regardless of edge count.
Question 62 of 75 Chapter 5
Which data structure is fundamentally used to implement Breadth-First Search (BFS) vs Depth-First Search (DFS)?
A. BFS uses a Queue (FIFO); DFS uses a Stack (LIFO) or system call stack recursion.
B. BFS uses a Stack; DFS uses a Queue.
C. Both use Priority Queues.
D. Both use Hash Maps.
✔ Correct Answer: Option A
Detailed Explanation: BFS explores neighbors level-by-level using a FIFO Queue. DFS explores deep along a single branch using a LIFO Stack (or recursive function calls).
🎯 Key Learning Point: BFS finds the shortest path in an unweighted graph; DFS is used for topological sorting and cycle detection.
Question 63 of 75 Chapter 5
Why does Dijkstra's Single-Source Shortest Path algorithm fail or produce incorrect results on graphs with negative edge weights?
A. It consumes too much memory.
B. Dijkstra uses a greedy approach assuming that once a vertex distance is finalized, no shorter path can be found; negative edges violate this monotonic property.
C. Negative numbers cannot be stored in priority queues.
D. It causes infinite loops.
✔ Correct Answer: Option B
Detailed Explanation: Dijkstra marks a node’s distance as finalized as soon as it is extracted from the min-priority queue, assuming edge additions only increase distance. A negative edge can retroactively provide a cheaper path to an already finalized node.
🎯 Key Learning Point: Use the Bellman-Ford algorithm (O(V * E)) or SPFA on graphs containing negative edge weights.
Question 64 of 75 Chapter 5
What is the time complexity of Dijkstra’s Algorithm implemented with a Min-Heap (Binary Heap) on a graph with V vertices and E edges?
A. O(V^2)
B. O((V + E) log V)
C. O(V * E)
D. O(V^3)
✔ Correct Answer: Option B
Detailed Explanation: Each vertex is extracted from the heap once (V * log V). In the worst case, each edge update (relaxation) triggers a decrease-key/insertion into the heap (E * log V). Total time is O((V + E) log V).
🎯 Key Learning Point: With a Fibonacci Heap, Dijkstra runs in O(E + V log V).
Question 65 of 75 Chapter 5
What algorithm finds the Shortest Path between ALL pairs of vertices in a weighted graph in O(V^3) time?
A. Dijkstra's Algorithm
B. Floyd-Warshall Algorithm
C. Kruskal's Algorithm
D. Prim's Algorithm
✔ Correct Answer: Option B
Detailed Explanation: Floyd-Warshall is a dynamic programming algorithm that evaluates all pairs (i, j) by testing whether path (i -> k -> j) is shorter than the direct path, iterating k from 1 to V in 3 nested loops: O(V^3) time.
🎯 Key Learning Point: Floyd-Warshall can detect negative weight cycles if the distance from any node to itself becomes negative: dist[i][i] < 0.
Question 66 of 75 Chapter 5
What is a Directed Acyclic Graph (DAG), and which operation is strictly valid only on DAGs?
A. Binary search
B. Topological Sorting
C. Matrix multiplication
D. Graph coloring
✔ Correct Answer: Option B
Detailed Explanation: A DAG is a directed graph containing no directed cycles. Topological sorting linearizes vertices such that for every directed edge u -> v, u appears before v. If a cycle exists, topological ordering is mathematically impossible.
🎯 Key Learning Point: Topological sorting can be performed using Kahn’s Algorithm (indegree-based BFS) or DFS post-order reversal in O(V + E) time.
Question 67 of 75 Chapter 5
What data structure does Kruskal's Minimum Spanning Tree (MST) algorithm rely upon to detect cycles in near O(1) time?
A. Segment Tree
B. Disjoint Set Union (DSU / Union-Find) with path compression and union by rank
C. Stack
D. Red-Black Tree
✔ Correct Answer: Option B
Detailed Explanation: Kruskal sorts edges by weight and greedily adds the cheapest edge if it connects two disconnected components. DSU checks whether two vertices share the same representative in near-constant O(α(V)) time using the Inverse Ackermann function.
🎯 Key Learning Point: Kruskal’s time complexity is dominated by sorting edges: O(E log E) = O(E log V).
Question 68 of 75 Chapter 5
How does Prim's Minimum Spanning Tree algorithm differ from Kruskal's algorithm?
A. Prim's grows a single connected tree from an arbitrary starting vertex; Kruskal's grows a forest of disconnected components by greedily picking the global lightest edge.
B. Prim's works only on directed graphs.
C. Kruskal's algorithm uses BFS.
D. Prim's cannot handle weighted graphs.
✔ Correct Answer: Option A
Detailed Explanation: Prim’s is a vertex-based algorithm that expands a single contiguous tree using a priority queue. Kruskal’s is an edge-based algorithm that considers all edges globally, merging disjoint components.
🎯 Key Learning Point: Prim’s is faster on dense graphs (E ≈ V^2); Kruskal’s is faster on sparse graphs (E ≈ V).
Question 69 of 75 Chapter 5
What is an 'Articulation Point' (Cut Vertex) in an undirected graph?
A. A vertex with degree 0.
B. A vertex whose removal increases the number of connected components in the graph (disconnecting the graph).
C. A vertex connected to all other vertices.
D. The vertex with highest weight.
✔ Correct Answer: Option B
Detailed Explanation: An articulation point is a critical single point of failure in network topology: removing it (and its incident edges) splits the graph into two or more disconnected subgraphs. Tarjan’s algorithm finds all articulation points in O(V + E) using discovery and low values.
🎯 Key Learning Point: A bridge (cut-edge) is an edge whose removal disconnects the graph.
Question 70 of 75 Chapter 5
How does Bellman-Ford detect whether a graph contains a negative weight cycle reachable from the source vertex?
A. By sorting edges.
B. It relaxes all E edges V – 1 times; if a V-th relaxation step still decreases any vertex distance, a negative cycle exists.
C. By counting odd degree vertices.
D. By running BFS.
✔ Correct Answer: Option B
Detailed Explanation: In a graph with V vertices, the shortest path without cycles can have at most V – 1 edges. If relaxing edges on a V-th iteration still reduces distance, negative edges are continually reducing path cost in an infinite loop.
🎯 Key Learning Point: Bellman-Ford runs in O(V * E) time, slower than Dijkstra, but handles negative weights.
Question 71 of 75 Chapter 5
What is a 'Bipartite Graph'?
A. A graph with 2 edges.
B. A graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V (no edges connect vertices in the same set).
C. A graph containing only directed loops.
D. A complete graph.
✔ Correct Answer: Option B
Detailed Explanation: A graph is bipartite if its vertices can be 2-colored such that no two adjacent vertices share the same color. A graph is bipartite if and only if it contains no odd-length cycles.
🎯 Key Learning Point: Check bipartiteness in O(V + E) using BFS/DFS 2-coloring.
Question 72 of 75 Chapter 5
What theorem states that a connected undirected graph has an Eulerian Circuit (a closed trail visiting every edge exactly once) if and only if every vertex has an even degree?
A. Euler's Theorem
B. Kuratowski's Theorem
C. Hall's Marriage Theorem
D. Cayley's Formula
✔ Correct Answer: Option A
Detailed Explanation: Euler proved in 1736 (Seven Bridges of Königsberg) that an Eulerian circuit exists if and only if all vertices have an even degree. If exactly 2 vertices have odd degree, an Eulerian path exists (starting at one odd vertex and ending at the other).
🎯 Key Learning Point: Eulerian circuit visits every EDGE once; Hamiltonian cycle visits every VERTEX once (NP-complete).
Question 73 of 75 Chapter 5
What is Tarjan’s Strongly Connected Components (SCC) algorithm?
A. A shortest path algorithm.
B. A linear-time O(V + E) algorithm based on DFS that uses discovery times and low-link values to partition a directed graph into maximal strongly connected subgraphs.
C. A maximum flow algorithm.
D. A sorting algorithm.
✔ Correct Answer: Option B
Detailed Explanation: A Strongly Connected Component (SCC) is a subgraph where every vertex is reachable from every other vertex. Tarjan’s algorithm uses a single DFS traversal and a stack to identify all SCCs in O(V + E) time.
🎯 Key Learning Point: Kosaraju’s algorithm also finds SCCs in O(V + E) using two DFS passes and graph transposition.
Question 74 of 75 Chapter 5
What problem does the Ford-Fulkerson method (and Edmonds-Karp algorithm) solve?
A. Traveling Salesperson Problem
B. Maximum Network Flow in a flow network from source s to sink t
C. Minimum vertex coloring
D. String matching
✔ Correct Answer: Option B
Detailed Explanation: Ford-Fulkerson computes maximum flow by repeatedly finding augmenting paths in the residual graph until no path exists. Edmonds-Karp implements this using BFS to find shortest augmenting paths in O(V * E^2) time.
🎯 Key Learning Point: Max-Flow Min-Cut Theorem: The maximum amount of flow passing from source to sink equals the total weight of edges in the minimum cut.
Question 75 of 75 Chapter 5
What algorithm solves the Single-Source Shortest Path problem on a Directed Acyclic Graph (DAG) in strict O(V + E) linear time, even with negative edge weights?
A. Dijkstra's Algorithm
B. Topological Sort followed by single-pass edge relaxation in topological order
C. Floyd-Warshall
D. Prim's Algorithm
✔ Correct Answer: Option B
Detailed Explanation: Because a DAG has no cycles, computing a topological sort takes O(V + E) time. Relaxing edges in topological order ensures each vertex distance is finalized before evaluating downstream neighbors, computing shortest paths in O(V + E) time regardless of negative weights.
🎯 Key Learning Point: DAG shortest path in O(V + E) is the engine behind Critical Path Method (CPM) project scheduling.

Explore Other Comprehensive 75-Question Subject Tracks

Continue your preparation across our active curriculum tracks. Every track provides 75 verified questions across 5 complete chapters.

🟢 100% Live Track
C Programming
75 Qs • 5 Chapters • Practice Now →
🟢 100% Live Track
Python Programming
75 Qs • 5 Chapters • Practice Now →
Active Track
📍 Data Structures
75 Qs • 5 Chapters (You are here)
🟢 100% Live Track
DBMS & SQL
75 Qs • 5 Chapters • Practice Now →
🟢 100% Live Track
Computer Networks
75 Qs • 5 Chapters • Practice Now →
🟢 100% Live Track
Operating Systems
75 Qs • 5 Chapters • Practice Now →
🟢 100% Live Track
Quantitative Aptitude
75 Qs • 5 Chapters • Practice Now →
📚 View All 92+ Subjects in Master Directory
Share
  • Facebook
Queryiest

Queryiest

Enlightened

Queryiest – Technology Writer | Software Developer | Digital Learning Enthusiast

Queryiest is a technology writer, software developer, and knowledge-sharing enthusiast passionate about simplifying complex technical concepts for students, professionals, and lifelong learners. With expertise in software development, programming, cybersecurity, artificial intelligence, digital tools, and emerging technologies, Queryiest creates practical, research-driven content that helps readers solve real-world problems. As a regular contributor to RTSALL, Queryiest publishes easy-to-understand guides, coding resources, technology news, career advice, and educational tutorials designed for beginners and professionals alike. Every article focuses on accuracy, clarity, and actionable insights to help readers stay informed in the rapidly evolving digital world. Whether it's programming, software engineering, AI, cybersecurity, online platforms, or digital productivity, Queryiest believes that quality knowledge should be accessible to everyone. The goal is to build a trusted learning resource where readers can discover reliable answers, improve their technical skills, and make informed decisions. Areas of Expertise: Software Development, Programming, Cybersecurity, Artificial Intelligence, Technology News, Coding Interview Preparation, Digital Learning, Productivity Tools, and Online Knowledge Sharing.

    Sidebar

    Ask A Question
    • Popular
    • Answers
    • Queryiest

      What is a database?

      • 3 Answers
    • Anonymous

      How to rotate an array in-place with O(1) space and ...

      • 3 Answers
    • hannah

      What steps can businesses take to identify the most valuable ...

      • 2 Answers
    • Vikram
      aarav0 added an answer Direct Technical Solution: Unlike IVFFlat (which partitions vector spaces with… September 11, 2026 at 9:57 pm
    • Abhishek
      Abhishek added an answer Direct Technical Solution: In C++20, range view adaptors (like std::views::filter,… September 11, 2026 at 9:57 pm
    • Sneha Patel
      Anonymous added an answer Direct Technical Solution: torch.cuda.empty_cache() releases only cached (unallocated) blocks back… September 11, 2026 at 9:57 pm

    Top Members

    Queryiest

    Queryiest

    • 201 Questions
    • 295 Points
    Enlightened
    Anonymous

    Anonymous

    • 11 Questions
    • 42 Points
    Begginer
    paperubofficial

    paperubofficial

    • 0 Questions
    • 22 Points
    Begginer

    Trending Tags

    ai asp.net aws basics aws certification aws console aws free tier aws login aws scenario-based questions c++ career cyber security cyber security interview git java javascript jobs jquery net core net core interview questions sql

    Explore

    • Home
    • Add group
    • Groups page
    • Communities
    • Questions
      • DSA Problems
    • Polls
    • Tags
    • Badges
    • Users
    • Help
    • New Questions
    • Trending Questions
    • Must read Questions
    • Hot Questions

    Footer

    About Us

    • Meet The Team
    • Blog
    • About Us
    • Contact Us

    Legal Stuff

    • Privacy Policy
    • Disclaimer
    • Terms & Conditions

    Help

    • Knowledge Base
    • Support

    Follow

    © 2023-25 RTSALL. All Rights Reserved