QUESTION 1

In a queue implementation that uses an array of fixed size,

the array must be made so large that the queue will never run out of space

it is necessary to use the array as a circular buffer

the array must be created from an ArrayList object

the queue must implement the List interface

QUESTION 2

The operation for removing an item from a queue is called

enqueue

dequeue

extract

disqueue

QUESTION 3

The stack pull operation

increases the capacity of a stack that is about to fill up

extracts one element from the stack and returns it

brings two stacks together and combines their elements

does not exist: There is no such stack operation

QUESTION 4

The stack empty operation

removes all elements from the stack

checks to see if there is at least one item on the stack

destroys the stack and creates a new empty one in its place

All of these are true

None of these are true

QUESTION 5

A binary tree traversal method that recursively traverses the left subtree, then visits the root, then traverses the right subtree is called

root-centric traversal

priority order traversal

postorder traversal

inorder traversal

QUESTION 6

A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0], and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes. If nodes in the same level are stored in left to right order, then the right child of the node stored at A[k] will be stored at

A[k/2]

A[2k]

A[2k+1]

A[2k+2]

QUESTION 7

The successor of a node in a binary tree is called its

neighbor

child

descendant

neighbor

QUESTION 8

Consider the operation of deleting the root of a binary search tree. If the root has one child, then

the root of the subtree should be recursively deleted

the element stored in the root node should be replaced with null

the reference to the root of the tree should be set to point to the one child

the operation should be recursively performed on the one subtree of the root

QUESTION 9

A node in a binary tree that has no children is called

a leaf

a single node

barren

a twig

QUESTION 10

Binary trees have been used

in compilers and interpreters to represent expressions

in computer hardware to model branching patterns of electronic signals

in the Java Collections Framework to internally implement the Vector class

All of these are true

None of these are true

QUESTION 11

Adding all items from a list to a certain data structure and then removing them one at a time yields a sorted version of the list. The data structure is a

priority queue

binary search tree

complete binary tree

binary sort tree

QUESTION 12

An empty binary tree has height

-1

0

1

None of these are true: the height of an empty binary tree is not defined.

QUESTION 13

When a new item is added to an AVL tree

the tree may become unbalanced in only one way

the tree may become unbalanced two different ways, but the two imbalances are mirror images of each other

the tree may become unbalanced in four different ways, but because of mirror images, there are really only two fundamentally different imbalances

the height of one of the subtrees of the root may become three times the height of the other subtre

QUESTION 14

A binary tree stores items that have a natural order in such a way that at each node X, all items stored in the left subtree of X are less than the item stored at X, and all items stored in the right subtree are greater than the item stored at X. Such a binary tree is called

an ordered binary tree

a binary search tree

an AVL tree

All of these are true

None of these are true