Data structures worksheet with answers

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

1. ALinked list
2. BStack
3. CHash table
4. DQueue

The depth of a node in a tree is:

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

What is the name of the queue operation that removes the element at the front?

1. ADequeue
2. BPush
3. CInsert
4. DEnqueue

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AA single sorted array of vertices
2. BAdjacency list
3. CA binary heap of edges
4. DAdjacency matrix

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA stack
2. BA FIFO queue
3. CA set with no ordering
4. DA min-priority queue

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

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

Why might a server choose its hash function at random from a universal family?

1. ATo make it very unlikely that an attacker can pick many keys that all collide
2. BTo guarantee that no two keys can ever collide, whatever keys an attacker sends
3. CTo make the hash table sorted
4. DTo remove the need to resize the table

Which property keeps every B-tree perfectly balanced?

1. AEvery node has exactly two children
2. BAll leaves are at the same depth
3. CThe keys are stored only in the root
4. DEach node stores one key