Term
Express in Big O Notation:
f(n) = n4 + 9456n3 + n |
|
Definition
|
|
Term
What is the dominant term of:
f(n) = n4 + 9456n3 + n |
|
Definition
|
|
Term
| With big O notation we express the runtime in terms of what? |
|
Definition
| How quickly it grows relative to the input, as the input gets arbitrarily large. |
|
|
Term
Express in Big O notation:
n3+50n2+10000 |
|
Definition
|
|
Term
What is the dominant term of:
n113+13n3+131313 |
|
Definition
|
|
Term
|
Definition
| Only entered in memory once, belongs to the class, its value is shared among all instances. |
|
|
Term
|
Definition
| A method that can be called using the class name without instantiating an object |
|
|
Term
| What is the difference between a static variable and an instance variable? |
|
Definition
| A static variable is shared among all instances of a class and an instance variable is accessed through a particular instance. |
|
|
Term
| Why can't a static method refer to an instance variable? |
|
Definition
| Static methods don't operate in the context of a particular object |
|
|
Term
|
Definition
| an Object form of primitive data |
|
|
Term
| Why does Java need wrapper classes? |
|
Definition
| We can't create advanced data structures out of primitive data |
|
|
Term
| Write a constructor for an Integer object called swiftObj and store the value 13. |
|
Definition
| Integer swiftObj = new Integer(13); |
|
|
Term
| Write a constructor for an Integer object called n and set the value to 22. |
|
Definition
| Integer n = new Integer(22); |
|
|
Term
| How do try/catch blocks work? |
|
Definition
| Take a section of code that has the potential to crash your program and put inside a try block. If it throws an exception or runtime error, it will jump to the catch block where there is code to handle the error. |
|
|
Term
| Why do people use try/catch blocks? |
|
Definition
| They allow for the program to handle an error and continue running without crashing |
|
|
Term
| When should you use try/catch blocks? |
|
Definition
| When there is code with the potential to to throw a runtime error or exception |
|
|
Term
| What is the advantage of using ArrayLists instead of arrays? |
|
Definition
| ArrayLists automatically size themselves to fit the contents of the structure |
|
|
Term
| What is the disadvantage of using ArrayLists instead of arrays? |
|
Definition
| We can’t put primitive types in an ArrayList |
|
|
Term
Write the code to loop through and output all the elements of an array list:
ArrayList<String> list |
|
Definition
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i).toString());
} |
|
|
Term
Write the code to loop through and output all of the elements of an ArrayList:
ArrayList<Dog> dogList |
|
Definition
for(int i = 0; i < dogList.size(); i++){
System.out.println(dogList.get(i).toString());
} |
|
|
Term
| What are the trade-offs in space complexity bewteen ArrayList and LinkedList? |
|
Definition
| LinkedList requires more space per object, while the ArrayList is resizable. |
|
|
Term
| What are the trade-offs in time complexity between ArrayList and LinkedList? |
|
Definition
| The ArrayList can access any element of the list in the same amount of time if the index value is know, while the LinkedList requires the list to be traversed from one end or the other to reach a position. |
|
|
Term
| Why is the time to increase the capacity of the array on an add operation negligible for an ArrayList? |
|
Definition
| Averaged over the number of insertions, the time to enlarge the array has little effect on the total time. |
|
|
Term
| Where are new elements added in a Queue? |
|
Definition
|
|
Term
| Where are elements removed from a Queue? |
|
Definition
|
|
Term
| What is the principle difference in behavior between a stack and a queue? |
|
Definition
| A stack reverses order, while a queue preserves order. |
|
|
Term
|
Definition
| A queue operation in which an element is removed from the front of the queue |
|
|
Term
|
Definition
| A queue operation that adds an element to the end of the queue |
|
|
Term
|
Definition
| first in first out. a description of a collection in which the first element added will be the first removed. |
|
|
Term
|
Definition
| A linear collection whose elements are added on one end and removed from the other |
|
|
Term
| What is the difference between a queue and a stack? |
|
Definition
| A queue is a FIFO collection while a stack is a LIFO colleciton |
|
|
Term
| What are the 4 basic operations on a queue? |
|
Definition
| enqueue, dequeue, first, isEmpty |
|
|
Term
Given the following queue X:
X.enqueue(new Integer(4));
X.enqueue(new Integer(1));
Object Y = X.dequeue();
X.enqueue(new Integer(8));
X.enqueue(new Integer(2));
X.enqueue(new Integer(5));
X.enqueue(new Integer(3));
Object Y = X.dequeue();
X.enqueue(new Integer(4));
X.enqueue(new Integer(9));
What would be the result of the following?
X.first();
|
|
Definition
|
|
Term
Given the following queue X:
X.enqueue(new Integer(4));
X.enqueue(new Integer(1));
Object Y = X.dequeue();
X.enqueue(new Integer(8));
X.enqueue(new Integer(2));
X.enqueue(new Integer(5));
X.enqueue(new Integer(3));
Object Y = X.dequeue();
X.enqueue(new Integer(4));
X.enqueue(new Integer(9));
What would be the result of the following?
Y = X.dequeue();
X.first();
|
|
Definition
|
|
Term
| What is the cost of the enqueue() operation? |
|
Definition
|
|
Term
| What is the cost of the dequeue() operation? |
|
Definition
|
|
Term
| What 2 types of pointers are used in queues? |
|
Definition
| head pointer and tail pointer |
|
|
Term
|
Definition
| Direct access to first object in the list |
|
|
Term
|
Definition
| direct access to the last object in the list |
|
|
Term
| Where are new elements added to stacks? |
|
Definition
|
|
Term
| Where are elements removed from a stack? |
|
Definition
|
|
Term
|
Definition
| A collection in which items with higher priority go first, and items with the same priority are ordered in accordance with the FIFO principal |
|
|
Term
| What is the cost of the push() operation for a stack? |
|
Definition
|
|
Term
| What is the cost of the pop() operation for a stack? |
|
Definition
|
|
Term
| What type of pointer does a stack use? |
|
Definition
|
|
Term
| When would you use a stack instead of a queue? |
|
Definition
| When all the objects are the same |
|
|
Term
|
Definition
| An object that defines an unusual or erroneous situation |
|
|
Term
|
Definition
|
|
Term
|
Definition
| A stack operation in which an element is removed from the top of a stack |
|
|
Term
|
Definition
| A stack operation in which an element is added to the top of a stack |
|
|
Term
|
Definition
| A linear collection whose elements are added and removed from the same end in a LIFO manner |
|
|
Term
| What is the characteristic behavior of a stack? |
|
Definition
| A stack is a LIFO structure |
|
|
Term
| What are the 5 basic operations of a stack? |
|
Definition
| push, pop, peek, isEmpty, size |
|
|
Term
Given the following operation for an initially empty stack X:
X.push(new Integer(4));
X.push(new Integer(3));
Integer Y = X.pop();
X.push(new Integer(13));
X.push(new Integer(22));
X.push(new Integer(15));
X.push(new Integer(7));
Integer Y = X.pop();
X.push(new Integer(9));
X.push(new Integer(5));
Given the resulting stack, what would be the result of the following?
Y = X.peek(); |
|
Definition
|
|
Term
Given the following operation for an initially empty stack
X:
X.push(new Integer(4));
X.push(new Integer(3));
Integer Y = X.pop();
X.push(new Integer(13));
X.push(new Integer(22));
X.push(new Integer(15));
X.push(new Integer(7));
Integer Y = X.pop();
X.push(new Integer(9));
X.push(new Integer(5));
Given the resulting stack, what would be the result of the following?
Y = X.pop();
Z = X.peek(); |
|
Definition
|
|
Term
|
Definition
| A stack of activation records used to keep track of method interactions during program execution |
|
|
Term
| What are the advantages of using the java.util.Stack implementation of a stack? |
|
Definition
| Because this implementation is an extension of the Vector class, it can keep track of the positions of elements in the stack with an index, so it doesn't need each node to store an additional pointer. |
|
|
Term
| What do the LinkedStack<T> and ArrayStack<T> classes have in common? |
|
Definition
| Both classes implement the StackADT interface, so both represent a stack collection, providing the necessary operations to use a stack. |
|
|
Term
| What is the potential problem with the java.util.Stack implementation? |
|
Definition
| This implementation is an extension of the Vector class, so it inherits a large number of operations that violate the basic assumptions of a stack |
|
|
Term
| How is a linked list constructed? |
|
Definition
| each element holds a reference to the next element in the list. The linked list class holds a reference to the first element. |
|
|
Term
|
Definition
| A linked list in which each node has references to both the next node and the previous node in the list |
|
|
Term
|
Definition
| A linked structure in which one object refers to the next, creating a linear ordering |
|
|
Term
|
Definition
| A data structure that uses object variables to create links between objects |
|
|
Term
| What special case exists when managing linked lists? |
|
Definition
| A special reference variable is maintained that specifies the first element in the list. If that element is deleted, or if a new element is added in front of it, the front reference must be carefully maintained. |
|
|
Term
| Why should a linked list node be separate from the element on the list? |
|
Definition
| Every object that we may want to put in a collection may not be designed to cooperate with the collection implementation. |
|
|
Term
| What is the difference between a doubly linked list and a singly linked list? |
|
Definition
| A singly linked list maintains a reference to the first element in a list and a next reference from each node to the following node, while a doubly linked list maintains two references: front and rear. |
|
|
