Prudence fake exam

Compiled by Brandon Skerritt

Question 1

Question 2

What does the following psuedocode output when n is 4?

product <- 1
for <- 1 to n do
    product <- product * i
output product

1. • 1
2. • 0
3. • 10
4. • 24
5. • 4

Question 1.2

What is the big O notation for this?

1. • O(n)
2. • O(n^3)
3. • O(log n)
4. • O(n^2)

Question 3

Question 4

Consider the following psuedo code to search if a value key is in a linked list and an instance of the linked list. What is being output at the end of the code if key is:

1. 25
2. 40

node ← head, found ← false
while node != NIL and found != true do
begin
    if node.data == key then
        found ← true
    node ← node.next
end
if found == true then
    output "FOUND!"
else output "NOT FOUND!"

• • 1. true 2. false
• • 1. NOT FOUND! 2. FOUND!
• • 1. true 2. true
• • 1. FOUND!. 2. FOUND!
• • 1. FOUND!. 2. NOT FOUND!

Question 5

Question 6

State the order of growth of the following functions:

10n²log n + n log² n + 2n³ + 30n + 100

1. • O(n² log n)
2. • O(n³)
3. • O(100)
4. • O(30n)
5. • O(n log² n)

Question 7

Consider the following binary tree rooted at the vertex r. What are the orders of vertices in an in-order traversal?

1. • r, a, b, c, d, e, f
2. • r, a, c, f, d, b, e
3. • f, c, d, a, e, b, r
4. • f, e, d, e, a, b, r
5. • c, f, a, d, r, e, b

Question 8

Which of the following statements is incorrect?

1. • Dynamic programming uses recursion.
2. • Dynamic programming uses a table.
3. • Dynamic programming computes solutions in a bottom up manner.
4. • Dynamic programming needs a base case.
5. • All are correct

Question 9

Question 10