Data structures worksheet with answers

The depth of a node in a tree is:

1. AThe number of children of that node
2. BThe number of nodes in its subtree
3. CThe number of edges from that node to the deepest leaf
4. DThe number of edges from the root to that node

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

1. ALevel by level from the top
2. BNode, then left subtree, then right subtree
3. CLeft subtree, then right subtree, then node
4. DLeft subtree, then node, then right subtree

What defines a binary tree?

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

What is true of the adjacency matrix of an undirected graph?

1. AIt is always upper triangular
2. BEach row has exactly one 1
3. CIts main diagonal always contains ones
4. DIt is symmetric about the main diagonal

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

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

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

Why can elements not simply be deleted from a standard Bloom filter by clearing their bits?

1. ABits in a Bloom filter cannot be changed after creation
2. BThose bits may also belong to other elements, which would cause false negatives
3. CDeleting would increase the false positive rate to 100%
4. DBloom filters store the full elements, and these cannot be located again once hashed

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA binary search tree only
2. BA hash map combined with a doubly linked list
3. CA stack only
4. DA single sorted array