Sample Quiz

Part 1: Lists and Iterators

 

¢  Write a line of code that will declare a reference variable for an ArrayList and construct an ArrayList with an initial capacity of 100. The name of the ArrayList is theNames and it consists of strings.

 

ArrayList<String> theNames = new ArrayList<String> (100);

 

¢  Assume that the above ArrayList has been created and populated with strings.

Write code that will remove the last element from the list.

 

theNames.remove(theNames.size()-1);

 

Notes:

(1) Size method returns length (number of elements)

(2) size - 1 is index of last element

¢  For the above ArrayList named theNames, write code that will add “Mary” so that it becomes the 5^th element in the ArrayList.

 

theNames.set(4, “Mary”);

 

Notes:

(1) The add method adds to end of list - not what is required here

(2) 4 is the index of the 5th element (since indices start at 0)

¢  Write code, using the java.util.Iterator interface, that will print the elements of the ArrayList named theNames. Assume that the interface has been imported.

 

Iterator<String> iter = theNames.iterator();

while(iter.hasNext())

{

      System.out.println(iter.next());

}

 

¢  Write a line of code that will declare a reference variable for a LinkedList The name of the  variable is linkedNames and it consists of integers.

 

LinkedList<Integer> linkedNames = new LinkedList<Integer>;

 

Order of Algorithms

 

¢  Assume that you have an ordered LinkedList and an ordered ArrayList, indicate the order of the algorithm (Big O notation) below for the indicated operation.

 

Searching

 

LinkedList: ________________________  O(N)

 

ArrayList:  _________________________ O(log N)

 

Insertion/Deletion

 

LinkedList: ________________________  O(1)

 

ArrayList:  _________________________ O(N)

 

Notes:

(1) See the detailed description in the handout I provided

(2) Order of Algorithms is tested on the AP exam

n   The Comparable class is  in Java.lang which is loaded automatically (it does not have to be imported). The following is an example line of code from a lesson where this class is discussed.

 

        If (list.get(inner).compareTo(list.get(inner+1) > 0 ……

 

What is returned by the method compareTo of class Comparable in each of the following scenarios?

 

Ø   inner is less than inner+1: ________________________________ -1    or less than 0

 

Ø   inner equals inner+1:_____________________________________ 0

 

Ø   inner is greater than inner+1:_____________________________ +1    or greater than 0

 

Note:

See description under Strings chapter in the manual

 

Part 2: Sets and Maps

 

¢  Write code that will create a reference to an object of the TreeSet class named myTree, containing strings.

 

Set <String> myTree = new TreeSet<String>( );

 

¢  Write code that will create a reference to an object of the HashSet class named myHash containing integers.

 

Set<Integer> = new HashSet<Integer>( );

 

¢  Write code that will create a reference to an object of the HashMap class named companyMap. The key is of type integer and the value is of type string.

 

HashMap <Integer, String> companyMap = new HashMap<Integer, String>();

 

¢  Write code that will create a reference to an object of the TreeMap class named treeMapping. The key is of type integer and the value is of type string.

 

TreeMap<Integer, String>treeMapping = new TreeMap<Integer, String>( );

 

¢  A ____________________ cannot have duplicate keys.  Map

 

¢  A ___________________ must not have two elements that are equal as specified by an object’s equals method.   Set

 

¢  A situation in which two different items have the same hash key is called a _______________

collision

 

¢  _____________________ binary search trees give good average performance for any data size. Balanced.

 

¢  A _______________________ maintains a correspondence between two sets of objects.  Map

 

¢  The TreeSet class provides an order _________________ run time for the operations of add, remove, and contains. This results from the fact that it uses a balanced binary tree implementation. log n

 

¢  Hashing is order ____________________ for the operations of add, remove, and contains. 1

 

¢  The _____________________ and ______________________ classes both implement binary search trees. TreeSet, TreeMap

 

¢  The TreeMap class provided an order ___________________________ run time for the operations put, get, and containsKey.  log n

 

¢  The _______________________ class implements the Map interface using a hash code into an array.  HashMap

 

¢  The _____________________ class implements the Map interface using a balanced binary search tree ordered by keys.  TreeMap

 

Circle the correct answer for the following 4 multiple-choice questions

 

¢  Assume that variable S is a set. Consider the following code segment

 

for (int k = 0; k < 10; k++)

{

    S.add(new Integer(k));

    for (int m = 1; m < 10; m+=2)

    {

        S.add(new Integer(m)):

    }

}

 

Notes:

(1) Duplicates not allowed with sets

(2) Observe

     Outer Loop (k)        Inner Loop (m)

     0                            1, 3, 5, 7, 9

     1 (duplicate)            no more entries since duplicates not allowed

     2

     3 (duplicate)

     4

     5 (duplicate)

     6

     7 (duplicate)

     8

     9 (duplicate)

 

So, outer loop provides 5 entries and inner loop provides 5 entries for a total of 10

 

¢  If S.size ) returns 0 before the code executes, what does it return after the code segment executes?

 

A. 0

B. 5

C. 10        ANSWER

D. 15

E. 20

 

¢  Suppose that we have a set of strings and we don’t know how it is implemented. If we use the set’s iterator to print the strings in the set, in what order will they be printed?

A. In alphabetical order

B. In reverse alphabetical order

C. In the order in which they were added to the set.

D. In the reverse of the order in which they were added to the set.

E. It is not possible to predict the order in which the strings will be printed.  ANSWER

Notes:

(1) Hashset doe not guarantee any particular order, so the order of the output is unknown

(2) Treeset uses a balanced binary search tree to keep elements in sorted order.

(3) The output, therefore, is not knowable if the implementation is not known

 

¢  Assume that variable M is a map. Consider the following code segment:

 

M.put(“1”, “apple”);

M.put(“2”, “banana”);

M.put(“3”, “orange”);

M.put(“1”, “orange”);

M.put(“2”, “plum”);

M.put(“4”, “banana”);

Notes:

1, apple, orange

2, banana, plum

3, orange

4, banana

 

 

¢  If M is empty before the code segment executes, which of the following best shows what it contains after the code segment executes?

 

A. (1, apple)  (1, orange)  (2, banana)  (2, plum)  (3, orange)  (4, banana)

B. (1, orange)  (2, plum)  (3, orange)  (4, banana)      ANSWER

C. (1, orange)  (2, plum)  (4, banana)

D. (1, apple, orange)  (2, banana, plum)  (3, orange)  (4, banana)

E. (1, 3, apple, orange)  (2, 4, banana, plum)

 

Part 3: Linked Lists

 

Assume that the following method has been added to the standard ListNode class.

public void printList()

{

      System.out.print(value);

      if (next != null)  next.printList();

}

 

¢  Which of the following best characterizes the running time of method printList when it is called for a list containing N nodes?

 

A. O(1)

B. O(log N)

C. O(N)                  ANSWER

D. O(NlogN)

E. O(N²)

 

¢  There are advantages and disadvantages to using a static data structure such as an array and a dynamic data structure such as a linked list. A list of advantages and disadvantages are provided below. In the column by each, indicate whether the statement refers (in general) to a LinkedList or to an ArrayList (place either Linked List  or Array List in the column by the statement as appropriate).

 

Statement	Generally Applies To
Memory is conserved	Linked List
Memory is allocated when program is run	Linked List
Easy to implement and use	ArrayList
Inserting/deleting is slower	ArrayList
Data structure is not random access	Linked List

 

¢  The LinkedList class is based on the ______________________________ data structure.

      Linked List

 

¢  The ArrayList class is based on the ______________________ data structure.  Array

 

¢  The ListNode class is constructed so that the elemens of a list are of type ________________.

Object

 

¢  The constructor for the ListNode class is responsible for creating a node and _________________________________________________________ initializing the two instance variables of a new node.

 

¢  A non-circular singly linked list or a non-circular doubly linked list must end with a _______________ value.  null

 

 

 

Part 4: Binary Search Trees

 

¢  A binary tree of characters is shown below.  Indicate the output that would be produced by each of the 3 traversals shown if visiting a node means printing its value.

 

Code for preorder traversal void preorder(Treenode temp) {     if (temp != null)     {          System.out.println(temp.getValue());          inorder (temp.getLeft());         preorder (temp.getRight());     }  }

Code for inorder traversal void inorder(Treenode temp) {     if (temp != null)                                        {          inorder (temp.getLeft());                                     System.out.println(temp.getValue());                  inorder (temp.getRight());                              }  }

Code for postorder traversal void postorder(Treenode temp) {     if (temp != null)     {          postorder (temp.getLeft());         System.out.println(temp.getValue());         postorder (temp.getRight());     }  }

 

 

Preorder traversal:______________________________________  a b d e g c f h i

 

Inorder traversal:  ______________________________________  d b g e a c h f i

 

Postorder traversal: ____________________________________  d g e b h I f c a

 

¢ Using the tree shown above, list the nodes (indicated by characters) that are defined as the following:

 

    Ø root:  a

 

    Ø leaf:  d, g, h, i

 

    Ø parent: a, b, c, d, e, f

 

    Ø child: b, c, d, e, f, g, h, i

 

¢ Using the tree shown above, what is the level of the node indicated by d?  2

 

¢ Using the tree shown above, the arrows connecting two nodes are referred to as _____________ edges

 

¢ The height of the above tree is _______________ 4

 

¢ The width of the above binary tree is 7

 

 

¢ Assume that you are reading from a file of integers that contains the following (10 is the first integer read and the remaining are read consecutively: 10  8  3  4  9  2  30  35. Draw the resulting binary search tree.

 

 

 

Part 5: Various

 

Circle the correct answer for the following multiple-choice questions

 

¢  Each item in a ___________ collection has a unique predecessor, except for the first item, and a unique successor, except for the last item.

 

a.	linear              ANSWER	c.	graph
b.	hierarchical	d.	unordered

 

 

¢  In which collection can an element have many predecessors and many successors?

 

a.	linear	c.	graph        ANSWER
b.	hierarchical	d.	unordered

 

 

¢  Which operation on a collection visits each item?

 

a.	cloning	c.	removal
b.	traversal    ANSWER	d.	search and retrieval

 

¢  Collections  are called:

 

a.	data stores	c.	lists
b.	databases	d.	abstract data types   ANSWER

 

¢  We use _____________ as a technique for ignoring or hiding details that are, for the moment, not essential.

 

a.	abstraction    ANSWER	c.	classes
b.	information hiding	d.	collections

 

 

¢  Which of the following positions is an iterator initially upon instantiation?

 

a.	null, no position	c.	Between two adjacent items
b.	Just before the first item ANSWER	d.	At the first item

 

¢  Which of the following methods is NOT a method in the Iterator class?

 

a.	hasNext()	c.	hasPrevious()   ANSWER
b.	next()	d.	remove()

 

  

¢  What does an interface contain?

 

a.	method headers  ANSWER	c.	method implementation
b.	private variables	d.	both a & c

 

 

¢  How do you add an item to one-D array if it is full?

 

a.	just add it, the JVM will automatically make it larger
b.	move the existing array elements to a larger array     ANSWER
c.	cannot be done
d.	redeclare the existing array to hold move values

 

    Accessing one-D array elements has a run-time complexity of:

 

a.	O( n )	c.	O( log n )
b.	O( n log n )	d.	O( 1 )    ANSWER

 

 

¢  To find the value of a node in a linked list we only need to know its index.     _____True  False_____        FALSE

 

¢  If we can accurately predict the maximum size of a list and do not expect it to vary then the linked implementation has the advantage in memory usage and run-time complexity.     

         _____True  False_____   FALSE (Array has advantage in this situation)

 

 

 

¢  Indicate whether the following statements are true or false by placing a check mark (√) in the appropriate column.

Statement	True			False
When searching for an item, regardless of the data, a binary search will always be faster than a sequential search.			ü
In an abstract class, some methods and constructors may be fully defined.		ü
You cannot create an object of an abstract class.		ü
You cannot declare a variable whose type is given by an interface.			ü
Instantiating an array of objects reserves room to store references only.		ü
A class can implement any number of interfaces, limited only by memory		ü
An object implements an interface if it belongs to a class that implements the interface.		ü
If a class implements multiple interfaces it cannot extend another class.			ü
A recursive mergesort will keep dividing the list in half until the sublists are one or two values in length.		ü
The order or recursive mergesort is O(NLog2N) or O(NLogN).		ü
The quicksort algorithm is the same order as the mergesort algorithm.		ü
The order of a binary search is O(LogN).		ü
The non-recursive version of the binary search algorithm requires less memory and fewer steps than the recursive version.		ü
In order to intelligently use the binary search, the values in the array must be sorted.		ü

 

¢  At the beginning of the study of collections, a “big picture” was presented. At that time I discussed 4 general types of collections – 2 of which are covered in the AP and 2 of which are not.  List those 4 general types of collections below. Place a check mark (ü ) by the two that are covered (tested).

 

    Ø   ________________________________________  Linear  ü

 

    Ø   ________________________________________  Hierarchical  ü

 

    Ø   ________________________________________  Graph

 

    Ø   ________________________________________  Unordered

 

¢  In the A portion of the course, 3 quadratic sorting algorithms were covere. Provide the names of these algorithms below.

 

    Ø   ________________________________________  Bubble

 

    Ø   ________________________________________  Selection

 

    Ø   ________________________________________  Insertion

 

 

¢  What is the output of the following code?

 

    public class Recursion

    {

      public static void main(String[] args)

      {

            int valuePassed = 4;

            myMethod(valuePassed);

      }

      static void myMethod( int counter)

      {

            if(counter == 0)

                   return;

            else

             {

                  System.out.println(counter);

                  counter = counter -1;

                  myMethod(counter);

                  return;

             }

      }

}

 

4

3

2

1

¢  What does it mean to say that the order of an algorithm is quadratic? (answer must be specific)

            The number of steps or run time goes as N squared. For example, if the number of steps for N = 4 is 16, then the number of steps

            for N = 5 is 25.

 ¢  What does log₂N mean? (answer must be specific – give an example.

               In general, the power to which a base, such as 2, must be raised to produce a given number. If n^x = a, the logarithm of a, with n as the

               base, is x; symbolically, log_n a = x.

               Specifically, the power to which 2 must be raised to equal N.

               log₂4 = 2  and    log₂8 = 3

 

                Note: Compare this with the quadratic above