# 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

Ques34. 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?
Op 1: Use bubble sort to sort the list in descending order and then print the first
number of the series.
Op 2: Use selection sort to sort the list in descending order and then print the first
number of the series.
Op 3: Implement one iteration of selection sort for descending order and print the
first number in the series.
Op 4: None of these
Op 5:
Correct Op : 3

Ques35. Lavanya wants to find the smallest number out of 26 inputted numbers. How
many minimum comparisons he has to make?
Op 1: 25
Op 2: 13
Op 3: 26
Op 4: 52
Op 5:
Correct Op : 1

Ques43. What is space complexity of a program?
Op 1: Amount of hard-disk space required to store the program
Op 2: Amount of hard-disk space required to compile the program
Op 3: Amount of memory required by the program to run
Op 4: Amount of memory required for the program to compile
Op 5:
Correct Op : 3

Ques44. 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?
Op 1: Fixed part
Op 2: Variable Part
Op 3: Product of fixed part and variable part
Op 4: None of these
Op 5:
Correct Op : 2

Ques45. While calculating time complexity of an algorithm, the designer concerns
himself/herself primarily with the run time and not the compile time. Why?
Op 1: Run time is always more than compile time.
Op 2: Compile time is always more than run time.
Op 3: Compile time is a function of run time.
Op 4: A program needs to be compiled once but can be run several times.
Op 5:
Correct Op : 4

Ques46. 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 operands is same, which of the following is true?
Op 1: Code A uses lesser memory and is slower than Code B
Op 2: Code A uses lesser memory and is faster than Code B
Op 3: Code A uses more memory and is faster than Code B
Op 4: Code A uses more memory and is slower than Code B
Op 5:
Correct Op : 1

Ques47. 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?
Op 1: &theta(n^2)
Op 2: &theta(n)
Op 3: &theta(n*log(n))
Op 4: None of these
Op 5:
Correct Op : 2

Ques48. Tarang writes an efficient program to add two upper triangular 10X10 matrices
(elements on diagonal retained). How many total additions will his program make?
Op 1: 100
Op 2: 55
Op 3: 25
Op 4: 10
Op 5:
Correct Op : 2

Ques50. 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?
Op 1: &theta(n^2)
Op 2: &theta(n)
Op 3: &theta(log3(n))
Op 4: &theta(3n
)
Op 5:
Correct Op : 3

Ques51. 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?
Op 1: &theta(n^2)
Op 2: &theta(n)
Op 3: &theta(n1/2)
Op 4: &theta(log(n))
Op 5:
Correct Op : 2

Ques52. 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.
Op 1: &theta(n^2)
Op 2: &theta(n)
Op 3: &theta(1)
Op 4: None of these
Op 5:
Correct Op : 3

Ques53. 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 loop iterates over the rows, while the inner loop iterates
over the columns. Shashi writes a code (Code B), where the outer loop iterates over
the columns, while the inner loop iterates over rows. Which of the following is true
with regard to their code ignoring any caching or memory storage effects?
Op 1: Code A is faster than Code B
Op 2: Code B is faster than Code A
Op 3: Code A and Code B will run in the same amount of time
Op 4: The comparison between the speed of the codes cannot be made.
Op 5:
Correct Op : 2

Ques54. 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?
Op 1: It has a time complexity of O(n3
)
Op 2: It has a time complexity of O(n4
)
Op 3: It has a time complexity of O(n2
)
Op 4: It has a time complexity of &theta(n3
)
Op 5:
Correct Op : 3

Ques55. 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?
Op 1: Both codes have same complexity
Op 2: The first code has higher time complexity than the second
Op 3: The second code has lower time complexity than the first code.
Op 4: Both codes are the same.
Op 5:
Correct Op : 2

Ques56. 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?
Op 1: Both code have the same time complexity
Op 2: Code A has higher time complexity
Op 3: Code B has higher time complexity
Op 4: No comparison can be made between the time complexity of the two codes.
Op 5:
Correct Op : 2

Ques57. 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?
Op 1: It is O(n)
Op 2: It is O(n2
)
Op 3: It is &theta(n)
Op 4: It is &omega(n)
Op 5:
Correct Op : 4

Ques58. 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?
Op 1: Code A
Op 2: Code B
Op 3: Gautam cannot determine
Op 4: Both codes have the same execution time, so deliver any.
Op 5:
Correct Op : 3

Ques59. 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?
Op 1: Code A
Op 2: Code B
Op 3: Surbhi cannot determine
Op 4: Both codes have the same execution time, so deliver any.
Op 5:
Correct Op : 1

Ques60. 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?
Op 1: Code A
Op 2: Code B
Op 3: Vibhu cannot determine
Op 4: Both codes have the same execution time, so deliver any.
Op 5:
Correct Op : 3

Ques61. 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?
Op 1: Code A
Op 2: Code B
Op 3: Both codes have the same execution time, so deliver any.
Op 4: None of these
Op 5:
Correct Op : 1

Ques61. Code A has to execute 4*n2 + 64 program statements, while Code B has to
execute 32*n program statements for a problem of size n. The time for executing a
single program statement is same for all statements. Rajesh was given a problem
with a certain size k and he delivered Code A. What could be the possible value of k?
Op 1: 1000
Op 2: 5
Op 3: 10
Op 4: 3
Op 5:
Correct Op : 4

Ques120. To solve a problem, it is broken in to a sequence of smaller sub-problems, till a
stage that the sub-problem can be easily solved. What is this design approach called?
Op 1: Top-down Approach
Op 2: Bottom-Up Approach
Op 3: Procedural Programming
Op 4: None of these
Op 5:
Correct Op : 1

Ques121. The time complexity of linear search algorithm over an array of n elements is
Op 1: O (log2 n)
Op 2: O (n)
Op 3: O (n log2 n )
Op 4: O (n2
)
Op 5:
Correct Op : 2

Ques122. Rajesh implements queue as a singly-linked linked list. The queue has n
elements. The time complexity to ADD a new element to the queue:
Op 1: O (1)
Op 2: O (log2 n)
Op 3: O (n)
Op 4: O (n log2 n )
Op 5:
Correct Op : 1

Ques123. The time required to insert an element in a stack with linked list
implementation is
Op 1: O (1)
Op 2: O (log2 n)
Op 3: O (n)
Op 4: O (n log2 n )
Op 5:
Correct Op : 1

Ques124. In the following sorting procedures, which one will be the slowest for any
given array?
Op 1: Quick sort
Op 2: Heap sort
Op 3: Merge Sort
Op 4: Bubble sort
Op 5:
Correct Op : 4

Ques125. Pankaj stores n data elements in a hash table. He is able to get the best
efficiency achievable by a hash table. What is the time complexity of accessing any
element from this hash table?
Op 1: O(1)
Op 2: O(n2
)
Op 3: O(log n)
Op 4: O(n)
Op 5:
Correct Op : 1

Ques126. Every element of a data structure has an address and a key associated with it.
A search mechanism deals with two or more values assigned to the same address by
using the key. What is this search mechanism?
Op 1: Linear Search
Op 2: Binary search
Op 3: Hash Coded Search
Op 4: None of these
Op 5:
Correct Op : 3

Ques127. The order of magnitude of the worst case performance of a hash coded search
(over N elements) is
Op 1: N
Op 2: N log2 N
Op 3: log2 N
Op 4: not dependent upon N
Op 5:
Correct Op : 1

Ques128. A sorting algorithm traverses through a list, comparing adjacent elements and
switching them under certain conditions. What is this sorting algorithm called?
Op 1: insertion sort
Op 2: heap sort
Op 3: quick sort
Op 4: bubble sort
Op 5:
Correct Op : 4

Ques129. A sorting algorithm iteratively traverses through a list to exchange the first
element with any element less than it. It then repeats with a new first element. What
is this sorting algorithm called?
Op 1: insertion sort
Op 2: selection sort
Op 3: heap sort
Op 4: quick sort
Op 5:
Correct Op : 2

Ques130. A sort which uses the binary tree concept such that any number in the tree is
larger than all the numbers in the subtree below it is called
Op 1: selection sort
Op 2: insertion sort
Op 3: heap sort
Op 4: quick sort
Op 5:
Correct Op : 3

Ques131. The average time required to perform a successful sequential search for an
element in an array A(1 : n) is given by
Op 1: (n+1) / 2
Op 2: log2n
Op 3: n(n+1) / 2
Op 4: n2
Op 5:
Correct Op : 1

Ques132. How many comparisons are needed to sort an array of length 5 if a straight
selection sort is used and array is already in the opposite order?
Op 1: 1
Op 2: 10
Op 3: 50
Op 4: 20
Op 5:
Correct Op : 2

Ques159. An array contains the following elements in order: 7 6 12 30 18. Insertion sort
is used to sort the array in ascending order. How many times will an insertion be
made?
Op 1: 2
Op 2: 3
Op 3: 4
Op 4: 5
Op 5:
Correct Op : 1

Ques160. An array of 5 numbers has the following entries in order: 7 4 5 10 8. Prashant
uses selection sort to sort this array in descending order. What will the array contain
after two iterations of selection sort?
Op 1: 10 8 7 5 4
Op 2: 10 8 5 7 4
Op 3: 8 10 5 7 4
Op 4: None of these
Op 5:
Correct Op : 2

Ques161. Srishti writes a program to find an element in the array A[5] with the following
elements in order: 8 30 40 45 70. She runs the program to find a number X. X is
found in the first iteration of binary search. What is the value of X?
Op 1: 40
Op 2: 8
Op 3: 70
Op 4: 30
Op 5:
Correct Op : 1

Ques161. Srishti writes a program to find an element in the array A[5] with the following
elements in order: 8 30 40 45 70. She runs the program to find a number X. X is
found in the first iteration of binary search. What is the value of X?
Op 1: 40
Op 2: 8
Op 3: 70
Op 4: 30
Op 5:
Correct Op : 1

Ques162. The array A has n elements. We want to determine the position of X in the
array. We know that X is present in the array A and X can be present at any location
in the array with equal probability. How many comparisons will be required on
average to find the element X using linear search?
Op 1: n
Op 2: (n+1)/2
Op 3: 2*n
Op 4: n^2
Op 5:
Correct Op : 2