DATA STRUCTURES EXAM REVIEW
QUESTIONS AND ANSWERS
Which notation describes the best-case complexity of an algorithm? - Correct Answers -
Big-Ω
What factor primarily determines the execution time of the add (∫lhs,∫rhs) method, which
simply adds two numbers? - Correct Answers -The number of operations involved.
Which of the following is a concrete instance of an algorithm, specifically designed to
run on a computer? - Correct Answers -A program
An algorithm has a space complexity of O(1) and a time complexity of O(N log N).
Which statement about the algorithm is true? - Correct Answers -The algorithm uses a
constant amount of memory irrespective of the input size, but its execution time
increases logarithmically with the input size.
Given an algorithm that processes a list of N items in such a way that for each new item
added, the execution time doubles, how would you best describe the time complexity of
this algorithm? - Correct Answers -O(2^N)
Given the following statements:
Wanting to identify the sentiment (positive, negative, neutral) of a piece of text.
A set of rules that analyzes word choice and frequency to determine sentiment.
A Java code that implements these rules and outputs the sentiment of a text.
Which sequence correctly categorizes these statements? - Correct Answers -1.
Problem 2. Algorithm 3. Program
If the space required by an algorithm grows proportionally to the square of the size of
the input, how would the space complexity be best described? - Correct Answers -
O(N^2)
When analyzing an algorithm's performance, why is it beneficial to focus on how many
times certain statements run as a function of the input size? - Correct Answers -It
enables estimation of how long two invocations of the same method will take relative to
each other based on input size.
Consider the scenario where you need to find the shortest path between two cities on a
map. How would you categorize the following descriptions?
The challenge of determining the shortest path.
The step-by-step method you devise to find this path.
, The code you write in Python to implement this method.
Match the descriptions with the appropriate concepts: - Correct Answers -1. Problem 2.
Algorithm 3. Program
Which statement best captures the underlying rationale for the importance of sorting in
computer science and software engineering? - Correct Answers -Sorting facilitates more
efficient searching, data compression, and overall data organization, impacting various
algorithms and computational tasks.
Considering Bubble Sort's mechanism of "bubbling up" the largest unsorted element
during each pass, what can be inferred about the position of the Unknown node type:
brUnknown node type: brnth largest element after Unknown node type: brUnknown
node type: brn passes? - Correct Answers -It will be in its correct final position.
As sorting algorithms are developed for incrementally larger arrays, what pattern
becomes evident? - Correct Answers -For every array size, the largest number is
ensured to be at the end, followed by applying the same sorting logic to the remaining
elements.
In the absence of efficient sorting, which of the following challenges is most likely to
arise in a software application? - Correct Answers -Slower retrieval and processing of
data.
How does the generalized Bubble Sort algorithm handle an array of any size? - Correct
Answers -It repeatedly ensures the largest number ends up at the end and then applies
the same process to the remaining elements.
After the first iteration of the Insertion Sort algorithm, what will be the order of the
following array: [15, 10, 12, 14, 11]? - Correct Answers -[10, 15, 12, 14, 11]
Given the array [20, 18, 22, 19, 21] and the Selection Sort process has already sorted
the smallest two numbers to the beginning, what will the array look like after the third
smallest number is sorted? - Correct Answers -[18, 19, 20, 22, 21]
Which of the following series of operations correctly represents the Insertion Sort
algorithm for the array [10, 9, 8, 11]? - Correct Answers -Compare 10 and 9, swap
them. Compare 9 and 8, swap them. Compare 10 and 11, no swap. Compare 10 and 8,
swap them.
Consider the Selection Sort algorithm applied to the array [6, 3, 7, 5, 2]. Here are the
steps:
[2, 3, 7, 5, 6]
[2, 3, 5, 7, 6]
[2, 3, 5, 6, 7]
[2, 3, 5, 6, 7]
QUESTIONS AND ANSWERS
Which notation describes the best-case complexity of an algorithm? - Correct Answers -
Big-Ω
What factor primarily determines the execution time of the add (∫lhs,∫rhs) method, which
simply adds two numbers? - Correct Answers -The number of operations involved.
Which of the following is a concrete instance of an algorithm, specifically designed to
run on a computer? - Correct Answers -A program
An algorithm has a space complexity of O(1) and a time complexity of O(N log N).
Which statement about the algorithm is true? - Correct Answers -The algorithm uses a
constant amount of memory irrespective of the input size, but its execution time
increases logarithmically with the input size.
Given an algorithm that processes a list of N items in such a way that for each new item
added, the execution time doubles, how would you best describe the time complexity of
this algorithm? - Correct Answers -O(2^N)
Given the following statements:
Wanting to identify the sentiment (positive, negative, neutral) of a piece of text.
A set of rules that analyzes word choice and frequency to determine sentiment.
A Java code that implements these rules and outputs the sentiment of a text.
Which sequence correctly categorizes these statements? - Correct Answers -1.
Problem 2. Algorithm 3. Program
If the space required by an algorithm grows proportionally to the square of the size of
the input, how would the space complexity be best described? - Correct Answers -
O(N^2)
When analyzing an algorithm's performance, why is it beneficial to focus on how many
times certain statements run as a function of the input size? - Correct Answers -It
enables estimation of how long two invocations of the same method will take relative to
each other based on input size.
Consider the scenario where you need to find the shortest path between two cities on a
map. How would you categorize the following descriptions?
The challenge of determining the shortest path.
The step-by-step method you devise to find this path.
, The code you write in Python to implement this method.
Match the descriptions with the appropriate concepts: - Correct Answers -1. Problem 2.
Algorithm 3. Program
Which statement best captures the underlying rationale for the importance of sorting in
computer science and software engineering? - Correct Answers -Sorting facilitates more
efficient searching, data compression, and overall data organization, impacting various
algorithms and computational tasks.
Considering Bubble Sort's mechanism of "bubbling up" the largest unsorted element
during each pass, what can be inferred about the position of the Unknown node type:
brUnknown node type: brnth largest element after Unknown node type: brUnknown
node type: brn passes? - Correct Answers -It will be in its correct final position.
As sorting algorithms are developed for incrementally larger arrays, what pattern
becomes evident? - Correct Answers -For every array size, the largest number is
ensured to be at the end, followed by applying the same sorting logic to the remaining
elements.
In the absence of efficient sorting, which of the following challenges is most likely to
arise in a software application? - Correct Answers -Slower retrieval and processing of
data.
How does the generalized Bubble Sort algorithm handle an array of any size? - Correct
Answers -It repeatedly ensures the largest number ends up at the end and then applies
the same process to the remaining elements.
After the first iteration of the Insertion Sort algorithm, what will be the order of the
following array: [15, 10, 12, 14, 11]? - Correct Answers -[10, 15, 12, 14, 11]
Given the array [20, 18, 22, 19, 21] and the Selection Sort process has already sorted
the smallest two numbers to the beginning, what will the array look like after the third
smallest number is sorted? - Correct Answers -[18, 19, 20, 22, 21]
Which of the following series of operations correctly represents the Insertion Sort
algorithm for the array [10, 9, 8, 11]? - Correct Answers -Compare 10 and 9, swap
them. Compare 9 and 8, swap them. Compare 10 and 11, no swap. Compare 10 and 8,
swap them.
Consider the Selection Sort algorithm applied to the array [6, 3, 7, 5, 2]. Here are the
steps:
[2, 3, 7, 5, 6]
[2, 3, 5, 7, 6]
[2, 3, 5, 6, 7]
[2, 3, 5, 6, 7]
