APCSP Final Test Prep

I Receive Grace!

What shape would be drawn by this algorithm?

A pentagon with sides of length 100 pixels.

You should be able to draw a square of any size with this procedure by calling it and specifying the parameter L. However, this procedure has a bug. What is the bug?

The procedure always draws a square with sides of 50 pixels. The parameter, L, is ignored.

For searching in an unordered list, which search algorithm is a better choice?

Linear

For searching an ordered (sorted) list, which search algorithm is a better choice?

Binary

When would a binary search algorithm be useful?

-Looking up a phone number in the phone book given a person’s full(unique) name. 

-Looking up a word in the dictionary.

When would a linear search algorithm be useful?

Looking up a phone number in the phone book given a person’s full(unique) name.   

Guessing a secret number between 1 and 100

Looking up a person’s name in the phone book given the person’s phone number.

Looking up a word in the dictionary

A sorted list of numbers contains 500 elements. What number(s) would be the closest to the maximum number of list elements that will be examined when performing a binary search for a value in the list?

-10

 (The exact answer is 9, but 10 was the closest of the choices given)

In the bubble sort demo, 13 cards are being sorted. How many passes does this version of the algorithm require to sort the cards?

13

1. When would a bubble sort algorithm provide an appropriate solution?

Arranging books on a bookshelf by the author’s last name. Sorting a stack of paper money into denominations – i.e., 1,5, $10, etc.

Suppose you are sorting the following list of numbers in ascending order using the bubble sort:[16, 4, 18, -3, 5, 2, 10, 26, 20, 8]
After the first pass through the numbers, what value would appear on the right of the list (replacing the 8)?

26

1. Suppose you are sorting the following list of words into alphabetical order using bubble sort:
   [dog, cat, horse, whale, deer, fox]
   After the first pass of the list, what word would appear on the right of the list?

Whale

1. Suppose you are sorting the following list of words into alphabetical order using bubble sort:

[papaya, orange, lemon, banana, zucchini, tomato, apple, squash, pumpkin]
What would be the correct order of the list after two passes through the list?

Tomato, Zucchini

What is the Length of the following list?

9

What piece of fruit is located at Index 4 of the following list?

Watermelon

1. What value will the global variable name have after Button1 is clicked?

Teddy

What value will the global variable name have after Button1 is clicked?

Abe

What does the following code do?

Displays 4, which is the maximum(largest) value in the list

1. According to the following table, how many lookups would be required in the worst case to find a number in a list of 1,000 elements using linear search?

1000

According to the following table, how many lookups would be required in the worst case to find a number in a list of 100 elements using binary search?

7

If you were using binary search to find the number 14 in the following list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], how many iterations would be required to find 14 in the list?

3

What does an algorithm’s efficiency refer to?

How long it takes to arrange the values in order

What does it mean to say that a bucket sort is more efficient than a bubble sort?

As the size of the list grows, bucket sort will be faster than bubble sort.

What characteristics are true of a bubble sort?

A comparison-based algorithm

A quadratic algorithm

What characteristics are true of a bucket sort?

More efficient than a bubble sort.

 A linear algorithm.

What would be true about this algorithm?

  Both Algorithm A and Algorithm B always calculate the correct average. 

Under what condition would it be most beneficial to use a heuristic approach to solve a problem?

When the problem cannot be solved within a reasonable time and an approximate solution is acceptable.

A certain computer has two identical processors that are able to run in parallel. Each processor can only run one process at a time, and each process must be executed on a single processor. The following table indicates the amount of time it takes to execute each of the three processes on a single processor. Assume that none of the processes are dependent on any of the other processes. How many seconds would best approximate the minimum possible time to execute all three processes when the two processors are run in parallel?

80 Seconds. Add the two shortest together

Consider an algorithm to solve a problem that takes 160 seconds to run one (1) processor. This algorithm can be divided among two processors to solve the same problem in 100 seconds. What is the speedup for this parallel algorithm?

1.6.  time 1/time 2 160/100

What are the three types of control structures found in algorithms? Provide an example of each type of control structure.

1. Sequence(like sequence of events in ELA)

2. Selection(if then else)

3. Repetition(Loop or while)

List one “good” reason to retain your search history. List one “good” reason to delete your search history.

Retain for convenience

Delete for privacy concern

Describe the significance of the global variable index. How was indexing used with lists in our Quiz App?

Related

Particular

Question to Que

The index variable is used with all of the lists to select a particular item. 

The items in each list at the same index are related to each other.

In the quiz app, the indexing allowed us to move from question to question.