APCSP Big Idea #3 Part III

A programmer notices the following two procedures in a library. The procedures do similar, but not identical, things.

• Procedure Square (n) returns the value n²

• Procedure Cube (n) returns the value n³

Which of the following procedures is a generalization of the procedures described?

A) Procedure Add (n, m), which returns the value n+m

B) Procedure Fourth (n), which returns the value n^4

C) Procedure Polynomial (n), which returns the value n³ + n²

D) Procedure Power (n,m), which returns the value n^m

D) Procedure Power (n,m), which returns the value n^m

An online game collects data about each player’s performance in the game. A program is used to analyze the data to make predictions about how players will perform in a new version of the game.

The procedure GetPrediction (idNum) returns a predicted score for the player with ID number idNum. Assume that all predicted scores are positive. The GetPrediction procedure takes approximately 1 minute to return a result. All other operations happen nearly instantaneously.

Two versions of the program are shown below.

Which of the following best compares the execution times of the two versions of the program?

A) Version I requires approximately 1 more minute to execute than version II.

B) Version I requires approximately 5 more minutes to execute than version II.

C) Version II requires approximately 1 more minute to execute than version I.

D) Version II requires approximately 5 more minutes to execute than version I.

D) Version II requires approximately 5 more minutes to execute than version I.

A student wants to determine whether a certain problem is undecidable. Which of the following will demonstrate that the problem is undecidable?

A

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.

B

Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.

C

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.

D

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.

B) 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 statements describes a limitation of using a computer simulation to model a real-world object or system?

Responses

A

Computer simulations can only be built after the real-world object or system has been created.

B

Computer simulations only run on very powerful computers that are not available to the general public.

C

Computer simulations usually make some simplifying assumptions about the real-world object or system being modeled.

D

It is difficult to change input parameters or conditions when using computer simulations.

C) Computer simulations usually make some simplifying assumptions about the real-world object or system being modeled.

A scientist wants to investigate several problems. In which of the following situations is using a simulation LEAST suitable for solving a problem?

Responses

A

When a scientific study requires performing a large number of trials that need to be conducted very quickly

B

When it is considered acceptable to make simplifying assumptions when modeling a real-world object or phenomenon

C

When performing an experiment that would be too costly or dangerous to conduct in the real world

D

When the solution to the problem requires real-world data inputs that are continually measured at regular intervals.

D) When the solution to the problem requires real-world data inputs that are continually measured at regular intervals.

A student is developing a program that allows users to look up the definitions of words that appear in a book.

The student plans to perform a large number of searches through a dictionary containing words and their definitions. The student will use a procedure written by a computer scientist to quickly search the dictionary (and knows that the procedure will return a definition if one is available). The student cannot modify the search procedure written by the computer scientist but can call the procedure by supplying a word.

Which of the following is a true statement about the student’s use of the computer scientist’s search procedure?

Responses

A

The student is changing the search procedure’s internal abstractions.

B

The student is modifying the search procedure to take a definition as an argument and return the corresponding word.

C

The student is reusing the computer scientist’s procedural abstraction by knowing what the procedure does without knowing how it does it.

D

The student is reusing the computer scientist’s procedural abstraction by using duplicate code each time a search needs to occur.

C) The student is reusing the computer scientist’s procedural abstraction by knowing what the procedure does without knowing how it does it.

A programmer notices the following two procedures in a library. The procedures do similar, but not identical, things.

• Procedure MaxTwo (x, y) returns the greater of its two integer parameters.

• Procedure MaxThree (x, y, z) returns the greatest of its three integer parameters.

Which of the following procedures is a generalization of the MaxTwo and MaxThree procedures?

A

Procedure Min (x, y), which returns the lesser of its two integer parameters

B

Procedure Max (numList), which returns the maximum value in the list of integers numList

C

Procedure MaxFour (w, x, y, z), which returns the greatest of its four integer parameters

D

Procedure OverMax (numList, max), which returns the number of integers in numList that exceed the integer value max

B) Procedure Max (numList), which returns the maximum value in the list of integers numList.

Consider the following spinner, which is used to determine how pieces are to be moved on a game board. Each region is of equal size.

Which of the following code segments can be used to simulate the behavior of the spinner?

In a science experiment, result X is expected to occur 25% of the time and result Y is expected to occur the remaining 75% of the time. The following code segment is intended to simulate the experiment if there are 100 trials.

Line 1:  xCount 0

Line 2:  yCount 0

Line 3:  REPEAT 100 TIMES

Line 4:  {

Line 5:     IF(RANDOM(1, 4) = 1)

Line 6:     {

Line 7:        xCount xCount + 1

Line 8:     }

Line 9:     IF(RANDOM(1, 4) > 1)

Line 10:    {

Line 11:       yCount yCount + 1

Line 12:    }

Line 13: }

Line 14: DISPLAY("Result X occurred")

Line 15: DISPLAY(xCount)

Line 16: DISPLAY("times and result Y occurred")

Line 17: DISPLAY(yCount)

Line 18: DISPLAY("times.")

A programmer runs the code segment, and the following message is displayed.

Result X occurred 24 times and result Y occurred 70 times.

The result shows that 94 trials were counted, rather than the intended 100 trials.

Which of the following changes to the code segment will ensure a correct simulation of the experiment?

A

Replacing line 9 with IF(RANDOM(1, 4) ≥ 2)

B

Replacing line 9 with ELSE

C

Interchanging lines 5 and 9

D

Interchanging lines 7 and 11

B

Replacing line 9 with ELSE

An online retailer uses an algorithm to sort a list of n items by price. The table below shows the approximate number of steps the algorithm takes to sort lists of different sizes.

Based on the values in the table, which of the following best characterizes the algorithm for very large values of n ?

A

The algorithm runs in reasonable time.

B

The algorithm runs, but not in reasonable time.

C

The algorithm attempts to solve an undecidable problem.

D

The algorithm attempts to find an approximate solution whenever it fails to find an exact solution.

A

The algorithm runs in reasonable time.

A student has a data file containing 10,000 numerical values. The student is writing a program to compute the average of the numbers contained in the file. Which of the following procedures is most likely to be useful in the student’s program?

Responses

A

A procedure that returns the quotient when dividing one value by another

B

A procedure that returns the sum when adding one value to another

C

A procedure that returns the sum of the values in the file

D

A procedure that returns true if the file contains any duplicate values and returns false otherwise

C

A procedure that returns the sum of the values in the file

Which of the following best explains the ability to solve problems algorithmically?

Responses

A

Any problem can be solved algorithmically, though some algorithmic solutions may require humans to validate the results.

B

Any problem can be solved algorithmically, though some algorithmic solutions must be executed on multiple devices in parallel.

C

Any problem can be solved algorithmically, though some algorithmic solutions require a very large amount of data storage to execute.

D

There exist some problems that cannot be solved algorithmically using any computer.

D

There exist some problems that cannot be solved algorithmically using any computer.

A researcher wrote a program to simulate the number of mice in an environment that contains predators. The program uses the following procedures.

Code for the simulation is shown below.

Based on the code, which of the following assumptions is made in the simulation?

A

The number of mice increases by 1 each day.

B

The number of mice does not change from day to day.

C

The number of predators increases by 1 each day.

D

The number of predators does not change from day to day.

D

The number of predators does not change from day to day.

Which of the following programs is most likely to benefit from the use of a heuristic?

Responses

A

A program that calculates a student’s grade based on the student’s quiz and homework scores

B

A program that encrypts a folder of digital files

C

A program that finds the shortest driving route between two locations on a map

D

A program that sorts a list of numbers in order from least to greatest

C

A program that finds the shortest driving route between two locations on a map

Which of the following are benefits of procedural abstraction?

Select two answers.

response - correct

Responses

A

Procedural abstraction prevents programmers from accidentally using the intellectual property of other programmers.

B

Procedural abstraction eliminates the need for programmers to document their code.

C

Procedural abstraction makes it easier for people to read computer programs.

D

Procedural abstraction provides an opportunity to give a name to a block of code that describes the purpose of the code block.

C

Procedural abstraction makes it easier for people to read computer programs.

D

Procedural abstraction provides an opportunity to give a name to a block of code that describes the purpose of the code block.

Consider a game in which a player flips a fair coin three times. If all three coin flips have the same result (either all heads or all tails) the player wins. Otherwise, the player loses.

Which of the following code segments best simulates the behavior of the game?

Responses

A

B

C

D

D

A population researcher is interested in predicting the number of births that will occur in a particular community. She created a computer model that uses data from the past ten years, including number of residents and the number of babies born. The model predicted that there would be 200 births last year, but the actual number of births last year was only 120.

Which of the following strategies is LEAST likely to provide a more accurate prediction?

A

Gathering data for additional years to try to identify patterns in birth rates

B

Refining the model used in the computer simulation to more closely reflect the data from the past ten years

C

Removing as many details from the model as possible so that calculations can be performed quickly

D

Taking into consideration more information about the community, such as the ages of residents

C

Removing as many details from the model as possible so that calculations can be performed quickly

The transportation department plans to build a new high-speed train route between two cities. The transportation department wants to implement a simulation of the train before any construction begins on this project. Which of the following statements is true about the use of a simulation for this project?

Responses

A

A simulation cannot be used to test the train under varying weather conditions.

B

Implementing a simulation is likely to increase the overall costs associated with the project.

C

Other high-speed train routes have been constructed in other locations, so a simulation is not needed.

D

Using a simulation may expose potential safety issues that can be corrected before construction begins.

D

Using a simulation may expose potential safety issues that can be corrected before construction begins.

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?

Responses

A

The model used by the simulation software cannot be modified once the simulation has been used.

B

The model used by the simulation software often omits details so that it is easier to implement.

C

Running a simulation requires more time to generate data from trials than observing the crowd exiting the arena at various events.

D

Running a simulation requires a large number of observations to be collected before it can be used to explore a problem.

B

The model used by the simulation software often omits details so that it is easier to implement.

Which of the following are ways in which a programmer can use abstraction to manage the complexity of a program?

Select two answers.

response - correct

Responses

A

Replacing each instance of repeated code with a call to a procedure

B

Replacing longer variable names with shorter variable names to reduce typing errors

C

Replacing several lines of documentation with a single line of documentation

D

Replacing the string variables name1, name2, name3, and name4 with a list of strings called names

A

D

Consider the following spinner, which is used to determine how pieces are to be moved on a game board. The region labeled "Move 1 space" is six times as large as each of the other two regions.

Which of the following code segments can be used to simulate the behavior of the spinner?

Responses

A

B

C

D

D

A computer scientist is analyzing four different algorithms used to sort a list. The table below shows the number of steps each algorithm took to sort lists of different sizes.

List Size	Number of Steps for Algorithm A	Number of Steps for Algorithm B	Number of Steps for Algorithm C	Number of Steps for Algorithm D
1	10	2	1	1
2	20	4	2	4
3	30	8	6	9
4	40	16	24	16
5	50	32	120	25

Based on the values in the table, which of the algorithms appear to run in reasonable time?

Select two answers.

response - correct

Responses

A

Algorithm A

B

Algorithm B

C

Algorithm C

D

Algorithm D

A

D

Which of the following is a benefit of using a simulation instead of an experiment to make a prediction?

Select two answers.

response - correct

Responses

A

A simulation allows investigation of a phenomenon without the real-world limitations on time, safety, or budget.

B

A simulation can be used to model real-world events that are impractical for experiments.

C

A simulation always produces the same output, so its results can be verified.

D

A simulation produces results that are more accurate than experimental results.

A

B

A car manufacturer uses simulation software during the design process for a new car. Which of the following are reasons to use simulation software in this context?

1. Using simulation software can save the company money by helping to compare designs early in the process, before prototype cars are built.

2. Using simulation software can help to identify safety issues by providing data about how different mechanical components will interact in a wide variety of situations.

3. The manufacturer can present simulation software to customers to demonstrate different design possibilities.

Responses

A

I and II only

B

I and III only

C

II and III only

D

I, II, and III

D

Flight simulation software, which imitates the experience of flying, is often used to train airline pilots. Which of the following is LEAST likely to be an advantage of using flight simulation software for this purpose?

Responses

A

Flight simulation software allows pilots to practice landing in a variety of different terrains and weather conditions without having to physically travel.

B

Flight simulation software could save money due to the cost of maintenance and fuel for actual training flights.

C

Flight simulation software provides a more realistic experience for pilots than actual training flights.

D

Flight simulation software allows for the testing of emergency air situations without serious consequences.

C

A programmer wrote the code segment below to display the average of all the elements in a list called numbers. There is always at least one number in the list.

The programmer wants to reduce the number of operations that are performed when the program is run. Which change will result in a correct program with a reduced number of operations performed?

Responses

A

Interchanging line 1 and line 2

B

Interchanging line 5 and line 6

C

Interchanging line 6 and line 7

D

Interchanging line 7 and line 8

D

A game program contains the following code to update three score variables, health, food, and knowledge. The maximum values for the three variables are 100, 80, and 25, respectively.

health health + 10

IF(health > 100)

{

health 100

}

food food + 1

IF(food > 80)

{

food 80

}

knowledge knowledge + 5

IF(knowledge > 25)

{

knowledge 25

}

The game program’s author would like to write a procedure that could be used to update any variable in the game (myScore) that has a maximum value (myLimit) by a given amount (myAmount). A correct call of the procedure is shown below.

myScore updateScore(myScore, myAmount, myLimit)

Which of the following is a correct implementation of updateScore ?

Responses

A

PROCEDURE updateScore(score, amount, limit)

{

score score + amount

IF (score > limit)

{

score limit

}

}

B

PROCEDURE updateScore(score, amount, limit)

{

score score + amount

IF(score > amount)

{

score limit

}

RETURN(limit)

}

C

PROCEDURE updateScore(score, amount, limit)

{

score score + amount

IF(score > limit)

{

score limit

}

RETURN(score)

}

D

PROCEDURE updateScore(score, amount, limit)

{

IF(score = health)

{

score score + 10

}

IF(score = food)

{

score score + 1

}

IF(score = knowledge)

{

score score + 5

}

IF(score > limit)

{

score limit

}

}

C

The following spinner is used in a game. The region labeled "blue" represents of the spinner. The regions labeled "orange" and "purple" are equal in size.

Which of the following code segments can be used to simulate the behavior of the spinner?

Select two answers.

response - correct

Responses

A

B

C

D

D

A computer program contains code in several places that asks a user to enter an integer within a specified range of values. The code repeats the input request if the value that the user enters is not within the specified range. A programmer would like to create a procedure that will generalize this functionality and can be used throughout the program. The correct use of the procedure is shown below, where min is the least acceptable value, max is the greatest acceptable value, and promptString is the string that should be printed to prompt the user enter a value.

inputVal getRange(min, max, promptString)

Which of the following is a correct implementation of the getRange procedure?

Responses

A

PROCEDURE getRange(min, max, promptString)

{

DISPLAY(promptString)

RETURN(INPUT())

}

B

PROCEDURE getRange(min, max, promptString)

{

DISPLAY(promptString)

x INPUT()

RETURN(x)

}

C

PROCEDURE getRange(min, max, promptString)

{

DISPLAY(promptString)

x INPUT()

REPEAT UNTIL(x ≥ min AND x ≤ max)

{

DISPLAY(promptString)

x INPUT()

}

}

D

PROCEDURE getRange(min, max, promptString)

{

DISPLAY(promptString)

x INPUT()

REPEAT UNTIL(x ≥ min AND x ≤ max)

{

DISPLAY(promptString)

x INPUT()

}

RETURN(x)

}

D

A company delivers packages by truck and would like to minimize the length of the route that each driver must travel in order to reach delivery locations. The company is considering two different algorithms for determining delivery routes.

Algorithm I

Generate all possible routes, compute their lengths, and then select the shortest possible route. This algorithm does not run in reasonable time.

Algorithm II

Starting from an arbitrary delivery location, find the nearest unvisited delivery location. Continue creating the route by selecting the nearest unvisited location until all locations have been visited. This algorithm does not guarantee the shortest possible route and runs in time proportional to .

Which of the following best categorizes algorithm II?

Responses

A

Algorithm II attempts to use an algorithmic approach to solve an otherwise undecidable problem.

B

Algorithm II uses a heuristic approach to provide an approximate solution in reasonable time.

C

Algorithm II provides no improvement over algorithm I because neither algorithm runs in reasonable time.

D

Algorithm II requires a much faster computer in order to provide any improvement over algorithm I.

B

Directions: The question or incomplete statement below is followed by four suggested answers or completions. Select the one that is best in each case.

The question below uses a robot in a grid of squares. The robot is represented as a triangle, which is initially in the center square of the grid and facing toward the top of the grid.

The following code segment is used to move the robot within the grid.

A gray square represents a possible final location of the robot after the code segment is executed. Which of the following represents all possible final locations for the robot?

Responses

A

B

C

D

B

Consider the following code segment.

Which of the following describes the possible values of ans as a result of executing the code segment?

Responses

A

Any integer value from 1 to 8, inclusive

B

Any integer value from 1 to 16, inclusive

C

Any integer value from 4 to 8, inclusive

D

Any integer value from 7 to 16, inclusive

D

A spinner contains 12 regions of equal size. The regions are numbered 1 to 12. Which of the following code segments can be used to simulate the results of spinning the spinner three times and assigns the sum of the values obtained by the three spins to the variable sum ?

Responses

A

sum RANDOM(1, 12) + RANDOM(1, 12) + RANDOM(1, 12)

B

sum RANDOM(1, 36)

C

sum 3 * RANDOM(1, 12)

D

sum 12 * RANDOM(1, 3)

A

A spinner is divided into three sections. The sector labeled Red is four times as large as each of the sectors labeled Blue and Yellow, which are of equal size.

The procedure below is intended to simulate the behavior of the spinner.

Which of the following can be used to replace 

 so that the procedure correctly simulates the spinner?

Responses

A

B

C

D

D

Consider a game where a player spins a wheel divided into four identical sections, labeled A, B, C, and D. If the player spins A, the score is 10. If the player spins B, the score is 5. If the player spins C or D, the score is -1.

The following code segment is intended to implement the game.

Which of the following could be used as a replacement for <MISSING STATEMENT> so the code segment works as intended?

Responses

A

B

C

D

B

Consider the following code segment.

Which of the following CANNOT be displayed as a result of executing the code segment?

Responses

A

1 1 1 1

B

1 2 3 2

C

1 2 3 4

D

1 3 2 4

D

Which of the following best explains why it is not possible to use computers to solve every problem?

Responses

A

Current computer processing capabilities cannot improve significantly.

B

Large-scale problems require a crowdsourcing model, which is limited by the number of people available to work on the problem.

C

The ability of a computer to solve a problem is limited by the bandwidth of the computer’s Internet connection.

D

There exist some problems that cannot be solved using any algorithm.

D

In which of the following scenarios would a simulation be the LEAST beneficial?

Responses

A

An engineering company wants to test whether a change to a car design will negatively affect fuel efficiency.

B

An insurance company wants to study the effect of cold weather patterns on health-care costs.

C

A manufacturing company wants to determine whether using robots in its facility will increase productivity.

D

A retail company wants to determine the most popular item that was sold on the company’s Web site last month.

D

In which of the following scenarios is using a simulation more beneficial than performing a calculation?

Select two answers.

response - correct

Responses

A

Determining the average grade of the students in a certain class

B

Keeping track of the high score in a game

C

Investigating ways to reduce the amount of trash in the ocean

D

Studying the effect of a genetic change in a population

C

D

Under which of the following conditions is it most beneficial to use a heuristic approach to solve a problem?

Responses

A

When the problem can be solved in a reasonable time and an approximate solution is acceptable

B

When the problem can be solved in a reasonable time and an exact solution is needed

C

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

D

When the problem cannot be solved in a reasonable time and an exact solution is needed

C

A student wants to create an algorithm that can determine, given any program and program input, whether or not the program will go into an infinite loop for that input.

The problem the student is attempting to solve is considered an undecidable problem.

Which of the following is true?

Responses

A

It is possible to create an algorithm that will solve the problem for all programs and inputs, but the algorithm can only be implemented in a low-level programming language.

B

It is possible to create an algorithm that will solve the problem for all programs and inputs, but the algorithm requires simultaneous execution on multiple CPUs.

C

It is possible to create an algorithm that will solve the problem for all programs and inputs, but the algorithm will not run in reasonable time.

D

It is not possible to create an algorithm that will solve the problem for all programs and inputs.

D

A new bank plans to make customer convenience a priority by minimizing the amount of time a customer waits in line. The bank is considering two options: a single line where the customer at the front waits for the next available teller, or separate lines for each teller. The bank decides to use a computer simulation of these two options to determine the average wait time for customers.

Which of the following is NOT true about the bank’s plan?

Responses

A

The bank can incorporate other factors, such as the number of tellers, in the simulation.

B

The bank can use the simulation to investigate these two options without causing inconvenience for customers.

C

The bank may consider new alternatives based on the simulation results.

D

The simulation will not produce usable results because actual customer data are not available.

D

A certain computer game is played between a human player and a computer-controlled player. Every time the computer-controlled player has a turn, the game runs slowly because the computer evaluates all potential moves and selects the best one. Which of the following best describes the possibility of improving the running speed of the game?

Responses

A

The game’s running speed can only be improved if the game is played between two human players instead of with the computer-controlled player.

B

The game’s running speed might be improved by using a process that finds approximate solutions every time the computer-controlled player has a turn.

C

The game’s running speed cannot be improved because computers can only be programmed to find the best possible solution.

D

The game’s running speed cannot be improved because the game is an example of an algorithm that does not run in a reasonable time.

B

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?

Responses

A

Making the code more readable

B

Making the code run faster

C

Providing more opportunities for code reuse

D

Reducing the amount of duplicated code

B

Directions: For the question or incomplete statement below, two of the suggested answers are correct. For this question, you must select both correct choices to earn credit. No partial credit will be earned if only one correct choice is selected. Select the two that are best in each case.

In a certain district, 20 percent of the voters are expected to vote for Candidate A in an election. The computer program below is intended to simulate the result of the election with n voters, and display the number of votes received by Candidate A.

 

Which of the following can be used to replace 

 in line 4 so that the program works as intended? 

Select two answers.

response - correct

Responses

A

B

C

D

A

D

In a certain game, a player may have the opportunity to attempt a bonus round to earn extra points. In a typical game, a player is given 1 to 4 bonus round attempts. For each attempt, the player typically earns the extra points 70% of the time and does not earn the extra points 30% of the time.

The following code segment can be used to simulate the bonus round.

Which of the following is NOT a possible output of this simulation?

Responses

A

The player had 1 bonus round attempts and 1 of them earned extra points.

B

The player had 2 bonus round attempts and 0 of them earned extra points.

C

The player had 3 bonus round attempts and 7 of them earned extra points.

D

The player had 4 bonus round attempts and 3 of them earned extra points.

C

For which of the following problems is using a simulation LEAST likely to be beneficial?

Responses

A

Determining the longest word in a textbook

B

Minimizing the customer wait times at a bank

C

Predicting the outcomes of weather patterns

D

Studying the formation of a galaxy

A

Consider the following algorithms. Each algorithm operates on a list containing n elements, where n is a very large integer.

1. An algorithm that accesses each element in the list twice

2. An algorithm that accesses each element in the list n times

3. An algorithm that accesses only the first 10 elements in the list, regardless of the size of the list

1, 2, and 3

Which of the following statements is true?

A

Every problem can be solved with an algorithm for all possible inputs, in a reasonable amount of time, using a modern computer.

B

Every problem can be solved with an algorithm for all possible inputs, but some will take more than 100 years, even with the fastest possible computer.

C

Every problem can be solved with an algorithm for all possible inputs, but some of these algorithms have not been discovered yet.

D

There exist problems that no algorithm will ever be able to solve for all possible inputs.

D

There exist problems that no algorithm will ever be able to solve for all possible inputs.

A graphic artist uses a program to draw geometric shapes in a given pattern. The program uses an algorithm that draws the shapes based on input from the artist. The table shows the approximate number of steps the algorithm takes to draw different numbers of shapes.

Number of Shapes Drawn	Number of Steps
4	17
5	24
6	35
7	50

Based on the values in the table, which of the following best characterizes the algorithm for drawing n shapes, where n is a very large number?

A

The algorithm runs in a reasonable amount of time because it will use approximately n steps to draw n shapes.

B

The algorithm runs in a reasonable amount of time because it will use approximately n² steps to draw n shapes.

C

The algorithm runs in an unreasonable amount of time because it will use approximately n steps to draw n shapes.

D

The algorithm runs in an unreasonable amount of time because it will use approximately n² steps to draw n shapes.

B

The algorithm runs in a reasonable amount of time because it will use approximately n² steps to draw n shapes.

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?

A

Appending a value to a list of n elements, which requires no list elements be examined.

B

Finding the fastest route that visits every location among n locations, which requires n! possible routes be examined.

C

Performing a binary search for a score in a sorted list of n scores, which requires that fewer than n scores be examined.

D

Performing a linear search for a name in an unsorted database of n people, which requires that up to n entries be examined.

B

Finding the fastest route that visits every location among n locations, which requires n! possible routes be examined.

A group of planners are using a simulation to examine whether or not a park that they are designing is going to affect foot traffic in the area. The simulation uses a model that includes input variables for the park such as the number of entrances, sidewalks, and bike trails and the square footage of open space (grassy areas). The simulation can then be run multiple times using different values for the input variables to represent different park designs.

However, the simulation takes a very long time to run. The planners update the model by removing some variables they consider less important than others.

Of the following, which is the most likely effect the updated model will have on the simulation?

A

The updated model is likely to decrease the runtime of the simulation because the time required for simulations generally depends on the complexity of the model used.

B

The updated model is likely to decrease the runtime of the simulation because simulations that use older models tend to require more time to run than simulations that use newer models.

C

The updated model is unlikely to decrease the runtime of the simulation because the simulation is computationally complex, regardless of the model used.

D

The updated model is unlikely to provide any benefit because removing details from a model will compromise the accuracy of the simulation.

A

The updated model is likely to decrease the runtime of the simulation because the time required for simulations generally depends on the complexity of the model used.

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

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.

B

A procedure isFound, which takes a word and a text file as input and returns true if the word appears in the text file

C

A procedure textMatch, which takes two text files as input and returns true if the two text files are identical.

D

A procedure sameSize, which takes two text files as input and returns true if the two text files contain the same number of words.

B

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 team of programmers is designing software. One portion of the project presents a problem for which there is not an obvious solution. After some research, the team determines that the problem is undecidable. Which of the following best explains the consequence of the problem being undecidable?

A

The problem can be solved algorithmically, but it will require an unreasonably long amount of time.

B

The problem can be solved algorithmically, but it will require an unreasonably large amount of data storage.

C

There is no possible algorithm that can be used to solve all instances of the problem.

D

There are several different possible algorithms that can solve the problem, but there is controversy about which is the most efficient.

C

There is no possible algorithm that can be used to solve all instances of the problem.

A student is writing a program that is intended to replace each negative value in a particular column of a spreadsheet with the value 0. Which of the following procedures is most likely to be useful in the student’s program?

A

A procedure containsNegatives, which returns true if any negative values appear in the column and returns false otherwise.

B

A procedure countNegatives, which returns the number of negative values that appear in the column.

C

A procedure findNegative, which returns the row number of the first negative value that appears in the column or -1 if there are no negative values.

D

A procedure minimum, which returns the minimum value that appears in the column.

C

A procedure findNegative, which returns the row number of the first negative value that appears in the column or -1 if there are no negative values.

Which of the following best explains how algorithms that run on a computer can be used to solve problems?

A

All problems can be solved with an algorithm that runs in a reasonable amount of time.

B

All problems can be solved with an algorithm, but some algorithms might need a heuristic to run in a reasonable amount of time.

C

All problems can be solved with an algorithm, but some algorithms might run in an unreasonable amount of time.

D

Some problems cannot be solved by an algorithm.

D

Some problems cannot be solved by an algorithm.