MINT üben

Reihungen, Suchen, Sortieren

Zehn Anwendungsaufgaben zum ganzen Kapitel — von Diagonalen und Suchverläufen bis zum Hochrechnen von Laufzeiten.

Dein Fortschritt:
0 / 0 Aufgaben
2

Aufgabenblock — AFB II

Zehn Aufgaben aus allen Unterkapiteln mit Schwerpunkt Effizienz: Programme analysieren, Suchen und Sortieren verfolgen, Operationen zählen, Laufzeiten hochrechnen und Speicher berechnen — mit gestuften Tipps, wenn du nicht weiterkommst.

A1
Zwei Diagonalen
AFB II

Für eine quadratische Tabelle int[][] m = {{3, 1, 4}, {1, 5, 9}, {2, 6, 5}}; läuft:

int s = 0, t = 0;
for (int i = 0; i < m.length; i++) {
    s = s + m[i][i];
    t = t + m[i][m.length - 1 - i];
}

Analysieren Sie das Programm: Welche Werte haben s und t am Ende?

Ansatz: m[i][i] liegt auf der Hauptdiagonale, m[i][2 − i] auf der Gegendiagonale.
Rechenweg: s: m[0][0] + m[1][1] + m[2][2]; t: m[0][2] + m[1][1] + m[2][0].
Lösung: a) 13 b) 11
Vollständige Lösung
s = 3 + 5 + 5 = 13, t = 4 + 5 + 2 = 11. Das mittlere Element 5 zählt in beiden Summen. Der Durchlauf braucht nur \(n\) Schritte, nicht \(n^2\) — es werden nur zwei Einträge je Zeile gelesen.
A2
Suche ohne Treffer
AFB II

In der sortierten Reihung

wird binär nach 36 gesucht. Untersuchen Sie den Ablauf: Wie viele Vergleiche finden statt, und welche Werte haben links und rechts am Ende?

Ansatz: Erste Mitte (0 + 11) / 2 = 5.
Rechenweg: Mitten 5 (26), 8 (40), 6 (31), 7 (35); danach links = 8, rechts = 7.
Lösung: a) 4 b) 8 c) 7
Vollständige Lösung
26 < 36 → links = 6; 40 > 36 → rechts = 7; 31 < 36 → links = 7; 35 < 36 → links = 8. Nun ist links > rechts: Rückgabe −1 nach 4 Vergleichen. Die Grenzen zeigen auf die Nachbarn 35 (Index 7) und 40 (Index 8), zwischen denen 36 stehen müsste.
A3
Zwei Verfahren, n = 12
AFB II

Vergleichen Sie Selectionsort und Bubblesort mit Abbruch auf einer bereits sortierten Reihung mit 12 Elementen: Wie viele Vergleiche braucht jedes Verfahren?

Ansatz: Selectionsort nutzt keine Vorsortierung.
Rechenweg: Selectionsort \(\frac{12 \cdot 11}{2}\); Bubblesort: ein Durchlauf ohne Tausch mit \(n - 1\) Vergleichen, dann Abbruch.
Lösung: a) 66 b) 11
Vollständige Lösung
Selectionsort sucht in jedem Durchlauf das Minimum im ganzen Rest: \(11 + 10 + \ldots + 1 = 66\). Bubblesort mit Abbruch bemerkt im ersten Durchlauf, dass nichts getauscht wurde, und hört nach 11 Vergleichen auf.