Deck 13: Collections

Question 1

Abstract Data Types have which of the following object-oriented features?

A) information hiding
B) inheritance
C) polymorphism
D) message passing
E) All of these

Answer 1

C

Question 2

A collection where the items stored there are of different types is referred to as a(n) ________ type.

A) homogeneous
B) heterogeneous
C) dynamic
D) abstract
E) vector

Answer 2

B

Question 3

All classes are considered Abstract Data Types.

Answer 3

False

Question 4

All Abstract Data Types are defined as classes in Java.

Question 5

Generics provide a mechanism for ensuring that collections are heterogeneous rather than homogeneous.

Question 6

The only difference between a stack and a queue is that stacks operate using FIFO and queues operate using LIFO.

Question 7

Which of the following criticisms of an array is applicable to a Java array?

A) It is an inefficient structure to access random elements.
B) It only supports first-in first-out types of accesses.
C) It is fixed in size (static).
D) It cannot be used to create an Abstract Data Type such as a queue or stack.
E) All of these

Question 8

An array can be classified as what type of object?

A) dynamic
B) ordered
C) first-in first-out
D) heterogeneous
E) collection

Question 9

A bi-directional list is an example of a non-linear data structure.

Question 10

It is possible to restrict the type of object which is stored within a Java collection by using a generic type when the collection is declared.

Question 11

Queues and stacks can be implemented using either arrays or linked lists.

Question 12

A linked list that contains six Nodes will have six reference pointers.

Question 13

The linked list is superior in all ways to the array when it comes to implementing a list.

Question 14

Which of the following is considered an Abstract Data Type?

A) array
B) reference variable
C) any of the primitive types
D) vector
E) All of these

Question 15

The push and enqueue operations are essentially the same operations. push is used for stacks and enqueue is used for queues.

Question 16

Trees and graphs, because they are dynamic in nature, cannot be implemented using Java arrays.

Question 17

An array is a list ADT.

Question 18

An Abstract Data Type is a data structure; that is, it is the listing of the instance data and the visibility modifiers for those instance data.

Question 19

The Abstract Data Type (ADT) is thought of as abstract because the operations that are to be implemented are separated from the actual implementation; that is, an ADT can be implemented in more than one way and that implementation is separate from how we might use the ADT.

Question 20

In order to input a list of values and output them in order, you could use a queue. In order to input a list of values and output them in opposite order, you could use a stack.

Question 21

Which of the following is used to see the top item of a stack without removing it from the stack?

A) push
B) pop
C) peak
D) see
E) top

Question 22

Example Code Ch 13-4
Assume that a linked list consists of Node objects, where Node has two instance data, int info and Node next. The linked list stores in the info data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list.
Refer to Example Code Ch 13-4: What is the result to the linked list of the following instructions? Assume that newNode is a Node, already constructed. newNode.data = 1;
NewNode.next = head.next;
Head.next = newNode;

A) The value 1 is inserted into the linked list before 20.
B) The value 1 is inserted into the linked list after 20 and before 11.
C) The value 1 is inserted into the linked list after 11 and before 13.
D) The value 1 is inserted into the linked list after 13 and before 19.
E) The value 1 is inserted into the linked list after 20 and the rest of the list is lost.

Question 23

What type of structure should be used to gain a last-in first-out access to data?

A) a vector
B) an array
C) a linked list
D) a queue
E) a stack

Question 24

A variation of a linked list is a circular linked list where the last Node in the list has next = head rather than next = null. One problem with this type of list is that

A) it wastes memory space since head already points at the first Node, so the last one does not need to
B) there is no ability to add a new Node at the end of the list since the last Node points at the first Node
C) it is more difficult to traverse the list since the old terminating condition, (next == null), is no longer true for the last node
D) a header Node for this type of list is more complex
E) All of these

Question 25

A linear data structure

A) always has more than one link per node
B) is sometimes represented as a tree or a graph
C) can have only a single link per node
D) almost always is kept in sorted order, either ascending or descending
E) None of these

Question 26

Example Code Ch 13-2
Assume that a linked list is implemented using the Node class where a Node contains instance data of int info; and Node next; where next references the next Node in the linked list. Also assume that head references the first Node in the list.
Refer to Example Code Ch 13-2: Which of the following instructions would create an initially empty linked list?

A) Node head = new Node();
B) Node head = Node
C) Node head = null;
D) Node head = new Node(0);
E) Node head = list;

Question 27

Example Code Ch 13-2
Assume that a linked list is implemented using the Node class where a Node contains instance data of int info; and Node next; where next references the next Node in the linked list. Also assume that head references the first Node in the list.
Refer to Example Code Ch 13-2: Assume Node temp references the last element of the linked list. Which of the following conditions is true about temp?

A) (temp.info == 0)
B) (temp.next == null)
C) (temp == head)
D) (temp == null)
E) (temp.next == null && temp.info == null)

Question 28

Example Code Ch 13-2
Assume that a linked list is implemented using the Node class where a Node contains instance data of int info; and Node next; where next references the next Node in the linked list. Also assume that head references the first Node in the list.
Refer to Example Code Ch 13-2: Assume Node2 is defined as follows: int data; Node2 a, b; where a refers to the Node2 before this one in a linked list and b refers to the Node2 after this one in a linked list. Node2 could then be used to create which of the following variations of a linked list?

A) singly linked list
B) doubly linked list
C) singly linked list with a header node
D) singly linked list with a top node
E) circularly linked list

Question 29

Example Code Ch 13-4
Assume that a linked list consists of Node objects, where Node has two instance data, int info and Node next. The linked list stores in the info data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list.
Refer to Example Code Ch 13-4: What will be returned by the following? return head.info;

A) 20
B) 11
C) 13
D) 19
E) 12

Question 30

Example Code Ch 13-4
Assume that a linked list consists of Node objects, where Node has two instance data, int info and Node next. The linked list stores in the info data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list.
Refer to Example Code Ch 13-4: What will the following statement accomplish? head.next.next = head.next.next.next;

A) It will result in the list ending after 13.
B) It will result in the value 13 being deleted from the list.
C) It will result in the list ending after 19.
D) It will result in the value 19 being deleted from the list.
E) It will result in the list ending after 12.

Question 31

In a linked list in Java

A) the link is an object
B) the link is a node
C) the link is a reference
D) the link is an int
E) the link is a class

Question 32

Example Code Ch 13-3
Assume that countIt and sumIt methods receive a parameter, Node temp, which references the first Node in a linked list where Node is a class that consists of data instances int info and Node next, and further assume that the int variables count and sum are initialized to 0.
Refer to Example Code Ch 13-3: Which of the following methods could be used to count the number of items in the linked list?

A) public int countIt(Node temp)
{
While (temp != null)
{
Count += temp.info;
Temp = temp.next;
}
Return count;
}
B) public int countIt(Node temp)
{
While (temp != null)
{
Count++;
}
Return count;
}
C) public int countIt(Node temp)
{
While (count != null)
{
Count++;
Temp = temp.next;
}
Return count;
}
D) public int countIt(Node temp)
{
While (temp != head)
{
Count++;
Temp = temp.next;
}
Return count;
}
E) public int countIt(Node temp)
{
While (temp != null)
{
If (next != null) count++;
Temp = temp.next;
}
Return count;
}

Question 33

Example Code Ch 13-2
Assume that a linked list is implemented using the Node class where a Node contains instance data of int info; and Node next; where next references the next Node in the linked list. Also assume that head references the first Node in the list.
Refer to Example Code Ch 13-2: Assume that the linked list has at least two Nodes in it. Which of the following instructions will return the second int value in the list?

A) return head.info;
B) return head.next.info;
C) return head.next.next.info;
D) return head.next.next.next.info;
E) It is not possible to return the second int value in the list using head.

Question 34

Example Code Ch 13-2
Assume that a linked list is implemented using the Node class where a Node contains instance data of int info; and Node next; where next references the next Node in the linked list. Also assume that head references the first Node in the list.
Refer to Example Code Ch 13-2: Assume Node temp is currently set equal to head. Which of the following while loops could be used to iterate through each element of a linked list?

A) while (head != null)
Head = temp.next;
B) while (temp != null)
Temp = temp.next;
C) while (head != null)
Temp = temp.next;
D) while (head != null)
Head = head.next;
E) while (temp != null)
Head = head.next;

Question 35

To simulate people waiting in a line, which data structure would you use?

A) a vector
B) a set
C) a list
D) a queue
E) a stack

Question 36

Example Code Ch 13-3
Assume that countIt and sumIt methods receive a parameter, Node temp, which references the first Node in a linked list where Node is a class that consists of data instances int info and Node next, and further assume that the int variables count and sum are initialized to 0.
Refer to Example Code Ch 13-3: Which of the following methods could be used to sum the number of items in the linked list?

A) public int sumIt(Node temp)
{
While (temp != null)
{
Sum += temp.info;
Temp = temp.next;
}
Return sum;
}
B) public int sumIt(Node temp)
{
While (temp != null)
{
Sum += temp.info;
}
Return sum;
}
C) public int sumIt(Node temp)
{
While (temp != null)
{
Sum++;
Temp = temp.next;
}
Return sum;
}
D) public int sumIt(Node temp)
{
While (temp != head)
{
Sum += temp.info;
Temp = temp.next;
}
Return sum;
}
E) public int sumIt(Node temp)
{
While (temp != null)
{
If (next != null) sum += temp.info;
Temp = temp.next;
}
Return sum;
}

Question 37

Example Code Ch 13-4
Assume that a linked list consists of Node objects, where Node has two instance data, int info and Node next. The linked list stores in the info data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list.
Refer to Example Code Ch 13-4: What will be returned by the following? return head.next.next.next.info;

A) 20
B) 11
C) 13
D) 19
E) 12

Question 38

A linked list that stores int values would be comprised of a group of Nodes. We might define the Node by

A) class Node
{
Node next;
}
B) class Node
{
Int next;
}
C) class Node
{
Int data;
}
D) class Node
{
Int data;
Node next;
}
E) class Node
{
Int[ ] data;
Node next;
}

Question 39

One operation that we might want to implement on a stack and a queue is full, which determines if the data structure has room for another item to be added. This operation would be useful

A) only if the queue or stack is implemented using an array
B) only if the queue or stack is implemented using a linked list
C) only for a queue
D) only for a stack
E) None of these; a full operation is not useful at all

Question 40

The advantage of creating a BookList for a list of books using a linked list instead of using an array is that the linked list

A) offers easier access to a random element in the list
B) uses less memory
C) is easier to implement and debug
D) can store types other than Books, unlike the array
E) is dynamic and so can be any size needed

Question 41

Two abstract data types are the ordered list and the unordered list. Explain how these two ADTs are similar and how they differ. To answer this question, assume that you do not know how they are implemented (that is, whether they are implemented using an array or a linked list).

Question 42

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
Refer to Example Code Ch 13-5: What value is returned by the last dequeue operation, denoted with a d3 as a comment.

A) 3
B) 5
C) 9
D) 2
E) 4

Question 43

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Refer to Example Code Ch 13-1: Assume that head references a linked list and stores in order, the int values 3, 6 and 2. Show the instructions needed to delete the Node with 3 so that head would reference the list 6 and 2.

Question 44

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
Refer to Example Code Ch 13-5: After this code executes, how many elements would remain in q?

A) 0
B) 4
C) 5
D) 6
E) 7

Question 45

What is an ADT (Abstract Data Type) and why are ADTs considered to be abstract?

Question 46

A double-ended queue, called a dequeue, is a queue that, instead of having single links in one direction, has a pair of links, one pointed in each direction. Dequeues allow one to "push" and "pop" information at either end. Is this ADT the same or different from a doubly linked list, as described in the textbook?

Question 47

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Refer to Example Code Ch 13-1: Show the instructions required to create a linked list that is referenced by head and stores in order, the int values 3, 6 and 2. Assume that Node's constructor receives no parameters.

Question 48

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Refer to Example Code Ch 13-1: Assume that head references a linked list and stores in order, the int values 3, 2 and 6. Show the instructions needed to move the value 2 in front of the value 6 so that the list is now 3, 2 and 6.

Question 49

A simple linear list

A) is an example of a degenerate tree
B) is an example of a degenerate graph
C) is an example of a degenerate digraph
D) cannot be represented as a degenerate tree, graph, or digraph
E) None of these

Question 50

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Refer to Example Code Ch 13-1: Assume that head references a linked list, although we don't know what is currently stored in that list. Write a block of code using a try-catch block that will work through the entire linked list, printing each element out, stopping only when we have reached the end of the list because a NullPointerException is thrown. Once the Exception is thrown, output the number of elements found in the list.

Question 51

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
Refer to Example Code Ch 13-5: If we replace the System.out.println statements (denoted in comments as d1, d2 and d3) with the statement q.enqueue(q.dequeue()); q would contain which order of int values after all instructions have executed?

A) 3, 5, 9, 2, 4, 1, 8
B) 3, 5, 9, 1, 8, 2, 4
C) 5, 9, 2, 4, 1, 8, 3
D) 3, 2, 4, 5, 9, 1, 8
E) 2, 4, 1, 8, 3, 5, 9

Question 52

Example Code Ch 13-6
Assume a stack class stores int values. Consider the following sequence of instructions.
Stack s = new Stack();
s.push(16);
s.push(12);
s.push(19);
int x = s.pop();
s.push(5);
s.push(9);
s.push(4);
int y = s.pop();
int z = s.pop();
Refer to Example Code Ch 13-6: After the instructions execute, x has the value

A) 16
B) 12
C) 19
D) 0
E) None of these; the instruction int x = s.pop() results in an exception being thrown

Question 53

Challenge: Assume a function g(x) is defined as follows where x is an int parameter:
g(x) = g(x - 1) * g (x - 3) if x is even and x > 3
= g(x - 2) if x is odd and x > 3
= x otherwise
Write a recursive method to compute
g. In implementing a queue using an array, a problem might arise if the queue is implemented in such a way that items in the queue are inserted at the next available location and removed from the next leading position, but such that, once deleted, the emptied space is unused. The problem that arises is one where there is free space still in the array, but it is not usable because it is not at the end. Demonstrate this problem with a queue that is stored in an array of size 5 for the following instructions. Next, explain how you might resolve this problem.
Queue q = new Queue(5); // assume the Queue constructor
takes 5 as the size of the array
q.enqueue(3);
q.enqueue(4);
q.enqueue(1);
q.dequeue();
q.dequeue();
q.enqueue(6);
q.enqueue(5);
q.dequeue(); // at this point, there are only 2 items
in the queue
q.enqueue(7); // this enqueue can not occur, why??

Question 54

What common exception(s) might arise when using an array? What common exception(s) might arise when using a linked list?

Question 55

A queue q stores int values. Show what q will look like after each of the following instructions is executed.
q.enqueue(6);
q.enqueue(12);
q.enqueue(13);
q.dequeue();
q.dequeue();
q.enqueue(19);
q.enqueue(21);
q.enqueue(22);
q.dequeue();
q.enqueue(20);

Question 56

An abstract data type not covered in detail in the chapter is the Set ADT. A Set is like a set as covered in Mathematics courses. For instance, a set of even numbers might be {2, 4, 8, 12, 18, 32}. List 6 operations that you might implement for a Set ADT.

Question 57

A dynamic data structure

A) almost always is implemented using lists of one sort or another
B) is just a collection
C) almost always is implemented using references (pointers) to objects
D) can have a fixed size
E) None of these

Question 58

One use of a stack is to reverse the order of input. Write a method that reads a series of Strings from the keyboard (assume the Scanner class has been imported) and outputs the Strings in reverse order of how they were entered. The input will end with the String "end" but do not output the String "end". Assume that SStack is a stack that can store Strings. Remember to declare and instantiate your SStack in your method.

Question 59

A stack s stores int values. Show what s will look like after each of the following instructions is executed.
s.push(5);
s.push(1);
s.push(4);
s.push(3);
s.pop();
s.push(2);
s.pop();
s.pop();
s.push(8);
s.push(7);
s.pop();
s.push(3);

Question 60

Example Code Ch 13-6
Assume a stack class stores int values. Consider the following sequence of instructions.
Stack s = new Stack();
s.push(16);
s.push(12);
s.push(19);
int x = s.pop();
s.push(5);
s.push(9);
s.push(4);
int y = s.pop();
int z = s.pop();
Refer to Example Code Ch 13-6: After the instructions execute, z has the value

A) 4
B) 9
C) 5
D) 12
E) 16