Introduction to Java Programming, Sixth Edition, Y. Daniel Liang
Chapter 20 Lists, Stacks, Queues, Trees, and Heaps
Section 20.2 Lists
1
________ is a data structure to store data in sequential order.
A.
A list
B.
A set
C.
A tree
D.
A stack
E.
A queue
2
Which of the following operations are supported by a list?
A.
Retrieve an element from this list.
B.
Insert a new element to this list.
C.
Delete an element from this list.
D.
Find how many elements are in this list.
E.
Find whether an element is in this list.
3
MyArrayList, MyLinkedList, MyAbstractList, and MyList are defined in Chapter 20. Which of the following statements are true?
A.
MyArrayList and MyLinkedList are two concrete implementations of MyList.
B.
MyArrayList is implemented using an array. The array is dynamically created. If the capacity of the array is exceeded, create a new larger array and copy all the elements from the current array to the new array.
C.
MyLinkedList is implemented using a linked structure.
D.
A linked structure consists of nodes. Each node is dynamically created to hold an element. All the nodes are linked together to form a list.
E.
MyAbstractList partially implements MyList.
4
In the implementation of MyArrayList, which of the following are true?
A.
size indicates the number of elements in the list.
B.
capacity is the length of the array used to store the elements in the list.
C.
capacity is always greater than size.
D.
size is reduced by 1 if an element is deleted from the list.
E.
capacity is reduced by 1 if an element is deleted from the list.
5
In the implementation of MyArrayList, which of the following are true?
A.
size never reduces.
B.
capacity never reduces.
C.
Inside MyArrayList, a regular array is used to store elements.
D.
size is not declared in MyArrayList, but declared in MyAbstractList as protected.
E.
If the current capacity equals to size, capacity is doubled when a new element is added to MyArrayList
6
In the implementation of MyLinkedList, which of the following are true?
A.
MyLinkedList contians all the methods defined in MyList. Additionally, MyLinkedList defines several new methods that are appropriate for processing a linked list.
B.
MyArrayList does not introduce new methods. All the methods in MyArrayList are defined in MyList.
C.
You can use a linked list to improve efficiency for adding and remove an element anywhere in a list.
D.
You should use an array list if your application does not require adding and remove an element anywhere in a list.
7
In the implementation of MyLinkedList, which of the following are true?
A.
Node is defined as an inner class inside MyLinkedList.
B.
Node is defined as a static inner class inside MyLinkedList because it does not reference any instance data fields in MyLinkedList.
C.
Node has a property named next that links to the node after this node.
D.
Node has a property named element that stores an element.
8
In the implementation of MyLinkedList, which of the following are true?
A.
MyLinkedList has a capacity property.
B.
MyLinkedList has the properties named first and last to point to the nodes in a linked list.
C.
If a linked list is empty, first is null and last is null.
D.
If a linked list contains one element, first points to the node and last is null.
E.
last.next is always null.
Section 20.3 Stacks and Queues
9
Which of the following are true?
A.
A stack can be viewed as a special type of list, where the elements are accessed, inserted, and deleted only from the end, called the top, of the stack.
B.
A queue represents a waiting list. A queue can be viewed as a special type of list, where the elements are inserted into the end (tail) of the queue, and are accessed and deleted from the beginning (head) of the queue.
C.
Since the insertion and deletion operations on a stack are made only at the end of the stack, using an array list to implement a stack is more efficient than a linked list.
D.
Since deletions are made at the beginning of the list, it is more efficient to implement a queue using a linked list than an array list.
10
In the implementation of MyStack and MyQueue, which of the following are true?
A.
MyStack contains all the methods defined in MyArrayList.
B.
MyQueue contains all the methods defined in MyLinkedList.
C.
MyStack contains an array list for storing elements.
D.
MyQueue contains a linked list for storing elements.
Section 20.4 Binary Trees
11
A __________ (with no duplicate elements) has the property that for every node in the tree the value of any node in its left subtree is less than the value of the node and the value of any node in its right subtree is greater than the value of the node.
A.
binary tree
B.
binary search tree
C.
list
D.
linked list
12
In the implementation of BinaryTree, which of the following are true?
A.
Node is defined as an inner class inside BinaryTree.
B.
Node is defined as a static inner class inside BinaryTree because it does not reference any instance data fields in BinaryTree.
C.
Node has a property named left that links to the left subtree and a property named right that links to the right subtree and a property named right
D.
BinaryTree contains a property named root. If tree is empty, root is null.
13
The ________ is to visit the left subtree of the current node first, then the current node itself, and finally the right subtree of the current node.
A.
inorder traversal
B.
preorder traversal
C.
postorder traversal
D.
breadth-first traversal
14
The _________ is to visit the left subtree of the current node first, then the right subtree of the current node, and finally the current node itself.
A.
inorder traversal
B.
preorder traversal
C.
postorder traversal
D.
breadth-first traversal
15
The _________ is to visit the current node first, then the left subtree of the current node, and finally the right subtree of the current node.
A.
inorder traversal
B.
preorder traversal
C.
postorder traversal
D.
breadth-first traversal
16
The _________ is to visit the nodes level by level. First visit the root, then all children of the root from left to right, then grandchildren of the root from left to right, and so on.
A.
inorder traversal
B.
preorder traversal
C.
postorder traversal
D.
breadth-first traversal
Section 20.5 Heaps
17
Which of the following statements are true?
A.
A heap is a complete binary tree.
B.
Each node is greater than or equal to any of its children.
C.
A binary tree is complete if every level of the tree is full except that the last level may not be full and all the leaves on the last level are placed left-most.
D.
A heap is a full binary tree.
18
To remove the root, you need to start a process by first placing _______ to the place of the root and move it down to maintain the heap property.
A.
one of the root's children
B.
the larger child of the root
C.
the smaller child of the root
D.
the last node in the heap
19
To add a new node, you need to start a process by first placing it as _______ and move it up to main the heap property.
A.
the new root
B.
the last node in the heap
C.
the left child of the root
D.
the right child of the root
Section 20.6 Priority Queues
20
Which data structure is appropriate to store patients in an emergency room?
A.
Stack
B.
Queue
C.
Priority Queue
D.
Linked List
21
Which data structure is appropriate to store customers in a clinic for taking flu shots?
A.
Stack
B.
Queue
C.
Priority Queue
D.
Array List
E.
Linked List
22
Suppose the rule of the party is that the participants who arrive later will leave earlier. Which data structure is appropriate to store the participants?
A.
Stack
B.
Queue
C.
Array List
D.
Linked List