CS2110 Final
Terms
undefined, object
copy deck
- Binary search requires linear time in the worst case.
- FALSE
- Trees and singly-linked lists are both DAGs.
- TRUE
- Swing Listeners are an example of the Observer pattern.
- TRUE
- Insertion sort has worst-case running time that is O(n lg n).
- FALSE
- The worst-case performance of looking up an element in a hash table is O(n), where n is the number of elements.
- TRUE
- In the worst case, both breadth-first and depth-first search can require state that is O(|V |) in size.
- TRUE
- A planar graph is one with no arrowheads on the edges.
- FALSE
- Dijkstra’s algorithm can be used to find a minimum spanning tree.
- TRUE
- Static methods may not refer to this.
- TRUE
- If class B is a subclass of class A and A implements interface C, then B automatically implements C even if it does not provide explicit implementations of the methods of C.
- TRUE
- In a Java GUI, a Container would use a LayoutManager to organize the layout of its Components.
- TRUE
- Binary search trees are faster than hash tables in practice.
- FALSE
- Breadth-first search uses a stack.
- FALSE
- DFS takes O(|E| + |V |) time if the graph is represented as an adjacency matrix. |E| is the number of edges and |V | is the number of vertices(nodes).
- FALSE
- The essential property of a good user interface is that it is easy for programmers to implement.
- FALSE
- In Java, each event such as a button click or keystroke spawns a new thread to handle the event.
- FALSE
- Insertion sort, selection sort, and bubblesort all have the same asymptotic worst-case complexity.
- TRUE
- When implementing quicksort, the first element of an interval is always a good choice for the pivot.
- FALSE
- At runtime, a successful downcast from type A to type B changes the dynamic type of the object from A to B.
- FALSE
- n2 log n + n(log n)2 is O(n2(log n)2)
- TRUE
- The AVL invariant states that a tree’s shortest and longest paths differ in length by at most 1.
- FALSE
- The rotate operation on AVL trees preserves inorder numbering.
- TRUE
- Abstract classes can be instantiated like any other class.
- FALSE
- A stack is a FIFO structure and a queue is a LIFO structure.
- FALSE
- If class A implements interface I, class B extends A, and class C extends B, then C implements I.
- TRUE
- If class A implements interface I, class B extends A, class C extends B, and interface J extends interface I, then C implements J.
- FALSE
- 3n is O(2n).
- FALSE
- log(3n) is O(log(2n)).
- TRUE
- log3 n is O(log2 n).
- TRUE
- log(n2) is O(log(n3)).
- TRUE
- The optimal number of collisions per bucket in a hashtable is 1.
- FALSE
- If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)).
- TRUE
- An occurrence of ’this’ in a static method will cause a compile-time error.
- TRUE
- Binary search is as efficient on linked lists as on arrays, provided the list is doubly linked.
- FALSE
- The finally block in a try-catch-finally statement is executed even if no exception is thrown and there is a return statement in the try block.
- TRUE
- A non-abstract subclass of an abstract class C must provide definitions for all the abstract methods of C.
- TRUE
- Downcasting is always legal and can be done without an explicit cast.
- FALSE
- Every dag has a unique topological sort.
- FALSE
- In the worst case, search in an unbalanced binary tree is asymptotically the same complexity as search in a balanced binary tree.
- FALSE
- An ActionListener registered with a JMenuItem is executed automatically whenever that JMenuItem is selected.
- TRUE
- A stack is a LIFO structure and a queue is a FIFO structure.
- TRUE
- If class A implements interface I, class B extends A, and class C extends B, then C implements I.
- TRUE
- If class A implements interface I, class B extends A, class C extends B, and I extends interface J, then C implements J.
- TRUE
- 10n is O(2n).
- FALSE
- log(10n) is O(log(2n)).
- TRUE
- log10n is O(log2n).
- TRUE
- log(n2) is O(log(n10).
- TRUE
- An occurrence of ’this’ in a static method will generate a compiler error.
- TRUE
- Binary search is as efficient on linked lists as on arrays, provided the list is doubly linked.
- FALSE
- A non-abstract subclass of an abstract class C must provide implementations of all the abstract methods of C.
- TRUE
- Upcasting is always legal and can be done without an explicit cast.
- TRUE
- An ActionListener registered with a JMenuItem is invoked automatically whenever that JMenuItem is selected by the user.
- TRUE
- Any call to a method that may throw an exception must be wrapped in a try-catch block.
- FALSE
- Any theorem that can be proved by strong induction can also be proved by weak induction.
- TRUE
- Quicksort is never asymptotically worse than mergesort.
- FALSE
- When implementing quicksort, the first element of an interval is always the best choice for the pivot.
- FALSE
- Quicksort can be implemented efficiently on doubly-linked lists without using any extra list nodes or arrays.
- TRUE
- In propositional logic, a formula is a tautology if and only if all its subformulas are tautologies
- FALSE
- A subclass inherits its parents public, protected and private fields
- FALSE
-
If MyIterator implements the Iterator interface, we can add any object of type Interator to ArrayList
. - FALSE
- Static initializers are run only once, when the class is loaded
- TRUE
- A call to super or this in a constructor must occur first.
- TRUE