Übungsblätter zur Vorlesung Algorithmen und
Datenstrukturen (Magister)
Sommersemester 2002 - Serie
4
Abgabetermin: 21. 6. 2002 vor der Vorlesung
1. Aufgabe: (6 Punkte)
Gegeben sei eine Folge von zwanzig Zahlen:
49,124,181,192,261,361,387,432,495,572,610,653,659,712
Benutzen Sie
um die Zahlen 181,361, 432 und 659 zu finden. Geben Sie die Anzahl der benötigten Vergleiche an. Bestimmen Sie auch die Zahl der Vergleiche bei der erfolglosen Suche nach dem Schlüsselwert 600.
2.Aufgabe: (6 Punkte) Gegeben sei eine Folge von Zahlen:
49,24,41,192,61,63,87,22,95
Sortieren Sie diese Zahlen mit
(a) Bubblesort
(b) Quicksort
(c) Mergesort.
Geben Sie jeweils die Zahl der nötigen Vergleiche an.
3. Aufgabe: (5 = 2+3 Pkte.)
(a) Welches der folgenden Arrays ist ein Heap?
A[1] = 1, A[2] = 3, A[3] = 5, A[4] = 2, A[5] = 4, A[6] = 5, A[7]
= 7.
B[1] = 7, B[2] = 6, B[3] = 3, B[4] = 5, B[5] = 4, B[6] = 1, B[7] =
2.
C[1] = 7, C[2] = 6, C[3] = 2, C[4] = 5, C[5] = 4, C[6] = 1, C[7] =
3.
Begründen Sie Ihre Aussage. Stellen Sie die Felder als Baum dar.
(b) Es sei das folgende Array gegeben:
A[1] = 7, A[2] = 6, A[3] = 5, A[4] = 1, A[5] = 4, A[6] = 2, A[7] = 3.
Sortieren Sie diesen Heap mit dem Verfahren Heapsort und geben Sie alle Heaps (Baumdarstellung an, die im Verlauf des Sortierens entstehen.
4. Aufgabe: (3 Punkte) Sortieren Sie die Zahlenfolge
49,12,81,19,61,01,87,32,95,02,10,15
mit Bucketsort (Sortieren durch Fachverteilen).