Algorithm Design and Problem-solving：练习题

In the context of computational thinking, which process involves breaking a complex problem into smaller, more manageable sub-problems to simplify the development of a solution?

Which statement best describes the relationship between decomposition and stepwise refinement in problem-solving?

A developer is evaluating the efficiency of a procedure that processes a square matrix of size \( n \times n \). The procedure is divided into two sequential phases:

Phase 1: A nested loop structure iterates through all the lower triangular elements of the matrix (where the row index is greater than or equal to the column index) to perform a calculation on each element.
Phase 2: A separate loop runs \( n \) times, where each iteration performs a binary search on a sorted 1D array of size \( n \).

Which of the following correctly identifies the overall worst-case time complexity of the procedure in Big O notation?

Which of the following statements best describes the primary purpose of abstraction when designing a computational solution to a real-world problem?

A bubble sort algorithm is being used to sort the following array of integers in ascending order:

[15, 4, 10, 2, 7]

What will be the state of the array after the first complete pass is finished?

Identify the basic programming construct that allows an algorithm to follow different paths of execution based on the result of a condition, and name the pseudocode statement used for multi-way selection.

Compare the best-case time complexity of a bubble sort algorithm with a linear search algorithm, using Big O notation, assuming the data is already sorted.

Compare the time complexity of a linear search and a binary search using Big O notation, and state the essential requirement for a binary search to be performed on a dataset.

A software developer is tasked with creating a new library management system. To manage the complexity, the developer uses various computational thinking techniques.

a) Define the term decomposition and explain how it helps the developer in this specific scenario.
b) Describe the process of stepwise refinement and state how it differs from decomposition.

A 1D array DataList contains the values: [15, 9, 23, 2, 8].
a) Show the state of the array after the second complete pass of a Bubble Sort algorithm (ascending order).
b) Explain the term Stepwise Refinement and how it relates to the design of an algorithm.
c) State the time complexity of the bubble sort in the best-case scenario and explain why this occurs if an optimization flag is used.