DAA Quiz

Approved & Edited by ProProfs Editorial Team

The editorial team at ProProfs Quizzes consists of a select group of subject experts, trivia writers, and quiz masters who have authored over 10,000 quizzes taken by more than 100 million users. This team includes our in-house seasoned quiz moderators and subject matter experts. Our editorial experts, spread across the world, are rigorously trained using our comprehensive guidelines to ensure that you receive the highest quality quizzes.

Learn about Our Editorial Process

| By Syed

Syed

Community Contributor

Quizzes Created: 1 | Total Attempts: 1,039

Questions: 10 | Attempts: 1,039 | Updated: Mar 20, 2023

Questions

Settings

Feedback

During the Quiz End of Quiz

Difficulty

Sequential Easy First Hard First

Play as

Quiz Flashcard

Create your own Quiz

Share on Facebook Share on Twitter Share on Whatsapp Share on Pinterest Share on Email Copy to Clipboard Embed on your website

Questions and Answers

1.

In quick sort, the number of partitions into which the file of size n is divided by a selected record is
- A.
  
  N
- B.
  
  N-1
- C.
  
  2
- D.
  
  N/2
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.

Rate this question:
2.

How many passes are required to sort a file of size n by bubble sort method?
- A.
  
  N2
- B.
  
  N
- C.
  
  N-1
- D.
  
  N/2
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.

Rate this question:
3.

The worst-case time complexity of Quick Sort is________.
- A.
  
  O(n2)
- B.
  
  O(log n)
- C.
  
  O(n)
- D.
  
  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:
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
- A.
  
  O (n log n)
- B.
  
  O (n2 log n)
- C.
  
  O (n2 + log n)
- D.
  
  O (n2)
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).

Rate this question:
5.

The correct order of the efficiency of the following sorting algorithms according to their overall running time comparison is
- A.
  
  Insertion>selection>bubble
- B.
  
  Insertion>bubble>selection
- C.
  
  Selection>bubble>insertion.
- D.
  
  Bubble>selection>insertion
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.

Rate this question:
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?
- A.
  
  O(nlog n)
- B.
  
  O(n)
- C.
  
  O(log n)
- D.
  
  O(n^2 )
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).

Rate this question:
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
- A.
  
  I and II
- B.
  
  II and III
- C.
  
  II and IV
- D.
  
  III and IV
- E.
  
  II, III, and IV
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.

Rate this question:
8.

The concept of order Big O is important because
- A.
  
  It can be used to decide the best algorithm that solves a given problem
- B.
  
  It determines the maximum size of a problem that can be solved in a given amount of time
- C.
  
  It is the lower bound of the growth rate of algorithm
- D.
  
  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.

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
- A.
  
  Insertion sort
- B.
  
  Selection sort
- C.
  
  Either of a and b
- D.
  
  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:
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?
- A.
  
  Mergesort
- B.
  
  Quicksort
- C.
  
  Insertion sort
- D.
  
  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:

Quiz Review Timeline +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

Current Version
Mar 20, 2023

Quiz Edited by
ProProfs Editorial Team
Mar 14, 2019

Quiz Created by
Syed

Daa Quiz

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

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

The worst-case time complexity of Quick Sort is________.

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

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

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

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

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?