Data structures worksheet with answers

What is the main difference between a static array and a dynamic array?

1. AA dynamic array stores its elements in linked nodes so it can grow one at a time
2. BA dynamic array can grow by moving to a larger block of memory
3. CA static array can only store numbers
4. DA static array allows slower index access

What does the peek (or top) operation on a stack do?

1. ARemoves the top element and returns it
2. BRemoves all elements from the stack
3. CReturns the top element without removing it
4. DReturns the bottom element of the stack

A graph consists of:

1. AVertices (nodes) connected by edges
2. BOnly a root and leaves
3. CRows and columns
4. DKeys and hashes only

An in-order traversal of a binary search tree visits the keys in:

1. AAscending sorted order
2. BDescending order always
3. CLevel order
4. DInsertion order

Why can a binary heap be stored in an array without any pointers?

1. AArrays automatically keep the keys in sorted order, so no pointers are needed
2. BAll keys in a heap are equal
3. CHeaps never contain more than 100 elements
4. DIt is a complete binary tree, so positions follow simple index formulas

In a hash table using open addressing, what is the maximum possible load factor?

1. A2
2. B1
3. CThere is no maximum
4. D0.5

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

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

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

1. AO(m)
2. BO(1 + α), where α = n / m
3. CO(n)
4. DO(log n)