close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Algorithmen und Datenstrukturen I WS 2014/2015– Serie 5

EinbettenHerunterladen
Universität Leipzig
Institut für Informatik
Abt. Automatische Sprachverarbeitung
Algorithmen und Datenstrukturen I
WS 2014/2015 – Serie 5
Ausgabe am
09.12.2014
Prof. G. Heyer, F. Holz
Abgabe bis
06.01.2015
Seite
1/2
Algorithmen und Datenstrukturen I
WS 2014/2015– Serie 5
19. (8 Punkte) Fachverteilen
Es seien folgende 11 Zeichenketten gegeben:
als aber an oben ben abo anis aus aal abel abba
Sortieren Sie diese Folge von Zeichenketten mittels Fachverteilen (vgl V. 5, F. 24).
Geben Sie für jeden der k Schritte den Inhalt aller Fächer nach dem Verteilen sowie
die entstehende Zeichenkettenfolge nach dem Sammeln an.
20. (7 Punkte) Komplexität Fachverteilen
Die fürstliche Post des Fürstentums Binaco verwendet fünfstellige Postleitzahlen im
Binärsystem zur Unterscheidung seiner 32 Zustellbezirke.
a) In der zentralen Poststelle werden täglich die n versandten Briefe per Fachverteilen mit zwei Fächern nach Postleitzahlen sortiert. Die Zeitfaktoren für
das Streuen und Sammeln sind dabei C1 = C2 = 1. Geben Sie den gesamten
Zeitaufwand TFach (n) unter der Annahme, daß in jeder Binärstelle Duplikate
auftreten, an.
b) Die Cousine eines stellvertretenden Staatssekretärs im Effizienzministerium
schlägt die Umstellung auf ein modernes Sortierverfahren mit Zeitaufwand
T (n) = 2 n log2 n vor. Berechnen Sie (Lösungsweg angeben!), für welche Zahl
an Briefen dieses Verfahren schneller als das Fachverteilen ist.
21. (6 Punkte) Eigenschaften Binärer Bäume
Gegeben sind die folgenden Binärbäume.
(i)
(ii)
0
0
6
1
2
3 5
4
6
1
2
3 5 9
(iii)
4
7 8
(iv)
1
2
1
4
3 5 9 X
2
3
a) (6 Punkte) Geben Sie für jeden der Bäume (i)–(iv) dessen Höhe an, und ob er
die folgenden Eigenschaften hat (ja/nein): strikt, ausgeglichen, fast vollständig,
vollständig. Geben Sie Ihre Ergebnisse in Form einer Tabelle, in der zu jedem
der Bäume jeweils eine Spalte steht.
Universität Leipzig
Institut für Informatik
Abt. Automatische Sprachverarbeitung
Prof. G. Heyer, F. Holz
Algorithmen und Datenstrukturen I
WS 2014/2015 – Serie 5
Ausgabe am
09.12.2014
Abgabe bis
06.01.2015
Seite
2/2
b) (4 Punkte) Geben Sie zu jedem der Bäume (i)–(iv) an, durch welchen Ausdruck
er gemäß ADT-Spezifikation BINTREE erzeugt wird.
22. (10 Punkte) Binäre Suchbäume
Gegeben sind die Schlüsselsequenzen
a) d, f, b, c, a, e
b) a, b, d, c, e, f
c) a, e, d, c, b, f
Bauen Sie zu jeder der Sequenzen den natürlichen binären Suchbaum auf. Fügen
Sie also die Schlüssel der Reihe nach in einen anfangs leeren Binärbaum ein. Als
Ordnung auf der Menge der Schlüssel sei die übliche alphabetische Ordnung definiert.
Zeichnen Sie den Baum nach dem letzten Einfügen. Löschen Sie danach jeweils
den Schlüssel e und zeichnen Sie den nun erhaltenen Baum. Gibt es mehrere
Möglichkeiten resultierender Bäume, so geben Sie alle an.
Document
Kategorie
Gesundheitswesen
Seitenansichten
8
Dateigröße
157 KB
Tags
1/--Seiten
melden