I85PREP
⌘ K
Hesse Abitur Computer Science, advanced course - independent foundations study materials
Hesse Abitur Computer Science, advanced course - independent foundations study resources

Hesse Abitur Computer Science, advanced course - independent foundations practice questions

One question at a time. Build your Hesse Abitur Computer Science, advanced course - independent foundations understanding.

First 50 of 190 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Programming, object modelling and software development

In Java, an abstract class:

  1. Cannot be instantiated directly and may contain abstract methods declared without a body Correct answer.
  2. Must contain only static methods
  3. Can never have a constructor declared
  4. Is identical to a primitive type

Explanation

An abstract class models a partial type: it may declare abstract methods (to be implemented by subclasses) and concrete members, but no direct instances - an LK modelling concept beyond GK object basics.

Question 2Programming, object modelling and software development

A Java interface (treating only pre–Java 8 abstract method declarations) specifies:

  1. A contract of method signatures that implementing classes must provide Correct answer.
  2. A concrete superclass with stored attributes
  3. A relational schema for SQL tables
  4. A primitive numeric range

Explanation

An interface declares method signatures without implementation; classes state `implements` and supply bodies. This separates contract from implementation - LK OOP design content.

Question 3Programming, object modelling and software development

In UML, the difference between composition (filled diamond) and aggregation (hollow diamond) is:

  1. Composition ties the part's lifetime to the whole; aggregation does not Correct answer.
  2. Composition forbids any methods on the whole
  3. Aggregation requires the part to be a primitive type
  4. They are identical notations

Explanation

Composition is a strong 'owns' relation: if the whole is destroyed, the parts cease to exist; aggregation is a weaker 'has-a' where parts outlive the whole. This UML distinction is LK-level modelling detail.

Question 4Programming, object modelling and software development

Dynamic (late) binding in Java means that for `Shape s = new Circle();`, the call `s.area()`:

  1. Dispatches to Circle's overridden area() based on the runtime type Correct answer.
  2. Always calls Shape's area() because of the declared type
  3. Cannot compile because types differ
  4. Resolves to a static method of Shape

Explanation

The declared type Shape determines the call's admissibility at compile time, but the runtime type Circle selects the overridden method - the mechanism behind polymorphism, examined at erhöhtes Niveau.

Question 5Programming, object modelling and software development

The Liskov Substitution Principle (informally) requires that:

  1. Subtypes must be usable wherever a supertype is expected without surprising behavior Correct answer.
  2. Subtypes must inherit every attribute as public
  3. Subtypes may weaken the supertype's method signatures arbitrarily
  4. A subtype may remove methods it dislikes

Explanation

LSP is a behavioural subtyping rule: objects of a subtype must honour the supertype's contract so that client code is unchanged. It is a design-by-contract idea at LK depth.

Question 6Programming, object modelling and software development

A class invariant is best described as:

  1. A condition that must hold for every instance before and after each public method call Correct answer.
  2. A loop counter inside one method
  3. A SQL constraint on a foreign key
  4. The name of a sorting algorithm

Explanation

Invariants characterise the valid state of an object; methods may temporarily violate them internally but must restore them before returning - a design-by-contract concept at LK level.

Question 7Programming, object modelling and software development

In Java a class may implement multiple interfaces but extend at most one class because:

  1. Java permits multiple interface inheritance but single class inheritance to avoid diamond ambiguity Correct answer.
  2. Java forbids interfaces entirely
  3. A class may extend at most zero classes
  4. Multiple interfaces always produce a compile error

Explanation

Java's single-class-inheritance rule avoids the diamond problem of multiple state inheritance, while multiple interfaces (pure contracts) keep type flexibility - an LK design rationale.

Question 8Programming, object modelling and software development

Given `List<Shape> shapes` holding Circle and Square objects, iterating and calling `area()` on each element:

  1. Invokes each element's runtime area() method via dynamic dispatch Correct answer.
  2. Calls a single Shape.area() for all elements
  3. Fails because lists cannot hold different types
  4. Returns a constant for every element

Explanation

A polymorphic collection stores references of the declared type but dispatches on each object's runtime type, so Circle.area() and Square.area() run as appropriate - LK polymorphism in collections.

Question 9Programming, object modelling and software development

For `Shape s = new Circle();`, which statement about types is correct?

  1. Static (compile-time) type Shape, dynamic (runtime) type Circle Correct answer.
  2. Both types are Circle
  3. Both types are Shape
  4. The static type is Circle and the dynamic type is Shape

Explanation

The declared variable type is the static type (Shape), used for legality checks; the object actually referenced is the dynamic type (Circle), used for method dispatch - the static/dynamic distinction is LK material.

Question 10Algorithms, recursion and complexity

The information-theoretic lower bound for any comparison-based sort of n distinct keys is:

  1. Ω(n log n) comparisons Correct answer.
  2. Ω(n) comparisons
  3. Ω(n²) comparisons
  4. Ω(log n) comparisons

Explanation

A comparison sort corresponds to a binary decision tree over n! orderings; its height is at least ⌈log₂(n!)⌉ = Ω(n log n) (Stirling). This lower bound is standard erhöhtes Niveau analysis.

Question 11Algorithms, recursion and complexity

Heapsort's worst-case time complexity on n elements is:

  1. Θ(n log n) Correct answer.
  2. Θ(n²)
  3. Θ(n)
  4. Θ(2ⁿ)

Explanation

Building the heap is O(n) and each of the n extractions costs O(log n) sift-down, giving Θ(n log n) worst case - and unlike quicksort, this is guaranteed, not just expected.

Question 12Algorithms, recursion and complexity

Insertion sort on a reverse-sorted array of n distinct elements performs how many comparisons (inversions)?

  1. n(n−1)/2 - the maximum inversion count Correct answer.
  2. n
  3. ⌈log₂ n⌉
  4. exactly n−1 swaps only, regardless of comparisons

Explanation

Reverse-sorted input has the maximum number of inversions, n(n−1)/2; each inversion forces one comparison-and-shift, so insertion sort runs in Θ(n²) on this input.

Question 13Algorithms, recursion and complexity

Which algorithm first arranges the data into a heap and then repeatedly extracts the maximum to the end of the array?

  1. Heapsort Correct answer.
  2. Mergesort
  3. Bubblesort
  4. Counting sort

Explanation

Heapsort = build-heap (O(n)) followed by n extract-max/sift-down steps, placing each max at the shrinking end - the heap-based O(n log n) sort.

Question 14Algorithms, recursion and complexity

Merging two already sorted runs of lengths p and q needs at most how many key comparisons?

  1. p + q − 1 Correct answer.
  2. p · q
  3. p + q
  4. max(p, q)

Explanation

Each comparison emits one element to the output; once one run is exhausted the rest of the other is copied without comparison. Hence at most p+q−1 comparisons - the LK merge-step bound underlying mergesort's Θ(n log n).

Question 15Algorithms, recursion and complexity

Quicksort with a uniformly random pivot has what expected time complexity?

  1. Θ(n log n) expected Correct answer.
  2. Θ(n²) expected
  3. Θ(n) expected
  4. Θ(2ⁿ) expected

Explanation

Randomisation makes balanced splits probable in expectation, so E[T(n)] = Θ(n log n); the Θ(n²) outcome still exists but is exponentially unlikely. This expectation analysis is erhöhtes Niveau material beyond the worst-case statement.

Question 16Algorithms, recursion and complexity

Which statement about heapsort stability is correct?

  1. Heapsort is generally not stable because extraction can reorder equal keys Correct answer.
  2. Heapsort is always stable by definition
  3. Stability is guaranteed only for n ≤ 10
  4. Heapsort's stability depends on the pivot choice

Explanation

The heap's array-based extraction swaps distant elements, which can change the relative order of equal keys, so heapsort is not stable in its standard form - an LK-level refinement of the stability concept.

Question 17Algorithms, recursion and complexity

Counting sort runs in O(n + k). In that bound, k represents:

  1. The range of the key values (max−min, or the size of the key universe) Correct answer.
  2. The number of elements n
  3. The recursion depth
  4. The number of comparisons

Explanation

Counting sort builds a frequency array over the key range k and is non-comparison based; it beats the Ω(n log n) comparison lower bound only when k = O(n). This trade-off is LK analysis.

Question 18Algorithms, recursion and complexity

The mergesort recurrence T(n) = 2T(n/2) + Θ(n) solves to:

  1. Θ(n log n) Correct answer.
  2. Θ(n²)
  3. Θ(2ⁿ)
  4. Θ(log n)

Explanation

Two half-size subproblems plus linear merge work: by the Master theorem (a=2, b=2, f=Θ(n)=Θ(n^{log_b a})) this is case 2, giving Θ(n log n). LK derivation rather than stating the result.

Question 19Algorithms, recursion and complexity

The Master theorem applies to recurrences of the form T(n) = a·T(n/b) + f(n). Which condition on a and b is required?

  1. a ≥ 1 and b > 1 Correct answer.
  2. a = 0 and b = 1
  3. a > b always
  4. b < 1

Explanation

a ≥ 1 (at least one subproblem) and b > 1 (the subproblem is strictly smaller) are the standard Master-theorem preconditions - an LK formal requirement.

Question 20Algorithms, recursion and complexity

The Towers of Hanoi puzzle with n disks, under the rule that a larger disk may never sit on a smaller one, requires how many disk moves?

  1. 2ⁿ − 1 moves Correct answer.
  2. n² moves
  3. n! moves
  4. exactly n moves

Explanation

To move n disks you move n−1 aside (T(n−1)), move the base disk (1), then move the n−1 back (T(n−1)): T(n)=2T(n−1)+1 with T(1)=1 solves to 2ⁿ−1 - a classic LK exponential recurrence.

Question 21Algorithms, recursion and complexity

By the Master theorem, T(n) = 2T(n/2) + Θ(n) (a=2, b=2, n^{log_b a}=n) gives:

  1. Θ(n log n) - case 2 (f matches n^{log_b a}) Correct answer.
  2. Θ(n²) - case 3
  3. Θ(n) - case 1
  4. Θ(2ⁿ)

Explanation

Here log_b a = 1, so n^{log_b a} = n and f(n)=Θ(n) matches it exactly - the critical-exponent equality that defines case 2, yielding Θ(n log n).

Question 22Algorithms, recursion and complexity

By the Master theorem, T(n) = 4T(n/2) + Θ(n) gives which order (a=4, b=2, n^{log_b a}=n²)?

  1. Θ(n²) - case 1 (f is polynomially smaller than n²) Correct answer.
  2. Θ(n log n)
  3. Θ(n)
  4. Θ(2ⁿ)

Explanation

log₂ 4 = 2, so n^{log_b a}=n²; f(n)=Θ(n) is polynomially smaller (case 1), and the recursion tree is dominated by its leaves → Θ(n²).

Question 23Algorithms, recursion and complexity

Converting a tail-recursive function to an equivalent loop typically changes the space complexity by:

  1. Reducing stack usage to O(1) because the recursive frame need not be kept Correct answer.
  2. Increasing stack usage to O(n)
  3. Leaving time complexity at Θ(2ⁿ)
  4. Making the function non-terminating

Explanation

A tail call does nothing after the recursive return, so a compiler/transform can reuse one frame, yielding O(1) space - an LK link between recursion form and resource cost.

Question 24Algorithms, recursion and complexity

Memoizing naive recursive fibonacci changes its time complexity from Θ(φⁿ) approximately to:

  1. Θ(n), since each fib(k) is computed once and reused Correct answer.
  2. Θ(n²)
  3. Θ(1)
  4. Θ(2ⁿ)

Explanation

Each fib(k) depends on fib(k−1) and fib(k−2); caching makes the n distinct subproblems linear in n, the bridge from naive recursion to dynamic programming at LK level.

Question 25Algorithms, recursion and complexity

The linear recurrence T(n) = T(n−1) + Θ(1) with a constant base case solves to:

  1. Θ(n) Correct answer.
  2. Θ(n log n)
  3. Θ(2ⁿ)
  4. Θ(log n)

Explanation

Each step shrinks the problem by one and adds constant work, so the total is the sum of n constant terms → Θ(n). This contrasts with T(n)=2T(n−1)+Θ(1)=Θ(2ⁿ).

Question 26Algorithms, recursion and complexity

A recursive inorder traversal of a balanced BST with n nodes has recursion depth approximately:

  1. Θ(log n), because the tree height is logarithmic when balanced Correct answer.
  2. Θ(n), because every node is visited
  3. Θ(n log n)
  4. Θ(2ⁿ)

Explanation

Recursion depth tracks the current path length, i.e. the tree height; a balanced BST has height Θ(log n). Total work is Θ(n) (all nodes), but depth is logarithmic - an LK distinction between total cost and stack depth.

Question 27Algorithms, recursion and complexity

Naive recursive fibonacci satisfies T(n) = T(n−1) + T(n−2) + Θ(1). Its growth is closest to:

  1. Θ(φⁿ) where φ = (1+√5)/2 ≈ 1.618 Correct answer.
  2. Θ(n²)
  3. Θ(n log n)
  4. Θ(2ⁿ)

Explanation

Solving the Fibonacci recurrence gives growth governed by the golden ratio φ ≈ 1.618, so T(n)=Θ(φⁿ) - the LK closed form, more precise than the loose 'exponential' label.

Question 28Algorithms, recursion and complexity

The complexity class P is the set of decision problems:

  1. Solvable by a deterministic algorithm in polynomial time Correct answer.
  2. Verifiable in polynomial time but not necessarily solvable
  3. Solvable only with exponential time
  4. That are undecidable

Explanation

P = decision problems with a deterministic polynomial-time algorithm. Defining P precisely (rather than the informal 'efficient') is LK complexity theory.

Question 29Algorithms, recursion and complexity

The class NP is the set of decision problems:

  1. Whose yes-answers can be verified in polynomial time (equivalently, solvable nondeterministically in polynomial time) Correct answer.
  2. Solvable only in exponential time
  3. That are provably intractable
  4. That are undecidable

Explanation

NP is defined by polynomial-time verification of certificates (or nondeterministic polynomial-time solution). Note NP does not stand for 'not polynomial' - an LK definition and a common misconception.

Question 30Algorithms, recursion and complexity

If A is NP-complete and A ≤p B (polynomial-time reduction), then B is:

  1. NP-hard (at least as hard as every problem in NP) Correct answer.
  2. Definitely in P
  3. Decidable in O(1)
  4. Regular

Explanation

An NP-complete problem reduces to B in polynomial time, so every NP problem reduces (via A) to B; B is therefore NP-hard. If additionally B ∈ NP, then B is NP-complete - an LK reduction-direction argument.

Question 31Algorithms, recursion and complexity

A decision problem is decidable if:

  1. There exists an algorithm that halts with the correct yes/no answer on every input Correct answer.
  2. It can be solved quickly in practice
  3. It has only finitely many inputs
  4. It is in P

Explanation

Decidability requires a total algorithm that always halts with the right answer. Decidable problems need not be fast or in P - an LK distinction between decidability and tractability.

Question 32Algorithms, recursion and complexity

To prove a new problem B is NP-hard, the standard method is to:

  1. Reduce a known NP-complete problem to B in polynomial time (A ≤p B) Correct answer.
  2. Reduce B to a problem in P
  3. Show B has a polynomial verification algorithm
  4. Show B is regular

Explanation

Reducing a known NP-complete A to B shows B is at least as hard as A, hence NP-hard. The reduction direction (A to B) is the LK-critical detail; the converse does not prove hardness.

Question 33Algorithms, recursion and complexity

Master theorem case 1 applies when f(n) = O(n^{log_b a − ε}) for some ε > 0. The result is:

  1. T(n) = Θ(n^{log_b a}) Correct answer.
  2. T(n) = Θ(n^{log_b a} log n)
  3. T(n) = Θ(f(n))
  4. T(n) = Θ(2ⁿ)

Explanation

When the combine work f is polynomially smaller than the leaf work n^{log_b a}, the recursion tree is leaf-dominated, giving Θ(n^{log_b a}) - the LK case-1 statement.

Question 34Algorithms, recursion and complexity

Which proof-style judgment about O-notation is correct?

  1. If f(n)=O(n) and g(n)=O(n), then (f+g)(n)=O(n) Correct answer.
  2. If f(n)=O(n), then necessarily f(n)=Ω(n²)
  3. O(n²) implies O(1)
  4. Θ(n) forbids f being O(n)

Explanation

Sums preserve O(n). O(n) does not imply Ω(n²); O(n²) is a weaker upper bound than O(1); Θ(n) implies O(n). Such closure facts are typical erhöhtes-Niveau complexity judgment.

Question 35Algorithms, recursion and complexity

Which reduction-style judgment is sound at LK depth?

  1. If A ≤p B and B ∈ P, then A ∈ P Correct answer.
  2. If A reduces to B and A is undecidable, then B must be decidable
  3. Polynomial reductions apply only to sorting algorithms
  4. P is defined using arbitrary exponential-time reductions only

Explanation

Polynomial-time reductions transfer membership in P from B to A. Undecidability transfers the other way: if A ≤ B and A is undecidable, B is undecidable.

Question 36Algorithms, recursion and complexity

Amortised analysis is used to:

  1. Bound the average cost per operation over a sequence, even if single operations are occasionally expensive Correct answer.
  2. Measure the wall-clock time of one specific operation
  3. Count the number of states in a DFA
  4. Prove a language is regular

Explanation

Some data structures have cheap common operations and rare expensive ones (e.g. dynamic-array resizing); amortised analysis averages across a sequence to state a tight per-operation bound - an LK analysis technique.

Question 37Digital representation and data structures

For a worst-case lookup, which statement about binary search trees is correct?

  1. Search is Θ(log n) in a balanced BST but can degrade to Θ(n) if the tree is skewed Correct answer.
  2. Search is always Θ(1) for every insertion sequence
  3. BSTs forbid inorder enumeration of keys
  4. A BST is identical to a FIFO queue

Explanation

Q1.4 höhere Datenstrukturen: BST cost tracks height. Balance keeps logarithmic height; sorted insertions into an unbalanced BST yield a chain of height n.

Question 38Digital representation and data structures

Which graph representation is preferable for a sparse directed graph with n vertices and m ≪ n² edges?

  1. Adjacency lists using Θ(n + m) space Correct answer.
  2. An adjacency matrix only, requiring Θ(n²) space regardless of m
  3. A single scalar with no edge storage
  4. A sorted array of all possible n² edges always materialised

Explanation

Adjacency lists scale with vertices plus edges. Matrices cost Θ(n²) even when few edges exist - a key Q1.4 modelling/complexity judgment.

Question 39Digital representation and data structures

BFS on an unweighted graph from a source yields:

  1. Shortest paths measured in number of edges Correct answer.
  2. A minimum spanning tree for arbitrary positive weights by definition
  3. A topological order of every cyclic graph
  4. Guaranteed Θ(1) time independent of n and m

Explanation

BFS explores by distance layers; first discovery is a shortest path in unweighted graphs - standard graph algorithm content at LK Q1.4.

Question 40Digital representation and data structures

A hash table with chaining resolves collisions by:

  1. Storing colliding keys in a secondary structure (often a list) at the same bucket Correct answer.
  2. Rejecting every key after the first insertion into the table
  3. Requiring the key universe to be sorted beforehand
  4. Converting the dictionary into a pure stack ADT

Explanation

Chaining is a core hashing technique under Q1.4 höhere Datenstrukturen: multiple keys mapping to one index share a bucket chain.

Question 41Digital representation and data structures

Load factor α = n/m in a hash table primarily influences:

  1. Expected chain length / probe cost under standard simple uniform hashing models Correct answer.
  2. Whether a DFA can recognise aⁿbⁿ
  3. The Notenpunkte scale maximum
  4. Whether SQL INNER JOIN is allowed

Explanation

Under uniform hashing, expected cost grows with load factor α = keys/buckets - an LK judgment linking representation to complexity.

Question 42Digital representation and data structures

AVL (or similarly balanced) BST rotations are used to:

  1. Restore height-balance invariants after updates so searches stay logarithmic Correct answer.
  2. Turn every tree into a queue permanently
  3. Guarantee Θ(n) search after each insertion
  4. Eliminate the need for ordered keys

Explanation

Rotations locally restructure trees to maintain balance - deeper Q1.4 content beyond plain BST usage at LK level.

Question 43Digital representation and data structures

Dijkstra’s algorithm (non-negative edge weights) computes:

  1. Single-source shortest paths Correct answer.
  2. Maximum cliques in general graphs in polynomial time for all instances
  3. Only whether a language is regular
  4. Primary keys of an ER diagram

Explanation

Dijkstra grows a shortest-path tree from a source when weights are non-negative - LK graph-algorithm judgment under höhere Datenstrukturen.

Question 44Digital representation and data structures

Which OO modelling of a graph fits Q1.4 style best?

  1. Classes for Graph, Vertex, and Edge with associations/collections (e.g., adjacency lists) Correct answer.
  2. Making Graph a subclass of Integer only
  3. Forbidding objects and using only global static procedures with no structure
  4. Storing the graph solely as a single boolean flag

Explanation

LA26 Q1.4 emphasises object-oriented modelling of higher data structures: entities become classes; links become associations and collections.

Question 45Digital representation and data structures

Open addressing (linear probing) handles hash collisions by:

  1. Searching a probe sequence of alternate slots in the table array Correct answer.
  2. Ignoring the hash function after the first collision
  3. Allocating an infinite Turing-machine tape per key
  4. Sorting the entire table with mergesort after every insert

Explanation

Open addressing keeps entries in the table array and probes on collision - complementary to chaining in Q1.4 hashing.

Question 46Entity modelling, relational algebra and SQL

A functional dependency A → B on a relation means:

  1. Any two tuples that agree on A must also agree on B Correct answer.
  2. B always equals A
  3. A and B are both primary keys
  4. A is always NULL when B is NULL

Explanation

An FD A→B is a constraint: the A-value determines the B-value, so identical A implies identical B. FDs are the formal basis for normal forms at LK depth.

Question 47Entity modelling, relational algebra and SQL

Boyce-Codd Normal Form (BCNF) requires that for every nontrivial functional dependency X → Y, X is:

  1. A superkey Correct answer.
  2. A single attribute
  3. A foreign key
  4. The empty set

Explanation

BCNF is a stricter 3NF: every determinant of a nontrivial FD must be a superkey. This removes anomalies 3NF can still allow - LK normalisation theory.

Question 48Entity modelling, relational algebra and SQL

An insertion anomaly in a relation means:

  1. Certain facts cannot be recorded unless an unrelated fact is also present Correct answer.
  2. Rows can be added without any primary key
  3. SELECT queries run too slowly
  4. Foreign keys are auto-generated

Explanation

Anomalies are the motivation for normalisation. In an insertion anomaly you cannot, for example, store a new course until a student enrols in it - LK rationale for normal forms.

Question 49Entity modelling, relational algebra and SQL

A surrogate key is:

  1. An artificial, system-generated identifier with no business meaning, used as a primary key Correct answer.
  2. A foreign key that references a different table
  3. A key composed of all attributes
  4. A key that is always NULL

Explanation

Surrogate keys (e.g. an auto-increment id) decouple identity from business attributes, which may change; their use and trade-offs are LK modelling decisions.

Question 50Entity modelling, relational algebra and SQL

Denormalisation is best described as:

  1. Intentionally introducing redundancy to speed up reads at the cost of update anomalies Correct answer.
  2. Removing all keys from a schema
  3. A required step before 1NF
  4. Deleting tables to save space

Explanation

Denormalisation trades normal-form purity for read performance, accepting extra write complexity and anomaly risk - an LK design trade-off beyond pure normalisation.