Foundations

Phase 0 Checkpoint: 15 questions on the foundations.

⏱️

15 questions · 21 marks · 40 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1NAT1 markLoop count

How many times does the body of for (i = 2; i <= 200; i += 2) run?

Numerical answer: ________

Q2NAT2 marksNested count

How many times does x++ run when n = 20?

for (i = 0; i < n; i++)
    for (j = 0; j < n; j += 2)
        x++;

Numerical answer: ________

Q3MCQ1 markCorrectness

A loop invariant is:

• (A) a condition that is false before the loop
• (B) a statement true before every iteration of the loop
• (C) a variable that never changes
• (D) the number of iterations

Q4NAT1 markLog

log₂(1/8) = ?

Numerical answer: ________

Q5NAT2 marksDoubling loop

How many times does the body run when n = 1000?

for (i = 1; i < n; i = i * 2)
    count++;

Numerical answer: ________

Q6NAT2 marksSum

Σ i for i = 1 … 200, minus Σ i for i = 1 … 100?

Numerical answer: ________

Q7MCQ1 markSwap rule

n^(log n) equals:

• (A) 2ⁿ
• (B) n²
• (C) 2^(log² n)
• (D) log(nⁿ)

Q8NAT1 markLinked list

Steps (pointer moves) from the head to reach the 20th node of a singly linked list?

Numerical answer: ________

Q9MSQ2 marksStacks and queues

Which are true?

• (A) A circular array gives constant-time enqueue and dequeue.
• (B) A queue removes the oldest element first.
• (C) Popping from a stack costs time proportional to its size.
• (D) A stack removes the most recently added element first.

Q10NAT1 markNodes at a level

Maximum number of nodes at level 5 of a binary tree (root at level 0)?

Numerical answer: ________

Q11NAT2 marksHeap insertion

Insert 10, 20, 15, 30, 40 one by one into an empty max-heap. Final array (1-based): what is at index 5?

Numerical answer: ________

Q12MCQ1 markBST worst case

The worst-case cost of searching a BST with n nodes is proportional to:

• (A) n log n
• (B) 1
• (C) n
• (D) log n

Q13NAT1 markEdges of a tree

A forest of 3 trees has 30 vertices in total. How many edges?

Numerical answer: ________

Q14NAT2 marksMax edges

A simple undirected graph has 15 vertices. Maximum number of edges?

Numerical answer: ________

Q15NAT1 markSix towns

How many edges does the six-town graph have?

Numerical answer: ________