Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

APCSP > Big Idea 3-Algorithms and Programming > Flashcards

Big Idea 3-Algorithms and Programming Flashcards

1
Q

A _______is an abstraction inside a program that can hold a value. Each _______ has associated data storage that represents one value at a time, but that value can be a list or other collection that in turn contains multiple values.

A

variable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Using _________ variable names helps with the readability of program code and understanding of what values are represented by the variables.

A

meaningful

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Some programming languages provide types to represent data, which are referenced using variables. These types include ___________________.

A

numbers, Booleans, lists, and strings

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A _______ is an ordered sequence of elements. For example, [value1, value2, value3, …] describes a ________ where value1 is the first element, value2 is the second element, value3 is the third element, and so on.
Warning! AP Exam starts index at 1.

A

list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

An ________ is an individual value in a list that is assigned a unique index.

A

element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

An _______ is a common method for referencing the elements in a list or string using natural numbers.

A

index

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

A _______ is an ordered sequence of characters.

A

string

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

________ provides a separation between the abstract properties of a data type and the concrete details of its representation.

A

Data abstraction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Data abstractions manage _______ in programs by giving a collection of data a name without referencing the specific details of the representation.

A

complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Data abstractions can be created using _______.

A

lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Developing a data abstraction to implement in a program can result in a program that is easier to __________.

A

develop and maintain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

The use of ______ allows multiple related items to be treated as a single value.

A

lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

An _______ is a finite set of instructions that accomplish a specific task.

A

algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Algorithms executed by programs are implemented using __________.

A

programming languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Every algorithm can be constructed using combinations of ________, _________, and _______.

A

sequencing, selection, and iteration.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

_________ is the application of each step of an algorithm in the order in which the code statements are given.

A

Sequencing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

A __________ is a part of program code that expresses an action to be carried out.

A

code statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

An _________ can consist of a value, a variable, an operator, or a procedure call that returns a value.

A

expression

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Expressions are evaluated to produce a ________.

A

single value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

True or False: Sequential statements execute in the order they appear in the code segment.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Comment: Clarity and readability are important considerations when expressing an algorithm in a programming language.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Arithmetic operators are part of most programming languages and include _______, _______, _______, _______, and _______ operators.

A

addition, subtraction, multiplication, division, and modulus

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Comment: The exam reference sheet provides a MOD b, which evaluates to the remainder when a is divided by b.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Assume that a is an integer greater than or equal to 0 and b is an integer greater than 0. For example, 17 MOD 5 evaluates to ___.

A

2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

__________ joins together two or more strings end-to-end to make a new string.

A

String concatenation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

A _________ is part of an existing string.

A

substring

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

A ______ is either true or false.

A

Boolean value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

_______ determines which parts of an algorithm are executed based on a condition being true or false.

A

Selection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

_______________ affect the sequential flow of control by executing different statements based on the value of a Boolean expression.

A

Conditional statements, or “if-statements,”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

_______ conditional statements consist of conditional statements within conditional statements.

A

Nested

31
Q

_________ is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.

A

Iteration

32
Q

Comment: Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.

A
33
Q

True or False: Algorithms can be written in different ways and still accomplish the same tasks.

A

True

34
Q

True or False: Algorithms can be written in different ways and still accomplish the same tasks.

A

True: Also, different algorithms can be developed or used to solve the same problem.

35
Q

True or False: Algorithms that appear similar should yield the same result or effect?

A

False: Algorithms that appear similar can yield different side effects or results.

36
Q

Comment: Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms.

A
37
Q

Comment: Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include:
determining the maximum or minimum value of two or more numbers
computing the sum or average of two or more numbers
identifying if an integer is or is not evenly divisible by another integer
determining a robot’s path through a maze

A
38
Q

Comment: Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.

A
39
Q

Comment: Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.

A
40
Q

Iteration statements can be used to ______ a list.

A

traverse

41
Q

Comment: Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:
determining a minimum or maximum value in a list
computing a sum or average of a list of numbers

A
42
Q

Linear search or sequential search algorithms check each element of a list, in ______, until the desired value is found or all elements in the list have been checked.

A

order

43
Q

The _________ search algorithm starts in the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.

A

binary

44
Q

Data must be in _______ order to use the binary search algorithm.

A

sorted

45
Q

Binary search is often more _______ than sequential/linear search when applied to sorted data.

A

efficient

46
Q

A _________ is a named group of programming instructions that may have parameters and return values.

A

procedure

Comment: Procedures are referred to by different names, such as method or function, depending on the programming language.

47
Q

________ are input variables of a procedure.

A

Parameters

48
Q

__________ specify the values of the parameters when a procedure is called.

A

Arguments

49
Q

Comment: A procedure call interrupts the sequential execution of statements, causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has been executed, flow of control is returned to the point immediately following where the procedure was called

A
50
Q

One common type of abstraction is ___________, which provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it.

A

procedural abstraction

Comment: Procedural abstraction allows a solution to a large problem to be based on the solutions of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems.

51
Q

The subdivision of a computer program into separate subprograms is called _________.

A

modularity

52
Q

A procedural abstraction may extract shared features to generalize functionality instead of duplicating code. This allows for program code reuse, which helps manage __________.

A

complexity

53
Q

Using _________ allows procedures to be generalized, enabling the procedures to be reused with a range of input values or arguments.

A

parameters

54
Q

A _________ contains procedures that may be used in creating new programs.

A

software library

Comment: The use of libraries simplifies the task of creating complex programs.

55
Q

Existing code segments can come from internal or external sources, such as _____________.

A

libraries or previously written code

56
Q

Using ____________ in a program means each execution may produce a different result.

A

random number generation

57
Q

___________ are abstractions of more complex objects or phenomena for a specific purpose.

A

Simulations

58
Q

A _________ is a representation that uses varying sets of values to reflect the changing state of a phenomenon.

A

simulation

59
Q

Comment: Simulations often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world.
The process of developing an abstract simulation involves removing specific details or simplifying functionality.

A
60
Q

Simulations can contain ________ derived from the choices of real-world elements that were included or excluded.

A

bias

61
Q

Comment: Simulations are most useful when real-world events are impractical for experiments (e.g., too big, too small, too fast, too slow, too expensive, or too dangerous).

A
62
Q

____________ can be used to simulate the variability that exists in the real world.

A

Random number generators

63
Q

A __________ is a general description of a task that can (or cannot) be solved algorithmically.

A

problem

64
Q

An ____________ also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an ________________.

A

instance of a problem

65
Q

A _____________ is a problem with a yes/no answer (e.g., is there a path from A to B?).

A

decision problem

66
Q

An __________ is a problem with the goal of finding the “best” solution among many (e.g., what is the shortest path from A to B?).

A

optimization problem

67
Q

_________ is an estimation of the amount of computational resources used by an algorithm. _________ is typically expressed as a function of the size of the input.

A

Efficiency

Comment: An algorithm’s efficiency is determined through formal or mathematical reasoning.
An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.

68
Q

True or False: Different correct algorithms for the same problem can have different efficiencies.

A

True

69
Q

Algorithms with a ________ efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with ________ or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

A

polynomial, exponential

70
Q

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, ________ solutions are sought.

A

approximate

71
Q

A __________ is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

A

heuristic

72
Q

A __________ is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).

A

decidable problem

73
Q

An ___________ is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.

A

undecidable problem

Comment: An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.

APCSP (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions