CSC 3280 Midterm

True/False

A stack implemented with an ArrayList can be written to execute push always in O(1) time

False

True/False

The following code will reverse the order of elements in dragonArmy, a Stack<String>. (Assume the stack has an appropriate isEmpty method.)

ArrayList<String> students = new ArrayList<String>();

while (!dragonArmy.isEmpty()) {

  students.add(dragonArmy.pop(), 0);

}

for (int i = 0; i < students.size(); i++) {

  dragonArmy.push(students.get(i));

}

False

How long does it take to get the element at the middle index of an ArrayList of n elements? (Round the index down for lists with an even number of elements.)

A. O(1)
B. O(n)
C. O(n log(n))

D. O(n^2)

A. O(1)

meeses is a Linked List with 12 elements. Which of the following will always do the same as:

System.out.println(meeses.get(2));

A. System.out.println(meeses.getFirst());

B. System.out.println(meeses.getTail().getFirst());

C. System.out.println(meeses.getTail().getTail().getFirst());

C. System.out.println(meeses.getTail().getTail().getFirst());

A(n) _________ is an instance of a class.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

object

Consider two versions of a Linked List class: a basic version that directly represents a node (with two fields) and a wrapper class that has references to both the first and last nodes in the list.  Which of the following methods is faster for the wrapped version?

A. add(E element)

B. remove(int i)

C. get(int i)

A. add(E element)

How long does it take to get the zeroeth element in an ArrayList?

A. O(1)

B. O(n)

C. O(n log(n))

D. O(n^2)

A. O(1)

True/False

System.out.println(weasleys.size());

weasleys.add(george);

System.out.println(weasleys.size());

If weasleys is an ArrayList it's possible for the above code to print:

12

12

False

A(n) _________ class may have some abstract method definitions and some implemented method.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

abstract

What is the maximum number of parent classes a class can directly extend?
A. 0

B. 1

C. 2

D. There is no maximum limit.

B. 1

True/False

A recursive linked list class with only two fields requires O(n) time to access the last element in a list with n elements.

True

Which of the following could be the pop and push methods in a Java implementation of a stack, where the field this.elements is an ArrayList? (Reminder: the ArrayList.remove(int i) method returns the element that is removed.)

A.

public void push(T element) {

  this.elements.add(element);

}

public T pop() {

  return this.elements.remove(0);

}

B.

public void push(T element) {

  this.elements.add(0, element);

}

public T pop() {

  int lastIndex = this.elements.size() - 1;

  return this.elements.remove(lastIndex);

}

C.

public void push(T element) {

  this.elements.add(element);

}

public T pop() {

  int lastIndex = this.elements.size() - 1;

  return this.elements.remove(lastIndex);

}

D.

public void push(T element) {

  this.elements.add(element);

}

public T pop() {

  int lastIndex = this.elements.size();

  return this.elements.remove(lastIndex);

}

C.

public void push(T element) {

  this.elements.add(element);

}

public T pop() {

  int lastIndex = this.elements.size() - 1;

  return this.elements.remove(lastIndex);

}

True/False

A linked list class can be implemented with only two fields.

True

A(n) _________ is a data structure where elements are always added and removed at the top. In order to access the element at the bottom, all other elements must be removed first.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

stack

True/False

The following code will reverse the order of elements in ollivanders, a stack of Wand obects. (Assume the stack has an appropriate isEmpty method)

Stack<Wand> tempWands = new Stack<Wand>();

while (!ollivanders.isEmpty()) {

  tempWands.push(ollivanders.pop());

}

while (!tempWands.isEmpty()) {

  ollivanders.push(tempWands.pop());

}

False

How long does it take to get the largest integer in an unsorted ArrayList of n integers?

A. O(1)
B. O(n)
C. O(n log(n))

D. O(n^2)

B. O(n)

How long does it take to get the last element in an ArrayList?

A. O(1)

B. O(n)

C. O(n log(n))

D. O(n^2)

A. O(1)

Which of the following is (probably) the name of the field that a doubly-linked list has that a singly-linked list doesn't?

A. previous

B. tail
C. next

D. first

A. previous

How long does it take to add an element to the end of an ArrayList with n elements?

A. Always O(1)

B. Always O(n)

C. Usually O(1), but sometimes O(n)

D. Sometimes O(n/2), sometimes O(n)

C. Usually O(1), but sometimes O(n)

A(n) _________ is an indexable Java data structure with a fixed size.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

array

A(n) _________ is similar to an abstract class, except that only the method signatures are given, with no implementing bodies.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

interface

True/False

Assume the Java class RavenclawStudent extends HogwartsStudent and both classes implement the levitate() method.  Then, in the following code, the RavenclawStudent's version will be invoked:
HogwartsStudent hjpev = new RavenclawStudent();

hjpev.levitate();

True

True/False

The following ocde will reverse the order of elements in sunshineRegment, a stack of String obects.

ArrayList<String> soldiers = new ArrayList<String>();

while (!sunshineRegiment.isEmpty()) {

  soldiers.add(sunshineRegiment.pop());
}

for (int i = 0; i < soldiers.size(); i++) {

  sunshineRegiment.push(soldiers.get(i));

}

True

True/False
A linked list class implemented with two fields takes O(1) time to add an element to the middle of a list with n elements.

False

A method turn implemented in Java class, Timeturner, _________ any methods with the same signature implemented in Timeturner's superclasses.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

overrides

A(n) _________ is a class that is extended by another class.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

superclass

How long does it take to get the top element in a stack of n elements if push and pop both run in constant time?

A. O(1)
B. O(n)
C. O(n log(n))

D. O(n^2)

A. O(1)

Which of the following is (probably) the name of the field that a doubly-linked list has that a singly-linked list doesn't?

A. previous

B. tail

C. next

D. first

A. previous

How long does it take to add an element to the front of an ArrayList with n elements?

A. Always O(1)

B. Always O(n)

C. Usually O(1), but sometimes O(n)

D. Sometimes O(n), sometimes O(n^2)

B. Always O(n)

A(n) _________ is a class that extends another class.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

subclass

A(n) _________ list is a recursive data structure with two fields. One of those fields has the same type as the object itself!
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

linked

Blaise Zabini decides to implement a Java stack on top of an ArrayList using a void version of pop. (If the user wants to see what's on top, they need to use peek instead.) Which pair of definitions for push and pop should Blaise use to correctly implement a stack?

A.

public void push(T element) {

  this.elements.add(0, elements);

}

public void pop() {

  this.elements.remove(0);

}

B.

public void push(T element) {

  this.elements.add(0, element);

}

public void pop() {

  this.elements.remove(this.elements.size() - 1);

}

C.

public void push(T element) {

  this.elements.add(element);

}

public void pop() {

  this.elements.remove(0);

}

D.

public void push(T element) {

  this.elements.add(this.elements.size()-1, element);

}

public void pop() {

  this.elements.remove(0);

}

A.

public void push(T element) {

  this.elements.add(0, elements);

}

public void pop() {

  this.elements.remove(0);

}

The java Animagus class extends the Wizard class, and thus any Animagus object _________ all fields from the Wizard class.
Fill in the blank with one of the following options:

abstract

array

inherits

interface

linked

object

overrides

stack

subclass

superclass

inherits

True/False

If the following line of Java code compiles, then SunshineGeneral is a subtype of SunshineRegimentSoldier.

SunshineRegimentSoldier hermione = new SunshineGeneral();

True

How long does it take to get the biggest element in an ArrayList of n elements, sorted lowest to highest?

A. O(1)

B. O(n)

C. O(n log(n))

D. O(n^2)

A. O(1)