How many edges does a spanning tree of a connected graph with 12 vertices contain?
Correct answer C. 11
Subject / 421 questions
Programming MCQs
Page 3 of Programming multiple-choice questions with answers. Tap an option to check yourself.
Page 3 of 22
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
Advertisement
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
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)
Advertisement
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
Which data structure does a program’s run-time system use to manage function calls and recursion?
Correct answer C. Stack
What is the postfix form of the infix expression A + B * C − D / E?
Correct answer A. A B C * + D E / −
What is the postfix form of the infix expression (A + B) * (C − D)?
Correct answer B. A B + C D − *
Advertisement
What is the value of the postfix expression 8 2 3 * − 4 2 / + ?
Correct answer A. 4
What is the value of the postfix expression 9 3 / 2 ^ 1 + , where ^ means exponentiation?
Correct answer D. 10
What is the postfix form of A ^ B ^ C, where ^ is exponentiation and is right-associative?
Correct answer B. A B C ^ ^
Which data structure is most suitable for checking whether the brackets in an expression such as {} are balanced?
Correct answer A. Stack
In a circular queue implemented with an array of size n, using front and rear indices with one slot always left empty, which condition means the queue is full?
Correct answer D. (rear + 1) % n == front