Data structures worksheet with answers

What does a hash function do in a hash table?

1. ACounts how many keys are stored
2. BEncrypts the values in the table
3. CMaps a key to an index in the table
4. DSorts the keys in the table

How many edges does a tree with n nodes have?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

In which order does a preorder traversal of a binary tree visit nodes?

1. ALeft subtree, then node, then right subtree
2. BNode, then left subtree, then right subtree
3. CLevel by level from the top
4. DLeft subtree, then right subtree, then node

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊i / 2⌋ + 1
2. BAt index i − 1
3. CAt index 2i + 1
4. DAt index ⌊(i − 1) / 2⌋

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(n), because later elements must shift
2. BO(log n), because of binary search
3. CO(1), because the index is known
4. DO(n²), because each element moves n times

AVL trees and red-black trees guarantee:

1. AO(log n) height through rebalancing
2. BThat keys are stored in insertion order
3. CConstant-time search in every case
4. DThat no node has two children

A Bloom filter can answer "is this element in the set?" with:

1. AExact answers always
2. BPossible false positives but no false negatives
3. CAnswers only for numbers
4. DPossible false negatives but no false positives

Why might a server choose its hash function at random from a universal family?

1. ATo guarantee that no two keys can ever collide, whatever keys an attacker sends
2. BTo make it very unlikely that an attacker can pick many keys that all collide
3. CTo remove the need to resize the table
4. DTo make the hash table sorted