Daa Quiz

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Syed
S
Syed
Community Contributor
Quizzes Created: 1 | Total Attempts: 1,041
| Attempts: 1,041
SettingsSettings
Please wait...
  • 1/10 Questions

    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

    • O (n log n)
    • O (n2 log n)
    • O (n2 + log n)
    • O (n2)
Please wait...
About This Quiz

The DAA Quiz assesses knowledge in sorting algorithms like Quick Sort, Bubble Sort, and Merge Sort. It delves into complexities, efficiency, and specific algorithm behaviors, crucial for learners in computer science and algorithm design.

Algorithms Quizzes & Trivia

Quiz Preview

  • 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:

Quiz Review Timeline (Updated): Mar 20, 2023 +

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
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.