AMCAT COMPUTER PROGRAMMMING PREVIOUS QUESTIONS (PAPERS)-2

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 Op: 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 Op: 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 Op: 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 Op: 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 Op: 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 Op:D

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 Op: 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 Op: 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 Op: 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 Op:B
Selection sort uses least operations