Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Divide & Conquer- 2 - Computer Science Engineering (CSE) MCQ

Test: Divide & Conquer- 2 - Computer Science Engineering (CSE) MCQ


Test Description

15 Questions MCQ Test - Test: Divide & Conquer- 2

Test: Divide & Conquer- 2 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Divide & Conquer- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Divide & Conquer- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Divide & Conquer- 2 below.
Solutions of Test: Divide & Conquer- 2 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Divide & Conquer- 2 solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Divide & Conquer- 2 | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Divide & Conquer- 2 - Question 1

Choose the false statements:

Detailed Solution for Test: Divide & Conquer- 2 - Question 1

Internal sorting is such a process that takes place entirely within the main memory of a computer. This is only possible whenever data items, to be sorted, is small enough to be accommodated in main memory. Hence, internal sorting do not need auxiliary storage.
External sorting is just opposite to interval sorting and used when input data, to be sorted, is very large. Hence, external sorting need auxiliary storage.

Test: Divide & Conquer- 2 - Question 2

A sorting technique that guarantees, that records with the same primary key occurs, in the same order in the sorted list as in the original unsorted list is said to be

Detailed Solution for Test: Divide & Conquer- 2 - Question 2

A sorting algorithm is said to be stable sorting algorithm if two objects /records with equal primary key appears in the same order in the sorted list as in the original unsorted list.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Divide & Conquer- 2 - Question 3

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Detailed Solution for Test: Divide & Conquer- 2 - Question 3

Randomized quick sort worst case time complexity = O (n2).

Test: Divide & Conquer- 2 - Question 4

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

List-I (Recursive Algorithm)
P. Binary search
Q. Merge sort
R. Quicksort
S. Tower of Hanoi
List-li (Recurrence Relation)

Which of the following is the correct match between the algorithms and their recurrence relations?

Detailed Solution for Test: Divide & Conquer- 2 - Question 4

Binary search : T(n) = T(n/2) + 1
Merge sort : T(n) = 2T(n/2) + cn
Quick sort : T(n) = T(n - k) + T(k) + cn

Tower of Hanoi : T(n) = 2T(n - 1) + 1

Test: Divide & Conquer- 2 - Question 5

Which of the following sorting algorithms has the lowest worst-case complexity?

Detailed Solution for Test: Divide & Conquer- 2 - Question 5

Test: Divide & Conquer- 2 - Question 6

In the following C function, let n ≥ m.
int gcd(n, m)
{
if (n% m = - 0} return m;
n = n% m;
return gcd (m, n);
}
How many recursive calls are made by this function?

Detailed Solution for Test: Divide & Conquer- 2 - Question 6

Let, T(m, n) be the total number of steps.
So, T(m, 0) = 0, T{m, n) = T{n, m m o d n ) on average

Test: Divide & Conquer- 2 - Question 7

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

Detailed Solution for Test: Divide & Conquer- 2 - Question 7

The relation T(n) = T(n/4) + T(3n/4) + n The pivot element is selected in such a way that it will divide the array into 1/4th and 3/4th always solving this relation give 

Test: Divide & Conquer- 2 - Question 8

The worst case running time to search for an element in a balanced binary search tree with n 2n elements is

Detailed Solution for Test: Divide & Conquer- 2 - Question 8

We know that in balanced BST there are log2n levels in both worst as well as best case where ‘n’ is number of elements

Test: Divide & Conquer- 2 - Question 9

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

Detailed Solution for Test: Divide & Conquer- 2 - Question 9

The recurrence tree for merge sort will have height n and O (n2) work will be done at each level of the recurrence tree (Each level involves ncomparisons and a comparison takes O(n) time in worst case). So time complexity of this merge sort will be O(n2 logn).

Test: Divide & Conquer- 2 - Question 10

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?​

Detailed Solution for Test: Divide & Conquer- 2 - Question 10

In the worst case length of binary search tree can be O(n).
So insertion of an object will take O(n) time in worst case.

Test: Divide & Conquer- 2 - Question 11

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.

Detailed Solution for Test: Divide & Conquer- 2 - Question 11

In worst case the pivot element position may be either first or last. In that case the elements are always divided in 1 : (n - 1) proportion. The recurrence relation for such a proportional division would be

Test: Divide & Conquer- 2 - Question 12

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Detailed Solution for Test: Divide & Conquer- 2 - Question 12

In worst case the BST may be Skewed BST. This case occurs when we insert the elements in increasing order or decreasing order. Example: Consider we insert elements, in the order 1, 12, 39, 43, 50......
The BST would be

To find ‘n’ is the worst case we may have to traverse to bottom of tree which takes O(n) time.
Hence for both insertion and deletion worst case goes to 

Test: Divide & Conquer- 2 - Question 13

The average number of comparisons performed by the merge sort algorithm, in merging two sorted lists of length 2 is

Detailed Solution for Test: Divide & Conquer- 2 - Question 13

Size sorted list has size 2, So, number of comparison is between min (2,2) to (2 + 2 - 1) = 3 So, 2, 3, 3 are number of comparisons.
So average number of comparison

Test: Divide & Conquer- 2 - Question 14

Pick the correct statements:

Detailed Solution for Test: Divide & Conquer- 2 - Question 14

Sequential to be organization suitable for batch processing and not suitable for interactive processing.

Test: Divide & Conquer- 2 - Question 15

Which of the following statements is true?
1. As the number of entries in the hash table increases, the number of collisions increases.
2. Recursive program are efficient.
3. The worst time complexity of quick sort is O(n2).
4. Binary search implemented using a linked list is efficient

Detailed Solution for Test: Divide & Conquer- 2 - Question 15

Recursive programs take more time than the equivalent non-recursive version and so not efficient. This is because of the function call overhead.
In binary search, since every time the current list is probed at the middle, random access is preferred. Since linked list does not support random access, binary search implemented this way is inefficient.

Information about Test: Divide & Conquer- 2 Page
In this test you can find the Exam questions for Test: Divide & Conquer- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Divide & Conquer- 2, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)