Data structures worksheet with answers

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AReading the first element
2. BInserting at the head
3. CRemoving the head element
4. DAccessing the element at index i

What defines a binary tree?

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

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

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

An adjacency matrix for a graph with V vertices uses how much memory?

1. AO(V²)
2. BO(log V)
3. CO(E)
4. DO(V + E)

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AIts right child, always
2. BThe rightmost node of its left subtree
3. CThe leftmost node of its right subtree
4. DIts parent, always

What is the purpose of a sentinel (dummy) node in a linked list?

1. ATo prevent the list from growing beyond a fixed maximum number of nodes
2. BTo store the number of elements
3. CTo make the list sorted
4. DTo simplify code by removing special cases at the head or tail

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

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

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[1, 3, 5, 8]
2. B[3, 1, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]