I85PREP
⌘ K
BW Abitur Informatics study materials
BW Abitur Informatics study resources

BW Abitur Informatics practice questions

One question at a time. Build your BW Abitur Informatics understanding.

First 50 of 200 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 1Algorithmen und Datenstrukturen

Welche Eigenschaft beschreibt die O-Notation f(n) = O(g(n)) formal korrekt?

  1. Es gibt Konstanten c > 0 und n0, sodass für alle n ≥ n0 gilt: f(n) ≤ c·g(n). Correct answer.
  2. Für alle n gilt f(n) ≥ g(n), wobei g eine obere Schranke der Laufzeit ist.
  3. Der Grenzwert lim f(n)/g(n) existiert und ist genau 1.
  4. Es gibt eine Konstante c > 0, sodass für alle n gilt: f(n) = c·g(n).

Explanation

Die O-Notation beschreibt eine asymptotische obere Schranke: Ab einem Schwellenwert n0 bleibt f(n) unterhalb eines konstanten Vielfachen von g(n). Die Konstante c und der Startindex n0 dürfen frei gewählt werden, müssen aber existieren. Gleichheit oder ein Grenzwert von 1 wird nicht verlangt.

Question 2Algorithmen und Datenstrukturen

Ein Feld enthält 1000 aufsteigend sortierte ganze Zahlen. Wie viele Vergleiche benötigt die binäre Suche im schlechtesten Fall höchstens?

  1. 100
  2. 1000
  3. 10 Correct answer.
  4. 500

Explanation

Die binäre Suche halbiert den Suchraum in jedem Schritt, daher ist die Zahl der Vergleiche durch ⌈log2(n+1)⌉ begrenzt. Für n = 1000 ergibt sich ⌈log2(1001)⌉ = 10. Lineares Durchsuchen wäre der einzige Fall mit bis zu 1000 Vergleichen.

Question 3Algorithmen und Datenstrukturen

Welche Datenstruktur eignet sich am besten für eine Warteschlange (Queue) mit den Operationen enqueue und dequeue in amortisiert konstanter Zeit?

  1. Sortiertes Array mit binärer Suche
  2. Verkettete Liste mit Zeiger auf Kopf und Ende Correct answer.
  3. Stack mit push und pop
  4. Binärer Suchbaum ohne Balancierung

Explanation

Eine einfach verkettete Liste mit Referenzen auf Kopf und Ende erlaubt das Anhängen am Ende und das Entfernen am Kopf jeweils in O(1). Damit sind beide Queue-Operationen amortisiert konstant. Ein Stack realisiert dagegen LIFO statt FIFO.

Question 4Algorithmen und Datenstrukturen

Was gilt für die Anzahl der Vergleiche beim Sortieren durch Einfügen (Insertion Sort) im besten Fall?

  1. Sie ist quadratisch, nämlich in O(n²).
  2. Sie ist linear, nämlich in O(n). Correct answer.
  3. Sie ist in O(n log n).
  4. Sie ist logarithmisch, nämlich in O(log n).

Explanation

Ist das Feld bereits sortiert, muss jedes neue Element nur einmal mit seinem linken Nachbarn verglichen werden. Damit entstehen n−1 Vergleiche, also lineare Kosten. Die quadratische Laufzeit tritt erst bei umgekehrt sortierter Eingabe auf.

Question 5Algorithmen und Datenstrukturen

Welche Aussage beschreibt die Rekursionsbasis einer rekursiven Funktion korrekt?

  1. Sie ist die Anzahl der Parameter, die an die Funktion übergeben werden.
  2. Sie ist die maximale Tiefe des Aufrufstapels während der Ausführung.
  3. Sie ist der Aufruf, der die Rekursion mit verkleinertem Parameter fortsetzt.
  4. Sie ist der Fall, der ohne weiteren rekursiven Aufruf direkt ein Ergebnis liefert. Correct answer.

Explanation

Die Rekursionsbasis beendet die Rekursion, indem sie für einen oder mehrere triviale Fälle das Ergebnis direkt zurückgibt. Ohne sie würde die Funktion endlos weiter aufrufen. Der rekursive Schritt mit verkleinertem Parameter ist davon zu unterscheiden.

Question 6Algorithmen und Datenstrukturen

Ein Stack enthält nach den Operationen push(1), push(2), push(3), pop(), push(4) von oben nach unten welche Elemente?

  1. 1, 2, 4
  2. 3, 4, 2
  3. 4, 3, 2, 1
  4. 4, 2, 1 Correct answer.

Explanation

Ein Stack arbeitet nach LIFO: Nach den drei push-Operationen liegt 3 oben. Das pop entfernt die 3, anschließend wird 4 oben aufgelegt. Von oben nach unten ergibt sich damit 4, 2, 1.

Question 7Algorithmen und Datenstrukturen

Welche Struktur entsteht, wenn man in einen anfangs leeren binären Suchbaum die Werte 50, 30, 70, 20, 40 in dieser Reihenfolge einfügt?

  1. 30 ist Wurzel, 20 und 50 sind Kinder der Wurzel, 40 und 70 sind Kinder von 50.
  2. 50 ist Wurzel, 30 und 70 sind Kinder der Wurzel, 20 und 40 sind Kinder von 30. Correct answer.
  3. 50 ist Wurzel, 30 und 70 sind Kinder der Wurzel, 20 und 40 sind Kinder von 70.
  4. 50 ist Wurzel, 20 und 70 sind Kinder der Wurzel, 30 und 40 sind Kinder von 20.

Explanation

Im binären Suchbaum landet jeder kleinere Wert im linken, jeder größere im rechten Teilbaum. Daher wird 30 linkes und 70 rechtes Kind von 50. Die 20 und die 40 sind beide kleiner als 50 und größer als 20, sie werden zu Kindern von 30.

Question 8Algorithmen und Datenstrukturen

Was bezeichnet man in der Informatik als Invariante einer Schleife?

  1. Die maximale Anzahl an Durchläufen, die durch n festgelegt ist.
  2. Den Zähler, der die Anzahl der Durchläufe begrenzt.
  3. Die Abbruchbedingung, die vor dem ersten Durchlauf geprüft wird.
  4. Eine Eigenschaft, die vor und nach jedem Schleifendurchlauf gilt. Correct answer.

Explanation

Eine Schleifeninvariante ist eine Aussage über den Programmzustand, die vor dem ersten Durchlauf gilt und durch jeden Durchlauf erhalten bleibt. Sie dient dem Korrektheitsbeweis, insbesondere der Nachprüfung der Nachbedingung nach dem Schleifenende.

Question 9Algorithmen und Datenstrukturen

Welche Laufzeit hat Merge Sort im schlechtesten Fall für n Elemente?

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

Explanation

Merge Sort teilt das Feld rekursiv in zwei Hälften und mischt die sortierten Teile in linearer Zeit zusammen. Die Rekursionsgleichung T(n) = 2T(n/2) + Θ(n) ergibt nach dem Master-Theorem Θ(n log n). Diese Schranke gilt unabhängig von der Eingabereihenfolge.

Question 10Algorithmen und Datenstrukturen

Ein Feld mit den Schlüsseln 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 wird mit Hashing und der Divisionsmethode h(k) = k mod 11 in eine Tabelle der Größe 11 eingefügt. Welche Kollision tritt zuerst auf, wenn von links nach rechts eingefügt wird?

  1. Die Schlüssel 13 und 94 kollidieren beide auf Index 2.
  2. Die Schlüssel 12 und 23 kollidieren beide auf Index 1.
  3. Die Schlüssel 44 und 88 kollidieren beide auf Index 0. Correct answer.
  4. Die Schlüssel 11 und 20 kollidieren beide auf Index 9.

Explanation

Mit h(k) = k mod 11 ergibt sich 44 mod 11 = 0 und 88 mod 11 = 0. Da 44 vor 88 eingefügt wird, entsteht die erste Kollision beim Einfügen von 88. Die anderen genannten Paare haben unterschiedliche Reste.

Question 11Algorithmen und Datenstrukturen

Warum benötigt die binäre Suche ein sortiertes Feld?

  1. Weil nur dann die Anzahl der Elemente als Zweierpotenz darstellbar ist.
  2. Weil nur dann der Zugriff auf ein Element in konstanter Zeit möglich ist.
  3. Weil nur dann aus dem Vergleich mit dem mittleren Element folgt, in welcher Hälfte der gesuchte Wert liegen muss. Correct answer.
  4. Weil nur dann Duplikate vor dem Suchen entfernt werden können.

Explanation

Die binäre Suche schließt nach jedem Vergleich eine Hälfte des Suchraums aus. Diese Schlussfolgerung ist nur zulässig, wenn die Elemente in sortierter Reihenfolge vorliegen. Ohne Sortierung könnte der gesuchte Wert auch in der verworfenen Hälfte liegen.

Question 12Algorithmen und Datenstrukturen

Ein balancierter binärer Suchbaum enthält n Knoten. Welche Aussage über die Höhe h ist bei AVL-Bäumen korrekt?

  1. h liegt in O(log n), weil sich die Höhen beider Teilbäume jedes Knotens um höchstens 1 unterscheiden. Correct answer.
  2. h liegt in O(n), weil AVL-Bäume keine Rotationen durchführen.
  3. h liegt in O(1), weil AVL-Bäume stets vollständig gefüllt sind.
  4. h liegt in O(n log n), weil jede Einfügung die Höhe verdoppelt.

Explanation

Die AVL-Bedingung begrenzt die Höhendifferenz der Teilbäume jedes Knotens auf höchstens 1. Daraus folgt eine Höhe in O(log n) und damit logarithmische Suchkosten. Rotationen stellen diese Eigenschaft nach Einfügungen und Löschungen wieder her.

Question 13Algorithmen und Datenstrukturen

Welche Aufgabe hat die Funktion merge im Merge Sort?

  1. Sie wählt ein Pivotelement und partitioniert das Feld darum.
  2. Sie fügt zwei bereits sortierte Teilfolgen zu einer sortierten Gesamtfolge zusammen. Correct answer.
  3. Sie teilt das Feld rekursiv in zwei Hälften gleicher Größe.
  4. Sie vertauscht benachbarte Elemente, bis keine Inversion mehr existiert.

Explanation

Merge Sort sortiert zunächst beide Hälften rekursiv und führt sie anschließend mit merge zusammen. Beim Zusammenfügen werden die beiden sortierten Folgen in linearer Zeit zu einer sortierten Folge verschmolzen. Das Aufteilen und das Partitionieren sind andere Schritte.

Question 14Algorithmen und Datenstrukturen

Eine rekursive Funktion zur Berechnung der Fibonacci-Zahl fib(n) ruft fib(n−1) und fib(n−2) auf, ohne Ergebnisse zu speichern. Welche Laufzeit ergibt sich?

  1. Quadratisch, weil zwei Aufrufe pro Ebene entstehen.
  2. Linear, weil jedes Teilproblem genau einmal berechnet wird.
  3. Exponentiell, weil dieselben Teilprobleme vielfach neu berechnet werden. Correct answer.
  4. Logarithmisch, weil sich die Eingabe in jedem Schritt halbiert.

Explanation

Ohne Zwischenspeicherung wächst die Anzahl der Aufrufe wie die Fibonacci-Folge selbst, also exponentiell. Viele Teilprobleme werden mehrfach berechnet. Erst mit Memoisierung oder dynamischer Programmierung sinkt die Laufzeit auf O(n).

Question 15Algorithmen und Datenstrukturen

Was beschreibt die Queue-Operation dequeue bei einer Implementierung mit zwei Stacks, die amortisiert in O(1) laufen soll?

  1. Ist der Ausgangsstack leer, werden alle Elemente des Eingangsstacks einzeln hinüberbewegt, dann wird das oberste Element entnommen. Correct answer.
  2. Es werden beide Stacks vollständig geleert und anschließend neu befüllt.
  3. Es wird das mittlere Element des Eingangsstacks entnommen.
  4. Es wird stets das zuletzt eingefügte Element entnommen, unabhängig vom gewählten Stack.

Explanation

Bei der Zwei-Stack-Queue dient ein Stack zum Einfügen und einer zum Ausgeben. Beim dequeue werden Elemente nur dann umgeschichtet, wenn der Ausgangsstack leer ist; dadurch wird jedes Element höchstens einmal bewegt. Daraus folgt amortisiert konstante Zeit.

Question 16Algorithmen und Datenstrukturen

Welche Aussage über die Tiefensuche (DFS) und die Breitensuche (BFS) in einem Graphen mit Adjazenzlisten ist korrekt?

  1. Beide laufen in O(V + E), wobei V die Zahl der Knoten und E die Zahl der Kanten ist. Correct answer.
  2. Beide laufen in O(E²), weil jede Kante zweimal geprüft wird.
  3. DFS läuft in O(V²), BFS in O(E), unabhängig von der Repräsentation.
  4. BFS läuft in O(V log V), weil eine Prioritätswarteschlange nötig ist.

Explanation

Bei Adjazenzlisten besucht jede Suche jeden Knoten einmal und betrachtet jede Kante konstant oft. Damit ergibt sich für DFS und BFS dieselbe Schranke O(V + E). Der Unterschied liegt in der Reihenfolge des Besuchs, nicht in der asymptotischen Laufzeit.

Question 17Algorithmen und Datenstrukturen

Ein Algorithmus soll in einem gewichteten Graphen mit nichtnegativen Kantengewichten die kürzesten Wege von einer Quelle zu allen Knoten bestimmen. Welches Verfahren ist geeignet?

  1. Die Tiefensuche mit Markierung besuchter Knoten.
  2. Der Bellman-Ford-Algorithmus, der hier zwingend schneller ist.
  3. Die topologische Sortierung, die für beliebige Graphen kürzeste Wege liefert.
  4. Der Dijkstra-Algorithmus mit einer Prioritätswarteschlange. Correct answer.

Explanation

Dijkstra nutzt aus, dass bei nichtnegativen Gewichten der jeweils nächste noch unbesuchte Knoten endgültig feststeht. Mit einer Prioritätswarteschlange läuft das Verfahren in O((V + E) log V). Die topologische Sortierung setzt einen gerichteten azyklischen Graphen voraus.

Question 18Algorithmen und Datenstrukturen

Was ist die wesentliche Eigenschaft eines Min-Heaps?

  1. Jeder Knoten ist kleiner oder gleich seinen Kindern, sodass das Minimum in der Wurzel steht. Correct answer.
  2. Die Inordnung entspricht einer vollständigen Sortierung aller Knoten im Baum.
  3. Die Höhe des Baums ist stets logarithmisch zur Anzahl der Blätter unabhängig von der Einfügereihenfolge.
  4. Für jeden Knoten gilt, dass der linke Teilbaum kleiner als der rechte ist.

Explanation

Die Heap-Eigenschaft fordert, dass jeder Knoten höchstens so groß ist wie seine Kinder. Damit steht das kleinste Element in der Wurzel und ist in O(1) abrufbar. Eine vollständige Sortierung liegt dagegen nicht vor.

Question 19Algorithmen und Datenstrukturen

Ein Algorithmus hat die Rekursionsgleichung T(n) = 2T(n/2) + n. Welche Lösung ergibt sich nach dem Master-Theorem?

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

Explanation

Hier gilt a = 2, b = 2 und f(n) = n. Da n^(log_b a) = n^1 = n ist, liegt der zweite Fall des Master-Theorems vor. Daraus folgt T(n) = Θ(n log n).

Question 20Algorithmen und Datenstrukturen

Welche Aussage über die Stabilität eines Sortierverfahrens ist korrekt?

  1. Ein stabiles Verfahren garantiert eine Laufzeit in O(n log n).
  2. Ein stabiles Verfahren sortiert nur bereits sortierte Eingaben korrekt.
  3. Ein stabiles Verfahren erhält die relative Reihenfolge von Elementen mit gleichem Sortierschlüssel. Correct answer.
  4. Ein stabiles Verfahren benötigt stets zusätzlichen Speicher in O(n).

Explanation

Stabilität bedeutet, dass Elemente mit gleichem Schlüssel nach dem Sortieren in derselben relativen Reihenfolge stehen wie zuvor. Das ist etwa beim mehrfachen Sortieren nach verschiedenen Kriterien wichtig. Stabilität sagt nichts über die Laufzeit aus.

Question 21Algorithmen und Datenstrukturen

Warum ist die lineare Suche in einem unsortierten Feld nicht durch die binäre Suche ersetzbar, wenn nur ein einzelner Zugriff auf ein Element erlaubt ist?

  1. Weil die binäre Suche bereits einen sortierten Zugriff voraussetzt und ohne Sortierung falsch entscheiden würde. Correct answer.
  2. Weil die binäre Suche nur für Zeichenketten definiert ist.
  3. Weil die lineare Suche im schlechtesten Fall schneller ist als die binäre Suche.
  4. Weil die binäre Suche nur auf verketteten Listen funktioniert.

Explanation

Die binäre Suche verwirft nach einem Vergleich eine Hälfte des Suchraums, was nur bei sortierter Ordnung zulässig ist. In einem unsortierten Feld kann der gesuchte Wert in der verworfenen Hälfte liegen. Die lineare Suche prüft dagegen jedes Element und benötigt keine Ordnung.

Question 22Algorithmen und Datenstrukturen

Ein Feld enthält die Schlüssel 5, 3, 8, 1, 9, 2, 7. Wie viele Inversionen enthält es? (Eine Inversion ist ein Paar i < j mit a[i] > a[j].)

  1. 9
  2. 7
  3. 11 Correct answer.
  4. 13

Explanation

Man zählt für jedes Element die kleineren Elemente rechts davon: 5 hat 3 (3,1,2), 3 hat 1 (1), 8 hat 4 (1,2,7), 1 hat 0, 9 hat 3 (2,7), 2 hat 0, 7 hat 0. Die Summe 3+1+4+0+3+0+0 ergibt 11. Die Inversionszahl entspricht der Zahl der Vertauschungen, die Bubble Sort benötigt.

Question 23Algorithmen und Datenstrukturen

Ein Algorithmus soll prüfen, ob ein gegebener gerichteter Graph einen Hamiltonkreis enthält. Welche Aussage ist korrekt?

  1. Das Problem ist in linearer Zeit mit der Tiefensuche lösbar.
  2. Das Problem ist in O(V²) mit dem Dijkstra-Algorithmus lösbar.
  3. Das Problem ist unlösbar, da kein Algorithmus existiert.
  4. Das Problem ist NP-vollständig; ein polynomieller Algorithmus ist bisher nicht bekannt. Correct answer.

Explanation

Das Hamiltonkreisproblem gehört zu den klassischen NP-vollständigen Problemen. Ein polynomieller Algorithmus ist bis heute nicht bekannt, wohl aber ein exponentieller, der alle Reihenfolgen prüft. Die Entscheidung ist damit berechenbar, aber vermutlich nicht effizient.

Question 24Algorithmen und Datenstrukturen

In einem balancierten Suchbaum sollen n Schlüssel gespeichert werden, und es sollen zusätzlich alle Schlüssel in einem Intervall [a, b] in sortierter Reihenfolge ausgegeben werden, wobei k Schlüssel im Intervall liegen. Welche Schranke ist mit einem augmentierten Baum erreichbar?

  1. O(log n · log k)
  2. O(n)
  3. O(log n + k) Correct answer.
  4. O(k log n)

Explanation

Mit Teilbaumgrößen als Zusatzinformation findet man den Anfang des Intervalls in O(log n). Anschließend werden die k Treffer über Nachfolgerzeiger in konstanter Zeit pro Element ausgegeben. Zusammen ergibt sich O(log n + k).

Question 25Algorithmen und Datenstrukturen

Warum kann ein Hashing-Verfahren mit offener Adressierung bei zu hoher Auslastung stark an Performance verlieren?

  1. Weil die Hashfunktion bei hohem Füllgrad ihre Werte nicht mehr berechnen kann.
  2. Weil die Sondierung bei hohem Füllgrad lange Ketten belegter Plätze durchlaufen muss, bevor ein freier Platz gefunden wird. Correct answer.
  3. Weil Kollisionen bei offener Adressierung grundsätzlich nicht behandelt werden können.
  4. Weil bei offener Adressierung die Schlüssel automatisch sortiert werden und die Suche dann länger dauert.

Explanation

Bei offener Adressierung werden Kollisionen durch Sondieren aufgelöst. Je voller die Tabelle, desto länger werden die Sondierungsfolgen, und die erwarteten Kosten pro Operation steigen deutlich über eine Konstante. Deshalb hält man den Füllgrad üblicherweise unter einem festen Schwellenwert.

Question 26Algorithmen und Datenstrukturen

Welche Datenstruktur eignet sich für die Verwaltung der noch zu bearbeitenden Knoten bei einer iterativen Breitensuche in einem Baum, damit die Knoten Ebene für Ebene verarbeitet werden?

  1. Ein Stack (LIFO)
  2. Eine Priority-Queue mit zufälligen Prioritäten
  3. Eine Queue (FIFO) Correct answer.
  4. Eine Hashtabelle mit den Knotenwerten als Schlüssel

Explanation

Die Breitensuche bearbeitet Knoten in der Reihenfolge ihres Abstands von der Wurzel. Eine Queue gibt die Elemente in der Reihenfolge ihres Einfügens zurück, sodass die Nachbarn der aktuellen Ebene vor denen der nächsten Ebene verarbeitet werden. Ein Stack würde dagegen eine Tiefensuche erzeugen.

Question 27Algorithmen und Datenstrukturen

Ein Feld enthält 100 aufsteigend sortierte ganze Zahlen. Wie viele Vergleiche benötigt die binäre Suche im schlechtesten Fall, um zu entscheiden, ob ein bestimmter Wert enthalten ist?

  1. höchstens 50
  2. höchstens 7 Correct answer.
  3. genau 100
  4. genau 10

Explanation

Die binäre Suche halbiert den Suchbereich in jedem Schritt, die Anzahl der Schritte ist daher durch ⌈log₂(n+1)⌉ nach oben begrenzt. Für n = 100 ergibt sich ⌈log₂ 101⌉ = 7. Jeder Schritt kostet einen Vergleich mit dem mittleren Element.

Question 28Algorithmen und Datenstrukturen

Welche Aussage beschreibt die wesentliche Eigenschaft eines binären Suchbaums ohne zusätzliche Balancierung?

  1. Für jeden Knoten gilt: alle Schlüssel im linken Teilbaum sind kleiner, alle im rechten Teilbaum größer als der Schlüssel des Knotens. Correct answer.
  2. Jeder innere Knoten besitzt genau zwei Kinder.
  3. Die Höhe des Baums ist immer logarithmisch in der Anzahl der Knoten.
  4. Die Inorder-Traversierung liefert die Schlüssel in absteigender Reihenfolge.

Explanation

Die Suchbaumeigenschaft ordnet die Schlüssel relativ zu jedem Knoten: links kleiner, rechts größer. Sie erlaubt das gezielte Absteigen beim Suchen. Eine Höhengarantie oder Vollständigkeit ist damit nicht verbunden.

Question 29Algorithmen und Datenstrukturen

Ein Algorithmus verarbeitet ein Feld der Länge n mit zwei verschachtelten Schleifen, wobei die innere Schleife jeweils von 0 bis i−1 läuft. Welche Anzahl von Schleifendurchläufen der inneren Schleife ergibt sich insgesamt?

  1. n
  2. 2n
  3. n²
  4. n·(n−1)/2 Correct answer.

Explanation

Die innere Schleife läuft für i = 0 bis n−1 jeweils i-mal. Die Summe 0+1+…+(n−1) ergibt n·(n−1)/2, also Θ(n²) mit halbiertem konstanten Faktor.

Question 30Algorithmen und Datenstrukturen

Welche Operationen bietet der abstrakte Datentyp Liste im Unterschied zum abstrakten Datentyp Stack?

  1. Nur Einfügen am Ende und Entnehmen am Ende
  2. Nur Vergleichen zweier Listen auf Gleichheit
  3. Zugriff auf ein Element an einer beliebigen Position sowie Einfügen und Löschen an beliebiger Position Correct answer.
  4. Nur Sortieren der enthaltenen Elemente

Explanation

Die Liste erlaubt den positionsbasierten Zugriff und das Einfügen bzw. Löschen an beliebiger Stelle. Der Stack beschränkt den Zugriff auf das zuletzt eingefügte Element. Damit ist die Liste das allgemeinere Konzept.

Question 31Algorithmen und Datenstrukturen

Ein Feld mit den Werten 4, 2, 7, 1, 9 wird mit Selection Sort aufsteigend sortiert. Welches Feld ergibt sich nach genau einem vollständigen Durchlauf des äußeren Schleifenschritts?

  1. 1, 2, 7, 4, 9 Correct answer.
  2. 2, 4, 7, 1, 9
  3. 1, 2, 4, 7, 9
  4. 1, 4, 2, 7, 9

Explanation

Selection Sort sucht im ersten Schritt das Minimum des gesamten Feldes, hier 1, und tauscht es mit dem ersten Element. Das ergibt 1, 2, 7, 4, 9; der Rest bleibt in seiner relativen Ordnung.

Question 32Algorithmen und Datenstrukturen

Welche Aussage über die Adjazenzmatrix eines gerichteten Graphen mit n Knoten ist korrekt?

  1. Aus ihr lässt sich die Anzahl der Kanten nicht ablesen.
  2. Sie benötigt stets weniger Speicher als eine Adjazenzliste.
  3. Sie benötigt unabhängig von der Kantenzahl Θ(n²) Speicherplatz. Correct answer.
  4. Sie kann nur für ungewichtete Graphen verwendet werden.

Explanation

Die Adjazenzmatrix hat n Zeilen und n Spalten, unabhängig davon, wie viele Kanten tatsächlich existieren. Für dünn besetzte Graphen ist sie daher speicherintensiver als eine Adjazenzliste. Die Anzahl der Kanten ergibt sich aus den Einträgen ungleich null.

Question 33Algorithmen und Datenstrukturen

Was gibt die Höhe eines Baums mit nur einem einzigen Knoten an, wenn die Höhe als Anzahl der Kanten auf dem längsten Weg von der Wurzel zu einem Blatt definiert ist?

  1. 0 Correct answer.
  2. Die Höhe ist für einen Einzelknoten nicht definiert.
  3. 1
  4. 2

Explanation

Bei dieser Definition zählt man die Kanten auf dem längsten Wurzel-Blatt-Pfad. Ein Baum mit nur der Wurzel, die zugleich Blatt ist, hat keinen solchen Kantenzug, die Höhe ist also 0.

Question 34Algorithmen und Datenstrukturen

Ein Feld der Länge 8 wird mit Insertion Sort bearbeitet. In welchem Fall benötigt der Algorithmus die wenigsten Vergleiche?

  1. Wenn das Feld bereits aufsteigend sortiert ist Correct answer.
  2. Wenn das Feld absteigend sortiert ist
  3. Wenn alle Elemente paarweise verschieden sind
  4. Wenn die Elemente zufällig angeordnet sind

Explanation

Bei bereits sortierter Eingabe bricht die innere Schleife nach jeweils einem Vergleich ab, da das einzufügende Element nicht kleiner als sein linker Nachbar ist. Insertion Sort läuft dann in Θ(n). Die stärkste Belastung entsteht bei absteigend sortierter Eingabe.

Question 35Algorithmen und Datenstrukturen

Ein Hashverfahren mit Verkettung (Chaining) nutzt m = 10 Buckets und die Hashfunktion h(k) = k mod 10. Welche Schlüssel kollidieren mit dem Schlüssel 37?

  1. Alle Schlüssel, die größer als 37 sind
  2. Alle Schlüssel k mit k mod 10 = 7, etwa 17, 27 und 47 Correct answer.
  3. Nur Schlüssel, die ebenfalls 37 sind
  4. Alle Schlüssel k mit k mod 10 = 3, etwa 13 und 23

Explanation

Die Kollision hängt allein vom Hashwert ab. 37 mod 10 ergibt 7, also landen alle Schlüssel mit demselben Rest 7 im selben Bucket. Die Verkettung speichert sie dort in einer Liste.

Question 36Algorithmen und Datenstrukturen

Ein vollständiger binärer Baum mit 15 Knoten wird in einem Feld gespeichert, wobei die Wurzel den Index 1 erhält und die Kinder eines Knotens mit Index i die Indizes 2i und 2i+1 haben. Welche Indizes belegen die Blätter?

  1. 1 bis 7
  2. 2 bis 15
  3. Nur Index 15
  4. 8 bis 15 Correct answer.

Explanation

Bei dieser Indizierung sind genau die Knoten ohne Kinder Blätter. Für einen vollständigen Baum mit 15 Knoten sind das die Indizes 8 bis 15, während 1 bis 7 innere Knoten sind.

Question 37Algorithmen und Datenstrukturen

Eine Rekursion zur Berechnung der Fakultät wird durch eine Schleife ersetzt. Welche Aussage über diese Umformung ist korrekt?

  1. Die rekursive Variante benötigt keinen Aufrufstapel.
  2. Die iterative Variante benötigt konstanten zusätzlichen Speicher, die rekursive benötigt Speicher proportional zur Rekursionstiefe. Correct answer.
  3. Beide Varianten haben unterschiedliche asymptotische Laufzeiten in n.
  4. Die iterative Variante ist immer asymptotisch schneller als die rekursive.

Explanation

Jeder rekursive Aufruf belegt einen Stackrahmen, sodass die Rekursion Speicher proportional zur Tiefe n benötigt. Die Schleifenvariante kommt mit einer konstanten Zahl lokaler Variablen aus. Die asymptotische Laufzeit bleibt in beiden Fällen linear.

Question 38Algorithmen und Datenstrukturen

Ein gerichteter Graph wird mit dem Algorithmus von Dijkstra bearbeitet, obwohl er eine Kante mit negativem Gewicht enthält. Welche Konsequenz ist zu erwarten?

  1. Dijkstra liefert weiterhin korrekte kürzeste Wege, weil er nur nichtnegative Kanten voraussetzt und negative ignoriert.
  2. Dijkstra kann falsche kürzeste Wege liefern, weil ein bereits abgeschlossener Knoten später über eine negative Kante verbessert werden könnte. Correct answer.
  3. Dijkstra terminiert bei negativen Kanten grundsätzlich nicht.
  4. Dijkstra erkennt negative Kanten und wechselt automatisch zum Bellman-Ford-Algorithmus.

Explanation

Dijkstra setzt voraus, dass die Distanz eines abgeschlossenen Knotens endgültig ist. Diese Annahme beruht auf nichtnegativen Kantengewichten; eine negative Kante kann einen bereits abgeschlossenen Knoten nachträglich verkürzen. Für Graphen mit negativen Kanten ist Bellman-Ford geeignet.

Question 39Algorithmen und Datenstrukturen

In einem Max-Heap mit den Werten 50, 40, 30, 10, 20 wird der Wert 45 eingefügt. Welche Position nimmt 45 nach dem Wiederherstellen der Heap-Eigenschaft ein?

  1. 45 bleibt am Ende des Feldes ohne weitere Änderung.
  2. 45 wird direkt Kind der Wurzel 50. Correct answer.
  3. 45 ersetzt die Wurzel 50.
  4. 45 wird Blatt unter 10.

Explanation

45 wird zunächst am Ende eingefügt und dann mit seinem Vater verglichen. Da 45 größer als 40 ist, steigt es auf und wird Kind von 50. Die Heap-Eigenschaft bleibt erhalten, weil 50 größer als 45 und 45 größer als 40 ist.

Question 40Algorithmen und Datenstrukturen

Ein balancierter Suchbaum soll neben dem Einfügen und Suchen auch das Entfernen des kleinsten Schlüssels effizient unterstützen. Welche Struktur ist dafür am besten geeignet?

  1. Ein balancierter Suchbaum wie ein AVL-Baum, bei dem das Minimum durch wiederholtes Nachlinksgehen gefunden wird Correct answer.
  2. Eine einfach verkettete Liste mit sortierter Einfügung
  3. Ein Feld mit binärer Suche und Verschieben der Elemente beim Löschen
  4. Ein binärer Suchbaum mit einem Zeiger auf das Minimum und ohne Balancierung

Explanation

In einem balancierten Suchbaum liegt das Minimum im am weitesten links gelegenen Knoten und ist in O(log n) erreichbar. Das Löschen erfordert ebenfalls nur O(log n) Schritte. Unbalancierte Bäume oder Felder mit Verschieben erreichen diese Schranke im schlechtesten Fall nicht.

Question 41Algorithmen und Datenstrukturen

Ein Algorithmus durchläuft einen Graphen mit n Knoten und m Kanten mit DFS unter Verwendung einer Adjazenzliste. Welche Laufzeit ergibt sich, wenn jeder Knoten und jede Kante konstant oft betrachtet wird?

  1. Θ(m²)
  2. Θ(n + m) Correct answer.
  3. Θ(n²)
  4. Θ(n·m)

Explanation

Die DFS besucht jeden Knoten einmal und betrachtet für jeden Knoten seine Adjazenzliste. Über alle Knoten hinweg werden die Kanten konstant oft geprüft, sodass die Gesamtkosten Θ(n + m) betragen.

Question 42Algorithmen und Datenstrukturen

Warum ist die Bestimmung eines minimalen Spannbaums mit dem Algorithmus von Kruskal für einen Graphen mit m Kanten effizient, wenn die Kanten vorab sortiert vorliegen?

  1. Weil der Algorithmus dann alle Kanten unabhängig von ihrem Gewicht aufnimmt.
  2. Weil dann gar keine Prüfung auf Kreise mehr nötig ist.
  3. Weil die Anzahl der Kanten im Spannbaum gleich m ist.
  4. Weil die Kanten dann nur noch mit einer Union-Find-Struktur auf Kreisfreiheit geprüft werden müssen. Correct answer.

Explanation

Kruskal betrachtet die Kanten in aufsteigender Gewichtsreihenfolge und nimmt eine Kante auf, wenn sie keinen Kreis schließt. Die Kreisprüfung erfolgt effizient über Union-Find. Entfällt die Sortierung, bleibt die Union-Find-Prüfung als wesentlicher Aufwand.

Question 43Algorithmen und Datenstrukturen

Ein Feld enthält die Werte 3, 1, 4, 1, 5, 9, 2, 6. Es soll stabil sortiert werden. Welche Aussage über die relative Reihenfolge gleicher Schlüssel ist bei einem stabilen Verfahren korrekt?

  1. Gleiche Schlüssel behalten ihre ursprüngliche relative Reihenfolge bei. Correct answer.
  2. Gleiche Schlüssel werden an den Anfang des Feldes verschoben.
  3. Gleiche Schlüssel werden immer vertauscht.
  4. Gleiche Schlüssel werden entfernt.

Explanation

Stabilität bedeutet, dass zwei Elemente mit gleichem Schlüssel nach dem Sortieren in derselben relativen Reihenfolge stehen wie vorher. Bei den beiden Einsen im Beispiel bleibt also die zuerst eingefügte Eins vor der zweiten.

Question 44Algorithmen und Datenstrukturen

Ein Algorithmus soll in einem ungerichteten Graphen prüfen, ob er zusammenhängend ist. Welches Verfahren ist dafür geeignet?

  1. Sortieren der Knotengrade und Prüfung auf aufsteigende Reihenfolge
  2. Berechnung eines minimalen Spannbaums und Vergleich der Kantenzahl mit m
  3. Bestimmung der kürzesten Wege mit Dijkstra und Prüfung auf Gleichheit aller Distanzen
  4. Einmalige Tiefensuche von einem beliebigen Startknoten aus und Vergleich der Anzahl besuchter Knoten mit der Gesamtzahl Correct answer.

Explanation

Ein zusammenhängender Graph wird von jedem Startknoten aus durch eine Traversierung vollständig erreicht. Stimmt die Zahl der besuchten Knoten mit n überein, ist der Graph zusammenhängend.

Question 45Algorithmen und Datenstrukturen

Ein Programm ruft eine rekursive Funktion auf, die für jeden Aufruf zwei weitere Aufrufe startet, bis eine Tiefe von 20 erreicht ist. Wie verhält sich die Anzahl der Aufrufe in Abhängigkeit von der Tiefe?

  1. Sie wächst linear mit der Tiefe.
  2. Sie wächst exponentiell, nämlich wie 2^20. Correct answer.
  3. Sie wächst logarithmisch mit der Tiefe.
  4. Sie bleibt konstant.

Explanation

Bei zwei Verzweigungen pro Ebene verdoppelt sich die Zahl der Aufrufe mit jeder Ebene. Bei Tiefe 20 entstehen daher etwa 2^20 Aufrufe, also exponentielles Wachstum.

Question 46Algorithmen und Datenstrukturen

Ein Feld der Länge n enthält paarweise verschiedene ganze Zahlen. Es soll das zweitgrößte Element bestimmt werden. Welche Aussage über den Zeitaufwand ist korrekt?

  1. Es sind mindestens n·log n Vergleiche nötig, weil das Feld sortiert werden muss.
  2. Das zweitgrößte Element lässt sich in Θ(n) Zeit durch einen einmaligen Durchlauf bestimmen. Correct answer.
  3. Das zweitgrößte Element lässt sich nur mit Hashing in linearer Zeit finden.
  4. Es sind Θ(n²) Vergleiche nötig.

Explanation

Ein einzelner Durchlauf kann das Maximum und das zweitgrößte Element gleichzeitig mitführen, indem das bisherige Maximum zum zweitgrößten wird, sobald ein größeres Element gefunden wird. Das kostet Θ(n) Zeit ohne Sortierung.

Question 47Algorithmen und Datenstrukturen

Ein AVL-Baum erhält durch eine Einfügung die Balancefaktoren −2 am Knoten A und −1 an dessen rechtem Kind B. Welche Rotation stellt die AVL-Eigenschaft wieder her?

  1. Eine einfache Linksrotation um A Correct answer.
  2. Eine Doppelrotation rechts-links um A und B
  3. Eine einfache Rechtsrotation um A
  4. Keine Rotation, da die Balancefaktoren zulässig sind

Explanation

Ein Balancefaktor von −2 mit gleichgerichtetem Vorzeichen −1 beim rechten Kind kennzeichnet den Rechts-Rechts-Fall. Eine einfache Linksrotation um A hebt den Knoten B an und stellt die Balance wieder her.

Question 48Algorithmen und Datenstrukturen

Ein Algorithmus mit Laufzeit Θ(n²) benötigt für n = 1000 etwa 4 Sekunden. Welche Laufzeit ist für n = 4000 unter der Annahme zu erwarten, dass der konstante Faktor gleich bleibt?

  1. Etwa 64 Sekunden Correct answer.
  2. Etwa 8 Sekunden
  3. Etwa 4 Sekunden
  4. Etwa 16 Sekunden

Explanation

Bei quadratischem Wachstum vervierfacht sich die Laufzeit, wenn sich n vervierfacht. Aus 4 Sekunden werden also 4 · 16 = 64 Sekunden. Der konstante Faktor bleibt dabei gleich.

Question 49Algorithmen und Datenstrukturen

Ein Problem soll mit einem Greedy-Algorithmus gelöst werden, der stets die lokal günstigste Wahl trifft. Welche Bedingung muss erfüllt sein, damit der Greedy-Ansatz ein globales Optimum liefert?

  1. Der Algorithmus muss zusätzlich dynamische Programmierung verwenden.
  2. Das Problem muss NP-vollständig sein.
  3. Die lokale Wahl muss durch eine Austausch- oder Schnitt-Eigenschaft global fortsetzbar sein, und das Problem muss optimale Teilstrukturen besitzen. Correct answer.
  4. Der Algorithmus muss alle möglichen Lösungen vollständig aufzählen.

Explanation

Greedy-Verfahren sind nur dann korrekt, wenn eine lokal optimale Wahl Teil einer global optimalen Lösung sein kann und Teilprobleme optimal gelöst werden. Diese Eigenschaft wird häufig über ein Austauschargument bewiesen.

Question 50Algorithmen und Datenstrukturen

In einem gerichteten azyklischen Graphen (DAG) sollen die kürzesten Wege von einer Quelle zu allen Knoten bestimmt werden, wobei negative Kantengewichte erlaubt sind, aber keine Zyklen existieren. Welches Vorgehen ist korrekt und effizient?

  1. Den Algorithmus von Dijkstra mit einer Priority-Queue verwenden
  2. Eine Breitensuche ohne Berücksichtigung der Kantengewichte durchführen
  3. Den Bellman-Ford-Algorithmus mit |V|·|E| Schritten verwenden
  4. Topologische Sortierung durchführen und die Distanzen in dieser Reihenfolge entspannen Correct answer.

Explanation

In einem DAG lassen sich die Knoten topologisch sortieren. Werden die Kanten in dieser Reihenfolge entspannt, ist jede Distanz bereits endgültig, wenn der Knoten an der Reihe ist. Das ergibt eine Laufzeit in Θ(n + m), auch bei negativen Kantengewichten.