Deck 5: Algorithms

Question 1

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?

A) Lewis
B) Pat
C) Tom

Answer 1

A

Question 2

Which of the following is the base case in the recursive function below? def xxx(N):
If (N == 0):
Print(N)
Else:
Xxx(N - 1)

A) N > 0
B) N = 0
C) N < 0

Answer 2

B

Question 3

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) $\text {Nancy }$
$\text {Sylvia}$
$\text {Lois}$
$\text {Alice}$
B) $\text {Alice}$
$\text {Lois}$
$\text {Nancy}$
$\text {Sylvia}$
C) $\text {Alice}$
$\text {Sylvia}$
$\text {Nancy}$
$\text {Lois}$
D) $\text {Lois}$
$\text {Nancy}$
$\text {Sylvia}$
$\text {Alice}$

Answer 3

$\text {Alice}$
$\text {Sylvia}$
$\text {Nancy}$
$\text {Lois}$

Question 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

Question 5

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

A) X = 3
While (X < 5):
X = X
B) X = 3
While (X < 5):
X = X + 1
C) X = 3
While (X < 5):
X = X - 1

Question 6

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

A) X < 5
B) X > 4
C) X < 4

Question 7

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

A) $\Theta \left( \log _ { 2 } n \right)$
B) $\Theta ( n )$
C) $\Theta \left( n \log _ { 2 } n \right)$
D) $\Theta \left( n ^ { 2 } \right)$

Question 8

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

A) Pseudocode
B) Iterative structures
C) Assertions
D) Recursion

Question 9

In general,an algorithm in which of the following categories is considered more efficient?

A) $\Theta \left( \log _ { 2 } n \right)$
B) $\Theta ( n )$
C) $\Theta \left( n \log _ { 2 } n \right)$
D) $\Theta \left( n ^ { 2 } \right)$

Question 10

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):
X = X + 2

A) X > 5
B)X < 5
C) X ≥ 5
D)X ≤ 5

Question 11

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

A) $\Theta \left( \log _ { 2 } n \right)$
B) $\Theta ( n )$
C) $\Theta \left( n \log _ { 2 } n \right)$
D) $\Theta \left( n ^ { 2 } \right)$

Question 12

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?

A) Lewis
B) Pat
C) Tom

Question 13

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)

A) X < 5
B) X > 4
C) X > 5

Question 14

Under the assumption that N takes on only integer values,which of the following is the termination condition in the following recursive function? def xxx(N):
If (N < 5):
Print(N)
Else:
Xxx(N - 1)

A) N < 5
B) N > 4
C) N > 5

Question 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
Repeat:
X = X + 2
Until (X > 5)

A) X > 5
B)X < 8
C) X ≥ 5
D)X ≤ 6

Question 16

Which of the following is an activity?

A) Algorithm
B) Program
C) Process

Question 17

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

A) Stepwise refinement
B) Pseudocode
C) Flowchart
D) Programming language

Question 18

Which of the following is a representation?

A) Algorithm
B) Program
C) Process

Question 19

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

A) X = 5
While (X < 6):
Print(X)
X = X + 1
B) X = 4
While (X < 5):
X = X + 1
Print(X)
C) X = 5 repeat:
Print( X)
X = X + 1
Until (X > 6)

Question 20

Under the assumption that N takes on only integer values,which of the following is the termination condition in the following recursive function? def xxx(N):
If (N < 5):
Xxx(N + 1)
Else:
Print(N)

A) N < 5
B) N > 4
C) N < 4

Question 21

What sequence of values would be printed if the function xxx described below were executed with the value of N being 9?
def xxx(N):
if (N < 4):
print(N)
yyy(7)
else:
yyy(2)
print(N)
def yyy(N):
if (N < 5):
print(N)
zzz(6)
else:
zzz(5)
def zzz(N):
if (N == 5):
print(7)
else:
print(8)
________________________

Question 22

What would be printed if the following instructions were executed?
X = 3
print(X)
Y = 5
if (X < Y):
print(6)
else:
print(7)
_________________

Question 23

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?
_______________

Question 24

Answer the following questions in terms of the function xxx below.
def xxx(N):
if (N < 7):
print(N)
else:
N = n + 3
print(N)
A.What value would be printed if the following function were executed with the value of N
being 4?
____________
B.What value would be printed if the following function were executed with the value of N
being 9?
____________

Question 25

What sequence of numbers would be printed if the following function were executed with the value of N being 0?
def xxx(N):
while (N < 4):
print(N)
N = N + 2
print(N)
__________________

Question 26

What sequence of numbers would be printed if the function named xxx as described below were executed with the value of N being 2?
def xxx (N):
print(N)
if (N < 3):
yyy(4)
print(N)
def yyy(N):
print(N)
xxx(5)
print(N)
_____________________

Question 27

Suppose the binary search algorithm was being used to search for the entry 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? _____________

Question 28

What sequence of numbers would be printed if the following function were executed with the value of N being 0?
def xxx(N):
print(N)
if (N < 2):
xxx(N + 1)
else:
print(N)
print(N)
__________________

Question 29

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):
X = X + 1

Question 30

Define each of the following terms.
A. Algorithm _______________________________________________________________
B. Program _______________________________________________________________
C. Process _______________________________________________________________

Question 31

What sequence of values will be printed when the following instructions are executed?
X = 5
if (X < 7):
print(6)
Y = 6
else:
print(4)
Y = 4
if (Y < 5):
print(3)
else:
print(2)
_______________________

Question 32

What would be printed if the following instructions were executed?
X = 3
while (X > 0):
print(X)
X = X - 1
_________________

Question 33

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

Question 34

List three of the primitives in the pseudocode developed in this chapter.
____________________
____________________
____________________

Question 35

At most,how many entries in a list of 5000 names will be interrogated when using the sequential search algorithm?
___________

Question 36

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

Question 37

At most,how many entries in a list of 5000 names will be interrogated when using the binary search algorithm?
___________

Question 38

What sequence of values will be printed when the following instructions are executed?
X = 5
while (X < 7):
print(X)
X = X + 1
print(X)
while (X > 2):
print(X)
X = X - 2
_______________________

Question 39

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?
_______________

Question 40

What sequence of numbers would be printed if the following function were executed with the value of N being 0?
def xxx(N):
print(N)
if (N < 5):
xxx(N + 2)
print(N)
__________________

Question 41

Use a repeat loop structure to produce a non-recursive program segment that prints the same sequence of numbers as the following recursive function.
def xxx(N):
print(N)
if (N < 5):
xxx(N + 1)

Question 42

Identify a flaw in the control of the following loop.
X = 3
while (X != 8):
X = X + 2

Question 43

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):
print(X)
X = X + 1

Question 44

Fill in the blank in the function below so that the function prints the integers from 0 up to the integer value it was given for N.That is,if the function is executed with the value of N being 3,it should print 0,1,2,3.
def xxx(N):
if (_________):
xxx(N - 1)
print(N)

Question 45

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):
X = X + 1

Question 46

The following function 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 function should report the value 2.)Find and correct the error.
def squareRoot(N):
X = 0
while (X*X <= N):
X = X + 1;
return X

Question 47

Use a while loop structure to produce a non-recursive program segment that prints the same sequence of numbers as the following recursive function.
def xxx(N):
print(N)
if (N < 5):
xxx(N + 1)

Question 48

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


$\begin{array}{ll}\text { Term } & \text { Descriptive Phrase } \\ \text { algorithm } & \text { The fundamental concept in computer science } \\ \text { pseudocode } & \text { An informal notation for representing algorithms } \\ \text { assignment statement } & \text { A means of saving the result of a computation for future use } \\ \text { if-else statement } & \text { A means of producing different actions depending on a condition } \\ \text { stepwise refinement } & \text { A divide and conquer approach to problem solving } \\ \text { loop invariant } & \text { A statement that is true each time a specific point in a repetitive } \\ & \text { process is reached } \\ \text { function } & \text { A program segment isolated as a unit } \\ \text { recursion } & \text { The technique of applying a program segment within itself } \\ \text { pretest loop } & \text { Looks before it leaps } \\ \text { proof of correctness } & \text { A formal means of verifying software } \\ \text { sequential search } & \text { Less efficient than the binary method } \\ \text { primitive } & \text { A basic building block }\end{array}$

Question 49

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.

Question 50

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)

Question 51

Identify a loop invariant associated with the point in the loop below at which a test for termination is performed.
X = 0
repeat:
print(X)
X = X + 2
until (X > 6)
___________________

Question 52

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):
...
else:
...
can be simulated with a program segment using only if-then statements.

Question 53

Rewrite the following routine using a pretest while statement.
repeat:
print(X)
X = X + 1
until (X > 5)