Java Software Solutions, 8e, Global Edition (Lewis/Loftus)
Chapter 13 Collections
13.1 Multiple-Choice Questions
1) An array can be classified as what type of object?
A) dynamic
B) ordered
C) first-in first-out
D) heterogeneous
E) collection
2) 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
3) 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
4) 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
5) 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
6) 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;
}
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
4
© Pearson Education Limited, 2015
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.
8) 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;
9) 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)
10) 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
11) 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;
12) 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
6
© Pearson Education Limited, 2015
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.
13) 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;
}
8
14) 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;
}
9
© Pearson Education Limited, 2015
Answer: 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.
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.
15) What will be returned by return head.next.next.next.info; ?
A) 20
B) 11
C) 13
D) 19
E) 12
16) What is returned by return head.info; ?
A) 20
B) 11
C) 13
D) 19
E) 6
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
18) 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
19) 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
20) 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
11
21) 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
22) 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
23) 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++) { … }
24) 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
25) To simulate people waiting in a line, which data structure would you use?
A) Vector
B) Queue
C) Stack
D) Set
E) List
26) 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
13
© Pearson Education Limited, 2015
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);
27) After the code above executes, how many elements would remain in q?
A) 0
B) 4
C) 5
D) 6
E) 7
28) 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