Data structures worksheet with answers

What does a hash function do in a hash table?

1. ASorts the keys in the table
2. BEncrypts the values in the table
3. CCounts how many keys are stored
4. DMaps a key to an index in the table

What defines a binary tree?

1. AEvery node has exactly two children
2. BEvery node stores a binary number
3. CThe tree has exactly two levels
4. DEvery node has at most two children

Which operation is slow in an array but fast at the head of a linked list?

1. AFinding the length of a fixed array
2. BInserting at the beginning
3. CReading the last element by index
4. DAccessing the 5th element

AVL trees and red-black trees guarantee:

1. AThat keys are stored in insertion order
2. BConstant-time search in every case
3. CThat no node has two children
4. DO(log n) height through rebalancing

What is the time complexity of searching for a key in a balanced binary search tree?

1. AO(1)
2. BO(log n)
3. CO(n log n)
4. DO(n)

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai + 1 and i + 2
2. Bi/2 and i/2 + 1
3. C2i + 1 and 2i + 2
4. D2i and 2i + 1

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AAll records are in linked leaves, which makes range scans efficient
2. BB+ trees store data only in the root
3. CB+ trees do not need to be balanced
4. DB+ trees use binary internal nodes, which reduces the number of disk reads

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

1. ATo keep the array sorted
2. BTo avoid repeated resizing when pushes and pops alternate near the boundary
3. CBecause the memory allocator can only release memory in quarters of a block
4. DBecause halving at one half would lose elements