ITSC 2214 Data Structures & Algorithms Test 2 Study Guide

Assume you are adding an item, ‘F’, to the end of
this list. You’ve already created a linear node called
temp with a pointer to ‘F’. What lines of code update
this list?

• back.setNext(temp);
  back = temp;
  numNodes++;

• back.getNext(setNext(temp));
  back = temp;
  numNodes++;

• back = temp;
  back.getNext(setNext(temp));
  numNodes++;

• back = temp;
  back.setNext(temp);
  numNodes++;

  
  

A queue processes items in what order?

• FIFO

• LIFO

• FILO

• LILO

• LIFO or FIFO

What are the contents of an ArrayList, myList,
after the following code is run:

myList.add("Ahab");
myList.add("Anitja");
myList.add("Yusef");
myList.add("Kelli");
myList.remove(1);
myList.remove(2);

• ["Ahab", "Anitja"]

• ["Ahab", "Kelli"]

• ["Ahab", "Yusef"]

• ["Yusef", "Kelli"]

• ["Anitja", "Kelli"]

What would be the complexity of the size()
method for a linked list if there was no count
variable?

• O(1)

• O(n)

• O(log n)

• O(n^2)

Given the following information, select all the
asserts that would properly test a dequeue
operation if you’ve only added one object to the
queue.

• result is what the dequeue operation returns
• expdRslt is what you think should be returned
• myQueue is the queue of objects

• assertEquals(result, expdRslt);

• assertEquals(myQueue.size, 0);

• assertTrue(myQueue.size == 0);

• assertEquals(myQueue.size(),0);

• assertTrue(result.equals(expdRslt));

Given the following code, what is returned? Assume that ArrayQueue is a
correctly implemented class, with lots of capacity. Also note that we are
using Java's built-in queue which uses add/remove instead of
enqueue/dequeue, which is just a different vocabulary.

String s;
Queue<String> myQueue = new ArrayQueue<Integer>;
myQueue.add(“a”);
myQueue.add(“b”);
s = myQueue.remove();
s = myQueue.remove();
myQueue.add(“c”);
myQueue.add(“d”);
s = myQueue.remove();
s = myQueue.remove();
return s;

• "a"

• "b"

• "c"

• "d"

• Nothing, this won't compile.

Given the following code using a queue X of
Integers, what is returned by a call to X.first()?

X.enqueue(new Integer(4));
X.enqueue(new Integer(3));
Integer y = X.dequeue();
X.enqueue(new Integer(7));
X.enqueue(new Integer(2));
X.enqueue(y);
y = X.dequeue();
X.enqueue(new Integer(3));
X.enqueue(new Integer(8));
? = X.first();

• 4

• 8

• 7

• 3

• Nothing, an exception is thrown

• 0

• 1

• 2

• 3

• 4

Linked nodes have what advantages over arrays
when implementing collections?

• No capacity issues

• Easier to program
  because of pointers

• Faster access to the
  elements in the
  collection

• None of the above

• T temp = front.getElement();

• temp = front.getElement();

• front = front.getNext();

• front.next = null;

• numNodes--;