CSC320 Test 2019-2020 Session Time: 15 minutes
I. Suppose that you have two different algorithms for solving a problem. To solve a problem of size n, the first algorithm
uses
exactly n(log n) operations and the second algorithm uses exactly n3 2 operations. As n grows, which algorithm uses
fewer
operations?
A. n(log n)
B. nll
2. Give a big-O estimate for the number of operati?ns (where an operation is an addition or a ~1ultiplication) used in
this
segment ofan algorithm. ·
I :=0
for i := I to 3
for j := I to 4
t := t + i*j
A. O(n)
B. O(n 1)
C. 0(/)
D. 0(nlogn) · ·
3. Give a big-O estimate for the number of operations. where an operation is a comparison or a multiplication, used
in this
segment ofan algorithm (ignoring comparisons used to test the coriditions in the for loops, where a,. a2, ... ,.a,, are
positive
real numbers).
m:=O
i :=Ito n
for _
· for j := i + I to n
m := max(a;ai,m)
A. 0(n)
B. O(n1)
C. 0(1)
D. 0(nlogri)
4. Suppose that an element is known to be among the first four elements in a list of 32 elements. Would a linear search
or a
binary search locate this element more rapidly?
A. Linear
B. Binary
S. Give a big-O estimate for the number of comparisons used by the algorithm that determines .the number of Is in
by examining each bitof the string to determine whether· it is a I bit.
a
bit string
A. O(/ogn)
B. O(n)
C. 0(n/ogn)
D. 0(n 1)
6. You are working on an embedded device (an ATM) that only has 4KB (4,096byt_es) of free memory, and you ~ish
to sort .
the 2,000,000 transactions withdrawal history by the amount of money withdrawn(discarding the original order
of
transactions). Choose the most appropriate and efficient sorting algorithms among the four listed below.
A. Bubble Sort B. Insertion Sort C. Merge Sort D. Heap Sort
7. You are running a library catalog. You know that the books in your collection are almost in sorted ascending order
by title,
with the exception of one book which is in the wrong place. You want the catalog to be completely sorted in ascending
order. Choose the most appropriate and efficient sorting algorithms among the four listed below. ·
A. Bubble Sort B. Insertion Sort C. Merge Sort D. Heap Sort
8. Which of the following sorting algorithm does not use recursion?
A. Quick sort B. Merge sort C. Heap sort . D. Insertion sort
9. Which of the following sorting techniques is most etlicicnt if the range of input data is not significantly greater
than a
number of elements to be sorted?
A. Selection sort B." Heap sort C. Counting sort D. Bucket sort
I0. Which of the following sorting algorithm creates a data structure while sorting?
A. Radix sort B. Merge sort C. Heap sort D. Insertion sort.
11. Consider the tree shown below, the node 14 violates the max-heap property. Once maxheapify procedure is applied
to it,
which position will it be in? . ·
1
A. 4
B. 5
C. 8
D. 9
E. 10
12. What is the height of the heap made from an array of length 50?
A. 4
B. · 5
C. 6
D. 7
13. What is the number of leaves of the heap made from an array of length 55?
A. 26 .1 ,
B. 27·
C. 28
D . . 29
14. Big-0mega notation expresses
Tight bounds
A.
Upper bounds
-8.
- - - - -·-=
C,_ l,ower bounds . J.
D. Worst cases
if n =1
15. ~t n be an integer. Finc\KGZS).
1
K~~~ = (lil) ~ l,
1{ : lfn
l .
>1
A. 12
8. 4
C. 13
D. . s . I . '
16. What is the auxiliary spa~e pomplexity of 1nerge sort'l
A. 0(1)
a. O(/ogn)
C . O(n)
D. O(n logn)
!"7. Function_g is a lower bound on funclion/iff for all x,
A. g(x) ~ flx)
B. g(x) ~ t'tx)
C . f= O(g)
D. g=O(t)
18. What is the worst case lime complexity of Quick Sort'!
A. O(n) -
/J. O(nlogn)
C. O(n 1)
D. O(n')
.
Mo
19. Which of the following is not true about comparison based sorting algorithms?
I\. The minimum possible time complexity ofa comparison based sorting algorithm is O(nlogn) for a random input array.
8 . Heap Sort is not' a comparison based sorting algorithm.
C. Any comparison b~Q sorting algorithm can be made stable by using position as a criteria when two elements are
comparea.
D. Counting Sort is not a comparison based sorting algorithm.
20. Which of the following is an example ofan incremi:nlal algorithm?
A. Merge Sort
B. Heap Sort
C. Insertion Sort
D. Quiel,: Sort
