Deutsch
Menü

Datenstrukturen und Algorithmen

Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?

  1. A23, 38
  2. B31, 52, 45, 38
  3. C23, 45, 31, 38
Antwort und Erläuterung anzeigen

Antwort: C. 23, 45, 31, 38

Zuerst ergibt (0 + 9) ÷ 2 = 4, also wird 38 mit a[4] = 23 verglichen; 38 ist größer, daher lo = 5. Dann ergibt (5 + 9) ÷ 2 = 7, der Vergleich erfolgt mit a[7] = 45; 38 ist kleiner, daher hi = 6. Danach liefert (5 + 6) ÷ 2 = 5 das Element a[5] = 31, also lo = 6, und schließlich stimmt a[6] = 38 überein. Das sind 4 Vergleiche, das Maximum für 10 Elemente, ⌊log₂ 10⌋ + 1 = 4. Die Folge 31, 52, 45, 38 entsteht, wenn die Mitte aufgerundet wird, was nicht der Regel in der Frage entspricht.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?
  2. Das Array 29, 10, 14, 37, 13 wird mit Selectionsort aufsteigend sortiert: Das Minimum des unsortierten Teils wird gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Wie sieht das Array aus, nachdem dieser Schritt zweimal ausgeführt wurde?
  3. Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?
  4. Welches Sortierverfahren hat auch im schlechtesten Fall die Komplexität O(n log n) und sortiert fast ohne zusätzlichen Speicher wie ein Arbeitsarray?
  5. Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?