1.
In quick sort, the number of partitions into which the file of
size n is divided by a selected record is
Correct Answer
C. 2
Explanation
In quick sort, the file of size n is divided into two partitions by selecting a pivot element. One partition contains elements smaller than the pivot, while the other contains elements larger than the pivot. Therefore, the number of partitions into which the file of size n is divided by a selected record is 2.
2.
How many passes are required to sort a file of size n by
bubble sort method?
Correct Answer
C. N-1
Explanation
In bubble sort, each pass compares and swaps adjacent elements until the largest element "bubbles" to the end of the list. Since the largest element is already in its correct position after each pass, the number of passes required to sort the file of size n is equal to the number of elements in the file minus one. Therefore, the correct answer is N-1.
3.
The worst-case time complexity of Quick Sort is________.
Correct Answer
A. O(n2)
Explanation
The worst-case time complexity of Quick Sort is O(n^2). This means that in the worst-case scenario, the algorithm will take a time proportional to the square of the input size to sort the elements. This occurs when the pivot chosen is either the smallest or largest element in the array, causing the partitioning step to divide the array into two sub-arrays of size 0 and n-1. As a result, the algorithm will have to recursively sort n-1 elements, each time reducing the size of the sub-array by only 1. Therefore, the time complexity becomes quadratic.
4.
A list of n strings, each of length n, is sorted into
lexicographic order using the merge-sort algorithm. The worst
case running time of this computation is
Correct Answer
A. O (n log n)
Explanation
The merge-sort algorithm has a time complexity of O(n log n) in the worst case scenario. This is because it divides the list into smaller sublists, recursively sorts them, and then merges them back together. The merge step takes O(n) time, and the sorting step is performed log n times. Therefore, the overall time complexity is O(n log n).
5.
The correct order of the efficiency of the following sorting
algorithms according to their overall running time comparison
is
Correct Answer
D. Bubble>selection>insertion
Explanation
The correct order of the efficiency of the sorting algorithms, from the most efficient to the least efficient, is bubble sort, selection sort, and insertion sort. Bubble sort compares adjacent elements and swaps them if they are in the wrong order, repeatedly iterating through the list until it is sorted. Selection sort finds the minimum element in each iteration and swaps it with the current element. Insertion sort builds the final sorted array one item at a time by comparing each element with those in the already sorted portion and inserting it in the correct position. Therefore, the correct order is bubble>selection>insertion.
6.
Consider the following function f:
int f(int n)
{
int s = 0;
while(n > 1)
{
n = n/2;
s++;
}
return s;
}
What is the asymptotic complexity in terms of n?
Correct Answer
C. O(log n)
Explanation
The given function takes an input 'n' and repeatedly divides it by 2 until 'n' becomes less than or equal to 1. The number of iterations required to reach this condition is equal to the logarithm base 2 of 'n'. Therefore, the time complexity of the function is O(log n).
7.
Consider a class List that implements an unordered list.
Suppose it has as its representation a dynamically expanding
(resizable) array. Which of these operations might need to
delete some dynamically allocated storage to avoid a memory
leak?
I. Default Constructor
II. Copy Constructor
III. Destructor
IV. Assignment operator
Correct Answer
D. III and IV
Explanation
The destructor needs to delete dynamically allocated storage to avoid a memory leak because it is responsible for freeing up any memory that was allocated during the object's lifetime. The assignment operator also needs to delete dynamically allocated storage because it may be called on an already initialized object, and in order to assign a new value, any previously allocated memory needs to be deallocated first. Therefore, the correct answer is III and IV.
8.
The concept of order Big O is important because
Correct Answer
A. It can be used to decide the best algorithm that solves a given
problem
Explanation
The concept of order Big O is important because it can be used to decide the best algorithm that solves a given problem. Big O notation allows us to analyze the efficiency and performance of algorithms by considering their time complexity. By comparing the Big O complexities of different algorithms, we can determine which algorithm is the most efficient and will provide the best solution for a given problem. This helps in optimizing code and improving overall performance.
9.
Suppose we are sorting an array of eight integers using some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown
here:
2 4 5 7 8 1 3 6
Correct Answer
A. Insertion sort
Explanation
In insertion sort, the array is divided into two parts - sorted and unsorted. The algorithm iterates through the unsorted part and compares each element with the elements in the sorted part, shifting them to the right if they are greater. In this case, after four iterations, the first four elements (2, 4, 5, 7) are already in sorted order. Insertion sort would then compare the fifth element (8) with the sorted elements and place it in the correct position. Therefore, the given array is partially sorted using insertion sort.
10.
Suppose we need to sort a list of employee records in ascending order, using the social security number (a 9-digit number) as the key (i.e., sort the records by social security number). If we need to guarantee that the running time will be no worse than n log n, which sorting methods could we use?
Correct Answer
A. Mergesort
Explanation
Mergesort is a sorting method that has a guaranteed worst-case time complexity of O(n log n). This means that regardless of the initial order of the employee records, mergesort will always take no worse than n log n time to sort them in ascending order based on their social security numbers. Quicksort is another option that could be used, but it does not guarantee a worst-case time complexity of n log n. Insertion sort is not suitable for this scenario as it has a worst-case time complexity of O(n^2), which is worse than n log n. Therefore, the correct answer is mergesort.