⏱️
15 questions · 21 marks · 45 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.
Q1MCQ1 markCompiler vs interpreter
Which statement is true?
- (A) An interpreter produces an executable file.
- (B) A compiler reports source errors before the program runs.
- (C) Compiled code needs the source program to run.
- (D) An interpreter cannot detect any errors.
Q2NAT2 marksBreak-even
Compile: 4 s. Compiled run: 0.1 s. Interpreted run: 0.5 s. Smallest number of runs at which compiling is strictly cheaper?
Numerical answer: ________
Q3MCQ1 markToolchain
The output of the C compiler proper (before the assembler) is:
- (A) preprocessed C
- (B) assembly language
- (C) an executable
- (D) a relocatable object file
Q4NAT1 markMacro
#define F(x) x*x+x. What is F(1+2)?
Numerical answer: ________
Q5MCQ1 markError phase
Which error is found by the semantic analyzer?
- (A) an illegal character $ in C code
- (B) a missing semicolon
- (C) calling a function with the wrong number of arguments
- (D) an index computed at run time that is out of range
Q6MSQ2 marksError phase
Which of these can a C compiler detect at compile time?
- (A) use of an undeclared variable
- (B) a misspelled keyword such as
retrun x; - (C) division by zero where the divisor is read from input
- (D) unbalanced parentheses
Q7MCQ1 markPhases
Which pair is in the back end?
- (A) lexical analysis, code optimization
- (B) intermediate code generation, code generation
- (C) syntax analysis, semantic analysis
- (D) semantic analysis, code generation
Q8NAT1 markStrings
How many prefixes (including ε and the string itself) does a string of length 9 have?
Numerical answer: ________
Q9NAT2 marksStrings
How many distinct non-empty substrings does abab have?
Numerical answer: ________
Q10MCQ1 markRegex
Which regular expression describes C identifiers?
- (A) [0-9][A-Za-z0-9_]*
- (B) [A-Za-z_][A-Za-z0-9_]*
- (C) [A-Za-z_]+[0-9]
- (D) ([A-Za-z]|[0-9])*
Q11NAT2 marksRegex counting
How many strings of length 4 over {a, b} contain exactly two a’s?
Numerical answer: ________
Q12NAT2 marksDFA
How many states does the minimal DFA have for all strings over {a, b} that end in abb?
Numerical answer: ________
Q13MSQ1 markNFA
Which are true about subset construction?
- (A) Each DFA state is a set of NFA states.
- (B) The DFA start state is the ε-closure of the NFA start state.
- (C) A DFA state is accepting if it contains an accepting NFA state.
- (D) The resulting DFA always has more states than the NFA.
Q14NAT1 markHashing
With h(k) = k mod 5 and chaining, keys 10, 15, 21, 26, 30 are inserted. What is the length of the longest chain?
Numerical answer: ________
Q15MCQ2 marksTrees
A tree’s preorder is A B D E C F and its postorder is D E B F C A. Which node is the parent of F?
- (A) A
- (B) B
- (C) C
- (D) E
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: (B)1 mark
Compile-time errors are reported during translation.
- (A) is wrong: Interpreters produce no target program.
- (C) is wrong: The executable runs alone.
- (D) is wrong: Interpreters detect errors when execution reaches them.
Re-read: Lesson 0.1.1 — Programs, machine code and why we translate; compiler vs interpreter
Q2 Answer: 112 marks
4 + 0.1n < 0.5n ⇒ n > 10 ⇒ 11.
Re-read: Lesson 0.1.1 — Programs, machine code and why we translate; compiler vs interpreter
Q3 Answer: (B)1 mark
The compiler emits assembly; the assembler makes the object file.
- (A) is wrong: That is the preprocessor’s output.
- (C) is wrong: That needs the linker.
- (D) is wrong: That is the assembler’s output.
Re-read: Lesson 0.1.2 — The toolchain: preprocessor, compiler, assembler, linker, loader
Q4 Answer: 81 mark
Textual expansion: 1+2*1+2+1+2 = 1 + 2 + 2 + 1 + 2 = 8 (not 3·3 + 3 = 12).
Re-read: Lesson 0.1.2 — The toolchain: preprocessor, compiler, assembler, linker, loader
Q5 Answer: (C)1 mark
Argument counts are checked against the function’s symbol table entry.
- (A) is wrong: Lexical.
- (B) is wrong: Syntax.
- (D) is wrong: Run time.
Re-read: Lesson 0.1.3 — The phases of a compiler; symbol table; error handler; which phase catches which error
Q6 Answer: (A) (B) (D)2 marks
retrun x; is caught (as a syntax error: name followed by name). Input-dependent division by zero is not.
Re-read: Lesson 0.1.3 — The phases of a compiler; symbol table; error handler; which phase catches which error
Q7 Answer: (B)1 mark
Back end = intermediate code, optimization, code generation (synthesis). Some books start the back end at optimization; both list code generation, and intermediate code generation is never front-end-only analysis.
- (A) is wrong: Lexical analysis is front end.
- (C) is wrong: Both are front end.
- (D) is wrong: Semantic analysis is front end.
Re-read: Lesson 0.1.3 — The phases of a compiler; symbol table; error handler; which phase catches which error
Q8 Answer: 101 mark
n + 1 = 10.
Re-read: Lesson 0.2.1 — Alphabets, strings, languages; sets, union, intersection
Q9 Answer: 72 marks
a, b, ab, ba, aba, bab, abab = 7.
Re-read: Lesson 0.2.1 — Alphabets, strings, languages; sets, union, intersection
Q10 Answer: (B)1 mark
First a letter or underscore, then letters, digits, underscores.
- (A) is wrong: Cannot start with a digit.
- (C) is wrong: Forces a final digit and forbids digits in the middle.
- (D) is wrong: Allows ε and leading digits.
Re-read: Lesson 0.2.2 — Regular expressions (what lexical analysis needs)
Q11 Answer: 62 marks
Choose 2 positions out of 4: C(4,2) = 6.
Re-read: Lesson 0.2.2 — Regular expressions (what lexical analysis needs)
Q12 Answer: 42 marks
States track how much of abb has just been seen: 0, 1, 2 or 3 symbols: 4.
Re-read: Lesson 0.2.3 — Finite automata: DFA, NFA and the idea of converting NFA to DFA
Q13 Answer: (A) (B) (C)1 mark
It may have fewer states than the NFA (the (a|b)*abb NFA has 11 states, its DFA 5).
Re-read: Lesson 0.2.3 — Finite automata: DFA, NFA and the idea of converting NFA to DFA
Q14 Answer: 31 mark
Bucket 0: 10, 15, 30; bucket 1: 21, 26. Longest = 3.
Re-read: Lesson 0.2.4 — Data structures: stack, tree, hash table, directed graph
Q15 Answer: (C)2 marks
Preorder: A root, B starts the first subtree (B, D, E), C starts the second (C, F). In postorder F comes just before C, so F is C’s child.
- (A) is wrong: A is the root; F appears inside C’s block.
- (B) is wrong: B’s block is B, D, E.
- (D) is wrong: E is a leaf under B.
Re-read: Lesson 0.2.4 — Data structures: stack, tree, hash table, directed graph
Wrong on Q → re-read
| Question | Topic | Re-read |
|---|---|---|
| Q1 | Compiler vs interpreter | Lesson 0.1.1 |
| Q2 | Break-even | Lesson 0.1.1 |
| Q3 | Toolchain | Lesson 0.1.2 |
| Q4 | Macro | Lesson 0.1.2 |
| Q5 | Error phase | Lesson 0.1.3 |
| Q6 | Error phase | Lesson 0.1.3 |
| Q7 | Phases | Lesson 0.1.3 |
| Q8 | Strings | Lesson 0.2.1 |
| Q9 | Strings | Lesson 0.2.1 |
| Q10 | Regex | Lesson 0.2.2 |
| Q11 | Regex counting | Lesson 0.2.2 |
| Q12 | DFA | Lesson 0.2.3 |
| Q13 | NFA | Lesson 0.2.3 |
| Q14 | Hashing | Lesson 0.2.4 |
| Q15 | Trees | Lesson 0.2.4 |