Computational thinking and Problem-solving：练习题

Which of the following is a necessary condition that must be met before a binary search algorithm can be used on a list of data items?

Consider the following recursive pseudocode function:

FUNCTION Calculate(n)
    IF n = 1 THEN
        RETURN 1
    ELSE
        RETURN n + Calculate(n - 1)
    END IF
END FUNCTION

What is the value returned by Calculate(4)?

State the Big O time complexity for finding a specific item in a sorted array containing \(n\) elements using binary search.

A programmer uses a stack Abstract Data Type (ADT) to support undo functionality. Explain why a stack is the most suitable data structure for this purpose.

Explain the role of the call stack during the execution of a recursive function, specifically stating what is stored during recursive calls and what occurs during the unwinding phase.

(a) Stepwise refinement is a key technique in computational thinking. Explain the purpose of using stepwise refinement when designing a complex computer program.

(b) A programmer is designing an algorithm to calculate the total price of a customer's order. The algorithm takes the Unit Price and the Quantity of an item as input, calculates the Subtotal, applies a 10% discount if the Subtotal is over \( 100 \), and then outputs the Final Total.

Complete the following identifier table for this algorithm by providing the data types and descriptions for the four variables mentioned.

A 1D array, MyList, contains 100 integer elements. A programmer needs to design an algorithm to search for a specific value, SearchValue, within this array.

(a) Write pseudocode for a linear search algorithm to find SearchValue in MyList. If the value is found, output its index position; otherwise, output a message stating the value was not found.

(b) Explain one reason why a linear search would be chosen over a binary search for this specific array.