Home / Amcat / AMCAT Computer Programming on Miscellaneous Searching and Sorting Question And Answer

AMCAT Computer Programming on Miscellaneous Searching and Sorting Question And Answer

AMCAT Computer Programming on Miscellaneous Searching and Sorting Question And Answer

AMCAT Computer Programming Question And Answer

1. Abhinav wants to find the largest number in a given list of 20 numbers. Which
of the following is an efficient approach to do this?

A) Use bubble sort to sort the list in descending order and then print the first
number of the series.
B) Use selection sort to sort the list in descending order and then print the first
number of the series.
C) Implement one iteration of selection sort for descending order and print the
first number in the series.
D) None of these

Correct Answer : C

2. Lavanya wants to find the smallest number out of 26 inputted numbers. How
many minimum comparisons he has to make?

A) 25
B) 13
C) 26
D) 52

Correct Answer : A

3. What is space complexity of a 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 for the program to compile

Correct Answer : C

4. The memory space needed by an algorithm has a fixed part independent of

the problem instance solved and a variable part which changes according to the

problem instance solved. In general, which of these two is of prime concern to an

algorithm designer?

A) Fixed part

B) Variable Part

C) Product of fixed part and variable part

D) None of these

Correct Answer : B

5. While calculating time complexity of an algorithm, the designer concerns

himself/herself primarily with the run time and not the compile time. Why?

A) Run time is always more than compile time.

B) Compile time is always more than run time.

C) Compile time is a function of run time.

D) A program needs to be compiled once but can be run several times.

Correct Answer : D

6. Pankaj and Mythili were both asked to write the code to evaluate the

following expression:

a – b + c/(a-b) + (a-b)2

Pankaj writes the following code statements (Code A):

print (a-b) + c/(a-b) + (a-b)*(a-b)

Mythili writes the following code statements (Code B):

d = (a-b)

print d + c/d + d*d

If the time taken to load a value in a variable, for addition, multiplication or division

between two Answererands is same, which of the following is true?

A) Code A uses lesser memory and is slower than Code B

B) Code A uses lesser memory and is faster than Code B

C) Code A uses more memory and is faster than Code B

D) Code A uses more memory and is slower than Code B

Correct Answer : A

7. Vrinda writes an efficient program to sum two square diagonal matrices

(matrices with elements only on diagonal). The size of each matrix is nXn. What is the

time complexity of Vrinda’s algorithm?

A) &theta(n^2)

B) &theta(n)

C) &theta(n*log(n))

D) None of these

Correct Answer : B

8. Tarang writes an efficient program to add two upper triangular 10X10 matrices

(elements on diagonal retained). How many total additions will his program make?

A) 100

B) 55

C) 25

D) 10

Correct Answer : B

9. There is an array of size n initialized with 0. Akanksha has to write a code

which inserts the value 3k at position 3k in the array, where k=0,1…(till possible).

Akanksha writes an efficient code to do so. What is the time complexity of her code?

A) &theta(n^2)

B) &theta(n)

C) &theta(log3(n))

D) &theta(3n)

Correct Answer : C

10. There are two matrices A and B of size nXn. The data in both these matrices

resides only at positions where both the indices are a perfect square. Rest all

positions have 0 as the data. Manuj has available a third matrix initialized with 0’s at

all positions. He writes an efficient code to put the sum of A and B in C. What is the

time complexity of Manuj’s program?

A) &theta(n^2)

B) &theta(n)

C) &theta(n1/2)

D) &theta(log(n))

Correct Answer : B

11. Ravi has to add an strictly upper triangular (no elements at diagonal) and a

strictly lower triangular square matrix (no elements at diagonal) and put the result in

a third matrix. What is the time complexity of Ravi’s algorithm? Assume that storing

a value in a memory space takes negligible time, while each addition between values

takes the dominating amount of time.

A) &theta(n^2)

B) &theta(n)

C) &theta(1)

D) None of these

Correct Answer : C

12. We have two 100X3 (rowsXcolumn) matrices containing mid-term exam marks

and end-term exam marks of 100 students. Each row refers to a particular student,

while columns refer to marks in English, Social Sciences and Maths. The end-term

and mid-term marks of each student in each subject have to be added to get his total

score in each subject, to be put in a third matrix (100X3). Parinidhi writes a code

(Code A), where the outer loAnswer iterates over the rows, while the inner loAnswer iterates

over the columns. Shashi writes a code (Code B), where the outer loAnswer iterates over

the columns, while the inner loAnswer iterates over rows. Which of the following is true

with regard to their code ignoring any caching or memory storage effects?

A) Code A is faster than Code B

B) Code B is faster than Code A

C) Code A and Code B will run in the same amount of time

D) The comparison between the speed of the codes cannot be made.

Correct Answer : B

13. A code takes the following code steps (equivalently time unit) to execute:

5*n3 + 6*n2 + 1. Which of the following is not true about the time complexity of the

program?

A) It has a time complexity of O(n3)

B) It has a time complexity of O(n4)

C) It has a time complexity of O(n2)

D) It has a time complexity of &theta(n3)

Correct Answer : C

14. We have two programs. We know that the first has a time complexity O(n2),

while the second has a complexity &omega(n2). For sufficiently large n, which of the

following cannot be true?

A) Both codes have same complexity

B) The first code has higher time complexity than the second

C) The second code has lower time complexity than the first code.

D) Both codes are the same.

Correct Answer : B

15. The time complexity of code A is &theta(n), while for Code B it is

&theta(log(n)). Which of the following is true for sufficiently large n?

A) Both code have the same time complexity

B) Code A has higher time complexity

C) Code B has higher time complexity

D) No comparison can be made between the time complexity of the two codes.

Correct Answer : B

16. Rajini is given an efficient code for summing two nXn matrices and putting the

result in a third matrix. She is asked to find it’s time complexity. She realizes that the

number of iterations required is more than n. What can she claim with regard to the

complexity of the code?

A) It is O(n)

B) It is O(n2)

C) It is &theta(n)

D) It is &omega(n)

Correct Answer : D

17. Gautam is given two codes, A and B, to solve a problem, which have

complexity &theta(n) and &theta(n2) respectively. His client wants to solve a problem

of size k, which Gautam does not know. Which code will Gautam deliver to the client,

so that the execution is faster?

A) Code A

B) Code B

C) Gautam cannot determine

D) Both codes have the same execution time, so deliver any.

Correct Answer : C

18. Surbhi is given two codes, A and B, to solve a problem, which have complexity

O(n3) and &omega(n4) respectively. Her client wants to solve a problem of size k,

which is sufficiently large. Which code will Surbhi deliver to the client, so that the

execution is faster?

A) Code A

B) Code B

C) Surbhi cannot determine

D) Both codes have the same execution time, so deliver any.

Correct Answer : A

19. Vibhu is given two codes, A and B, to solve a problem, which have complexity

O(n4) and &omega(n3) respectively. Her client wants to solve a problem of size k,

which is sufficiently large. Which code will Gautam deliver to the client, so that the

execution is faster?

A) Code A

B) Code B

C) Vibhu cannot determine

D) Both codes have the same execution time, so deliver any.

Correct Answer : C

20. Pavithra is given two codes, A and B, to solve a problem, which have

complexity &theta(n3) and &omega(n3) respectively. Her client wants to solve a

problem of size k, which is sufficiently large. Which code should she deliver to the

client in the present scenario?

A) Code A

B) Code B

C) Both codes have the same execution time, so deliver any.

D) None of these

Correct Answer : A

 

Check Also

AMCAT Logical Reasoning Previous Paper

AMCAT Logical Reasoning Previous Questions And Answers 1:  Statement : Nearly 25% of drivers who …

Leave a Reply

Your email address will not be published. Required fields are marked *