AP CSP Unit 6 Review 1

AP CSP Unit 6 Review

Algorithms

Multiple Select

What does an algorithm need to be (choose all that apply)?

• Clear instructions

• Accurate

• Easy to understand

• Complex

Multiple Choice

Which of the following is an example of the use of heuristics?

• Trying every possible combination of letters when unscrambling a word

• Considering each possible move when playing chess

• Using the formula “area=length x width” to find the area of a rectangle

• Playing chess using a defensive strategy that has often been successful for you

Multiple Choice

A binary search is to be performed on the list:

3, 5, 9, 10, 23

How many comparisons would it take to find the number 9?

• 1

• 3

• 4

• It can't find the number 9

Multiple Choice

A linear search is to be performed on the list:

12, 6, 8, 1, 3

How many comparisons would it take to find the number 1?

• 1

• 2

• 3

• 4

Multiple Choice

Identify the description of a binary search.

• Put the elements in order, check each item in turn

• Order elements,compare middle value,split list in order&loop

• Elements do not need to be in order, check each item in turn

• Randomize data, compare middle value, split list in order & loop

Multiple Choice

Identify the description of a linear search.

• Put the elements in order, check each item in turn

• Order elements,compare middle value,split list in order&loop

• Elements do not need to be in order, check each item in turn

• Randomize data, compare middle value, split list in order & loop

Multiple Choice

What is the largest number of comparisons needed to perform a binary search on an array with 42 elements?

• 2

• 5

• 6

• 41

• 42

Multiple Choice

We are searching for a number key in a sorted list that has n elements. Under what circumstances will Linear Search / Sequential Search be more efficient than Binary Search?

• key is the last element in the array

• key is in the middle of the array

• n is very large

• key is the first element in the array

• key does not exist in the array

Multiple Choice

A robot is programming a new game called “Open the box!” You give him a number and he tries to open a numbered box. He’s using Binary Search to accomplish this. Unfortunately, the boxes are not sorted. They are in the following order:

1, 3, 6, 9, 14, 10, 21

Which box can NEVER be found using binary search?

• 9

• 6

• 14

• 10

Multiple Choice

Given this array:

1, 2, 4, 5, 6, 7, 8, 12, 14, 21, 22, 42, 53

How many comparisons are required to find 42 using the Linear Search / Sequential Search?

• 3

• 2

• 12

• 5

Multiple Choice

Given this list:

1, 2, 4, 5, 6, 7, 8, 12, 14, 21, 22, 42, 53

How many comparisons are required to find 42 using the Binary Search?

• 3

• 2

• 10

• 5

Multiple Choice

True or false: If an array is already sorted, Linear Search / Sequential Search is more efficient than Binary Search.

• True

• False

Multiple Choice

What must be true before performing a binary search?

• The elements must be sorted.

• It can only contain binary values.

• The elements must be some sort of number (i.e. int, double, Integer)

• There are no necessary conditions.

Multiple Choice

You are at the yellow arrow, pointing in the direction indicated. How would you move to fill in the 2 black squares?

• Straight x 1, Turn right, Straight x 1, Fill Square, Straight x 2, Turn left, Straight x 1, Fill Square

• Straight x 2, Turn right, Straight x 1, Fill Square, Straight x 2, Turn left, Straight x 1, Fill Square

• Straight x 2, Turn right, Straight x 1, Fill Square, Straight x 2, Turn right, Straight x 1, Fill Square

• Straight x 2, Turn right, Straight x 1, Fill Square, Straight x 2, Turn left, Straight x 2, Fill Square

Multiple Select

What's the difference between a flow chart and pseudocode? (choose all that apply)

• Nothing

• Flow chart uses symbols

• Pseudocode is more colorful

• Flow chart has data flow arrows

• Pseudocode and flow charts both use arrows for data flow

Multiple Choice

If it is AFTER 7am, what do you need to do?

• Take the bus

• Take the subway

• Check the time

• Leave home

Multiple Choice

Which of these does NOT represent an algorithm?

• Following recipe instructions

• Working out how an engine works

• Tying your shoelaces

• Making a cup of coffee

Multiple Choice

What is one purpose of pseudocode?

• To program a computer

• So we can see the different symbols

• It helps us with the variables

• It helps us plan the code

• Flow charts are helpful to us when planning