# CS502 Quiz 1 Solved Fall 2012

Question # 1
In in-place sorting algorithm is one that uses arrays for storage:

Both of above may be true according to algorithm
More than 3 arrays of one dimension.

Question # 2
Which sorting algorithm is faster :

O(n^2)
O(nlogn)
O(n+k)
O(n^3)

Question # 3
In stable sorting algorithm:

One array is used
In which duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative position after sorting.

Question # 4
Counting sort has time complexity:

O(n)
O(n+k)
O(k)
O(nlogn)

Question # 5
Counting sort is suitable to sort the elements in range 1 to k:
Select correct option:
K is large
K is small
K may be large or small
None

Question # 6
Memorization is :

To store previous results for further use.                                               (I think)
To avoid unnecessary repetitions by writing down the results of recursive calls and looking them again if needed later
To make the process accurate.
None of the above

Question # 7
The running time of quick sort depends heavily on the selection of

No of inputs
Arrangement of elements in array
Size o elements
Pivot elements

Question # 8 of 10 ( Start time: 07:37:25 PM ) Total Marks: 1

Select correct option:
Bubble sort
Insertion sort
Both of above

Question # 9
In Quick sort algorithm, constants hidden in T(n lg n) are
(Don’t Know)
Large
Medium
Not known
small

Question # 10
Quick sort is

Stable and In place
Not stable but in place
Stable and not in place
Some time in place and some time stable

1-One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.

pointers

constants

variables

functions

2- For the heap sort we store the tree nodes in

level-order traversal

in-order traversal

pre-order traversal

post-order traversal

3- The sieve technique works in ___________ as follows

phases

numbers

integers

routines

4- In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,

linear

arithmetic

geometric

exponent

5- We do sorting to,

keep elements in random positions

keep the algorithm run in linear order

keep the algorithm run in (log n) order

keep elements in increasing or decreasing order

6- In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,

T(n)

T(n / 2)

log n

n / 2 + n / 4

7- In which order we can sort?

increasing order only

decreasing order only

increasing order or decreasing order

both at the same time

8- In Sieve Technique we do not know which item is of interest

True

False

9- For the sieve technique we solve the problem,

recursively

mathematically

precisely

10- Divide-and-conquer as breaking the problem into a small number of

pivot

Sieve

sub problems

Selection