1.
Searching and sorting algorithms are best implemented with which data structure?
Correct Answer
C. Both of the above
Explanation
Both array-based lists and linked lists can be used to implement searching and sorting algorithms effectively. Array-based lists provide direct access to elements and can be easily traversed, making them suitable for algorithms that require random access. On the other hand, linked lists are efficient for insertion and deletion operations, which are common in sorting algorithms. Therefore, both data structures can be utilized depending on the specific requirements of the algorithm.
2.
What is the key used in a search algorithm?
Correct Answer
A. Used in operations such as searching, sorting, inserting and deleting
Explanation
The key used in a search algorithm is used in operations such as searching, sorting, inserting, and deleting. This key is a value that is used to identify and locate specific data within a data structure. It helps in determining the position or order of the data and is crucial for performing various operations on the data efficiently.
3.
Which search algorithm is best for a large list?
Correct Answer
C. Binary search
Explanation
Binary search is the best search algorithm for a large list because it has a time complexity of O(log n), which means it can quickly find the desired element by repeatedly dividing the search space in half. In contrast, sequential search has a time complexity of O(n), which means it needs to check each element in the list one by one. A for each loop is not a search algorithm but rather a way to iterate over a collection. Therefore, binary search is the most efficient option for searching a large list.
4.
A binary search algorithm can be best described as what?
Correct Answer
B. A divide and conquer technique
Explanation
A binary search algorithm can be best described as a divide and conquer technique. This is because it repeatedly divides the search space in half until the target element is found or determined to be not present. By dividing the search space in half at each step, it efficiently narrows down the possible locations of the target element, making it a highly efficient search method.
5.
On average, a sequential search algorithm would make N/2 number of comparisons for a list of size N.
Correct Answer
A. True
Explanation
A sequential search algorithm works by iterating through a list of elements one by one until it finds the desired element or reaches the end of the list. In the worst case scenario, the desired element is at the end of the list, and the algorithm would need to make N comparisons to find it. However, on average, the desired element could be anywhere in the list, so the algorithm would make approximately N/2 comparisons. Therefore, the statement that a sequential search algorithm would make N/2 number of comparisons for a list of size N is true.
6.
A function f(n) is Big-O of g(n) if there exist positive constants c and n_{0} such that f(n) <= cg(n) for all n >= n_{0}
Correct Answer
A. True
Explanation
The statement is true because it accurately describes the concept of Big-O notation. According to the definition given, a function f(n) is said to be Big-O of g(n) if there exist positive constants c and n0 such that f(n) is less than or equal to cg(n) for all values of n greater than or equal to n0. This means that f(n) grows no faster than g(n) for sufficiently large values of n.
7.
The following best describes which algorithm?
The elements are compared and swapped if the first is found to be greater than the second.
Correct Answer
C. Bubble sorting algorithm
Explanation
The given description of the algorithm matches the process of bubble sorting. In bubble sorting, the elements are compared pairwise and swapped if they are in the wrong order, with the largest element "bubbling" to the end of the list in each iteration. This process continues until the list is sorted. Therefore, the correct answer is the bubble sorting algorithm.
8.
The purpose of the bubble sorting algorithm is what?
Correct Answer
C. Both choices above
Explanation
The purpose of the bubble sorting algorithm is to sort the contents of the list. It is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. Additionally, while bubble sort is not the most efficient algorithm for searching an item in a list, it can potentially speed up the search by sorting the list first, which allows for faster search algorithms to be applied. Therefore, the correct answer is both choices above.
9.
A selection sort algorithm sorts the list by which method?
Correct Answer
A. Finding the smallest element in the list and moving this to the begining of the unsorted list
Explanation
A selection sort algorithm sorts the list by finding the smallest element in the list and moving it to the beginning of the unsorted list. This process is repeated until the entire list is sorted. This method ensures that the smallest element is always placed in the correct position, gradually building a sorted list from left to right. The other options, keeping a list of the smallest elements for later use when searching and none of the above, do not accurately describe the method of a selection sort algorithm. Therefore, the correct answer is finding the smallest element in the list and moving it to the beginning of the unsorted list.
10.
The insertion sort algorithm improves on the selection sort method by reducing the number of comparisons.
Correct Answer
A. True
Explanation
The statement is true because the insertion sort algorithm is more efficient than the selection sort method in terms of the number of comparisons it makes. In insertion sort, each element is compared with the elements before it and inserted into its correct position, resulting in fewer comparisons overall. This makes insertion sort a better choice when the list to be sorted is partially sorted or nearly sorted, as it can take advantage of the existing order and reduce the number of comparisons needed.
11.
The quick sort algorithm divides the list into two sublists, then sorts each sublists, and then combines both sublists.
Correct Answer
A. True
Explanation
The quick sort algorithm is a divide and conquer algorithm that works by selecting a pivot element and partitioning the other elements into two sublists, according to whether they are less than or greater than the pivot. These sublists are then recursively sorted. Finally, the sorted sublists are combined to obtain the final sorted list. Therefore, the statement that the quick sort algorithm divides the list into two sublists, sorts each sublist, and then combines both sublists is true.
12.
The heap sort algorithm begins by converting the list into a heap, then sorting.
Correct Answer
A. True
Explanation
The statement is true. The heap sort algorithm does indeed begin by converting the list into a heap. A heap is a specialized binary tree structure in which the parent node is always greater (or smaller) than its child nodes. By converting the list into a heap, the algorithm ensures that the largest (or smallest) element is at the root of the heap. After the conversion, the algorithm proceeds to sort the list by repeatedly swapping the root element with the last element of the heap and then reducing the size of the heap.