Data structures worksheet with answers

What is the name of the stack operation that adds an element to the top?

1. AEnqueue
2. BPush
3. CPop
4. DPeek

What does each node in a doubly linked list contain?

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

How are the elements of an array stored in memory?

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

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

1. ADescending order always
2. BLevel order
3. CInsertion order
4. DAscending sorted order

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

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

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index 2i + 1
2. BAt index ⌊(i − 1) / 2⌋
3. CAt index ⌊i / 2⌋ + 1
4. DAt index i − 1

Deleting a node with two children from a binary search tree is usually done by:

1. ASwapping it with the root
2. BRemoving the whole subtree
3. CRebuilding the subtree below it from scratch and reinserting every key it contained
4. DReplacing it with its in-order successor (or predecessor) and deleting that node

The time complexity of decrease-key in a binary heap (given the element's position) is:

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