Free Practice Quiz Question List

10 Data Structure and Algorithm Trade-offs Online Quiz Questions

Use this free practice quiz with 20 questions to review 10 Data Structure and Algorithm Trade-offs, test your knowledge, and prepare for your next test or exam.

20 questions

Choose one

1 point

Why is inserting an element near the beginning or middle of a dynamic array typically $O(n)$ ?

A
The elements after the insertion point must be shifted, so it is typically $O(n)$ .
B
The insertion is always $O(1)$ because arrays support constant-time indexing.
C
The array must be sorted first, so the operation is typically $O(\log n)$ .
D
The insertion requires hashing every existing element, so it is typically $O(n\log n)$ .

True or false

1 point

True or false: In a linked list, inserting at a known node can be $O(1)$ , even though finding that node may take $O(n)$ .

A
True
B
False

Written response

1 point

What structure should be used when a program needs efficient insertion and removal at both the front and the rear?

Fill in the blank

1 point

Binary search requires data and takes comparisons in the usual analysis.

Choose one

1 point

A program must repeatedly perform range queries and produce keys in sorted order. Which structure is the best general choice?

A
A hash table, because it naturally maintains sorted order and supports range queries.
B
A linked list, because range queries require scanning nodes in insertion order.
C
A balanced tree, because it maintains sorted order, supports range queries, and has typical $O(\log n)$ search, insertion, and deletion.
D
A stack, because its LIFO ordering provides efficient predecessor and successor queries.

True or false

1 point

True or false: A stable sorting algorithm preserves the relative order of records that have equal sort keys.

A
True
B
False

Written response

1 point

A task-processing system must add and remove tasks efficiently at either end of a sequence. What structure is most appropriate?

Fill in the blank

1 point

An LRU cache commonly combines a for key lookup with a for recency ordering.

Choose one

1 point

A collection of $n$ items is sorted once, followed by $m$ binary searches. What is the total asymptotic time complexity?

A
$O(mn)$
B
$O(n+m)$ in every implementation
C
$O(n\log m + m\log n)$
D
$O(n\log n + m\log n)$

Open ended

1 point

A service stores records by unique identifier. Most requests look up one exact identifier, but some requests require sorted iteration and range queries. Explain when a hash table is preferable, when a balanced tree is preferable, and what trade-offs should guide the final choice.

Choose one

1 point

A scheduler repeatedly needs to retrieve the task with the highest priority. Which structure is the most appropriate primary choice?

A
A linked list, because it provides constant-time access to every priority value.
B
A heap or priority queue, because it is designed to retrieve the next highest- or lowest-priority item efficiently.
C
A hash table, because hashing automatically returns the numerically smallest key.
D
A stack, because LIFO order is equivalent to priority order.

Choose one

1 point

A program sorts an array of $n$ items once and then performs $m$ binary searches on it. What is the total asymptotic time complexity?

A
$O(mn)$
B
$O(n\log n + m\log n)$
C
$O(n + m)$ in the worst case
D
$O(n\log m)$

Choose one

1 point

A program needs fast exact lookup by record ID and efficient sequential processing of all records. Which combined design best fits these requirements, assuming records may move within the main storage?

A
A stack and a queue
B
A balanced tree and a heap
C
A dynamic array and a hash table mapping IDs to indices
D
A linked list and a binary search tree

Choose one

1 point

A system must repeatedly retrieve all keys within specified ranges and iterate through the keys in sorted order. Which structure is the best primary choice?

A
A balanced tree
B
A hash table
C
A stack
D
A basic array

Choose one

1 point

A singly linked list must insert an item after a node that is identified only by its value. Which complexity statement is most accurate for the complete insertion task?

A
The entire operation is always $O(1)$ because linked lists never move elements.
B
The entire operation is always $O(\log n)$ because links provide direct access.
C
The operation is always $O(n^2)$ because each node has a link.
D
The link update is $O(1)$ after locating the node, but locating it may make the total $O(n)$ .

True or false

1 point

True or false: A recursive binary search on a sorted array has recurrence $T(n)=T(n/2)+O(1)$ , so its running time is $O(\log n)$ .

A
True
B
False

Written response

1 point

What is the worst-case time complexity of a linear search through an unsorted collection of $n$ items?

Written response

1 point

What is the usual complexity description for appending to a dynamic array over a long sequence of append operations?

Choose all

1 point

Select all statements that accurately describe hash-table trade-offs.

A
Lookup is guaranteed $O(1)$ even when all keys collide.
B
A hash table always maintains keys in sorted order.
C
Expected lookup, insertion, and deletion can be $O(1)$ with a good hash function and controlled load factor.
D
The worst case can be $O(n)$ , and sorted-order operations are not naturally supported.

Choose all

1 point

Which properties are required for a correct recursive function? Select all that apply.

A
A base case that can return without another recursive call
B
Progress toward the base case on each recursive call
C
A rule for combining recursive results into the final result
D
A hash table for storing every previously visited input