CMPT-280 FINAL EXAM
PREPERATION CORRECT 100%
What are the operations of a List ADT? - ANSWER- Create a new, empty list
- Insert a new data item at the front of the list
- Insert a new item at the end of the list
- Delete the first item in the list
- Delete the last item in the list
- Obtain the i-th item in the list
Give a brief description of the Linked List class. - ANSWERA java class with attributes
head and numEl. This class stores LinkedNode<I> items, where LinkedNode has
attributes: item and nextNode.
What is Black Box Testing? - ANSWERWe cannot see the code, we simply look at the
inputs and outputs and build test cases around that.
What is White Box Testing? - ANSWERWe get to look at the code and consider all of
the different paths through the program. Test for 0, 1, 2 and many loops, items etc.
What is the Active Operation Approach? - ANSWERFinding the statement that runs the
most in the code and using that to get the Big-Oh-Notation of the code.
What are the methods of Cursors? - ANSWER- itemExists
- item
- goFirst
- goForth
- goLast
- goBefore
- goAfter
- before
- after
(A cursor doesn't have to provide all of the methods for example a cursor in a Stack
would only need the item and itemExists methods since you aren't allowed to
manipulate the cursor)
What is the difference between iterators and cursors? - ANSWERA cursor is a property
of the collection. Where an iterator is a different distinct object.
What is the Timing Analysis of Insertion and Deletion from a Doubly-Linked List? -
ANSWERYou can insert from the beginning in O(1) time middle in (O(n) time however,
O(1) in some cases) and the end in O(1) time.
, You can delete from the beginning in O(1) time and from the end in O(n) time.
What is the difference between mutable and immutable? What are examples of each? -
ANSWERImmutable - Cannot be changed, [Integer Double Float Character]
Mutable - Can be changed, [LinkedNode280 LinkedList280]
Shallow Clone - ANSWEROnly one new object instance is created. If the Object has
instance variables those are copied as well. If the object contains any references to
other objects those are copied as well but that is as deep as it goes.
Deep Clone - ANSWERClones all of the other objects reference either directly on
indirectly by the object being cloned.
What is a data structure? - ANSWERA collection of data elements and a set of
associations between those elements.
What is an abstract data type (ADT)? - ANSWERIs an abstraction that permits
programmers to makes use of a data structure without knowing the internal
implementation.
These are used to allow for reduced coupling (the degree to which two modules of code
depend on each other) and increased cohesion (the degree to which components of a
modules of code are related or belong together).
ADT Specification - ANSWERReview Assignment 2
Define the term parent, child, ancestor, descendant, sibling, level and height in terms of
trees. - ANSWERParent - The node above the current node
Child - The node/nodes below the current node
Ancestor - Any node above the current node that is still in the same subtree
Descendant - Any node below the current node that is still in the same subtree
Height - The amount of the rows in the current tree.
Level - The current row that you are on (at the root node level = 0)
Arrayed Binary Trees - ANSWERItems in the array are offset by 1 (the starting index is
1). The left child is stored at 2i and the right child is stored at 2i+1. The parent is stored
at offset i/2.
Breadth First Search - ANSWERStarts at the root and always visits all the nodes on the
current level of the tree before visiting nodes on the next level of the tree.
PREPERATION CORRECT 100%
What are the operations of a List ADT? - ANSWER- Create a new, empty list
- Insert a new data item at the front of the list
- Insert a new item at the end of the list
- Delete the first item in the list
- Delete the last item in the list
- Obtain the i-th item in the list
Give a brief description of the Linked List class. - ANSWERA java class with attributes
head and numEl. This class stores LinkedNode<I> items, where LinkedNode has
attributes: item and nextNode.
What is Black Box Testing? - ANSWERWe cannot see the code, we simply look at the
inputs and outputs and build test cases around that.
What is White Box Testing? - ANSWERWe get to look at the code and consider all of
the different paths through the program. Test for 0, 1, 2 and many loops, items etc.
What is the Active Operation Approach? - ANSWERFinding the statement that runs the
most in the code and using that to get the Big-Oh-Notation of the code.
What are the methods of Cursors? - ANSWER- itemExists
- item
- goFirst
- goForth
- goLast
- goBefore
- goAfter
- before
- after
(A cursor doesn't have to provide all of the methods for example a cursor in a Stack
would only need the item and itemExists methods since you aren't allowed to
manipulate the cursor)
What is the difference between iterators and cursors? - ANSWERA cursor is a property
of the collection. Where an iterator is a different distinct object.
What is the Timing Analysis of Insertion and Deletion from a Doubly-Linked List? -
ANSWERYou can insert from the beginning in O(1) time middle in (O(n) time however,
O(1) in some cases) and the end in O(1) time.
, You can delete from the beginning in O(1) time and from the end in O(n) time.
What is the difference between mutable and immutable? What are examples of each? -
ANSWERImmutable - Cannot be changed, [Integer Double Float Character]
Mutable - Can be changed, [LinkedNode280 LinkedList280]
Shallow Clone - ANSWEROnly one new object instance is created. If the Object has
instance variables those are copied as well. If the object contains any references to
other objects those are copied as well but that is as deep as it goes.
Deep Clone - ANSWERClones all of the other objects reference either directly on
indirectly by the object being cloned.
What is a data structure? - ANSWERA collection of data elements and a set of
associations between those elements.
What is an abstract data type (ADT)? - ANSWERIs an abstraction that permits
programmers to makes use of a data structure without knowing the internal
implementation.
These are used to allow for reduced coupling (the degree to which two modules of code
depend on each other) and increased cohesion (the degree to which components of a
modules of code are related or belong together).
ADT Specification - ANSWERReview Assignment 2
Define the term parent, child, ancestor, descendant, sibling, level and height in terms of
trees. - ANSWERParent - The node above the current node
Child - The node/nodes below the current node
Ancestor - Any node above the current node that is still in the same subtree
Descendant - Any node below the current node that is still in the same subtree
Height - The amount of the rows in the current tree.
Level - The current row that you are on (at the root node level = 0)
Arrayed Binary Trees - ANSWERItems in the array are offset by 1 (the starting index is
1). The left child is stored at 2i and the right child is stored at 2i+1. The parent is stored
at offset i/2.
Breadth First Search - ANSWERStarts at the root and always visits all the nodes on the
current level of the tree before visiting nodes on the next level of the tree.
