CSCI 211 Test 1

Question 1

variables declared as “primitive types” ? represent information and are stored on the ?

Answer 1

directly; runtime stack

Question 2

runtime stack

Answer 2

belongs to the program; keeps track of return addresses for method calls and variables that are local to a method (including method parameters)

Question 3

variables declared as class types are ? to objects

Answer 3

“references”

Question 4

objects are stored on the

Answer 4

runtime heap

Question 5

the reference to an object is on the

Answer 5

runtime stack

Question 6

pass by value

Answer 6

when calling a method, copies of the argument values are given to the method parameters

Question 7

pass by references

Answer 7

a copy is given to the method parameters, but the copy of the reference points to the same object as the original (gives you the ability to make changes to the object)

Question 8

object

Answer 8

a programming construct that consists of a state and set of behaviors; an instance of a class

Question 9

an object’s state is described by

Answer 9

data members (e.g. int count, boolean full)

Question 10

class

Answer 10

describes a set of objects of the same type (data members, methods); a blueprint that says how to build an object of that type; contains actual code

Question 11

interface

Answer 11

a set of methods that are provided by a unit of code; java lets us declare an interface as a set of methods (doesn’t require an implementation)

Question 12

Java allows us to group a collection of classes into a ?

Answer 12

package; just put “package packagename;” at the top of all files in the package

Question 13

when application code wants to use a package

Answer 13

import packagename.*; (matches all classes in the package)

Question 14

API (Application Programming Interface)

Answer 14

the set of public methods supported by the classes in the package (their interfaces) is an example

Question 15

public

Answer 15

visible to the application

Question 16

private

Answer 16

only accessible by class

Question 17

(no access modifier)

Answer 17

default = package access only

Question 18

protected

Answer 18

visible to child classes and the package

Question 19

collection

Answer 19

a container that holds of group of objects, often called elements

Question 20

the Java Collection Framework supports several types of collection:

Answer 20

List, Set, Maps

Question 21

List

Answer 21

an ordered collection; order can be determined by insertion order or sometimes by the compareTo() method of the Comparable Interface or a Comparator object that’s passed to a sort() method of the collection

Question 22

Set

Answer 22

usually no guarantee that order will be preserved; null elements are allowed; NO duplicates are allowed (they will be ignored if entered)

Question 23

Maps

Answer 23

a collection of key-value pairs (each key is associated with one value object - typically use key to look up a value)

Question 24

List Interface provides methods such as

Answer 24

void add(E, e);
void add(int index, E e);

Question 25

ArrayList vs LinkedList

Answer 25

ArrayList uses an array, which is quick for “random access,” but slow for insertion and deletion
LinkedList uses a “chain” of “Nodes,” each containing an element; slow for finding elements (“random access”) because it has to traverse the list from top to bottom, but quick for insertion and deletion

Question 26

Stack

Answer 26

a specialist list; elements are added and removed from the top of the stack (behaves like a stack of dinner places); an example of a LIFO data structure

Question 27

Stack methods

Answer 27

push(E element) - add element to top of stack
E pop() - remove the topmost element from the stack, then return element
E peek() - returns a reference to the topmost element

Question 28

how to create an instance of the Stack class

Answer 28

Stack< Integer > s = new Stack<>();

Question 29

Queue

Answer 29

elements are added to the tail (end) of the queue and removed from the head (beginning), like a bank teller line; FIFO data structure

Question 30

Queue methods

Answer 30

add(E element) - add element to end of queue (aka enqueue); throws exception on failure
boolean offer(E element) - add to end of queue; returns false on failure
E remove() - remove element from head of queue (aka dequeue)

Question 31

how to create an instance of the Queue class

Answer 31

Queue< Integer > q = new LinkedQueue<>();

Question 32

Deque

Answer 32

can add or remove elements from either end

Question 33

Deque methods

Answer 33

addFirst(E element)
addLast(E element)
E removeFirst()
E removeLast()

Question 34

PriorityQueue

Answer 34

order of elements is data dependent; elements are removed in order of priority, as determined by a compareTo() method

Question 35

We can make our own stack using Linked Lists:

Answer 35

a Node class will proved a reference to the next Node in the linked list, and also a reference to the data being stored (“payload”); the Node class could be an “inner class” - defined inside of another class; also, we should use generics to allow the same stack class to handle a variety of element types

Question 36

Test Driven Development

Answer 36

write Unit tests for all the cases you can think of at the same time as the code, then write just enough code to pass the test; tests should expose bugs, then you can use the debugger with the tests to diagnose the cause of the bugs; each test should be small and self-contained so they are each run separately

Question 37

how to write a test that should throw an exception

Answer 37

@Test(expected = NoSuchElementException.class)
void testName() {
     //test stuff
}

Question 38

how to write a test

Answer 38

@Test
void testName {
     //stuff
}

Question 39

how to write a Stack class

Answer 39

class Stack {
     class Node {
          T data;
          Node next;
     }
     Node top;
     public push(T element) {
          Node n = new Node();
          n.data = element;
          n.next = top;
          top = n;
     }
     public T pop() {
          if(top==null) {
               throw new NoSuchElementException();
          }
          T retval = top.data;
          top = top.next;
          return retval;
     }
}

Question 40

Iterators

Answer 40

for Collection classes, we can use a special loop syntax:
MyCollection collection = getCollection();
for(Element e : collection) {
     //do something with e
     S.o.pl(e);
}

the loop body executes once for each element where the loop variable e takes on each value in the collection in succession
with Java collections, an exception is thrown if the collection is modified (however, the Iterator interface has a remove() method that may be implemented if needed)

Question 41

to implement an Iterator

Answer 41

in the Collection: class Foo implements Iterable
must implement the Iterable interface
public Interator iterator();

in the class that implements Iterator: public class FooIterator implements Iterator
public boolean hasNext()
public T next()

Question 42

growth functions

Answer 42

we can estimate the behavior (execution time/memory consumption) of a program (or algorithm) by counting the number of operations (should be important to the performance) performed for a given problem size (the number of elements in a collection, denoted by n); we can relate n (the problem size) to the number of operations using a growth function (e.g. comparisons = 5n+2)

Question 43

Big O Notation

Answer 43

a way of characterizing the asymptotic behavior of the growth function for an algorithm; throw away all constants, except for exponents; keep only the term that grows most quickly with increasing n

Question 44

Big O Notation examples:

a) 5n+2
b) log(n)+n
c) n^2 + 400
d) 17
e) n * log(n)

Answer 44

a) O(n) “linear time”
b) O(n) “linear time”
c) O(n^2) “quadratic time”
d) O(1) “constant time”
e) O(n^2) “quadratic time”
f) O(nlogn) (best sorting algorithms are nlogn)

Question 45

Getting a growth function from code examples:
a) for(i=0; i < n; i++) {
// do something
}
b) for(i=0;  i < 12; i++) {
//do something
}
c) for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
//do something
}
}

Answer 45

a) O(n) because the loop body executes n times
b) O(1) because the loop body executes 12 times no matter what
c) O(n^2) because the outer loop runs n times and the inner loop runs n times

Question 46

Logarithms

Answer 46

log base 2 of x tells how many times we can (recursively) divide x into two halves (e.g. binary search)

Question 47

public void push ( T element )

Answer 47

Node n = new Node();
n.data = element;
n.next = top;
top = n;

Question 48

public T pop ( )

Answer 48

if ( top == null ) {
throw new NoSuchElementException();
}
T retval = top.data;
top = top.next;
return retval;

Question 49

class Node

Answer 49

T data;

Node next;

Question 50

public void add ( E e )

Answer 50

Node n = new Node;
n.element = e;
if ( front == null ) {
front = back = n;
}
else {
back.next = n;
back = n;
}

Question 51

public E remove ( )

Answer 51

if ( front == null ) {
throw new NoSuchElementException();
}
E retval = front.element;
front = front.next;
return retval;

Question 52

Use an iterator to traverse a list and remove any occurrence of the number 5

Answer 52

Iterator < Integer > iter = list.iterator();
while ( iter.hasNext()) {
Integer i = iter.next();
if(i == 5) {
iter.remove;
}
}

Question 53

Write code that prints all the elements in a Bag containing Items

Answer 53

Bag < Item > theBag = foo.getRelevantItems();
for ( Item i : theBag) {
S.o.pl(i);
}

Question 54

public boolean hasNext ( )

Answer 54

if ( next == null) {
return false;
}
else {
return true;
}

Question 55

public E next ( )

Answer 55

if ( hasNext() == false ) {
return null;
}
E retval = next.element;
next = next.next;
return retval;