https://wiki.stageing.freitagsrunde.org//api.php?action=feedcontributions&feedformat=atom&user=212.202.170.193FreitagsrundenWiki - Benutzerbeiträge [de]2026-11-01T13:42:25ZBenutzerbeiträgeMediaWiki 1.45.6wiki.stageing.freitagsrunde.org//index.php?title=Informatik_3/Ged%C3%A4chtnisprotokoll_Klausur_SS05&diff=7335Informatik 3/Gedächtnisprotokoll Klausur SS052007-07-22T22:54:44Z<p>212.202.170.193: /* 4. Eichhornaufgabe */ typo</p>
<hr />
<div>__NOTOC__<br />
Dies ist ein Gedächtnisprotokoll von der Klausur vom 20. Juli 2005.<br />
<br />
== 1. Aufgabe: Multiple Choice (4 mal wahr/falsch) ==<br />
<br />
* Eine perfekte Skipliste hat immer Höhe O(log n).<br />
* Ein binärer Baum hat immer Höhe O(log n).<br />
* Ein AVL-Baum, in den 2^n - 1 Knoten eingefügt wurden, ist immer vollständig. (Vorsicht!)<br />
* Noch eine Frage<br />
<br />
<br />
== 2. AVL-Baeume. ==<br />
<br />
* Mit wievielen Knoten kann ein AVL-Baum die Schicht 2 vollständig haben?<br />
* Wieviele Knoten muss man in einen AVL-Baum einfuegen, sodass er garantiert vollständig ist?<br />
<br />
* Löschen eines Knotens in einem max. unausgewogenen Baum (eine Doppel, eine Einzelrotation).<br />
<br />
* Simulation Prim.<br />
<br />
== 3. Rot-Schwarz-Baeume ==<br />
* Einfügen eines Knotens in einen RB-Baum mit 2 Rotationen (4 Knoten Ausgangsgröße).<br />
* Welche Pfadlänge hat der kürzeste Pfad Wurzel -> Blatt in einem Baum der Höhe 7 minimal?<br />
<br />
== 4. Eichhornaufgabe ==<br />
<br />
* Gegeben ein "Netzwerk" (Matrix) von Bäumen, Darstellung als Graph mit Kantenbewertung.<br />
<br />
* Implementierung eines Hashs mit Double Hashing: Konstruktoren & Klassen, Insert, Search.<br />
* KW-Baum-Beschreibung ("Wie findet man aus dem Graphen die Wege mit geringstem Risiko. Welcher Algorithmus ist geeignet?)<br />
<br />
== 5. Greedy ==<br />
* n Mitarbeiter, n Bueros.<br />
Gegeben:<br />
* Kosten fuer "Weg" von Buero_x -> Buero_y = | x - y | (Indizes).<br />
* Besuchsfrequenz eines Mitarbeiters i bei einem Mitarbeiter j: f(i, j)<br />
<br />
Gesucht:<br />
* Darstellung fuer Loesung<br />
* Kostenberechnung fuer _einen_ Weg.<br />
* Kostenberechnug fuer Mitarbeiter i (Summe aus (Distanzen mal Frequenzen))<br />
* Kosten fuer alle Mitarbeiter.<br />
<br />
<br />
* Geben Sie einen Algorithmus an, der die minimalen Kosten von einem Mitarbeiter zu allen anderen berechnet.<br />
<br />
== 6. Aufgabe ==<br />
Überlegen Sie sich eine (Verkettung von) Datenstrukturen, mit der man möglichst effizient:<br />
* Einfuegen<br />
* Suchen<br />
* Loeschen<br />
* Remove_oldest<br />
<br />
machen kann, geben Sie O(x) Abschätzung an.</div>212.202.170.193