Deck 4: Networking and the Internet

Question 1

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 < 5
B) N > 4
C) N > 5

Answer 1

A

Question 2

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

Answer 2

B

Question 3

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 3

A

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

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

A) $\varTheta$ (lg n)
B) $\varTheta$ (n)
C) $\varTheta$ (n lg n)
D) $\varTheta$ ( n² )

Question 6

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

A) X $\leftarrow$ 5
B) X $\leftarrow$ 4
C) X $\leftarrow$ 5

Question 7

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

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

Question 8

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

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

Question 9

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

Question 10

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 < 5
B) N > 4
C) N < 4

Question 11

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

A) $\varTheta$ (lg n)
B) $\varTheta$ (n)
C) $\varTheta$ (n lg n)
D) $\varTheta$ ( n² )

Question 12

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

A) X > 5
B) X < 8
C) X $\ge$ 5
D) X $\le$ 6

Question 13

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

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

Question 14

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

A) X > 5
B) X < 5
C) X $\ge$ 5
D) X $\le$ 5

Question 16

Which of the following is an activity?

A) Algorithm
B) Program
C) Process

Question 17

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

A) $\varTheta$ (lg n)
B) F $\varTheta$ (n)
C) $\varTheta$ (n lg n)
D) $\varTheta$ ( n² )

Question 18

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

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

Question 19

Which of the following lists would not be obtained at some point when applying the insertion sort algorithm to the list below?

Question 20

Which of the following is a representation?

A) Algorithm
B) Program
C) Process

Question 21

The pseudocode used in this chapter included both an if-then statement and an if-then-else statement.
Show how the statement can be simulated with a program segment using only if-then statements.

Question 22

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.

Question 23

Identify a flaw in the control of the following loop.

Question 24

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

Question 25

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

Question 26

Use a repeat loop structure to produce a non-recursive program segment that prints the same sequence of numbers as the following recursive procedure.

Question 27

Identify a loop invariant associated with the point in the loop below at which a test for termination is performed. ___________________

Question 28

Use a while loop structure to produce a non-recursive program segment that prints the same sequence of numbers as the following recursive procedure.

Question 29

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 30

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.

Question 31

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 32

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 33

Rewrite the following routine using a pretest while statement.