《大学英语期末复习TestBank1005.pdf》由会员分享，可在线阅读，更多相关《大学英语期末复习TestBank1005.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Test BankChapter Five (Algorithms)Multiple Choice Questions1. Which of the following is an activity? A. Algorithm B. Program C. Process ANSWER: C 2. Which of the following is a representation? A. Algorithm B. Program C. Process ANSWER: B 3. Which of the following set of instructions defines an algor
2、ithm in the formal, strict sense? A. X 3;B. X 3;C. X 3;while (X 5)do while (X 5) do while (X 5) do (X X) (X X + 1) (X X - 1)ANSWER: B 4. Which of the following is not a means of repeating a block of instructions? A. Pretest loop B. Posttest loop C. Recursion D. Assignment statement ANSWER: D 5. When
3、 searching within the list Lewis, Maurice, Nathan, Oliver, Pat, Quincy, Roger, Stan, Tom which of the following entries will be found most quickly using the sequential search algorithm? A. Lewis B. Pat C. Tom ANSWER: A 6. When searching within the list Lewis, Maurice, Nathan, Oliver, Pat, Quincy, Ro
4、ger, Stan, Tom which of the following entries will be found most quickly using the binary search algorithm? A. Lewis B. Pat C. Tom ANSWER: B 7. Which of the following lists would not be obtained at some point when applying the insertion sort algorithm to the list below? Sylvia Nancy Lois Alice A. Na
5、ncy B. Alice C. Alice D. Lois Sylvia Lois Sylvia Nancy Lois Nancy Nancy Sylvia Alice Sylvia Lois Alice ANSWER: C 8. In general, an algorithm in which of the following categories is considered more efficient? A. (lg n) B. (n) C. (n lg n) D. ( n2 ) ANSWER: B 9. The insertion sort algorithm is an examp
6、le of an algorithm in which of the following classes? A. (lg n) B. (n) C. (n lg n) D. ( n2 ) ANSWER: D 10. The binary search algorithm is an example of an algorithm in which of the following classes? A. (lg n) B. (n) C. (n lg n) D. ( n2 ) ANSWER: A 11. Under the assumption that X takes on only integ
7、er values, which of the following is the termination condition for the following loop? while (X 5) do ( . . . )A. X 4 C. X 4 ANSWER: B 12. Under the assumption that X takes on only integer values, which of the following is the termination condition for the following loop? repeat ( . . . ) until (X 5
8、)A. X 4 C. X 5 ANSWER: A 13. Under the assumption that N takes on only integer values, which of the following is the termination condition in the following recursive procedure? procedure xxx (N) if (N 5) then (apply the procedure xxx to the value N + 1) else (print the value of N)A. N 4 C. N 4 ANSWE
9、R: B 14. Under the assumption that N takes on only integer values, which of the following is the termination condition in the following recursive procedure? procedure xxx (N) if (N 5) then (print the value of N) else (apply the procedure xxx to the value N - 1) A. N 4 C. N 5 ANSWER: A 15. Which of t
10、he following is a loop invariant at the point at which the test for termination is performed in the following loop structure? X 3; while (X 5 B. X 5) A. X 5 B. X 0 B. N = 0 C. N 0 ANSWER: B 18. Preconditions, postconditions, and loop invariants are examples of which of the following? A. Pseudocode B
11、. Iterative structures C. Assertions D. Recursion ANSWER: C 19. Which of the following does not print the same sequence of numbers as the others? A. X 5B. X 4C. X 5 while (X 6) do while (X 6)ANSWER: C 20. Which of the following is not a way of representing algorithms? A. Stepwise refinement B. Pseud
12、ocode C. Flowchart D. Programming language ANSWER: A Fill-in-the-blank/Short-answer Questions1. Define each of the following terms. A. Algorithm _ B. Program _ C. Process _ ANSWER: A. An ordered collection of unambiguous, executable steps that defines a terminating process B. A representation of an
13、algorithm (perhaps nonterminating algorithm) C. The action of executing a program (or algorithm) 2. List three of the primitives in the pseudocode developed in this chapter. _ _ _ ANSWER: Possible answers include: the assignment statement using , the if-then-else statement, the while statement, the
14、repeat statement, and the definition and activation of procedures. 3. What sequence of values will be printed when the following instructions are executed? X 5; if (X 7) then (print the value 6; Y 6) else (print the value 4; Y 4) if (Y 5) then (print the value 3) else (print the value 2) _ ANSWER: 6
15、, 2 4. What sequence of values will be printed when the following instructions are executed? X 5; while (X 2) do (print the value of X; X X - 2) _ ANSWER: 5, 6, 7, 7, 5, 3 5. What sequence of values would be printed if the procedure xxx described below were executed with the value of N being 9? proc
16、edure xxx (N) if (N 4) then (print the value of N; apply the procedure yyy to the value 7) else (apply the procedure yyy to the value 2; print the value of N) procedure yyy (N) if (N 5) then (print the value of N; apply the procedure zzz to the value 6) else (apply the procedure zzz to the value 5)
17、procedure zzz (N) if (N = 5) then (print the value 7) else (print the value 8) _ ANSWER: 2, 8, 9 6. When searching for the entry X within the list R, S, T, U, V, W, Z how many entries will be considered before discovering that the entry is not present? (Note that the list is in alphabetical order.)
18、_ ANSWER: 3 7. When searching for the entry X within the list R, S, T, U, V, W, Z how many entries will be considered before discovering that the entry is not present? (Note that the list is in alphabetical order.) _ ANSWER: 7 8. Suppose the binary search algorithm was being used to search for the e
19、ntry Tom in the list Nathan, Oliver, Pat, Quincy, Rodger, Stan, Tom A. What would be the first entry in the list to be considered? _ B. What would be the second entry in the list to be considered? _ ANSWER: A. Quincy B. Stan 9. At most, how many entries in a list of 5000 names will be interrogated w
20、hen using the binary search algorithm? _ ANSWER: 13 10. At most, how many entries in a list of 5000 names will be interrogated when using the sequential search algorithm? _ ANSWER: 5000 11. Which of the sequential or binary search algorithms would find the name Kelly in the list John, Kelly, Lewis,
21、Maurice, Nathan, Oliver, Pat, Quincy, Roger, Stan, Tom more quickly? _ ANSWER: Sequential 12. Which of the sequential or binary search algorithms would find the name Roger in the list John, Kelly, Lewis, Maurice, Nathan, Oliver, Pat, Quincy, Roger, Stan, Tom more quickly? _ ANSWER: Binary 13. What w
22、ould be printed if the following instructions were executed? X 3; print the value of X; Y 5; if (X 0) do (print the value of X; X X - 1) _ ANSWER: 3, 2, 1 15. Answer the following questions in terms of the procedure xxx below. procedure xxx (N) if (N 7) then (print the value of N) else (add 3 to the
23、 value of N and print the value of N) A. What value would be printed if the following procedure were executed with the value of N being 4? _ B. What value would be printed if the following procedure were executed with the value of N being 9? _ ANSWER: A. 4 B. 12 16. What sequence of numbers would be
24、 printed if the following procedure were executed with the value of N being 0? procedure xxx (N) while (N 4) do (print the value of N; N N + 2; print the value of N ) _ ANSWER: 0, 2, 2, 4 17. What sequence of numbers would be printed if the following procedure were executed with the value of N being
25、 0? procedure xxx (N) print the value of N; if (N 5) then (apply the procedure xxx to the value N + 2); print the value of N _ ANSWER: 0, 2, 4, 6, 6, 4, 2, 0 18. What sequence of numbers would be printed if the following procedure were executed with the value of N being 0? procedure xxx (N) print th
26、e value of N; if (N 2) then (apply the procedure xxx to the value N + 1) else (print the value of N) print the value of N _ ANSWER: 0, 1, 2, 2, 2, 1, 0 19. What sequence of numbers would be printed if the procedure named xxx as described below were executed with the value of N being 2? procedure xxx
27、 (N) procedure yyy (N) print the value of N; print the value of N; if (N 3) apply the procedure xxx to the value 5; then (apply procedure yyy print the value of N to the value 4); print the value of N _ ANSWER: 2, 4, 5, 4, 2 20. Circle the portion of the program below in which control of the loop is
28、 initialized. Draw a rectangle around the portion in which the test for termination is performed. Underline the portion in which the state of the loop is moved toward the termination condition. X 3; while (X 9) do (X X + 1)ANSWER: Circle: X 3 , Rectangle: while (X 022. Identify a loop invariant asso
29、ciated with the point in the loop below at which a test for termination is performed. X 0; repeat (print the value of X; X X + 2) until (X 6) _ ANSWER: Possible answers include: X 0, X 5) ANSWER: One possible solution is: print the value of X; X X + 1; while (X 5) do (print the value of X; X X + 1)
30、2. If numeric values are represented in two s complement notation, does the following program represent an infinite process? Explain your answer. X 2 while (X 0) do (X X + 1) ANSWER: (CAUTION: This problem relies on material from Chapter 1.) No, the process will terminate because X will become negat
31、ive due to overflow. 3. Identify a flaw in the control of the following loop. X 3 while (X 8) do (X X + 2)ANSWER: The termination condition will never be reached because X will always be odd. 4. Do the following instructions define an algorithm? Explain your answer. Write down all the positive odd i
32、ntegers. Select the integer in the middle of the list. Print the even integer that is one less than the selected odd integer. ANSWER: No, the instructions are not executable (not effective). 5. Use a repeat loop structure to produce a non-recursive program segment that prints the same sequence of nu
33、mbers as the following recursive procedure. procedure xxx (N) print the value of N: if (N 6)6. Use a while loop structure to produce a non-recursive program segment that prints the same sequence of numbers as the following recursive procedure. procedure xxx (N) print the value of N: if (N 5) then (a
34、pply the procedure xxx to the value N + 1) ANSWER: print the value of N; while (N 6) do (print the value of N; N N + 1) 7. Use a repeat loop rather than a while loop to accomplish the same results as the following program segment. Assume that X will have only integer values. (You may also use an if
35、statement if you like.) while (X 5) do (print the value of X; X X + 1) ANSWER: if (X 5) then (repeat (print the value of X; X X + 1) until (X = 5) 8. Suppose the statement “ X is an integer and X 3) ANSWER: X = 4 9. The pseudocode used in this chapter included both an if-then statement and an if-the
36、n-else statement. Show how the statement if (X = 5) then ( . . . ) else ( . . . ) can be simulated with a program segment using only if-then statements. ANSWER: First pick a variable that does not already appear in the program. Call it Y. Then the following is a solution: Y Xif (Y = 5) then ( . . .
37、) if (Y 5) then ( . . . )(Note that “if (X = 5) then ( ); if (X 5) then () ” is not correct since the first then clause may change the value of X.) 10. The following procedure was designed to compute the largest integer whose square is no greater than N, where N is assumed to be a positive number. (If N is 5, then the procedure should report the value 2.) Find and correct the error. procedure squareroot (N) X 0; while (X2 N) do (X X + 1); report the value of X ANSWER: The value reported should be X - 1.