A data type whose properties (domain and operations) are specified independently of any particular implementation
A model of a complex system that includes only the details essential to the perspective of the viewer of the system
The process of testing the system in its real environment with real data
A record used at run time to store information about a function call, including the parameters, local variables, register values, and return address
A linked list that identifies all vertices to which a particular vertex is connected; each vertex has its own adjacency list
For a graph with N nodes, an N by N table that shows the existence (and weights) of all edges in the graph
Two vertices in a graph that are connected by an edge
A logical sequence of discrete steps that describes a complete solution to a given problem, computable in a finite amount of time
A logical proposition that can be true or false
Related to the average number of steps required by an algorithm, calculated across all possible sets of input values
A binary search tree that rebalances itself when the heights of the two subtrees of any node differ by no more than 1
A value associated with a tree node that is the difference in height between its two subtrees
A node whose balance factor is no more than 1
The case for which the solution can be stated nonrecursively
The class being inherited from
Related to the minimum number of steps required by an algorithm, given an ideal set of input values in terms of efficiency
A notation that expresses computing time (complexity) as the term in a function that increases most rapidly relative to the size of a problem
A binary tree in which the key value in any node is greater than the key value in its left child and any of its children (the nodes in the left subtree) and less than the key value in its right child and any of its children (the nodes in the right subtree)
A structure with a unique starting node (the root), in which each node is capable of having two child nodes, and in which a unique path exists from the root to every other node
The time at which a name or symbol is bound to the appropriate code
A representation that maps each item in the component type to a Boolean flag
Testing a program or function based on the possible input values, treating the code as a “black box”
A property of Red-Black trees that dictates that every path from a given node to a NULL node must have the same number of black nodes
An ADT for which there is a logical limit on the number of items in the structure
A code segment that is not always executed; for example, a switch statement has as many branches as there are case labels
A collection of elements associated with a particular hash location
The number of items in a set
linked list of elements that share the same hash location
list in which every node has a successor; the “last” element is succeeded by the “first” element
An unstructured type that encapsulates a fixed number of data components with the functions that manipulate them; the predefined operations on an instance of a class are whole assignment and component access
A special member function of a class that is implicitly invoked when a class object is defined
Testing a program or function based on covering all the statements, branches, or paths of the code
(i) Software that declares and manipulates objects (instances) of a particular class (ii) User of the software
The tendency of elements to become unevenly distributed in the hash table, with many elements clustering around a single hash location
The condition resulting when two or more keys produce the same hash location
A binary tree that is either full or full through the next-to-last level, with the leaves on the last level located as far to the left as possible
A graph in which every vertex is directly connected to every other vertex
The data type of the components or items in a set
A data type that allows a collection of values to be associated with an object of that type
A mechanism by which an internal data member of one class is defined to be an object of another class type
An operation that creates a new instance of a class
A special member function of a class that is implicitly invoked when passing parameters by value, initializing a variable in a declaration, and returning an object as the value of a function
The separation of a data type’s logical properties from its implementation
The separation of the representation of data from the applications that use the data at a logical level; a programming language feature that enforces information hiding
A collection of data elements whose organization is characterized by accessing operations that are used to store and retrieve the individual data elements; the implementation of the composite data members in an abstract data type
The process of removing known errors
An operation that not only copies one class object to another but also makes copies of any pointed-to data
An operator that, when applied to a pointer variable, denotes the variable to which the pointer points
The class that inherits
Tracing an execution of a design or program on paper
A binary set operation that returns a set made up of all the items that are in the first set but not the second set
When a function directly calls itself
A graph in which each edge is directed from one vertex to another (or the same) vertex
A linked list in which each node is linked to both its successor and its predecessor
Allocation of memory space for a variable at run time (as opposed to static allocation at compile time)
The run-time determination of which implementation of an operation is appropriate
A pair of vertices representing a connection between two nodes in a graph
A set with no members
An unusual, generally unpredictable event, detectable by software or hardware, that requires special processing; the event may or may not be erroneous
A hash method that breaks the key into several pieces and concatenates or exclusive-ORs some of the pieces to form the hash value
A pool of memory locations reserved for dynamic allocation of data
A binary tree in which all of the leaves are located on the same level and every nonleaf node has two children
The set of valid input data for a program or function
Memory locations that can no longer be accessed
The case for which the solution is expressed in terms of a smaller version of itself
A type for which the operations are defined but the types of the items being manipulated are not
A data structure that consists of a set of nodes and a set of edges that relate the nodes to one another
A function used to manipulate the key of an element in a list to identify its location in the list
The technique used for ordering and accessing elements in a list in a relatively constant amount of time by manipulating the key to identify its location in the list
A placeholder node at the beginning of a list; used to simplify list processing
A complete binary tree, each of whose elements contains a value that is greater than or equal to the value of each of its children
The maximum level
Running the program with the test cases listed in the test plan
When a chain of two or more function calls returns to the function that originated the chain
The practice of hiding the details of a function or data structure with the goal of controlling access to the details of a module or structure
A mechanism used with a hierarchy of classes in which each descendant class inherits the properties (data and operations) of its ancestor class
A systematic way of visiting all nodes in a binary tree that visits the nodes in the left subtree of a node, then visits the node, and then visits the nodes in the right subtree of the node
A verification method in which one member of a team reads the program or design line by line and the other members point out errors
Testing performed to integrate program modules that have already been independently unit tested
A binary set operation that returns a set made up of all the items that are in both of the input sets
An operation that allows us to process all components in a data structure sequentially
(i) A member of a record (struct or class) whose value is used to determine the logical and/or physical order of the items in a list; (ii) a value in the base type of a map, used to look up its associated value
An item in a map, consisting of two values: the key, which is taken from the base type, and the associated value, which can be retrieved by looking up the key
A tree node that has no children
A type of double rotation, with a left rotation followed by a right rotation
A type of rotation where it appears as though nodes are being rotated around the root of the right subtree
The number of items in a list; the length can vary over time
The distance of a node from the root; the root is level 0
Resolving a hash collision by sequentially searching a hash table beginning at the location returned by the hash function
Each element except the first has a unique predecessor, and each element except the last has a unique successor
An unordered collection of distinct components, each consisting of a key-value pair, where the key is a unique value chosen from the possible values of a single data type, called the base type; values may be retrieved by looking up the associated key
The loss of available memory space that occurs when memory is allocated dynamically but never deallocated
Testing based on measurable factors
A cohesive system subunit that performs a share of the work
The description of a group of objects with similar properties and behaviors; a pattern for creating individual objects
An operation that allows us to observe the state of an object without changing it
Giving the same name to more than one function or using the same operator symbol for more than one operation; usually associated with static binding
Computation in which multiple operations are performed simultaneously
(i) A combination of branches that might be traversed when a program or function is executed; (ii) a sequence of vertices that connects two nodes in a graph
A testing technique whereby the tester tries to execute all possible paths in a program or function
The ability to determine which of several operations with the same name is appropriate; a combination of static and dynamic binding
Assertions that state what results are expected at the exit of an operation or function, assuming that the preconditions are true
A systematic way of visiting all nodes in a binary tree that visits the nodes in the left subtree of a node, then visits the nodes in the right subtree of the node, and then visits the node
Assertions that must be true on entry into an operation or function for the postconditions to be guaranteed
A systematic way of visiting all nodes in a binary tree that visits a node, then visits the nodes in the left subtree of the node, and then visits the nodes in the right subtree of the node
The process of determining the degree to which software fulfills its intended purpose
The process of determining the degree to which a software product fulfills its specifications
Resolving a hash collision by using the rehashing formula (HashValue ± I2) % array-size, where I is the number of times that the rehash function has been applied
An abstract data type in which elements are added to the rear and removed from the front; a “first in, first out” (FIFO) structure
The number of possibilities for each position; the digits in a number system
Resolving a hash collision by generating pseudorandom hash values in successive applications of the rehash function
A solution that is expressed in terms of (1) smaller instances of itself and (2) a base case
A function call in which the function being called is the same as the one making the call
A definition in which something is defined in terms of a smaller version of itself
To rewrite existing code to reflect changes in requirements and design decisions
Reexecution of program tests after modifications have been made to ensure that the program still works correctly
Resolving a collision by computing a new hash location from a hash function that manipulates the original location rather than the element’s key
A statement of what is to be provided by a computer system or software product
A type of double rotation, with a right rotation followed by a left rotation
A type of rotation where it appears as though nodes are being rotated around the root of the left subtree
The ability of a program to recover following an error; the ability of a program to continue to operate within its environment
The top node of a tree structure; a node with no parent
A data structure that keeps track of activation records during the execution of a program
A sequence of steps that describes an interaction between a client and an application or program
The object to which a member function is applied
Computation that proceeds one step at a time
An unordered collection of distinct values (items or components), chosen from the possible values of a single data type, called the component (base) type
An operation that copies one class object to another without copying any pointed-to data
The discipline devoted to the design, production, and maintenance of computer programs that are developed on time and within cost estimates, using tools that help to manage the size and complexity of the resulting software products
A standard, integrated set of software engineering tools and techniques used on a project or by an organization
A detailed description of the function, inputs, processing, outputs, and special requirements of a software product; it provides the information needed to design and implement the program
A list that is sorted by the value in the key; a semantic relationship exists among the keys of the items in the list
A sorting algorithm that preserves the order of duplicates
An abstract data type in which elements are added and removed from only one end; a last-in, first-out (LIFO) structure
The condition resulting from trying to push an element onto a full stack
The condition resulting from trying to pop an empty stack
Every statement in the program is executed at least once
The compile-time determination of which implementation of an operation is appropriate
A special function that can be used in top-down testing to stand in for a lower-level function
A set X is a subset of set Y if each item of X is an element of Y; if at least one element of Y is not in X, then X is a proper subset of Y
An alternative form or syntax that makes programs easier to express and read; often translated into programming constructs supported by the base language
The case in which a function contains only a single recursive invocation and it is the last statement to be executed in the function
A C++ language construct that allows the compiler to generate multiple versions of a class type or a function by allowing parameterized types
A program that sets up the testing environment by declaring and assigning initial values to variables, then calls the subprogram to be tested
A document showing the test cases planned for a program or module, their purposes, inputs, expected outputs, and criteria for success
The process of executing a program with data sets designed to discover errors
A placeholder node at the end of a list; used to simplify list processing
An operation that changes the internal state of an object
A node whose balance factor is greater than 1
An ADT for which there is no logical limit on the number of items in the structure
A graph in which the edges have no direction
A binary set operation that returns a set made up of all the items that are in either of the input sets
Testing a module or function by itself
The set containing all the values of the component type
A list in which data items are placed in no particular order; the only relationships between data elements are the list predecessor and successor relationships
A collection of scenarios related to a common goal
A node in a graph
A verification method in which a team performs a manual simulation of the program or design
A graph in which each edge carries a value
Related to the maximum number of steps required by an algorithm, given the worst possible set of input values in terms of efficiency