CSE 2231 Final
Abstract class - answerA "partial" or "incomplete" class that contains bodies for some
but (typically) not all of the methods of the interfaces it claims to implement
Factoring out common code - answer Method bodies that can be written once— and
work for any implementation of Natural Number Kernel because they are programmed
to that interface—have been factored out into an abstract class
Can you instantiate an abstract class? - answer No - You can't use an abstract class
like a normal class and create objects from it
UUT - answerUnit under testing
How to achieve single-point control over change in this situation - answer"Re-route" all
UUT constructor calls to another method, which then calls the UUT constructor, so only
the body of that one method needs to be changed to accommodate a different UUT
Class ending with "L" - answerKernel class that directly represents the new type using a
component from Java libraries
Instance variable - answerThere is a distinct variable (with the same name) for each
instance of the class in which it is declared
Criteria for kernel implementation - answer1. Easy to understand and write
2. More efficient
Sequence3 on Stack - answerSequence represented as 2 stacks, left and right.
Sequence = rev(left) + right
Representation of sequence is 2 stacks "facing each other" in the middle of sequence
Client view - answerMathematical models, method contracts
Kernel interface shows WHAT the software does
Implementer view - answerData representation, algorithms
Kernel class shows HOW the software does it
Abstract state space - answerThe set of all possible math model values as seen by the
client
Concrete state space - answerThe set of all possible math model values of the data
representation
, Abstraction function - answerHow to interpret any concrete value (that satisfies the
representation invariant) as an abstract value?
@correspondence
Representation invariant - answerWhat configurations of values of the instance
variables can arise?
@convention
Why hashing? - answer1. Can be quickly identified
2. Must contain the item
T/F: Nodes in a linked list must always have consecutive memory addresses? -
answerFalse
T/F: Nodes in a linked list can be accessed in constant time? - answerFalse
T/F: Nodes in a linked list require at least one smart node? - answerFalse
T/F: Nodes in a linked list can be accessed sequentially in linear time? - answerTrue
T/F: The process of building a heap will completely sort its elements? - answerFalse
T/F: A subroutine is needed to adjust the root of a subtree to its proper position,
assuming the subtree is a heap except for its root - answerTrue
T/F: Heaps are parameterized by a type and an ordering process? - answerTrue
T/F: A heap is a binary tree with extra constraints on its shape and organization -
answerTrue
Collection type definition - answerAny type whose abstract mathematical model
involves: string, set, multiset, tree, binary tree
Collection type examples - answerArray, queue, set, sequence, stack, map, sorting
machine
Array pros - answer-Direct access
-Constant time access (regardless of length)
Array cons - answer-Fixed size; can run out of room
-Fixed size; initialization might be expensive if entries go unused
-Adding/removing entires in the middle requires moving other entries, which is slow
Array is represented by... - answerA contiguous block of memory locations with
consecutive memory addresses so the memory address of the entry at index i can be
directly calculated from the memory address of the first entry, by using simple arithmetic
Abstract class - answerA "partial" or "incomplete" class that contains bodies for some
but (typically) not all of the methods of the interfaces it claims to implement
Factoring out common code - answer Method bodies that can be written once— and
work for any implementation of Natural Number Kernel because they are programmed
to that interface—have been factored out into an abstract class
Can you instantiate an abstract class? - answer No - You can't use an abstract class
like a normal class and create objects from it
UUT - answerUnit under testing
How to achieve single-point control over change in this situation - answer"Re-route" all
UUT constructor calls to another method, which then calls the UUT constructor, so only
the body of that one method needs to be changed to accommodate a different UUT
Class ending with "L" - answerKernel class that directly represents the new type using a
component from Java libraries
Instance variable - answerThere is a distinct variable (with the same name) for each
instance of the class in which it is declared
Criteria for kernel implementation - answer1. Easy to understand and write
2. More efficient
Sequence3 on Stack - answerSequence represented as 2 stacks, left and right.
Sequence = rev(left) + right
Representation of sequence is 2 stacks "facing each other" in the middle of sequence
Client view - answerMathematical models, method contracts
Kernel interface shows WHAT the software does
Implementer view - answerData representation, algorithms
Kernel class shows HOW the software does it
Abstract state space - answerThe set of all possible math model values as seen by the
client
Concrete state space - answerThe set of all possible math model values of the data
representation
, Abstraction function - answerHow to interpret any concrete value (that satisfies the
representation invariant) as an abstract value?
@correspondence
Representation invariant - answerWhat configurations of values of the instance
variables can arise?
@convention
Why hashing? - answer1. Can be quickly identified
2. Must contain the item
T/F: Nodes in a linked list must always have consecutive memory addresses? -
answerFalse
T/F: Nodes in a linked list can be accessed in constant time? - answerFalse
T/F: Nodes in a linked list require at least one smart node? - answerFalse
T/F: Nodes in a linked list can be accessed sequentially in linear time? - answerTrue
T/F: The process of building a heap will completely sort its elements? - answerFalse
T/F: A subroutine is needed to adjust the root of a subtree to its proper position,
assuming the subtree is a heap except for its root - answerTrue
T/F: Heaps are parameterized by a type and an ordering process? - answerTrue
T/F: A heap is a binary tree with extra constraints on its shape and organization -
answerTrue
Collection type definition - answerAny type whose abstract mathematical model
involves: string, set, multiset, tree, binary tree
Collection type examples - answerArray, queue, set, sequence, stack, map, sorting
machine
Array pros - answer-Direct access
-Constant time access (regardless of length)
Array cons - answer-Fixed size; can run out of room
-Fixed size; initialization might be expensive if entries go unused
-Adding/removing entires in the middle requires moving other entries, which is slow
Array is represented by... - answerA contiguous block of memory locations with
consecutive memory addresses so the memory address of the entry at index i can be
directly calculated from the memory address of the first entry, by using simple arithmetic
