Prudence fake exam

Compiled by Brandon Skerritt

Question 1

img

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
    • 0
    • 10
    • 24
    • 4

Question 1.2

What is the big O notation for this?

    • O(n)
    • O(n^3)
    • O(log n)
    • O(n^2)

Question 3

img

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!"

img

Question 5

img

Question 6

State the order of growth of the following functions:

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

    • O(n² log n)
    • O(n³)
    • O(100)
    • O(30n)
    • 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?

img

    • r, a, b, c, d, e, f
    • r, a, c, f, d, b, e
    • f, c, d, a, e, b, r
    • f, e, d, e, a, b, r
    • c, f, a, d, r, e, b

Question 8

Which of the following statements is incorrect?

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

Question 9

img

Question 10

img