# 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
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

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

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