AMCAT Previous Years Questions on Miscellaneous : Searching and Sorting Complexity Theory

Topics
Sub- Topics
Expected Questions
Basic Programming
10 – 12 Questions
Data Structures
6 – 8 Questions
OOPs
4 – 6 Questions
Miscellaneous
4 – 5 Questions



Question 1
Which of the following Sorting Algorithm will perform the worst if the numbers are ordered in the opposite form?
A. Quick Sort
B. Radix
C. Bubble
D. Selection



Correct Option : A
Quick sort performs the worst if arranged in alphabetic/ ascending order
 
 

Question 2
Binary Search can have _____ number of maxm comparsions?
A. log(n) + 1
B. 2*log n
C. n
D. (n+1)/2

Correct Option : A
Most number of comparision possible for BST is log(n) + 1
 
Question 3
What is the third number from the left while doing bubble sort in the 3rd iteration for 5 1 4 2 8?
A. 4
B. 5
C. 2
D. 8
Correct Option : A

First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
 
Question 4
Find the 3rd number from the left in the 3rd iteration while doing selection sort for – arr[] = 64 25 12 22 11
A. 22
B. 12
C. 25
D. 64

Correct Option: A
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0…4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1…4] // and place it at beginning of arr[1…4] 11 12 25 22 64 // Find the minimum element in arr[2…4] // and place it at beginning of arr[2…4] 11 12 22 25 64



 

Question 5
In breadth-first search, which of the following options is true?
A. Beginning from a node, first all its adjacent nodes are traversed.
B.Beginning from a node, each adjacent node is fully explored before traversing the next adjacent node
C. Beginning from a node, nodes are traversed in cyclical order
D. none of these

Correct Option: A
a is the answer. https://en.wikipedia.org/wiki/Breadth-first_search




 

Question 6
Which of the following algorithm will be the slowest amongst the following
A. Shell
B. Heap
C. Quick
D. Bubble
 

Correct Option: A
Check here – http://prepinsta.com/time-complexities-placements/
 
Question 7
Select the appropriate code that performs bubble sort. a)
for(int j=arr.length-1; j>=0; j–)
{
for(int k=0; k<j; k++)
{
if(arr[k] > arr[k+1])
{
int temp = arr[k];
arr[k] = arr[k+1];
arr[k+1] = temp;
}
}
}
b)
for(int j=arr.length-1; j>=0; j–)
{
for(int k=0; k<j; k++)
{
if(arr[k] < arr[k+1])
{
int temp = arr[k];
arr[k] = arr[k+1];
arr[k+1] = temp;
}
}
}
c)
for(int j=arr.length; j>=0; j–)
{
for(int k=0; k<j; k++)
{
if(arr[k] > arr[k+1])
{
int temp = arr[k];
arr[k] = arr[k+1];
arr[k+1] = temp;
}
}
}
A. A
B. B
C. C
D. D

Correct Option: A

The outer loop keeps count of number of iterations, and the inner loop checks to see if swapping is necessary.

 
Question 8
What is the advantage of bubble sort over other sorting techniques?
A. It is faster
B. Consumes less memory
C. Detects whether the input is already sorted
D. All of the mentioned

Correct Option: C 



 

Question 9
The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?
A. 4
B. 2
C. 1
D. 0

Correct Option: B
There are only 2 elements that are unsorted thus 2 is the answers you can do the iterations also to verify this 


 

Question 10
Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general?
A. Insertion sort
B. Selection sort
C .Heap sort
D. None




Correct Option: A
Selection sort uses least operations

Question. 1 A code with θ(n) and θ(n^2). Which code will execute faster for a code of size J?
A. θ(n)
B. θ(n2)
C. Cant be said as size of J is unknown
D. Both will be equal

Correct Option: C
Cant be determined as the size of K is not known.

 
Question 2
In regards to time complexity which will perform better ω(n^4) or O(n^3)?
A. ω(n^4)
B. O(n^3)
C. Both Equally
D. Cant be said

Correct Option: A
ω(n^4) as it is omega is measured for best time complexity

Question 3
In case of the worst timing, which might be the worst to implement in sorting algorithm?
A. Quick
B. Merge
C. Tim
D. Heap
 
Correct Option: A 
Quick sort has worse time complxity of O(n^2)

Question 4
The time required to insert in the Queue is?
A. O(n)
B. O(n^2)
C. O(1)
D. O(log n)

Correct Option: C
 
Question 5
Which of the following has the quickest average time complexity?
A. Quick
B. Radix
C. Bubble
D. Heap
 

Correct Option: B
Radix sort is quickest amongst these in average time

 
Question 6
There are 2 buildings and on each’s window, a flower pot is kept. Ravi’s mother tells him to multiply each cell/window to the other and store in a matrix? What would be time complexity if he writes a code to do so?
A. Omega(n)
B. Omega(n^2)
C. Theta (n)
D. Theta (n^2)
 

Correct Option: D
Two for loops thus, Theta (n^2)

 
Question 7
There are 2 buildings and on each’s window, a flower pot is kept. Ravi’s mother tells him to add each cell/window to the other and store in a matrix? What would be time complexity if he writes a code to do so?
A. Theta(n)
B. Theta( log n)
C. Theta(n^2)
D. Theta(n log n)
 

Correct Option: A
Theta(n) will be the answer

 
Question 8
What is space complexity of the program?
A. Amount of hard disk space required to store the program.
B. Amount of hard disk space required to compile the program.
C. Amount of memory required by the program to run.
D. Amount of memory required by the program to compile 

Correct Option: C