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

What is a weighted graph?

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

What is the defining feature of a set as an abstract data type?

1. AIt stores elements without duplicates
2. BIt stores elements in sorted order
3. CIt stores key-value pairs
4. DIt allows access only at one end

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA stack
2. BA hash table
3. CA balanced binary search tree
4. DAn unsorted linked list

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

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

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

1. AO(1)
2. BO(E)
3. CO(V)
4. DO(log V)

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[1, 5, 8, 3]
2. B[3, 1, 8, 5]
3. C[1, 3, 5, 8]
4. D[1, 3, 8, 5]

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

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