A-Level Computer Science Data Structures Quiz

A software system manages a large number of tasks that need to be processed in the order they arrive. However, some tasks are designated as 'high priority' and should be processed before any 'normal priority' tasks, regardless of their arrival time. Within the high-priority tasks themselves, the processing order is still based on arrival time. Which of the following data structures, or combination of data structures, would be most appropriate to manage the tasks in this system efficiently?

• A single queue

• A stack

• A priority queue

• Two queues, one for high priority and one for normal priority, processed in that order.

Consider a scenario where you are implementing an 'undo' functionality in a text editor. You need to store the sequence of actions performed by the user so that they can be reversed one by one, starting with the most recent action. Which data structure is the most suitable for this purpose?

• A queue

• A linked list

• A stack

• An array

A directed graph is being used to represent a network of one-way streets in a city. You need to find the shortest path from a starting intersection to all other reachable intersections. Which algorithm is most appropriate for this task when edge weights represent the time taken to travel along a street (assume non-negative weights)?

• Depth-First Search (DFS)

• Breadth-First Search (BFS)

• Dijkstra's Algorithm

• A* Search

You are designing a system to store a dynamic collection of elements where insertions and deletions need to be performed frequently and efficiently at arbitrary positions within the collection. The order of elements is important. Which data structure would be the most efficient choice in terms of time complexity for these operations in the average case, compared to a static array?

• Stack

• Queue

• Singly Linked List

• Hash Table

A binary search tree is a hierarchical data structure that allows for efficient searching, insertion, and deletion of elements while maintaining a sorted order. Which of the following statements about a binary search tree is FALSE?

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• A pre-order traversal visits the root node, then the left subtree, then the right subtree.

• In the worst-case scenario, searching in a binary search tree can always achieve a time complexity of O(log n).

A hash table is used to store key-value pairs, providing fast average-case lookups. However, collisions can occur when two different keys hash to the same index. Which of the following is a common method for resolving collisions in a hash table?

• Rehashing the entire table when a collision occurs.

• Using a separate array to store colliding elements at the same index.

• Storing colliding elements in a linked list at the calculated index (chaining).

• Discarding the new element that causes a collision.

Consider a circular queue implemented using a fixed-size array. The queue has a front pointer and a rear pointer. The queue is initially empty. Elements are enqueued and dequeued. Which condition correctly indicates that the circular queue is FULL?

• front == rear

• front == (rear + 1) mod size

• rear == (front - 1) mod size

• front > rear

You are traversing a tree data structure. A specific traversal visits all the nodes of a subtree before moving to the next sibling subtree. The root is visited before its children. What type of tree traversal is being described?

• In-order traversal

• Pre-order traversal

• Post-order traversal

• Breadth-First Traversal

A graph is a data structure consisting of a set of vertices (nodes) and a set of edges connecting them. A connected graph is one where there is a path between every pair of vertices. Which of the following statements about graphs is FALSE?

• A tree is a type of connected graph with no cycles.

• A complete graph is one where every pair of distinct vertices is connected by a unique edge.

• The maximum number of edges in an undirected graph with n vertices is (n(n−1)​)/2

• An undirected graph cannot be represented using an adjacency matrix.

Which of the following is a key advantage of using a linked list over a static array for storing a list of items?

• Faster access to an element at a specific index.

• More efficient use of memory when the maximum size is known in advance.

• Easier insertion and deletion of elements within the list at arbitrary positions.

• Direct access to the last element in a singly linked list.