MCQ Flashcards
(15 cards)
In the context of asymptotic analysis, which of the following is true about the
Θ (Theta) notation?
a) It represents the upper bound of an algorithm’s running time.
b) It denotes the lower bound of an algorithm’s running time.
c) It signifies an algorithm’s average-case running time.
d) It is used to denote the exact running time of an algorithm.
e) It bounds the function from above and below, hence represents the exact growth of
the running time.
Correct answer:
d) It is used to denote the exact running time of an algorithm.
- What is the time complexity of an algorithm described by the recurrence
T(n) = 3T(n/3) + n^2?
a) O(n log n)
b) O(n^2)
c) O(n^2 log n)
d) O(n^3)
e) O(2^n)
Correct answer: b) O(n^2)
- What is a key characteristic of linear data structures?
a) They allow hierarchical relationships between elements.
b) They store elements in a non-sequential manner.
c) Each element in the structure has multiple predecessors and successors.
d) Elements cannot be accessed directly, only sequentially.
e) There is a unique first and last element, with each element having a unique
predecessor and successor.
Correct answer: e)
There is a unique first and last element, with each element having a unique
predecessor and successor.
- When implementing a list using arrays, what is a major consideration to keep in mind?
a) The elements in the list are linked using pointers.
b) The size of the list is dynamic and can grow as needed.
c) Arrays allow for both sequential and direct access to elements.
d) Memory allocation for the list is static and predetermined.
e) The implementation is less complex than linked lists.
Correct answer: d
d) Memory allocation for the list is static and predetermined.
- In a job interview, you’re asked about the data structure that could help solve the
problem of matching parentheses. The problem consists of reading an array of n
characters, each of which is either an open or a close parenthesis, and output true of
false depending on whether they match or not. For instance, (()()) does match
but ()()( and (())) does not match.
a) Queue
b) Stack
c) Linked List
d) Hash table
e) Graph
Correct answer: b) Stack
- If you had to sort a list of 1030 numbers ranging in value from 0 to 999999, which sort
algorithm would be the most appropriate choice?
a) Insertion Sort
b) Quicksort
c) Mergesort
d) Heapsort
e) Radixsort
Correct answer: e) RadixSort
- Which of the following sorting algorithms is typically the most efficient for very large
datasets?
a) Selection Sort
b) Bubble Sort
c) Insertion Sort
d) Quick Sort
e) Merge Sort
Correct answer: e) Merge Sort
- In the Quicksort algorithm, what role does the ‘partition’ function play?
a) It selects the best pivot for sorting.
b) It divides the array into smaller sub-arrays based on the pivot.
c) It swaps elements to ensure the pivot is in the correct position.
d) It sorts the sub-arrays after the pivot has been placed.
e) It recursively calls Quicksort on the entire array
Correct answer: c)
c) It swaps elements to ensure the pivot is in the correct position.
- What is the primary purpose of using colours (white, grey, black) in graph traversal
algorithms like Breadth-First Search (BFS)?
a) To indicate the shortest path to each node.
b) To represent different weights of edges.
c) To keep track of the discovery and exploration of the nodes.
d) To distinguish between different types of nodes.
e) To improve the aesthetic appeal of the graph representation.
Correct answer: c)
c) To keep track of the discovery and exploration of the nodes.
- In graph theory, what is a spanning tree?
a) A tree that covers all the nodes of the graph with the minimum number of edges.
b) A tree that includes all the edges of the graph.
c) A tree formed by the depth-first search algorithm.
d) A tree that spans the physical area covered by the graph.
e) A tree that contains the most direct paths between all pairs of nodes.
Correct answer: a) A tree that covers all the nodes of the graph with the minimum number of edges.
- What is the fundamental difference between a tree and a general graph?
a) Trees contain cycles, while graphs do not.
b) Trees always have more nodes than graphs.
c) A tree is a connected, undirected graph with no cycles.
d) Trees are used only in computer science, while graphs are used in various fields.
e) Graphs can have directed or undirected edges, while trees can only have undirected
edges.
Correct answer: e)
e) Graphs can have directed or undirected edges, while trees can only have undirected
edges.
- Given a connected undirected graph, a ‘cut vertex’ (or articulation point) is a vertex
whose removal increases the number of connected components in the graph. Consider
a graph with vertices {A, B, C, D, E} and edges {AB, BC, CD, DE, EA}. Which vertex is a
cut vertex?
a) Vertex A
b) Vertex B
c) Vertex C
d) Vertex D
e) No vertex is a cut vertex
Correct answer: e) No vertex is a cut vertex
Key reasoning:
* The graph forms a cycle: A–B–C–D–E–A.
* In a cycle, removing any one vertex does not disconnect the graph.
* Therefore, no single vertex increases the number of connected components.
- In a Binary Search Tree (BST), what property must all nodes in the left subtree of a
given node satisfy?
a) They must be greater than or equal to the given node.
b) They must be less than the given node.
c) They must have a higher depth than the given node.
d) They must be leaf nodes.
e) They must be complete binary trees themselves.
Correct answer: b
b) They must be less than the given node
- When performing the ‘sink’ operation in a max heap, what condition leads to a node
swap?
a) The parent node is smaller than either of its children.
b) The parent node is larger than both of its children.
c) The left child is larger than the right child.
d) The children nodes are in the wrong order.
e) The parent node is equal to one of its children.
Correct answer: ) The parent node is smaller than either of its children
* ‘Sink’ (heapify down) maintains max-heap property by swapping with larger child
- In heap sort, what is the initial step before the actual sorting process begins?
a) Building a heap from the given data.
b) Sorting the leaf nodes.
c) Performing a binary search.
d) Swapping the root and last element.
e) Dividing the heap into two sub-heaps.
Correct answer: a)
a) Building a heap from the given data
* Step 1 in heap sort: heapify the array to form a valid max-heap before sorting
