An algorithm must have five essential characteristics: finiteness (termination), definiteness (clear instructions), input, output, and effectiveness (basic enough to be carried out).
Incorrect! Try again.
22When designing an algorithm, what is typically the primary concern immediately after understanding the problem?
Fundamentals of Algorithmic Problem Solving:
Medium
A.Choosing between exact and approximate problem solving
B.Ascertaining the capabilities of the computational device
C.Deciding on appropriate data structures
D.Proving the algorithm's correctness
Correct Answer: Ascertaining the capabilities of the computational device
Explanation:
After understanding the problem, the next step is usually understanding the capabilities of the computing device, such as whether it supports sequential or parallel execution.
Incorrect! Try again.
23Which design technique is characterized by dividing a problem into smaller instances of the same problem, solving them recursively, and then combining their solutions?
Basic Algorithm Design Techniques
Medium
A.Dynamic Programming
B.Greedy Approach
C.Backtracking
D.Divide and Conquer
Correct Answer: Divide and Conquer
Explanation:
Divide and Conquer involves dividing a problem into smaller subproblems, solving them recursively, and then combining their results to solve the original problem.
Incorrect! Try again.
24Which of the following is NOT typically considered when analyzing an algorithm's efficiency?
Analyzing Algorithm
Medium
A.Space efficiency
B.Simplicity of the code syntax
C.Optimality
D.Time efficiency
Correct Answer: Simplicity of the code syntax
Explanation:
Algorithm analysis focuses on time efficiency, space efficiency, and optimality, rather than the aesthetic simplicity of the programming language syntax used to implement it.
Incorrect! Try again.
25Which linear data structure is most appropriate for evaluating postfix mathematical expressions?
Linear Data Structure
Medium
A.Stack
B.Queue
C.Linked List
D.Hash Table
Correct Answer: Stack
Explanation:
A stack is the ideal data structure for evaluating postfix expressions because it operates on a Last-In-First-Out (LIFO) principle, allowing operands to be stored and popped when operators are encountered.
Incorrect! Try again.
26In a simple undirected graph with vertices, what is the maximum number of edges?
Graphs and Trees
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
In a simple undirected graph, every vertex can connect to every other vertex, resulting in unique edges.
Incorrect! Try again.
27For a matrix multiplication algorithm involving two matrices, what is the most appropriate measure of input size?
Measuring of Input Size
Medium
A.The dimension of the matrices
B.The value of the largest element in the matrices
C.The total sum of all elements
D.The number of rows in the first matrix only
Correct Answer: The dimension of the matrices
Explanation:
The order of the matrix, , determines the number of operations required, making it the standard measure of input size for matrix operations.
Incorrect! Try again.
28Why is counting the number of basic operations preferred over measuring actual execution time in seconds?
Units for Measuring Running Time
Medium
A.It is easier to program
B.It is independent of hardware and software environments
C.It depends on the hardware speed
D.It depends on the compiler used
Correct Answer: It is independent of hardware and software environments
Explanation:
Counting basic operations provides an objective metric that evaluates the algorithm itself, unaffected by processor speed, compiler optimizations, or system load.
Incorrect! Try again.
29Which of the following functions has the highest order of growth?
Order of Growth
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The factorial function grows faster than exponential functions like , polynomial functions like , and linearithmic functions like .
Incorrect! Try again.
30In Sequential Search on an array of size , what is the average-case number of key comparisons for a successful search (assuming all positions are equally likely)?
Worst-Case, Best-Case, and Average-Case Efficiencies
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
For a successful search, the key can be found at position with probability . The average number of comparisons is .
Incorrect! Try again.
31If , which of the following is true regarding its Big-O notation?
O(Big-oh)-notation
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Big-O notation represents the upper bound. For a polynomial, the highest degree term dominates as grows, so .
Incorrect! Try again.
32What does formally imply?
Big-omega notation
Medium
A. grows strictly slower than .
B.There exist positive constants and such that for all .
C.There exist positive constants and such that for all .
D.
Correct Answer: There exist positive constants and such that for all .
Explanation:
Big-Omega establishes a lower bound, meaning grows at least as fast as up to a constant factor for large .
Incorrect! Try again.
33Which of the following statements is equivalent to ?
Big-theta notation
Medium
A. and
B. but
C. but
D.Neither nor applies to
Correct Answer: and
Explanation:
Big-Theta () provides a tight bound, meaning the function is bounded both above (Big-O) and below (Big-Omega) by multiplied by different constants.
Incorrect! Try again.
34If and , what is the tightest bound for ?
Useful Property Involving the Asymptotic Notations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
When adding two functions, the asymptotic complexity is determined by the term that has the higher order of growth, hence .
Incorrect! Try again.
35If , where is a constant, what can be concluded?
Using Limits for Comparing Orders of Growth
Medium
A. has a smaller order of growth than
B. has a larger order of growth than
C.No conclusion can be drawn
D. and have the same order of growth
Correct Answer: and have the same order of growth
Explanation:
A limit converging to a positive constant indicates that both functions grow at the same rate asymptotically, implying .
Incorrect! Try again.
36Which of the following sorting algorithms exhibits a worst-case time complexity of but an average-case of ?
Worst-Case, Best-Case, and Average-Case Efficiencies
Medium
A.Bubble Sort
B.Quick Sort
C.Merge Sort
D.Heap Sort
Correct Answer: Quick Sort
Explanation:
Quick Sort generally performs with average complexity, but its worst-case time complexity degrades to if the pivot choices are repeatedly poor.
Incorrect! Try again.
37What is the primary advantage of a Doubly Linked List over a Singly Linked List?
Fundamental Data Structure:
Medium
A.It allows traversal in both forward and backward directions
B.It inherently prevents cycle formation
C.It requires less memory per node
D.It provides access time to the -th element
Correct Answer: It allows traversal in both forward and backward directions
Explanation:
A Doubly Linked List stores pointers to both the next and previous nodes, enabling bi-directional traversal, unlike a Singly Linked List.
Incorrect! Try again.
38In a binary search tree (BST), an inorder traversal yields the elements in which order?
Graphs and Trees
Medium
A.Random order
B.Level-by-level order
C.Descending order
D.Ascending order
Correct Answer: Ascending order
Explanation:
An inorder traversal of a BST visits the left child, the root, and then the right child. Because of the BST property, this results in a sequence sorted in ascending order.
Incorrect! Try again.
39Evaluate the limit to determine the relative order of growth.
Using Limits for Comparing Orders of Growth
Medium
A., meaning grows faster than
B.$0$, meaning grows faster than
C.$1$, meaning they have the same order of growth
D.$0$, meaning grows faster than
Correct Answer: $0$, meaning grows faster than
Explanation:
Using L'Hôpital's rule, the derivative of is , and the derivative of is $1$. The limit as is $0$, showing linear functions grow strictly faster than logarithmic ones.
Incorrect! Try again.
40What defines the 'basic operation' of an algorithm?
Fundamentals of the Analysis of Algorithm Efficiency:
Medium
A.The initialization of loop counters
B.The operation that consumes the most time or is executed the most frequently
C.The first operation written in the pseudo-code
D.The return statement of the algorithm
Correct Answer: The operation that consumes the most time or is executed the most frequently
Explanation:
The basic operation is typically the most time-consuming operation in the innermost loop, heavily dictating the overall running time of the algorithm.
Incorrect! Try again.
41Evaluate the limit where and . What does the result imply about their asymptotic relationship?
Using Limits for Comparing Orders of Growth
Hard
A.The limit is undefined, so they are asymptotically incomparable
B.The limit is , implying
C.The limit is a positive constant, implying
D.The limit is $0$, implying
Correct Answer: The limit is $0$, implying
Explanation:
By applying L'Hopital's rule repeatedly, any polynomial function of a logarithm grows strictly slower than any positive fractional power of . Hence the limit is $0$, meaning .
Incorrect! Try again.
42Which of the following statements about Big-O notation is FALSE for positive functions and ?
O(Big-oh)-notation
Hard
A.If , then
B.If , then
C.If and , then
D.If , then
Correct Answer: If , then
Explanation:
Big-O notation does not generally hold for exponentials. For example, let and . Clearly , but is not .
Incorrect! Try again.
43Consider an algorithm that searches a sorted array of distinct elements by probing the element at index , then performs a linear search. What is the average-case efficiency if the search key is known to be in the array and uniformly distributed?
Worst-Case, Best-Case, and Average-Case Efficiencies
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The linear search will search the remaining elements. Since the key is uniformly distributed, the average number of checks in the linear portion is about , which is .
Incorrect! Try again.
44Let and . What is the relationship between and ?
Big-theta notation
Hard
A.
B.
C.They are not asymptotically comparable
D.
Correct Answer:
Explanation:
By Stirling's approximation, . Therefore, .
Incorrect! Try again.
45Consider the recurrence relation . What is the asymptotic time complexity of ?
Analyzing Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Let . Then . Letting , we get , which solves to . Substituting back , we get .
Incorrect! Try again.
46Rank the following functions by order of growth from slowest to fastest: , , , .
Order of Growth
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Comparing the orders: is near linear, is quadratic-logarithmic, which grows faster than any polynomial, and which grows even faster. Thus, .
Incorrect! Try again.
47In a connected undirected graph with vertices and edges, a DFS tree is constructed. Which of the following edges CANNOT exist in relative to the DFS tree?
Graphs and Trees
Hard
A.Back edges to an ancestor
B.Tree edges
C.Cross edges between different subtrees
D.Forward edges to a descendant
Correct Answer: Cross edges between different subtrees
Explanation:
In an undirected graph, DFS traversal classifies edges into only two types: tree edges and back edges. Cross edges and forward edges do not exist in the DFS classification for undirected graphs.
Incorrect! Try again.
48When analyzing the time complexity of an algorithm that tests whether an integer is prime by trial division up to , what is the appropriate measure of the input size and the resulting complexity?
Measuring of Input Size
Hard
A., Time
B., Time
C., Time
D., Time
Correct Answer: , Time
Explanation:
The input size is the number of bits required to represent , so . The algorithm takes steps, which is . Thus it is an exponential time algorithm in terms of input size.
Incorrect! Try again.
49Which of the following limits proves that ?
Useful Property Involving the Asymptotic Notations
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By definition, if . For and , the ratio approaches infinity, establishing .
Incorrect! Try again.
50Which design technique is MOST intrinsically linked to solving overlapping subproblems by storing their results?
Basic Algorithm Design Techniques
Hard
A.Backtracking
B.Divide and Conquer
C.Dynamic Programming
D.Greedy Method
Correct Answer: Dynamic Programming
Explanation:
Dynamic Programming is specifically designed to handle overlapping subproblems by memoization or tabulation (storing results) to prevent redundant calculations, unlike Divide and Conquer which typically applies to non-overlapping subproblems.
Incorrect! Try again.
51Let be a polynomial of degree with a positive leading coefficient, and be a polynomial of degree with a positive leading coefficient. Under what condition is ?
Big-omega notation
Hard
A.
B. only
C.
D.
Correct Answer:
Explanation:
means grows at least as fast as . For polynomials, this holds true if and only if the degree of is greater than or equal to the degree of ().
Incorrect! Try again.
52Why is counting the number of basic operations preferred over measuring the actual execution time in seconds when analyzing algorithmic efficiency?
Units for Measuring Running Time
Hard
A.Basic operations naturally account for operating system context switches.
B.Execution time in seconds cannot be converted into asymptotic notation.
C.Actual time depends on specific hardware, compiler, and environmental factors, whereas operation count is machine-independent.
D.Basic operations always take exactly 1 nanosecond, making the calculation perfectly precise.
Correct Answer: Actual time depends on specific hardware, compiler, and environmental factors, whereas operation count is machine-independent.
Explanation:
Counting basic operations provides an abstract, machine-independent metric for an algorithm's efficiency, allowing comparison of algorithms regardless of the underlying hardware or software environment.
Incorrect! Try again.
53You are implementing a Queue using exactly two Stacks. What is the amortized time complexity of the enqueue and dequeue operations, respectively?
Linear Data Structure
Hard
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:
By pushing to one stack for enqueue and popping from the other for dequeue (transferring elements only when the second stack is empty), each element is pushed and popped at most twice. Thus, the amortized cost per operation is .
Incorrect! Try again.
54Which phase of algorithmic problem solving immediately follows the design of the algorithm and precedes coding?
Fundamentals of Algorithmic Problem Solving:
Hard
A.Understanding the problem
B.Proving the algorithm's correctness
C.Testing the algorithm
D.Analyzing the algorithm's efficiency
Correct Answer: Proving the algorithm's correctness
Explanation:
After designing an algorithm, one must formally or informally prove its correctness to ensure it solves the intended problem for all valid inputs before proceeding to implement and analyze it extensively.
Incorrect! Try again.
55Given the nested loops:
for i = 1 to n
for j = 1 to i^2
for k = 1 to n/2
count++
What is the exact asymptotic order of the count variable?
Analyzing Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The inner loop runs times. The middle loop runs times. The total operations are . Since , multiplying by yields .
Incorrect! Try again.
56An algorithm requires operations. What class of problems typically exhibits this extremely slow-growing complexity?
Algorithms
Hard
A.Computing the Fibonacci sequence recursively
B.Finding the maximum in an unsorted array
C.Binary search on an unbalanced tree
D.Interpolation search on uniformly distributed sorted data
Correct Answer: Interpolation search on uniformly distributed sorted data
Explanation:
Interpolation search has an average-case time complexity of for uniformly distributed sorted arrays, which aligns with the given operational count.
Incorrect! Try again.
57For the QuickSelect algorithm used to find the -th smallest element in an unsorted array of size , what are the expected average-case and strict worst-case time complexities, respectively?
Worst-Case, Best-Case, and Average-Case Efficiencies
Hard
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:
QuickSelect uses partitioning similar to QuickSort. On average, it discards a fraction of the array, leading to the geometric series sum yielding . In the worst case (e.g., repeatedly picking the maximum element as pivot), it degrades to .
Incorrect! Try again.
58A hash table uses open addressing with linear probing. The load factor is close to 1. What happens to the expected number of probes for an unsuccessful search?
Fundamental Data Structure:
Hard
A.It approaches
B.It remains regardless of
C.It approaches
D.It approaches
Correct Answer: It approaches
Explanation:
In open addressing with linear probing, primary clustering causes the expected number of probes for an unsuccessful search to be roughly . As , this value grows quadratically with respect to .
Incorrect! Try again.
59If and , what can be definitively deduced about the relationship between and ?
Useful Property Involving the Asymptotic Notations
Hard
A.No definitive asymptotic relationship can be deduced
B.
C.
D.
Correct Answer: No definitive asymptotic relationship can be deduced
Explanation:
is bounded above by , and is bounded below by . This means is larger than both, but tells us nothing about how and compare to each other. They could be equal, or one could be asymptotically strictly larger than the other.
Incorrect! Try again.
60Let and . Evaluate the limit comparison between and .
Using Limits for Comparing Orders of Growth
Hard
A.The limit does not exist, and the functions are not asymptotically comparable using Big-O, Big-Omega, or Big-Theta
B.The limit is a constant, so
C., so
D., so
Correct Answer: The limit does not exist, and the functions are not asymptotically comparable using Big-O, Big-Omega, or Big-Theta
Explanation:
Because oscillates between and $1$, oscillates between and . Thus, the ratio oscillates wildly between $0$ and , meaning the limit does not exist and the standard asymptotic bounds do not hold.