Master Searching and Sorting Algorithms: A Comprehensive Guide for Year 13 Computer Science Students

Question 1

Identify the sorting algorithm with a worst-case time complexity of O(n^2).

Accepted Answer

Bubble sort

Answer

Binary search

Answer

Merge sort

Question 2

What is the worst-case time complexity of Linear Search?

Accepted Answer

O(n)

Answer

O(1)

Question 3

What is the time complexity of Bubble Sort for an array of size n?

Accepted Answer

O(n^2)

Answer

O(n)

Question 4

Which of the following is the time complexity of binary search in a sorted array?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log^2 n)

Question 5

Which of the following sorting algorithms is considered stable, preserving the original order of equal elements?

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Quick sort

Answer

Selection sort

Question 6

What is a fundamental difference between binary search and linear search?

Accepted Answer

Binary search requires a sorted array, unlike linear search.

Answer

Linear search is generally faster than binary search for small arrays.

Answer

Binary search can operate on arrays of any data type, while linear search is restricted to integers.

Answer

Linear search consumes less memory compared to binary search.

Question 7

In the merge step of merge sort, what operation is performed to combine the sorted subarrays?

Accepted Answer

Elements from both subarrays are compared, and the smaller element is inserted into the merged array.

Answer

Elements from the first subarray are copied into the merged array, followed by elements from the second subarray.

Answer

The first elements of both subarrays are swapped.

Answer

Elements from both subarrays are summed and inserted into the merged array.

Question 8

What is the primary purpose of using a sentinel value in binary search?

Accepted Answer

To mark the end of the search range, simplifying the comparison process.

Answer

To indicate the position of the searched element in the sorted array.

Answer

To enhance the search speed by reducing the number of comparisons required.

Answer

To prevent accessing elements outside the array bounds.

Question 9

Which implementation of merge sort optimizes space usage?

Accepted Answer

In-place merge sort

Answer

Bottom-up merge sort

Answer

Balanced merge sort

Answer

Natural merge sort

Question 10

What is the time complexity of the partitioning step in quick sort, which divides the array into two subarrays?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n^2)

Answer

O(1)

Question 11

What is a key distinction between the iterative and recursive approaches to binary search?

Accepted Answer

Iterative binary search uses a loop, while recursive binary search uses recursion.

Answer

Recursive binary search is significantly faster than iterative binary search.

Answer

Iterative binary search requires less memory compared to recursive binary search.

Answer

Recursive binary search is more straightforward to implement than iterative binary search.

Question 12

Identify the option that is NOT a primary sorting algorithm.

Accepted Answer

Binary Search

Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Question 13

Select the most efficient searching algorithm when the data is sorted.

Accepted Answer

Binary Search

Answer

Linear Search

Answer

Breadth-First Search

Answer

Depth-First Search

Question 14

Specify the two main stages involved in a quick sort algorithm.

Accepted Answer

Partitioning and recursive sorting

Answer

Comparison and exchange

Answer

Merging and sorting

Answer

Searching and insertion

Question 15

Indicate the data structure employed in a breadth-first search algorithm.

Accepted Answer

Queue

Answer

Stack

Answer

Tree

Answer

Graph

Question 16

Determine the worst-case time complexity of a linear search algorithm.

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n log n)

Answer

O(log n)

Question 17

State an application of searching algorithms.

Accepted Answer

Locating a specific element within a dataset

Answer

Sorting a dataset into ascending or descending order

Answer

Generating a random number

Answer

Compressing a file to reduce its size

Question 18

What is the worst-case time complexity for linear search?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 19

Which searching algorithm is most efficient for a sorted array?

Accepted Answer

Binary Search

Answer

Linear Search

Answer

Bubble Sort

Answer

Merge Sort

Question 20

What is the time complexity of the linear search algorithm on average?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 21

Which step is crucial in the bubble sort algorithm?

Accepted Answer

Comparing adjacent elements and swapping them if necessary

Answer

Dividing the array into smaller subarrays and sorting them recursively

Answer

Creating a new array with the sorted elements

Answer

Using a pivot element to partition the array

Question 22

Which factor should NOT be considered when selecting a sorting algorithm?

Accepted Answer

User's personal preference

Answer

Size of the dataset

Answer

Nature of the data

Answer

Type of hardware available

Question 23

What is the main purpose of the 'partition' step in the quick sort algorithm?

Accepted Answer

To create two subarrays with elements smaller and larger than the pivot

Answer

To sort the entire array in ascending or descending order

Answer

To identify the median element of the array

Answer

To find the maximum and minimum values in the array

Question 24

In which scenario is a searching algorithm typically used?

Accepted Answer

Finding a specific record in a database

Answer

Identifying the maximum value in a financial dataset

Answer

Sorting a list of names

Answer

Checking the validity of a password

Question 25

What is the distinction between stable and unstable sorting algorithms?

Accepted Answer

Stable algorithms maintain the order of equal elements, while unstable algorithms do not.

Answer

Unstable algorithms are faster than stable algorithms.

Answer

Stable algorithms require more memory space than unstable algorithms.

Answer

Only bubble sort is a stable sorting algorithm.

Question 26

Which searching algorithm efficiently finds the target element in a sorted array in O(log n) time?

Accepted Answer

Binary search

Answer

Linear search

Question 27

What is the worst-case time complexity of insertion sort?

Accepted Answer

O(n^2)

Answer

O(n)

Question 28

What is the purpose of a pivot element in quick sort?

Accepted Answer

To divide the array into two partitions

Answer

To mark the sorted portion of the array

Question 29

What data structure is used to implement a binary search tree?

Accepted Answer

Binary tree

Answer

Linked list

Question 30

What is the primary goal of a red-black tree?

Accepted Answer

To maintain a balance between search efficiency and insertion/deletion efficiency

Answer

To allow for constant-time search, insertion, and deletion operations

Question 31

Which sorting algorithm is the most efficient for a nearly sorted array?

Accepted Answer

Insertion sort

Answer

Bubble sort

Answer

Merge sort

Answer

Quick sort

Question 32

What is the worst-case time complexity of a binary search?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 33

Which of the following is NOT a comparison-based sorting algorithm?

Accepted Answer

Counting sort

Answer

Bubble sort

Answer

Merge sort

Answer

Quick sort

Question 34

Which of the following search algorithms is suitable for a sorted array?

Accepted Answer

Binary search

Answer

Linear search

Answer

Breadth-first search

Answer

Depth-first search

Question 35

What is a key property of a stable sorting algorithm?

Accepted Answer

Preserves the order of equal elements

Answer

Runs in O(n) time

Answer

Can handle duplicate elements

Answer

Is efficient for nearly sorted arrays

Question 36

Which of the following is a limitation of a bubble sort?

Accepted Answer

Slow performance for large arrays

Answer

Not stable

Answer

High space complexity

Answer

Difficult to implement

Question 37

What is the average-case time complexity of a merge sort?

Accepted Answer

O(n log n)

Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Question 38

Which algorithm offers the most efficient approach for searching a pre-sorted array?

Accepted Answer

Binary search

Answer

Linear search

Answer

Bubble sort

Answer

Quick sort

Question 39

In quick sort, what is the pivot element?

Accepted Answer

A randomly chosen element

Answer

The first element

Answer

The last element

Answer

The median element

Question 40

In the best-case scenario, what is the time complexity of linear search?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 41

Describe the distinction between stable and unstable sorting algorithms.

Accepted Answer

Stable algorithms preserve the relative order of equal elements, whereas unstable algorithms do not.

Answer

Stable algorithms are always more efficient than unstable algorithms.

Answer

The stability of a sorting algorithm has no bearing on its time complexity.

Answer

Both stable and unstable algorithms can be used for any sorting task.

Question 42

Given an array of n integers, which sorting algorithm would you select to guarantee that the sorted output is consistent regardless of the number of duplicates in the array?

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Quick sort

Answer

Counting sort

Question 43

Which of the following sorting algorithms operates by dividing the input into increasingly smaller subarrays until they are sorted?

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Insertion Sort

Answer

Selection Sort

Question 44

What is the best-case time complexity of binary search, in terms of the number of items (n) in a sorted array?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 45

What is the worst-case time complexity of the Quick Sort algorithm, in terms of the number of items (n) in the input array?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(1)

Question 46

Which technique in Merge Sort is utilized to combine two sorted subarrays into a single sorted array?

Accepted Answer

In-place merging

Answer

Recursive merging

Answer

Bubble sort

Answer

Heap sort

Question 47

What is a key advantage of utilizing a binary search tree for performing search operations?

Accepted Answer

Significantly reduced search time in comparison to linear search

Answer

Efficient insertion and deletion of elements

Answer

Automatic sorting of elements in ascending order

Answer

Capacity to store large datasets

Question 48

Which sorting algorithm performs its operations without requiring additional memory space?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 49

What is the primary purpose of selecting a pivot element in the Quick Sort algorithm?

Accepted Answer

Partitioning the array into two subarrays based on the pivot's value

Answer

Determining the median value of the array

Answer

Identifying the smallest element in the array

Answer

Sorting the array in descending order

Question 50

Which searching algorithm divides the input array into halves, checks if the desired element is in the current half, and continues the search in the corresponding subarray until the element is found?

Accepted Answer

Binary search

Answer

Linear search

Answer

Bubble sort

Answer

Quick sort

Question 51

Which sorting algorithm follows the divide-and-conquer approach, recursively dividing the input array into two subarrays, sorting each subarray, and merging them to obtain the sorted array?

Accepted Answer

Merge sort

Answer

Quick sort

Answer

Bubble sort

Answer

Selection sort

Question 52

Which sorting algorithm selects the smallest unsorted element and places it at the beginning of the unsorted portion of the array in each pass?

Accepted Answer

Selection sort

Answer

Bubble sort

Answer

Insertion sort

Answer

Merge sort

Question 53

Which searching algorithm starts from one end of the array and sequentially compares each element to the desired element until it is found?

Accepted Answer

Linear search

Answer

Binary search

Answer

Breadth-first search

Answer

Depth-first search

Question 54

Which measure quantifies the efficiency of a searching algorithm, expressed as the maximum number of element comparisons required to find the desired element?

Accepted Answer

Time complexity

Answer

Space complexity

Answer

Input size

Answer

Output size

Question 55

Which measure quantifies the amount of memory an algorithm requires to run, expressed as the additional memory needed beyond the input data?

Accepted Answer

Space complexity

Answer

Time complexity

Answer

Input size

Answer

Output size

Question 56

Which searching algorithm is most efficient for finding an element in a large, sorted array?

Accepted Answer

Binary search

Answer

Linear search

Answer

Selection sort

Answer

Bubble sort