Data structures worksheet with answers

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

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

In a singly linked list, each node contains:

1. AData and an index
2. BData and a reference to the next node
3. CData and references to all other nodes
4. DOnly data

A graph consists of:

1. AKeys and hashes only
2. BVertices (nodes) connected by edges
3. COnly a root and leaves
4. DRows and columns

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

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

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

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

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

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

A Bloom filter can answer "is this element in the set?" with:

1. APossible false negatives but no false positives
2. BAnswers only for numbers
3. CExact answers always
4. DPossible false positives but no false negatives

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

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