Data structures worksheet with answers

What does each node in a doubly linked list contain?

1. ATwo copies of the data and one pointer
2. BData and a pointer to the next node only
3. CData, a pointer to the next node and a pointer to the previous node
4. DData and two pointers, one to the next node and one to the node after that

Which data structure works on the principle "first in, first out"?

1. AStack
2. BBinary tree
3. CQueue
4. DHeap

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

1. ALeft subtree, then right subtree, then node
2. BRight subtree, then node, then left subtree
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

Which data structure does a running program use to keep track of active function calls and their local variables?

1. AThe call stack
2. BA hash table of functions
3. CA binary search tree of frames
4. DThe heap memory queue

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

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

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

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[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A60
2. B70
3. C40
4. D80