Test Bank - Data Structures and Abstractions with Java, 5th edition by Frank M. Carrano,
Chapter 1-30
Permutation - (answer)A reordering of a sequence of n elements A[1..n]. A bijection π:{1..n} → {1..n}.
The sequence 1..n has n! different _______s.
Graph - (answer)A pair G=(V,E) with a finite set of vertices, V, and edges E⊆V×V. There are many
variations (directed, undirected, bipartite, planar, connected, DAG, weighted, Euclidean, sparse, dense)
and several data structures (adjacency matrix, adjacency list, edge list, half-edge, quad-edge) to
represent the different variations. This abstraction has many uses. CLRS B.4
DAG - (answer)A directed, acyclic graph. Used for precedence constraints (do this before that). CLRS p.
1172
Priority queue - (answer)A data structure storing elements with comparable keys that supports insert,
delete, find_min, and sometimes decrease_key.
Used in Heapsort, Prim's MST, and Dijkstra's shortest paths. CLRS 6.1, 23.2, 24.3.
Union find - (answer)A data structure for disjoint sets supporting make_set(x): creates set {x}
find(x): returns a name for the set containing x,
union(x,y): makes union of find(x) ∪ find{y}, eliminating the original sets if they were different.
Useful for connected components. CLRS 21 (not covered).
Fibonacci heap - (answer)A priority queue for n elements that supports insert, delete, and find_min in
O(lg n) time and decrease_key in O(1). Ideal for Prim's MST & Dijkstra's shortest paths. CLRS 19 (not
covered)
Direct access dictionary - (answer)Stores unique keys from the range [0..k] in an array K[0..k], supporting
insert, delete, search in the obvious ways. CLRS 11.1
Hash table - (answer)A table with m slots that stores n keys, indexed by a hash function h:Key-> Slot, to
support Search, Insert, & Delete. Load factor α=n/m. CLRS 11.2
Hash functions should be fast and distribute keys well (simple uniform hashing). 11.3
Chapter 1-30
Permutation - (answer)A reordering of a sequence of n elements A[1..n]. A bijection π:{1..n} → {1..n}.
The sequence 1..n has n! different _______s.
Graph - (answer)A pair G=(V,E) with a finite set of vertices, V, and edges E⊆V×V. There are many
variations (directed, undirected, bipartite, planar, connected, DAG, weighted, Euclidean, sparse, dense)
and several data structures (adjacency matrix, adjacency list, edge list, half-edge, quad-edge) to
represent the different variations. This abstraction has many uses. CLRS B.4
DAG - (answer)A directed, acyclic graph. Used for precedence constraints (do this before that). CLRS p.
1172
Priority queue - (answer)A data structure storing elements with comparable keys that supports insert,
delete, find_min, and sometimes decrease_key.
Used in Heapsort, Prim's MST, and Dijkstra's shortest paths. CLRS 6.1, 23.2, 24.3.
Union find - (answer)A data structure for disjoint sets supporting make_set(x): creates set {x}
find(x): returns a name for the set containing x,
union(x,y): makes union of find(x) ∪ find{y}, eliminating the original sets if they were different.
Useful for connected components. CLRS 21 (not covered).
Fibonacci heap - (answer)A priority queue for n elements that supports insert, delete, and find_min in
O(lg n) time and decrease_key in O(1). Ideal for Prim's MST & Dijkstra's shortest paths. CLRS 19 (not
covered)
Direct access dictionary - (answer)Stores unique keys from the range [0..k] in an array K[0..k], supporting
insert, delete, search in the obvious ways. CLRS 11.1
Hash table - (answer)A table with m slots that stores n keys, indexed by a hash function h:Key-> Slot, to
support Search, Insert, & Delete. Load factor α=n/m. CLRS 11.2
Hash functions should be fast and distribute keys well (simple uniform hashing). 11.3
