# Sample Final Flashcards

Open hashing allows overflow into lists.

True.

A hash function is better if it produces few collisions.

True.

Hash functions cannot produce the same location for different keys.

False.

A hash function is better if each possible index is equally likely to occur given random keys.

True.

A process known as folding bits can reduce the impact of structure (a lack of randomness) on individual bits.

True.

Pseudo-Random probing generates random numbers during probing to avoid collisions.

False.

Using the modulo operator (%) with even numbers is a way to spread out locations independently of array size.

False.

Hashing grows more efficient as the load factor increases, encouraging small hash arrays.

False.

Using buckets with a size that is a prime number reduces probing collisions in open hashing.

False.

Closed hashing implies perfect hashing, as there is no place for duplicate keys.

False.

A hash function is used to convert a key into a location, or index.

True.

Hashing can be used to provide fast access to data in large datasets.

True.

Quadratic probing avoids clustering in many cases, but generally, not all hash table slots can be accessed during probing.

True.

Perfect hashes ensure that there can be no collisions.

True.

Open hashing allows overflow into lists, removing the need for probing.

False.

Secondary clustering happens when different keys hash to the same spot and have the same probing sequence; this cannot be fixed by conventional probing.

True.

Closed hashing stores values that hash to the same space into buckets, then performs probing when those buckets are full.

True.

Probing functions generally ignore the key.

True.

Probing functions are not hashing functions.

True.

A hash function is better if it is cheap.

True.

Hashing the key twice is called double hashing and it limits the need to perform probing.

False.

Hash functions can produce different locations for the same key.

False.

Finding an element in a heap takes theta(n) operations.

True.

A heap in an array will in general always be full.

False.

The height of a heap in an array is known if we know how many elements are in it.

True.

A heap is a tree-based data structure.

True.

Building a heap from an array can be done in theta(n) operations.

True.

Finding an element in a heap takes theta(log n) operations.

False.

A heap can only be implemented using a linked list.

False.

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

True.

If you add one child to any node that has only one child, and two children to every leaf node, you have added n + 1 nodes.

True.

Preorder is a traversal of a binary tree where the left child is processed before the parent node, and the right child is processed last.

False.

If you add one child to any node that has only one child, and two children to every leaf node, you have added n nodes.

False.

Binary trees must be traversed depth-first.

False.