Computer Science Fundamentals: practice problems and exam questions

Number systems, algorithms and complexity, data structures, databases and SQL, and computer networks: the broad base of a first year in computer science.

Practise this course for freePractise this courseTake a mock exam5 free problems every day. No card needed.

Cram pack (PDF)Formula sheets, method steps and practice problems with full solutions, ready to print.

Topics in this course

  1. Number systemsbinary and hex to decimal · two's complement · bits, ranges and memorycalculations
  2. Propositional logic & proofstruth tables · equivalences and proof methods · quantifiers and argumentscalculations
  3. Digital logic: gates, K-maps & flip-flopsgates, truth tables and delays · Boolean algebra, K-maps and multiplexers · don't-cares, flip-flops and counterscalculations
  4. Number theory & modular arithmeticgcd and remainders · inverses and congruences · modular powers and RSAcalculations
  5. Algorithms & complexitykey terms and facts · applying the concepts · cases and analysismultiple choice
  6. Data structureskey terms and facts · applying the concepts · cases and analysismultiple choice
  7. Graph theorydegrees and edges · Euler paths and trees · shortest paths and spanning treescalculations
  8. Databases & SQLkey terms and facts · applying the concepts · cases and analysismultiple choice
  9. Computer networkskey terms and facts · applying the concepts · cases and analysismultiple choice
  10. IPv4 subnettinghosts per subnet · dividing a network · address rangescalculations

Exam tips for Computer Science Fundamentals

  • Convert between binary and hexadecimal in groups of four bits.
  • In SQL, WHERE filters rows before grouping and HAVING filters groups after.
  • State the complexity of the worst case unless the question asks for the average.

Worked examples

Number systemsEasy
place values2256B16E1

Convert the hexadecimal number 0x2BE to decimal. Find N.

0x2BEA = 10 … F = 15

Find N

Show hints
  1. Hex places are worth 1, 16, 256, 4096 from the right.
  2. Replace letters by their values (A = 10 … F = 15), multiply by the place value and add.
  3. 2 = 2, B = 11, E = 14.
Show the answer and the step-by-step solution

Positional number systems: each digit is worth its value times a power of the base. In binary the places are worth 1, 2, 4, 8, 16, …; in hexadecimal 1, 16, 256, …, with A–F standing for 10–15. In 8-bit two's complement the leftmost bit is worth −128 instead of +128, which is how negative numbers are stored.

Multiply each digit by its place value

2·256 + 11·16 + 14·1 = 702

Answer

0x2BE = 702
Propositional logic & proofsMedium
(b → a) ∧ (c → a)b → (c → a)b ∧ (c → a)(b → c) → a

Which formula is logically equivalent to (b ∧ c) → a? Click it.

(b ∧ c) → a
  1. 1(b → a) ∧ (c → a)
  2. 2b → (c → a)
  3. 3b ∧ (c → a)
  4. 4(b → c) → a
Show hints
  1. Equivalent formulas agree in every row of the truth table. One row where they differ rules an option out.
  2. Try a row that makes (b ∧ c) → a 0 and check which options are also 0 there.
  3. Exportation: (a ∧ b) → c ≡ a → (b → c). Both are 0 only when a = 1, b = 1 and c = 0.
Show the answer and explanation

Logical equivalence: two formulas are equivalent (≡) when they have the same value in every row of the truth table. A tautology is 1 in every row, a contradiction is 0 in every row, and a contingency is neither. Useful laws: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositive); ¬(a → b) ≡ a ∧ ¬b; and the distributive laws, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

The law

Exportation: (a ∧ b) → c ≡ a → (b → c). Both are 0 only when a = 1, b = 1 and c = 0.
(b ∧ c) → a ≡ b → (c → a)

Check with the truth table

a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0

Answer

b → (c → a)

The columns after the bar are the options in the order shown.

How practising works

  • “Practise this course” mixes problems from all its topics, like a real exam.
  • Every problem has new values, so you learn the method instead of an answer.
  • Stuck? Open a small hint first, and the full explanation only when you need it.
  • Mock exams are timed and have no hints, and you get your score and a full review at the end.

Calculators for this course

IP subnet calculatorBinary, decimal and hex converterScientific notation calculator (and engineering notation)

Related courses

Computer NetworksData Structures and AlgorithmsDiscrete MathematicsDigital ElectronicsFE Electrical and Computer exam practiceElectronics 1
Practise this course for freePractise this courseTake a mock exam5 free problems every day. No card needed.