FE Electrical Software Engineering Practice Problems

sum = 0
for i = 1 to 5
    sum = sum + i
end for

Answer: C) 15

The loop variable takes the values 1, 2, 3, 4, 5 in turn - a 'for ... to' loop in the exam's pseudocode includes both end values - and each is added to the running total:

$$0 \to 1 \to 3 \to 6 \to 10 \to 15$$

That is \(1 + 2 + 3 + 4 + 5 = 15\), or in closed form \(n(n+1)/2\) with \(n = 5\). The accumulator pattern - initialise to zero, add inside the loop - is the most common loop there is, and the two things to check are that the total starts at 0 and that the last value of \(i\) is really included.

10 is the sum through 4, the last iteration dropped - the result of reading 'to 5' as 'while less than 5'.

5 is the final value of \(i\) itself, mistaken for the sum.

20 is one extra term, as if the loop ran to 6 and then stopped short, or \(4 \times 5\) from a misremembered formula.

Answer: B) 4

Quadratic time means the running time is proportional to the square of the input size. Doubling the input squares the doubling:

$$\dfrac{T(2n)}{T(n)} = \dfrac{c(2n)^2}{cn^2} = \dfrac{4cn^2}{cn^2} = 4$$

The constant \(c\) cancels, and so does \(n\): for any polynomial the ratio is the same whatever the starting size, which is exactly why Big O is useful. It tells you how an algorithm scales without knowing how fast the machine is. The rule generalises: an \(O(n^k)\) algorithm slows by \(2^k\) when the input doubles, so the exponent is the whole story.

2 is the linear answer, \(O(n)\): doubling the input doubles the work. A quadratic algorithm does worse than that because every element interacts with every other.

8 is \(2^3\), the factor for a cubic algorithm.

16 is \(2^4\), or equivalently the factor of 4 squared a second time - the doubling applied to the exponent as well as to the input.

Answer: A) Right child of node 12

Handbook: FE Reference Handbook 10.6, Software Engineering → Data Structures, p. 416 (PDF viewer: page 421) defines a tree and notes that "a binary tree is a specialized case where each parent node can have no more than two children nodes." The Handbook does not state the ordering rule that makes a binary tree a binary search tree, so do not spend exam time looking for it: in a BST every value in a node's left sub-tree is smaller than the node and every value in its right sub-tree is larger. Insertion follows that rule down from the root until it reaches an empty child slot.

Step 1 – Descend from the root.

At 20: \(14 < 20\) → go left, to 10.

At 10: \(14 > 10\) → go right, to 12.

At 12: \(14 > 12\) → go right. Node 12 has no right child, so the descent stops here.

Step 2 – Place the node: 14 becomes the right child of 12. Check the result: 14 sits in 10's right sub-tree (all values there must exceed 10 — true) and in 20's left sub-tree (all values there must be below 20 — true).

Step 3 – Eliminate the distractors:

(B) Left child of 22 is where you land by reversing the very first comparison: treating 14 as greater than 20 sends the search right to 30, then left to 25, then left to 22, then left again. Every later step is correct — only the root comparison was wrong.

(C) Right child of 10 stops one level too early. That position is not empty; it already holds 12, and the search must continue past it.

(D) Left child of 12 would require \(14 < 12\). That slot is reserved for values between 10 and 12.

Step 4 – Answer: The correct answer is (A) Right child of node 12.

Cost: the insertion took three comparisons, one per level. That is why the Handbook's Big-O table on p. 417 lists a Binary Search Tree as \(O(\log n)\) on average — and \(O(n)\) in the worst case, when the tree degenerates into a chain.

Answer: D) 8

All four keys end in 5, so all four hash to the same home slot, and linear probing has to find each one a new place:

\(h(25) = 5\), slot 5 is free: 25 goes in slot 5.

\(h(35) = 5\), slot 5 is taken; probe 6, free: 35 goes in slot 6.

\(h(45) = 5\), slots 5 and 6 are taken; probe 7, free: 45 goes in slot 7.

\(h(15) = 5\), slots 5, 6 and 7 are taken; probe 8, free: 15 goes in slot 8.

The Handbook describes the hash table as an array of buckets or slots that the hash function indexes into; what happens on a collision is up to the implementation, and this one keeps walking forward. The example shows the weakness of that choice: the four colliding keys have formed a run of occupied slots, and any later key hashing to 5, 6, 7 or 8 will have to walk past all of them. That growth of runs is called primary clustering, and it is why probing tables are kept well under full.

5 is the home slot, the answer if collisions were ignored - but a slot holds one key, and 25 is already there.

6 and 7 are where the probe sequence stops for 35 and 45 respectively; a candidate who stops probing after the first or second occupied slot lands on one of them. Key 15 arrives last and has to pass all three.

Answer: D) 6

Handbook: FE Reference Handbook 10.6, Software Engineering → Flow Chart Definition, p. 418 (PDF viewer: page 423), for the symbols: rounded box = start or stop point, rectangle = process/operation, diamond = decision. The Euclidean algorithm itself does not appear anywhere in the Handbook, so the flowchart is the complete specification — do not spend exam time searching for a gcd formula.

Step 1 – Read the function. If \(b = 0\) the function returns \(a\). Otherwise it computes the remainder \(r = a \bmod b\), calls itself as \(\text{gcd}(b, r)\), and returns whatever that call returns.

Step 2 – Descend through the calls:

\(\text{gcd}(48, 18)\): \(b \neq 0\), \(r = 48 \bmod 18 = 12\) → call \(\text{gcd}(18, 12)\)

\(\text{gcd}(18, 12)\): \(b \neq 0\), \(r = 18 \bmod 12 = 6\) → call \(\text{gcd}(12, 6)\)

\(\text{gcd}(12, 6)\): \(b \neq 0\), \(r = 12 \bmod 6 = 0\) → call \(\text{gcd}(6, 0)\)

\(\text{gcd}(6, 0)\): \(b = 0\) → return \(a = 6\)

Step 3 – Unwind. Each caller returns v unchanged, so the 6 travels back up through all three levels and \(\text{gcd}(48, 18) = 6\).

Step 4 – Check the result: \(48 = 6 \times 8\) and \(18 = 6 \times 3\), and no larger value divides both.

Step 5 – Eliminate the distractors:

(A) 18 is simply the second argument, returned without recursing. The function returns \(b\) only in the sense that \(b\) becomes the \(a\) of the next call — never on the first pass, since \(b \neq 0\) here.

(B) 12 is the first remainder, \(48 \bmod 18\). Stopping there ignores the recursive call — the algorithm continues until the remainder reaches 0.

(C) 3 does divide both 48 and 18, but it is not the greatest such value. Any common divisor will satisfy a spot check; only the algorithm identifies the largest.

Step 6 – Answer: The correct answer is (D) 6.