Data structures worksheet with answers

What is a directed graph?

1. AA graph whose edges have a direction from one vertex to another
2. BA graph that has no cycles
3. CA graph in which every pair of distinct vertices is joined by an edge
4. DA graph whose edges all have weights

In an undirected graph, what is the degree of a vertex?

1. AThe number of edges connected to it
2. BThe length of the longest path from it
3. CThe number of vertices in the graph
4. DIts position in the adjacency list

In a tree, what is a leaf?

1. AA node with no children
2. BA node with no parent
3. CThe node with the largest value
4. DA node with exactly one child

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. A20
2. B70
3. C40
4. D50

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 postorder traversal?

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

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊(i − 1) / 2⌋
2. BAt index ⌊i / 2⌋ + 1
3. CAt index 2i + 1
4. DAt index i − 1

How can you detect whether a singly linked list contains a cycle using O(1) extra memory?

1. AMove one pointer by one step and another by two steps and check whether they meet
2. BStore every visited node in a hash set
3. CCount the nodes until the count exceeds the list length field
4. DSort the list and look for duplicates

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

1. ATo avoid repeated resizing when pushes and pops alternate near the boundary
2. BBecause halving at one half would lose elements
3. CTo keep the array sorted
4. DBecause the memory allocator can only release memory in quarters of a block