Data structures worksheet with answers

In a singly linked list, what does the next pointer of the last node contain?

1. AThe address of the first node
2. BThe address of the previous node
3. CThe number of nodes in the list
4. DNull (no node)

How are the elements of an array stored in memory?

1. AIn a tree of memory pages
2. BIn one contiguous block, one after another
3. CIn random locations chosen by a hash
4. DScattered, linked by pointers

In a hash table, what is a collision?

1. ATwo equal keys are stored twice
2. BTwo different keys map to the same index
3. CA key cannot be hashed at all
4. DThe table runs out of memory

Which data structure is used to check whether the brackets in "{[()]}" are balanced?

1. AA queue
2. BA stack
3. CA binary search tree
4. DA hash table

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AAn unsorted linked list
2. BA hash table
3. CA stack
4. DA balanced binary search tree

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A1 2 3 4 5
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

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)

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most n / 2
2. BThe height is exactly log₂ n
3. CThe height is at most log₂ n + 1
4. DThe height is at most 2 log₂(n + 1)