Deck 13: Collections

Question 1

An array can be classified as what type of object?

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

Answer 1

E
Explanation: E) An array stores a group of items and is dubbed a collection type (as opposed to other types that can store a single item). There are numerous collection types, the array being one composed only of homogeneous items (the array stores multiple items but they all must be of the same type).

Question 2

Assume that the countIt and sumIt methods in the questions below 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.
Which of the following methods could be used to sum all of the 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;
}

Answer 2

A
Explanation: A) Answer B does not advance temp to reference the next Node, and is therefore an infinite loop. Answer C counts the number of items in the list but does not sum up the values of these items. Answer D has the wrong loop condition and answer E counts all of the items in the list except for the last one.

Question 3

For the questions below, 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 list.
What will be returned by return head.next.next.next.info; ?

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

Answer 3

D
Explanation: D) The variable head references the first item, which stores 20, head.next references the second item, which stores 11, head.next.next references the third item, which stores 13, and head.next.next.next references the fourth item, which stores 19.

Question 4

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 5

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 the above

Question 6

For the questions below, 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 list.
What is returned by return head.info; ?

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

Question 7

The advantage of creating a BookList 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 8

For the questions below, 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.
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 9

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

A) information hiding
B) inheritance
C) polymorphism
D) message passing
E) all of the above

Question 10

Assume that the countIt and sumIt methods in the questions below 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.
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 11

For the questions below, 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.
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 12

For the questions below, 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.
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 13

What will the statement head.next.next = head.next.next.next; accomplish?

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 14

A collection in 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

Question 15

Which of the following lists of commands 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 16

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 the above

Question 17

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 18

Which of the following is considered an Abstract Data Type?

A) array
B) reference variable
C) any of the primitive types (e.g., int, double, char)
D) vector
E) all of the above

Question 19

For the questions below, 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.
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 20

For the questions below, 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.
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 21

For the questions below, assume Node is a class consisting of an int info and a Node next and header is a HeaderNode that has Node front, rear and int count where front references the first item in the list, rear references the last item in the list and count is the number of elements in the list.
To simulate people waiting in a line, which data structure would you use?

A) Vector
B) Queue
C) Stack
D) Set
E) List

Question 22

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

Question 23

For the questions below, 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( );
After the instructions execute, z has the value

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

Question 24

For the questions below, assume Node is a class consisting of an int info and a Node next and header is a HeaderNode that has Node front, rear and int count where front references the first item in the list, rear references the last item in the list and count is the number of elements in the list.
Previously, to iterate through a linked list, we used a while loop. Which of the following for-loops could replace the previous while loop that would start at head and go until temp == null?

A) for (Node temp = header.front, int j = 0; j < header.count; temp = temp.next) { ... }
B) for (int j = 0; j < header.count; j++) { ... }
C) for (Node temp = header.front; temp != header.rear; temp = temp.next) { ... }
D) for (Node temp = header.front, int j = 0; j < header.count; temp = temp.next, j++) { ...}
E) for (Node temp = header.front, int j = 0; j < header.count && temp != header.rear; temp = temp.next, j++) { ... }

Question 25

For the questions below, 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);
What value is returned by the last dequeue operation (denoted above with a d3 in comments)?

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

Question 26

For the questions below, 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);
After the code above executes, how many elements would remain in q?

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

Question 27

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 the above

Question 28

For the questions below, 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);
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 29

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 the above, a full operation is not useful at all

Question 30

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 but a single link per node
D) almost always is kept in sorted order either ascending or descending
E) none of the above

Question 31

In order to gain a last-in first-out access to data, which type of structure should be used?

A) Vector
B) Array
C) Linked List
D) Queue
E) Stack

Question 32

For the questions below, 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( );
After the instructions execute, x has the value

A) 16
B) 12
C) 19
D) 0
E) none of the above, the instruction int x = s.pop( ) results in an Exception being thrown

Question 33

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 34

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 the above

Question 35

An array is a List Abstract Data Type.

Question 36

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 37

For the questions below, assume Node is a class consisting of an int info and a Node next and header is a HeaderNode that has Node front, rear and int count where front references the first item in the list, rear references the last item in the list and count is the number of elements in the list.
The expression LIFO stands for

A) LIst FOundation
B) LInk FOrmation
C) Last In Front Of
D) Last In First Out
E) Long Int Float Object

Question 38

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 39

For the questions below, assume Node is a class consisting of an int info and a Node next and header is a HeaderNode that has Node front, rear and int count where front references the first item in the list, rear references the last item in the list and count is the number of elements in the list.
This type of linked list is referred to as a

A) singly linked list
B) doubly linked list
C) singly linked list with a header node
D) doubly linked list with a header node
E) singly linked list with a head and rear references

Question 40

The push and enqueue operations are essentially the same operations, push is used for Stacks and enqueue is used for Queues.

Question 41

For the next questions, use the following class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Assume that head references a linked list that stores the values 3, 6 and 2. Show the instructions needed to delete the Node with 3 from the list so that head would reference the list of 6 and 2.

Question 42

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 43

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

Question 44

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

Question 45

What changes would have to be made to the BookNode class in order to define it as its own class outside of BookList?

Question 46

For the next questions, use the following class definition of a linked list Node:
class Node
{
int info;
Node next;
}
Assume that head references a linked list that stores the values 3, 6 and 2 in that order. Show the instructions needed to move the value 2 in front of the value 6 (so that the list is now 3, 2, 6).

Question 47

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 48

Rather than defining BookNode inside of BookList, another option is to define BookNode as a separate class and import it into BookList. Why might we do this rather than define BookNode inside of BookList?

Question 49

Draw this structure.

Question 50

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

Question 51

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

Question 52

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

Question 53

For the next questions, use the following class definition of a linked list Node:
class Node
{
int info;
Node next;
}
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 54

For the next questions, use the following class definition of a linked list Node:
class Node
{
int info;
Node next;
}
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 55

All classes are considered Abstract Data Types.

Question 56

What changes would have to be made to the BookList class in order to properly use the separate BookNode class?

Question 57

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 58

All Abstract Data Types are defined as classes in Java.

Question 59

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

Question 60

Assume that DoubleNode temp references the node with the value 3. Provide code to delete this DoubleNode without disconnecting the rest of the list.

Question 61

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

Question 62

A Stack s stores int values. Show what s will look like after each of the following instructions is executed.

Question 63

An abstract data type not covered in detail in the chapter is the Set ADT. A Set is like a set as covered in your 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 64

(Challenger Problem) 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 item2 in the queue
q.enqueue(7); // this enqueue can not occur, why?
?

Question 65

Two abstract data types are the ordered list and the unordered list. Explain how these two ADTs are similar and how they will 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 66

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

Question 67

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 allows 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 68

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.