DAA Quiz

2.

How many passes are required to sort a file of size n by bubble sort method?

N2
N
N-1
N/2

Correct Answer

A. 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.

Rate this question:

3.

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?

Mergesort
Quicksort
Insertion sort
Either mergesort or quicksort

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.

Rate this question:

4.

The worst-case time complexity of Quick Sort is________.

O(n2)
O(log n)
O(n)
O(n logn)

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.

Rate this question:

5.

The correct order of the efficiency of the following sorting algorithms according to their overall running time comparison is

Insertion>selection>bubble
Insertion>bubble>selection
Selection>bubble>insertion.
Bubble>selection>insertion

Correct Answer

A. 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.

Rate this question:

6.

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

Insertion sort
Selection sort
Either of a and b
None of the above

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.

Rate this question:

7.

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?

O(nlog n)
O(n)
O(log n)
O(n^2 )

Correct Answer

A. 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).

Rate this question:

8.

The concept of order Big O is important because

It can be used to decide the best algorithm that solves a given problem
It determines the maximum size of a problem that can be solved in a given amount of time
It is the lower bound of the growth rate of algorithm
Both A and B

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.

Rate this question:

9.

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

I and II
II and III
II and IV
III and IV
II, III, and IV

Correct Answer

A. 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.

Rate this question:

10.

In quick sort, the number of partitions into which the file of size n is divided by a selected record is

N
N-1
2
N/2

Correct Answer

A. 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.

Rate this question:

Daa Quiz

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

Quiz Preview

How many passes are required to sort a file of size n by bubble sort method?

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?

The worst-case time complexity of Quick Sort is________.

The correct order of the efficiency of the following sorting algorithms according to their overall running time comparison is

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

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?

The concept of order Big O is important because

In quick sort, the number of partitions into which the file of size n is divided by a selected record is