Data structures worksheet with answers

In a graph, what is a cycle?

1. AA vertex with no edges
2. BA path that starts and ends at the same vertex
3. CA path that visits every vertex
4. DAn edge with a weight of zero

How are the elements of an array stored in memory?

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

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

1. AStack
2. BBinary tree
3. CHeap
4. DQueue

AVL trees and red-black trees guarantee:

1. AThat keys are stored in insertion order
2. BThat no node has two children
3. CConstant-time search in every case
4. DO(log n) height through rebalancing

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

How much memory does an adjacency list use for a graph with V vertices and E edges?

1. AO(V²)
2. BO(E²)
3. CO(V + E)
4. DO(V × E)

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

1. APossible false negatives but no false positives
2. BExact answers always
3. CPossible false positives but no false negatives
4. DAnswers only for numbers

Which property must a red-black tree satisfy?

1. AEvery red node must have red children, so red nodes always form unbroken chains to the leaves
2. BEvery path from a node to its descendant leaves has the same number of black nodes
3. CEvery node must be red
4. DThe root must be red