The minimum is removed from the min-heap by moving the last element to the root and sifting it down. What is the resulting array?
Correct answer B. [3, 4, 7, 10, 8]
Subject / 609 questions
Programming MCQs
Page 12 of Programming multiple-choice questions with answers. Tap an option to check yourself.
Page 12 of 31
Which data structure does breadth-first search (BFS) use to keep track of vertices still to be explored?
Correct answer D. Queue
Which data structure is used, explicitly or through recursion, to implement depth-first search (DFS)?
Correct answer C. Stack
Advertisement
What is the space required to store a graph with V vertices and E edges as an adjacency matrix?
Correct answer D. O(V²)
An undirected graph has edges A–B, A–C, B–D, B–E, C–F and E–F, and each adjacency list is kept in alphabetical order. What is the depth-first search order starting from A?
Correct answer D. A, B, D, E, F, C
A directed graph has edges A→B, A→C, B→D, C→D and D→E. Which of these is a valid topological order?
Correct answer B. A, C, B, D, E
For which kind of graph does a topological ordering exist?
Correct answer C. A directed acyclic graph (DAG)
A weighted undirected graph has edges A–B (1), B–C (2), A–C (3), B–D (4), C–D (5), C–E (6) and D–E (7). What is the total weight of its minimum spanning tree found by Kruskal’s algorithm?
Correct answer B. 13
How many edges does a spanning tree of a connected graph with 12 vertices contain?
Correct answer C. 11
Advertisement
Why can Dijkstra’s shortest-path algorithm give wrong results on a graph with negative edge weights?
Correct answer C. It finalises a vertex's distance when the vertex is removed from the queue, assuming later paths cannot be shorter
A directed graph has edges S→A (4), S→B (1), B→A (2), A→C (1) and B→C (5). What is the shortest distance from S to C?
Correct answer C. 4
Which algorithm detects a cycle in a linked list using two pointers that move at different speeds?
Correct answer C. Floyd's tortoise and hare algorithm
What is the extra space required by Floyd’s cycle-detection algorithm on a linked list of n nodes?
Correct answer A. O(1)
What is the time complexity of reversing a singly linked list of n nodes in place?
Correct answer B. O(n)
What is the main purpose of a header (dummy) node in a linked list?
Correct answer B. To remove special cases for inserting or deleting at the front of the list
Advertisement
How many pointers must be changed to insert a new node between two existing nodes of a doubly linked list?
Correct answer A. 4
Which principle does a stack follow?
Correct answer A. Last In, First Out (LIFO)
Starting with an empty stack, the operations push 1, push 2, push 3, pop, push 4, pop, pop, push 5, pop are performed. In what order are values popped?
Correct answer D. 3, 4, 2, 5
What is the condition called when a pop operation is attempted on an empty stack?
Correct answer B. Underflow
For a stack implemented with an array of size MAX where top starts at −1, which condition indicates the stack is full?
Correct answer A. top == MAX − 1