Data structures worksheet with answers

How are the elements of an array stored in memory?

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

In a tree, what are sibling nodes?

1. ANodes that have no children
2. BA node and its parent
3. CNodes that share the same parent
4. DNodes at the same depth in different subtrees

What is a weighted graph?

1. AA graph that is stored on disk
2. BA graph in which some vertices are heavier than others because they have more edges
3. CA graph in which each edge has a numeric value such as a cost or distance
4. DA graph with more edges than vertices

The keys 50, 30, 70, 20, 40 are inserted in this order into an empty binary search tree. What is the left child of 30?

1. A40
2. B50
3. C20
4. D70

A trie (prefix tree) is especially efficient for:

1. AStoring matrices
2. BSorting numbers
3. CPrefix searches such as autocomplete
4. DFinding shortest paths

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A4 2 5 1 3
2. B1 2 3 4 5
3. C1 2 4 5 3
4. D4 5 2 3 1

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AB+ trees do not need to be balanced
2. BB+ trees use binary internal nodes, which reduces the number of disk reads
3. CAll records are in linked leaves, which makes range scans efficient
4. DB+ trees store data only in the root

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. APrefix-sum queries and single-element updates
2. BSorting the array and binary search
3. CFinding the median in O(1)
4. DInserting elements at any position