final data struc

The ADT dictionary is appropriate for problems that must manage data by

a. value

b. order

c. priority

d. importance

a. value

What does the ADT dictionary use to identify its entries?

a. it’s position in the list

b. a search key

c. its priority

d. what group it belongs to

b. a search key

Which of the following is not an ADT dictionary operation?

a. add a new entry

b. retrieve an entry

c. sort the entries

d. traverse the entries in sorted search-key order

c. sort the entries

Which of the following is the better choice when attempting to add a new entry to a dictionary where the search key already exists?

a. replace the existing entry with a new entry

b. crash the program

c. throw an exception

d. deny the attempt

d. deny the attempt

In the header file for the class ArrayDictionary, the text declares which of the following

methods as private?

a. destroyDictionary()

b. isEmpty()

c. getNumberOfEntries()

d. clear()

a. destroyDictionary()

In the class ArrayDictionary declared by the text, which of the following methods bears the

responsibility for keeping the array items sorted?

a. remove

b. add

c. getValue

d. traverse

b. add

According to the text, for the ADT dictionary, in which of the following situations would a sorted array-based implementation be appropriate for frequent retrievals?

a. when the maximum size is unknown

b. when the maximum size is known

c. when you have duplicate search keys

d. when search keys are all similar.

c. when you have duplicate search keys

According to the text, for the ADT dictionary, what implementation should be used when you do not know the maximum size of the dictionary?

a. link-based

b. array-based

c. max-heap

d. binary search tree

d. binary search tree

According to the text, for the ADT dictionary, a sorted array-based implementation will shift data during what two operations?

a. additions and removals

b. additions and traversals

c. removals and traversals

d. searches and gets

a. additions and removals

Which of the following dictionary operations has efficiency O(n) no matter what implementation if the ADT dictionary is chosen?

a. retrieval

b. traversal

c. removal

d. addition

b. traversal

What is the implementation of the ADT dictionary which has efficiency O(log n) for addition?

a. unsorted link-based

b. sorted array-based

c. binary search tree

d. sorted link-based

c. binary search tree

What is the implementation of the ADT dictionary which has efficiency O(1) for addition?

a. sorted link-based

b. sorted array-based

c. binary search tree

d. unsorted link-based

d. unsorted link-based

What kind of function tells you where a dictionary entry is currently or will be placed if it is new?

a. hash function

b. logarithmic function

c. interrogatory function

d. big O function

a. hash function

What is it called when a hash function maps two or more search keys into the same integer

a. an accident

b. a collision

c. a perfect hash function

d. an exception

b. a collision

When you begin at the hash location and search the dictionary sequentially, this is called what?

a. closed addressing

b. Horner’s rule

c. linear probing

d. inverse probing

c. linear probing

The process of enlarging a hash table and computing new hash indices for its contents is called

a. re-probing

b. de-hashing

c. inverse hashing

d. re-hashing

d. re-hashing

You define a hash table so that each location table\[i\] is itself an array. This array is referred to as a(n)

a. bucket

b. bracket

c. closet

d. shelf

a. bucket

To make an intelligent choice among various possible dictionary implementations, you must analyze the efficiency with which each supports the dictionary operations

True

The getValue(searchKey) method for an ADT dictionary retrieves the specified search key for a given value.

False

The client code should not be able to modify an entry’s search key once that entry is in the dictionary.

True

An ADT dictionary should never allow duplicate search keys

False

The traverse method visits all dictionary entries.

True

A dictionary must store and form an association between search key and data value only for a sorted version of the dictionary, not for unsorted.

False

A linear link-based implementation of the ADT dictionary does not need to shift data for an add or a remove operation.

True

A linear link-based implementation of the ADT dictionary supports addition and removel operations more efficiently than an array-based implementation.

False

A binary search tree implementation of the ADT dictionary is nonlinear

True

In the ArrayDictionary class, we must sort the items each time traverse is called.

False

The binary search tree implementation of the ADT dictionary has a binary search tree as a data member.

True

The add method for the template for TreeDictionary presented in the text does not allow for duplicate entries.

False

It is important to know both what operations are needed for a given application of an ADT dictionary and how often each operation is required.

True

A sorted array-based implementation of the ADT dictionary cannot use a binary search.

False

A binary search is impractical with a link-based implementation of the ADT dictionary.

True

An implementation of the ADT dictionary using a binary search tree is a poor choice for retrieval dominate applications.

False

Because linear implementations are easy to understand conceptually they are appropriate for dictionaries that will only contain a small number of entries.

True

According to the text, if the size of a problem is small, the difference in efficiency among possible solutions is likely insignificant.

True

If the size of a dictionary is small, a linear implementation is inadequate and difficult to understand.

False

A perfect hash function maps each search key into a unique location of the hash table.

True

It is insufficient for hash functions to operate only on integers.

False

Digit selection does not distribute entries in the hash table.

True

Quadratic probing causes no clustering at all.

False

Double hashing drastically reduces clustering.

True

With separate chaining, the size of the dictionary is dynamic and can exceed the size of the hash table.

True

On average, quadratic probing and double hashing require more comparisons than linear probing.

False

Dictionary traversal is inefficient when using hashing.

True

If you use a binary search tree to implement an ADT dictionary, when does the efficiency of this implementation suffer?

a. when the tree loses its balance

b. when the tree is too balanced

c. when the data portions of the nodes are too large \\n

d. when a node accidentally has three branches

a. when the tree loses its balance

What is sensitive to the order of additions to and removals from a binary tree?

a. the contents of the nodes

b. the height of the tree

c. the complexity of the links

d. the implementation of the binary tree

b. the height of the tree

A binary tree is considered balanced if the heights of its two subtrees differ by

a. at least 1

b. exactly 1

c. at most 1

d. zero

c. at most 1

You can traverse a 2-3 tree in sorted order by performing the analogue of a(n) _______ traversal on a binary tree.

a. pre-order

b. post-order

c. tri-order

d. in-order

d. in-order

A 2-3 tree with n nodes cannot be taller than

a. log2(n + 1)

b. log2(n)

c. n + 1

d. 2n + 1

a. log2(n + 1)

A 2-3 tree implementation of a dictionary is of what efficiency for all its operations?

a. O(log2(n + 1))

b. O(log n)

c. O(n)

d. O(n + 1)

a. O(log2(n + 1))

In a 2-3-4 tree, how many data items must a node have if it has 4 children?

a. 2

b. 3

c. 4

d. 5

b. 3

A red-black tree has the advantages of a 2-3-4 tree …

a. but requires more storage

b. and requires the same amount of storage

c. but requires less storage

d. but is less complicated

c. but requires less storage

What distinguishes the root of a red-black tree?

a. it is red

b. it is either red or black, but will have 4 children

c. it is either red or black and has exactly 1 child

d. it is black

d. it is black

When working with a red-black tree, splitting nodes involves color pointer changes, called

rotations. What does this do to the tree?

a. shorten the tree

b. lengthen the tree

c. keeps it the same length

d. reverses the tree

a. shorten the tree

The efficiency of using a binary search tree to implement an ADT dictionary suffers when the tree loses its balance.

True

Numerous additions to and removals from a binary search tree will invariably destroy its balance.

False

You can search an AVL tree almost as efficiently as a minimum height binary search tree.

True

An AVL tree implementation of a dictionary is of equal difficulty to other implementations.

False

It can be proven that the height of an AVL tree with n nodes will always be very close to the theoretical minimum of log2(n + 1).

True

A 2-3 is pretty much the same as a binary tree.

False

A 2-3 tree is never taller than a minimum-height binary tree.

True

The leaf of a 2-3 tree must contain exactly 2 data items.

False

Searching a 2-3 tree is efficient.

True

Searching a 2-3 tree is more efficient than searching a binary search tree.

False

According to the text, maintaining the shape of a 2-3 tree is relatively easy

True

A 2-3-4 tree requires the same amount of storage as a 2-3 tree.

False

The algorithms for adding data to and removing data from a 2-3-4 tree require fewer steps than those for a 2-3 tree.

True

Every red node of a red-black tree has a black parent and a red child.

False

Every path from the root to a leaf in a red-black tree contains the same number of black nodes

True

A graph consists of ______ sets.

a. two

b. three

c. four

d. five

a. two

A subset of a graph’s vertices and edges is known as a ______.

a. bar graph

b. line graph

c. subgraph

d. circuit

c. subgraph

Two vertices that are joined by an undirected edge are said to be ______ each other.

a. related to

b. bordering

c. utilizing

d. adjacent to

d. adjacent to

A path is a sequence of ______ in a graph.

a. vertices

b. edges

c. subgraphs

d. cycles

b. edges

All ______ begin and end at the same vertex and do not pass through any other vertices more than once.

a. paths

b. simple paths

c. cycles

d. simple cycles

d. simple cycles

Which of the following is true about a simple cycle?

a. it can pass through a vertex more than once

b. it cannot pass through a vertex more than once

c. it begins at one vertex and ends at another

d. it passes through only one vertex

b. it cannot pass through a vertex more than once

A graph is ______ if each pair of distinct vertices has a path between them.

a. complete

b. disconnected

c. connected

d. full

c. connected

A graph is ______ if it has at least one pair of vertices without a path between them.

a. complete

b. disconnected

c. connected

d. full

b. disconnected

A complete graph has a(n) ______ between each pair of distinct vertices.

a. edge

b. path

c. cycle

d. circuit

a. edge

A ______ can have duplicate edges between vertices.

a. spanning tree

b. connected graph

c. complete graph

d. multigraph

d. multigraph

A self edge is also called a ______.

a. cycle

b. loop

c. circuit

d. multigraph

b. loop

The ______ of a weighted graph have numeric labels.

a. vertices

b. edges

c. paths

d. cycles

c. paths

The edges in a ______ indicate a direction.

a. complete graph

b. multigraph

c. digraph

d. spanning tree

c. digraph

If a graph has a directed edge from vertex x to vertex y, which of the following is true about x and y?

a. y is a predecessor of x \\n

b. x is a successor of y

c. x is adjacent to y

d. y is adjacent to x

d. y is adjacent to x

A graph-traversal algorithm stops when it ______. \\n

a. first encounters the designated destination vertex

b. has visited all the vertices that it can reach

c. has visited all the vertices

d. has visited all the vertices and has returned to the origin vertex

b. has visited all the vertices that it can reach

A ______ is the subset of vertices visited during a traversal that begins at a given vertex.

a. circuit

b. multigraph

c. digraph

d. connected component

d. connected component

An iterative DFS traversal algorithm uses a(n) ______.

a. list

b. array

c. queue

d. stack

d. stack

A ______ order is a list of vertices in a directed graph without cycles such that vertex x precedes vertex y if the graph has a directed edge from x to y.

a. graphical

b. topological

c. hierarchical

d. spatial

b. topological

A ______ is an undirected connected graph without cycles.

a. tree

b. multigraph

c. digraph

d. connected component

a. tree

A connected undirected graph that has n vertices must have at least ______ edges.

a. n

b. n – 1

c. n / 2

d. n \* 2

b. n - 1

A connected undirected graph that has n vertices and exactly n – 1 edges ______.

a. cannot contain a cycle

b. must contain at least one cycle

c. can contain at most two cycles

d. must contain at least two cycles

a. cannot contain a cycle

A connected undirected graph that has n vertices and more than n – 1 edges ______.

a. cannot contain a cycle

b. must contain at least one cycle

c. can contain at most two cycles

d. must contain at least two cycles

b. must contain at least one cycle

A tree with n nodes must contain ______ edges.

a. n

b. n – 1

c. n – 2

d. n / 2

b. n - 1

The sum of the weights of the edges in a path can be called all of the following EXCEPT ______.

a. length

b. weight

c. height

d. cost

c. height

A ______ is a special cycle that passes through every vertex in a graph exactly once.

a. multigraph

b. tree

c. spanning tree

d. circuit

d. circuit

A(n) ______ begins at a vertex v, passes through every edge exactly once, and terminates at v.

a. multigraph

b. spanning tree

c. Euler circuit

d. Hamilton circuit

c. Euler circuit

A(n) ______ begins at a vertex v, passes through every vertex exactly once, and terminates at v.

a. multigraph

b. spanning tree

c. Euler circuit

d. Hamilton circuit

d. Hamilton circuit

An Euler circuit exists if and only if each vertex touches ______.

a. two edges

b. three edges

c. an even number of edges

d. an odd number of edges

c. an even number of edges

Adjacent vertices are joined by an edge

True

A simple path may pass through the same vertex more than once.

False

All paths begin and end at the same vertex

False