WorksheetsAP CSP Algorithms & Programming (College Board Style)
Total questions: 15
Worksheet time: 30mins
For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a reasonable amount of time?
Appending a value to a list of n elements, which requires no list elements be examined.
Finding the fastest route that visits every location among n locations, which requires n!n! possible routes be examined.
Performing a binary search for a score in a sorted list of n scores, which requires that fewer than n scores be examined.
Performing a linear search for a name in an unsorted database of nn people, which requires that up to n entries be examined.
Which of the following is a benefit of using a list as a data abstraction in a program?
Lists often allow their size to be easily updated to hold as many data values as needed.
Lists convert all elements to strings so that they can be inspected character-by-character.
Lists prevent duplicate data values from appearing in the list.
Lists are used to store all input data so that there is a running record of all user input.
The variable isOpen is to be used to indicate whether or not a store is currently open. Which of the following is the most appropriate data type for isOpen ?
number
string
lsit
boolean
Assume that both lists and strings are indexed starting with index 1.
The list wordList has the following contents.
["abc", "def", "ghi", "jkl"]
Let myWord be the element at index 3 of wordList. Let myChar be the character at index 2 of myWord. What is the value of myChar ?
"e"
"f"
"h"
"i"
A time stamp indicates the date and time that a measurement was taken. A data scientist has a list containing 10,000 time stamps, sorted in chronological order. Which of the following is closest to the maximum number of values that will need to be examined when performing a binary search for a value in the list?
15
10
5000
10,000
A computer science student completes a program and asks a classmate for feedback. The classmate suggests rewriting some of the code to include more procedural abstraction. Which of the following is NOT a benefit of procedural abstraction?
Making the code more readable
Making the code run faster
Providing more opportunities for code reuse
Reducing the amount of duplicated code
The list wordList contains a list of 10 string values. Which of the following is a valid index for the list?
-1
"hello"
1.25
4
Suppose that a list of numbers contains values [-4, -1, 1, 5, 2, 10, 10, 15, 30]. Which of the following best explains why a binary search should NOT be used to search for an item in this list?
The list contains both positive and negative elements.
The list contains an odd number of elements.
The elements of the list are not sorted.
The list contains duplicate elements.
Consider the following code segment.
x ←← 25
y ←← 50
z ←← 75
x ←← y
y ←← z
z ←← x
Which of the variables have the value 50 after executing the code segment?
x only
y only
x and z only
x, y, and z
A city planner is using simulation software to study crowd flow out of a large arena after an event has ended. The arena is located in an urban city. Which of the following best describes a limitation of using a simulation for this purpose?
The model used by the simulation software cannot be modified once the simulation has been used.
The model used by the simulation software often omits details so that it is easier to implement.
Running a simulation requires more time to generate data from trials than observing the crowd exiting the arena at various events.
Running a simulation requires a large number of observations to be collected before it can be used to explore a problem.
A student wants to determine whether a certain problem is undecidable. Which of the following will demonstrate that the problem is undecidable?
Show that for one instance of the problem, an algorithm can be written that is always capable of providing a correct yes-or-no answer.
Show that for one instance of the problem, a heuristic is needed to write an algorithm that is capable of providing a correct yes-or-no answer.
Show that for one instance of the problem, an algorithm that runs in unreasonable time can be written that is capable of providing a correct yes-or-no answer.
Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.
Which of the following procedures would be most useful as part of a program to determine whether a word appears in two different text files?
A procedure getWords, which takes a positive integer n and a text file as input and returns the first n words in the text file.
A procedure isFound, which takes a word and a text file as input and returns true if the word appears in the text file
A procedure textMatch, which takes two text files as input and returns true if the two text files are identical.
A procedure sameSize, which takes two text files as input and returns true if the two text files contain the same number of words.
The variable age is to be used to represent a person’s age, in years. Which of the following is the most appropriate data type for age ?
number
Boolean
string
list
A programmer has a need to round many numeric values to the nearest integer. Which of the following best explains the benefit of using a list as a data abstraction in this situation?
Keeping the numeric values in a list makes it easier to round a number to the nearest integer.
Keeping the numeric values in a list makes it easier to apply the same computation to every data element.
Keeping the numeric values in a list makes it easier to prevent a program from unintentionally changing the value of a variable.
Keeping the numeric values in a list makes it easier to prevent a program from attempting to access an index beyond the length of the list.
Which of the following is a benefit of using a simulation instead of an experiment to make a prediction?
A simulation always produces the same output, so its results can be verified.
A simulation produces results that are more accurate than experimental results.
A simulation allows investigation of a phenomenon without the real-world limitations on time, safety, or budget.
A simulation can be used to model real-world events that are impractical for experiments.
