Computer Science An Overview 11th Edition By J. Glenn Brookshear - Test Bank

Computer Science An Overview 11th Edition By J. Glenn Brookshear – Test Bank

 

Instant Download – Complete Test Bank With Answers

 

 

Sample Questions Are Posted Below

 

Test Bank—Chapter Five (Algorithms)

 

Multiple Choice Questions

 

1. Which of the following is an activity?

 

1. Algorithm B. Program C. Process

 

ANSWER: C

 

2. Which of the following is a representation?

 

1. Algorithm B. Program C. Process

 

ANSWER: B

 

3. Which of the following set of instructions defines an algorithm in the formal, strict sense?

 

1. 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?

 

1. Pretest loop B. Posttest loop                    C. Recursion         D. Assignment statement

 

ANSWER: D

 

5. When 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?

 

1. Lewis B. Pat                     C. Tom

 

ANSWER: A

 

6. When 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 binary search algorithm?

 

1. 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

 

1. Nancy 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?

 

1. Q(lg n) B. Q(n)                  C. Q(n lg n)          D. Q( n² )

 

ANSWER: B

 

9. The insertion sort algorithm is an example of an algorithm in which of the following classes?

 

1. Q(lg n) B. Q(n)                  C. Q(n lg n)          D. Q( n² )

 

ANSWER: D

 

10. The binary search algorithm is an example of an algorithm in which of the following classes?

 

1. Q(lg n) B. Q(n)                  C. Q(n lg n)          D. Q( n² )

 

ANSWER: A

 

11. Under the assumption that X takes on only integer values, which of the following is the termination condition for the following loop?

 

while (X < 5) do

( . . . )

 

1. X < 5 B. 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)

 

1. X < 5 B. 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)

 

1. N < 5 B. N > 4 C. N < 4

 

ANSWER: 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)

 

1. N < 5 B. N > 4 C. N > 5

 

ANSWER: A

 

15. Which of the 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) do

(X ¬ X + 2)

 

1. X > 5 B. X < 5 C. X ³ 5                 D. X £ 5

 

ANSWER: D

 

16. Which of the following is a loop invariant at the point at which the test for termination is performed in the following loop structure?

 

X ¬ 3;

repeat (X ¬ X + 2)

until (X > 5)

 

1. X > 5 B. X < 8 C. X ³ 5                 D. X £ 6

 

ANSWER: B

 

17. Which of the following is the base case in the recursive procedure below?

 

procedure xxx (N)

if (N = 0) then (print the value of N)

else (apply the procedure xxx to the value N – 1)

 

1. N > 0 B. N = 0 C. N < 0

 

ANSWER: B

 

18. Preconditions, postconditions, and loop invariants are examples of which of the following?

 

1. Pseudocode B. Iterative structures         C. Assertions        D. Recursion

 

ANSWER: C

 

19. Which of the following does not print the same sequence of numbers as the others?

 

1. X ¬ 5     B. X ¬ 4                                         C. X ¬ 5

while (X < 6) do          while (X < 5) do                repeat

(print the value of X;           (X ¬ X + 1;               (print the value of X;

X ¬ X + 1)               print the value of X)     X ¬ X + 1)

until (X > 6)

 

ANSWER: C

 

20. Which of the following is not a way of representing algorithms?

 

1. Stepwise refinement B. Pseudocode     C. Flowchart         D. Programming language

 

ANSWER: A

 

 

 

 

Fill-in-the-blank/Short-answer Questions

 

1. Define each of the following terms.

 

1. Algorithm _______________________________________________________________

 

1. Program _______________________________________________________________

 

1. Process _______________________________________________________________

 

ANSWER: A. An ordered collection of unambiguous, executable steps that defines a terminating process

1. A representation of an algorithm (perhaps nonterminating algorithm)
2. 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 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, 2

 

4. What sequence of values will be printed when the following instructions are executed?

 

X ¬ 5;

while (X < 7) do

(print the value of X;

X ¬ X + 1)

print the value of X;

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?

 

procedure 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)

 

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.)

 

____________

 

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 entry Tom in the list

 

Nathan, Oliver, Pat, Quincy, Rodger, Stan, Tom

 

1. What would be the first entry in the list to be considered? _____________

 

1. 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 when 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, 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 would be printed if the following instructions were executed?

 

X ¬ 3;

print the value of X;

Y ¬ 5;

if (X < Y) then (print the value 6)

else (print the value 7)

 

_________________

 

ANSWER: 3, 6

 

14. What would be printed if the following instructions were executed?

 

X ¬ 3;

while (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 value of N and

print the value of N)

 

1. What value would be printed if the following procedure were executed with the value of N

being 4?

 

____________

 

1. 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 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 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 the 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 (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 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 < 9), Underline: X ¬ X + 1

 

21. Fill in the blank in the procedure below so that the procedure prints the integers from 0 up to the integer value it was given for N. That is, if the procedure is executed with the value of N being 3, it should print 0, 1, 2, 3.

 

procedure xxx (N)

if (_________) then (apply the procedure xxx to the value N – 1);

print the value of N)

 

ANSWER: N > 0

 

22. Identify a loop invariant associated 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 < 9, X is an even integer, and others

 

 

 

 

Vocabulary (Matching) Questions

 

The following is a list of terms from the chapter along with descriptive phrases that can be used to produce questions (depending on the topics covered in your course) in which the students are ask to match phrases and terms. An example would be a question of the form, “In the blank next to each phrase, write the term from the following list that is best described by the phrase.”

 

Term                                       Descriptive Phrase

algorithm                                               The fundamental concept in computer science

pseudocode                                          An informal notation for representing algorithms

assignment statement                         A means of saving the result of a computation for future use

if-then-else statement                         A means of producing different actions depending on a condition

stepwise refinement                            A divide and conquer approach to problem solving

loop invariant                                       A statement that is true each time a specific point in a repetitive

process is reached

procedure                                              A program segment isolated as a unit

recursion                                                The technique of applying a program segment within itself

pretest loop                                           Looks before it leaps

proof of correctness                            A formal means of verifying software

sequential search                                 Less efficient than the binary method

primitive                                                A basic building block

 

 

 

General Format Questions

 

1. Rewrite the following routine using a pretest while statement.

 

repeat (print the value of X;

X ¬ X + 1)

until (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)

 

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 negative 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 integers.

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 numbers as the following recursive procedure.

 

procedure xxx (N)

print the value of N:

if (N < 5) then (apply the procedure xxx to the value N + 1)

 

ANSWER: repeat (print the value of N;

N ¬ N + 1)

until (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 (apply 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 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 < 5” is a loop invariant at the point at which the test for termination is performed in the loop outlined below. What can be concluded about the value of X immediately after the loop is terminated?

 

repeat ( . . . )

until (X > 3)

 

ANSWER: X = 4

 

9. The pseudocode used in this chapter included both an if-then statement and an if-then-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 ¬ X

if (Y = 5) then ( . . . )

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 (X² £ N) do

(X ¬ X + 1);

report the value of X

 

ANSWER: The value reported should be X – 1.