COS2611 EXAM PACK 2023

COS2611 EXAM
PACK 2023




UPDATED REVISION
PACK

, MCQ
October 2017
1. Which of the following functions is ordered by growth rate from largest to smallest?
ORDERS OF MAGNITUDE (small to large): 1, N, log , Nlog , N , N , 2 , N!
a. Nlog , 2 , N , 2
b. 2 , Nlog , N , 2
c. 2 , N , Nlog , 2
d. 2 , 2 , N , Nlog
e. 2 , N , 2 , Nlog
2. What is the running time of the following code fragment?
for (int i = 0; i < 5n; i++) 1; 5N + 1; 5N = 10N + 2
sum++; O(N)
a. O(1)
b. O(N)
c. O(log )
d. O(Nlog )
e. O(N )

Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2) 1; 10001; 10000/2 = O(1)
2. for (int k = 1; k <= n; k++) 1; N + 1; N = 2N + 2
3. sum++; (2N + 2) ∗ 1

4. for (int p = n; p > 1; p /= 2) 1; N + 1; log= N + 2 + log
5. for (int q = 0; q < 500; q++) 1; 501; 500 = O(1)
6. sum--; (log + N + 2) ∗ 1
3. How many times is statement 3 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(Nlog )
e. O(log )
4. How many times is statement 6 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
5. What is running time of the entire code fragment?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
6. An algorithm takes 5 seconds for an input size of 10. How long will it take for an input size of 20 if the
running time is(NO )?
∗
5sec = 10 ; 𝑥sec = 20 𝑥sec =
a. 2s
b. 4s
c. 30s
d. 40s
e. None of the above
7. An algorithm takes 5 seconds for an input size of 500. How large a problem can be solved in 50 seconds
(N)?
if the running time is linear O
∗
5sec = 500; 50sec = 𝑥 𝑥 =
a. 50
b. 500
c. 5000

, d. 50000
e. None of the above

Consider the following list where each node is of type nodeType and answer questions 8, 9 and 10.




8. What is the output of the following C++ code?
while (p->link != NULL)
{
p = p->link->link;
q = q->link;
cout << q->info << ", ";
}
START(p: 10, q: 25); p:q:25,60; p: 50,
q: 50; p: 70,
q:24
a. 50, 60, 70,
b. 25, 50, 60, 70,
c. 60, 50, 25,
d. 25, 60, 50,
e. None of the above
9. What is the output of the following C++ code?
while (p->link != NULL)
{
p = p->link->link;
q = q->link;
cout << q->link->info << ", ";
}
START(p: 10, q: 25
); p: 25, q: 60,
q → link = 50; p, q: q50,
→ link = 24; p: 70, q:q→link=70
24,
a. 50, 24, 25,
b. 60, 24, 70,
c. 25, 50, 70,
d. 50, 24, 70,
e. None of the above
10. What is the output of the following C++ code?
while (q != NULL)
{
p = p->link;
cout << q->info << ", ";
q = p->link->link;
}
START(p: 10, q: 25
) ; p: 20,
q → info: 25
, q: 60; p: 25,
q → info: 60
, q: 50; p: 60,
q → info: 50
, q: 24; p: 50,
q → info: 24
, q: 70
a. 25, 60, 50,
b. 25, 60, 50, 24,
c. 20, 60, 50, 24, 70,
d. 25, 60, 50, 24, 70,
e. None of the above


May 2017
1. What is the Big-Oh value for the following function: 3n + 2n ++nlog
6n ?
a. O(N )
b. O(N )
c. O(N )
d. O(N )
e. O(Nlog )
2. What is the running time for the following code fragment?
int sum = 0; 1
int i = 2; 1

while (i < n) N+1
{
sum += i; N

, i += 2; N 𝑇𝑜𝑡𝑎𝑙 =3N+3
}
a. O(1)
b. O(N)
c. O(log )
d. O(Nlog )
e. O(N )

Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j < n; j++) 1; N + 1; N = 2N + 2 = O(N)
2. for (int k = 1; k <= n; k++) 1; N + 1; N
3. sum++; (3N + 2) ∗ N = 3N + 2N

4. for (int p = n; p > 1; p /= 2) 1; N + 1; log= N + 2 + log
5. for (int q = 0; q <= 500; q += 4) 1; 501; 125 = O(1)
6. sum--; (N + 2 + log ) ∗ 1
3. How many times is statement 3 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(Nlog )
e. O(log )
4. How many times is statement 6 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
5. What is the running time of the entire code fragment?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
6. An algorithm takes 2 seconds for an input size of 10. How long will it take for an input size of 20 if the
running time is(2O )?
∗
2sec = 2 ; 𝑥sec = 2 𝑥sec =
a. 2s
b. 4s
c. 30s
d. 64s
e. None of the above
7. An algorithm takes 5 seconds for an input size of 500. How large a problem can be solved in 40 seconds
(N)?
if the running time is linear O
∗
5sec = 500; 40sec = 𝑥 𝑥 =
a. 4
b. 40
c. 400
d. 4000
e. None of the above

Consider the following list where each node is of type nodeType and answer questions 8, 9 and 10.




8. What is the output of the following C++ code?
while (p->link != NULL)
{
cout << q->info << ", ";