35-Minuten-Mini
Vier neue Varianten: Schleifen, Liste/Pointer, lineare Rekurrenz und ein kleiner Heap-Trace.
Noch nicht gestartet.
Jetzt zählt dein eigener Start.
Wähle eine Runde, lege Papier bereit und starte erst dann den Timer. Antworten werden lokal gespeichert. Nach Abgabe oder Zeitablauf erscheinen Musterwege, Trainingspunkte und Reparaturfelder.
Saubere Einordnung: Beide Sets sind von uns konstruierte Transferaufgaben aus lokalen Kursmustern. Nur 90 Minuten, 80 Punkte und keine Hilfsmittel sind als realer Prüfungsrahmen belegt. Aufgabenmix und Trainingspunkte sind nicht offiziell.
90-Minuten-Runde
Sechs Blöcke über Code/Laufzeit, Mini-Code, Sortieren/Heap, Bäume, 2-3-4/Hashing und Greedy.
Noch nicht gestartet.
Aufgaben bleiben bis zum Start verdeckt.
Lege Papier und Stift bereit. Der Startknopf zeigt das Set und setzt gleichzeitig die nicht pausierbare Uhr in Gang.
int countPairs(int a[], int n) {
int c = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < 0) return c;
for (int j = i + 1; j < n; ++j)
if (a[i] < a[j]) ++c;
}
return c;
}- Was zählt
c? - Nenne eine konkrete Best-Case-Eingabe und die Laufzeit.
- Nenne eine Worst-Case-Eingabe, zähle die zentralen Vergleiche und gib Θ an.
Musterweg & Rubrik
- c zählt Paare
i<jmita[i]<a[j]bis zum ersten negativen Element. (3 P) - Best:
a[0]<0; sofortiger Rücksprung, Θ(1). (3 P) - Worst: kein negativer Wert, etwa streng steigend; Vergleiche
(n−1)+…+1=n(n−1)/2, Θ(n²). (4 P)
Pointer-Fahrt
Konstruierter Transfer nach Aufgabensammlung A2.int evenSum(Node* p) {
int s = 0;
while (p != nullptr) {
if (p->value % 2 == 0) s += p->value;
p = p->next;
}
return s;
}Gegeben ist head → 5 → −2 → 7 → 4 → nullptr.
- Trace
pundsnach jedem Knoten. - Welcher Wert wird zurückgegeben?
- Best und Worst für eine Liste der Länge k?
Musterweg & Rubrik
- s: 0 nach 5, −2 nach −2, −2 nach 7, 2 nach 4; Rückgabe 2. (3 P)
p=p->nextbesucht jeden der vier Knoten genau einmal. (2 P)- Bei fester Listenlänge k gibt es keinen frühen Abbruch: Best = Worst = Θ(k). (4 P)
Eine lineare Rekurrenz
Konstruierter Transfer nach Aufgabensammlung A3.int h(int n) {
if (n <= 1) return 1;
return n + h(n - 1);
}- Berechne
h(4). - Stelle Basisfall und Laufzeitrekurrenz auf.
- Rolle die Rekurrenz aus und nenne die asymptotische Laufzeit.
Musterweg & Rubrik
h(4)=4+3+2+1=10. (2 P)T(1)=c₀,T(n)=T(n−1)+c. (3 P)- Nach n−1 Einsetzungen:
c₀+(n−1)c; damit Θ(n). Funktionswert und Laufzeit nicht verwechseln. (4 P)
Min-Heap: delete-min
Konstruierter Transfer nach Übungsblatt 4, HeapSort.Arraydarstellung des Min-Heaps: [2, 5, 4, 11, 8, 7, 9].
- Entferne das Minimum.
- Notiere jeden Arrayzustand beim Bubble-down.
- Nenne Best- und Worst-Case-Laufzeit in Abhängigkeit von n.
Musterweg & Rubrik
- 2 entfernen, 9 nach oben:
[9,5,4,11,8,7]; mit kleinerem Kind 4 tauschen:[4,5,9,11,8,7]; dann mit 7:[4,5,7,11,8,9]. (4 P) - Endheap korrekt und Form/Eigenschaft erhalten. (2 P)
- Best Θ(1) bei sofort erfüllter Heap-Eigenschaft; Worst Θ(log n) entlang der Höhe. (1 P)
bool hasDuplicate(int a[], int n) {
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (a[i] == a[j]) return true;
return false;
}- Was macht die Funktion?
- Konkreter Best Case inklusive Vergleichen und Θ?
- Konkreter Worst Case, exakte Vergleichssumme und Θ?
- Formuliere einen klausurtauglichen Begründungssatz.
Musterweg & Rubrik
- Prüft, ob zwei Arrayelemente gleich sind. (3 P)
- Best:
a[0]==a[1]; ein Vergleich, Θ(1). (5 P) - Worst: alle Werte verschieden;
(n−1)+…+1=n(n−1)/2, Θ(n²). (6 P) - Satz nennt Eingabe, zentrale Operation, Häufigkeit und Klasse. (4 P)
Array-Stack: 5–15 Zeilen C++
Konstruierter Transfer nach Aufgabensammlung A8.struct Stack {
int* data;
int capacity;
int size; // Anzahl gespeicherter Werte
};
bool push(Stack& s, int value) { /* ergänzen */ }
bool pop(Stack& s, int& out) { /* ergänzen */ }Implementiere beide Funktionen. Bei voll/leer soll false zurückkommen, sonst true. out erhält den entfernten Wert.
Musterweg & Rubrik
bool push(Stack& s, int value) {
if (s.size == s.capacity) return false;
s.data[s.size++] = value;
return true;
}
bool pop(Stack& s, int& out) {
if (s.size == 0) return false;
out = s.data[--s.size];
return true;
}- Konsistente size-Konvention und Grenzen. (4 P)
- push korrekt. (5 P)
- pop korrekt, out vor Rückgabe gesetzt. (5 P)
Sortieren & Heap
Transfer nach A1 und Übungsblatt 4.- SelectionSort auf
[5,2,4,1,3]: Notiere die Arrays nach den ersten zwei äußeren Runden sowie die Gesamtzahl der Vergleiche. - Min-Heap
[1,4,3,9,7,8,5]: führe einmaldelete-minmit allen Zuständen aus und nenne Best/Worst.
Musterweg & Rubrik
- Selection: nach Runde 1
[1,2,4,5,3]; nach Runde 2 unverändert[1,2,4,5,3]. (4 P) - Insgesamt 4+3+2+1=10 Vergleiche, Θ(n²). (2 P)
- Heap: 1 entfernen, 5 hoch →
[5,4,3,9,7,8]→ mit 3 tauschen →[3,4,5,9,7,8]. (4 P) delete-min: Best Θ(1), Worst Θ(log n) über einen Wurzel-Blatt-Pfad. (2 P)
BST & InOrder-Code
Transfer nach Aufgabensammlung A10 und Übungsblatt 8.Füge in einen leeren BST ein: 8, 3, 10, 1, 6, 14, 4, 7, 13.
- Zeichne oder beschreibe den Baum.
- InOrder-Ausgabe?
- Suchpfad zu 7?
- Schreibe eine rekursive InOrder-Funktion mit
nullptr-Basisfall. Laufzeit?
Musterweg & Rubrik
- Wurzel 8; links 3 mit 1 und 6(4,7); rechts 10 mit rechtem 14(linkes 13). (4 P)
- InOrder: 1,3,4,6,7,8,10,13,14. (3 P)
- Suchpfad: 8 → 3 → 6 → 7. (2 P)
if(n==nullptr)return; inorder(n->left); visit(n); inorder(n->right);(5 P)- Besucht jeden Knoten: Θ(n). (2 P)
- Ein voller 2-3-4-Knoten enthält
[10|20|30]. Zeige den Split und nenne zwei Invarianten. - Hashtabelle Größe 7,
h(x)=x%7; belegt: Index 0→14, 2→9, 3→17. Füge 16 mit linearem Sondieren+1,+2,…ein. Besuchsfolge, Zielindex, Sondierungszahl (Start zählt nicht)?
Musterweg & Rubrik
- 20 steigt zum Elternknoten; Kinder werden
[10]und[30]. (5 P) - Invarianten z. B. sortierte Schlüssel, passende Kinderbereiche, 1–3 Schlüssel, Blätter gleiche Tiefe. (2 P)
16%7=2: 2 belegt → 3 belegt → 4 frei; Ziel 4, zwei Sondierungen. (5 P)
Greedy-Gegenbeispiel
Konstruierter Transfer nach Übungsblatt 6 und Vorlesungsstoff Greedy/Backtracking.Münzen {1,3,4}, Zielsumme 6. Greedy nimmt immer die größte noch passende Münze.
- Welche Lösung findet Greedy?
- Gib eine bessere Lösung an.
- Warum widerlegt das die allgemeine Optimalität?
- Was würde Backtracking anders tun?
Musterweg & Rubrik
- Greedy: 4+1+1, also drei Münzen. (2 P)
- Optimal: 3+3, zwei Münzen. (2 P)
- Eine konkrete Instanz mit schlechterem Greedy-Ergebnis reicht als Gegenbeispiel zur allgemeinen Optimalität. (2 P)
- Backtracking verzweigt über Alternativen, verwirft unpassende Pfade und kann 3+3 finden. (2 P)
Markiere, was du wirklich gezeigt hast.
Vergib pro Aufgabe nur die Punkte aus der sichtbaren Rubrik und markiere Fehlerarten. Das Ergebnis ist ein interner Trainingsscore — keine Prognose für die echte Klausur.
0 / 35
Noch keine Selbstpunkte eingetragen.
Zwei Reparaturen vor der 90-Minuten-Runde
Löse jeweils einen veränderten Fall ohne Musterweg und hake erst danach ab.