Informatik 3/Gedächtnisprotokoll Klausur SS07 - Versionsgeschichte

Bmay: Formatierung korrigiert, Kategorisiert

2013-02-24T13:07:34Z

Formatierung korrigiert, Kategorisiert

85.178.58.114: /* Aufgabe 7: Geld wechseln (6 Punkte) */

2008-01-28T19:13:05Z

‎Aufgabe 7: Geld wechseln (6 Punkte)

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T10:16:29Z

‎Aufgabe 1: Multiple Choice (7 Punkte)

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T09:49:29Z

‎Aufgabe 1: Multiple Choice (7 Punkte)

77.132.128.7: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T08:56:40Z

‎Aufgabe 1: Multiple Choice (7 Punkte)

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

2007-07-31T11:15:56Z

‎Aufgabe 2: HashTables (7 Punkte)

Sodoku: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-07-30T18:34:01Z

‎Aufgabe 1: Multiple Choice (7 Punkte)

TomyLobo: /* Aufgabe 3: Suchbäume (11 Punkte) */

2007-07-30T17:46:30Z

‎Aufgabe 3: Suchbäume (11 Punkte)

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

2007-07-30T13:53:40Z

‎Aufgabe 2: HashTables (7 Punkte)

TomyLobo: Punkte bei Klausureinsicht mitgeloggt, die stimmen jetzt so :)

2007-07-30T13:51:25Z

Punkte bei Klausureinsicht mitgeloggt, die stimmen jetzt so :)

@@ Zeile 2: / Zeile 2: @@
 Kreuzen Sie jeweils wahr bzw. falsch an:
 * Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.
 * Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
@@ Zeile 8: / Zeile 7: @@
 * Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
 * Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
-Worst Case Aufwand von
+Worst Case Aufwand von:
 * Wert in eine Hashliste mit Separate Chaining einfuegen
 * Einen Wert in einer Skipliste finden
@@ Zeile 21: / Zeile 19: @@
 Hashtabelle der Größe 4.
-*Hashfunktion: h(k) = k mod 4
+* Hashfunktion: h(k) = k mod 4
-*Kollisonsauflösung"double hashing" a(k) = k+2
+* Kollisonsauflösung: z.B. "double hashing" a(k) = k+2
+* Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
 (A,5) (B,11) (C,9) (D,14)
@@ Zeile 33: / Zeile 30: @@
 C -> 1,0
 D -> 2
 Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 == Aufgabe 3: Suchbäume (11 Punkte) ==
 '''AVL-Bäume'''
 *Einfügen von 3 in den folgenden AVL-Baum:
@@ Zeile 44: / Zeile 41: @@
 *Löschen von 10 aus dem folgenden AVL-Baum:
 [[Bild:Info3-ss2007-3-avltree.png]]
 '''Rot/Schwarz-Bäume'''
 *Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
 [[Bild:Info3-ss2007-3-rbtree.png]]
 *Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
@@ Zeile 57: / Zeile 52: @@
 *** boolean isBlack(Node node);
 *** class Node{ int color; Node left; Node right; }
 '''B-Baum'''
 * Element in B-Baum einfügen.
 [[Bild:Info3-ss2007-3-btree.png]]
 == Aufgabe 4: Graphen (10 Punkte) ==
 a) Baue eine Adjazenzmatrix zu folgendem Graphen:
@@ Zeile 84: / Zeile 78: @@
 == Aufgabe 5: Übungsorganisation (4 Punkte) ==
 Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.
@@ Zeile 105: / Zeile 100: @@
 Algorithmus:
 Ablauf:
@@ Zeile 125: / Zeile 118: @@
 == Aufgabe 7: Geld wechseln (6 Punkte) ==
 Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.
@@ Zeile 138: / Zeile 132: @@
 [[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]

@@ Zeile 132: / Zeile 132: @@
 c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).
 == Siehe auch ==
 [[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]

@@ Zeile 11: / Zeile 11: @@
 Worst Case Aufwand von
-* Hash einfuegen
+* Wert in eine Hashliste mit Separate Chaining einfuegen
 * Einen Wert in einer Skipliste finden
 * Rotieren in einem AVL-Baum

@@ Zeile 3: / Zeile 3: @@
 Kreuzen Sie jeweils wahr bzw. falsch an:
 * ..
-* Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V|*(|V|-1)/2 Kanten.
+* Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.
 * Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
 * Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.

@@ Zeile 3: / Zeile 3: @@
 Kreuzen Sie jeweils wahr bzw. falsch an:
 * ..
 * Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
 * Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.

@@ Zeile 8: / Zeile 8: @@
 * Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
 <br>
 == Aufgabe 2: HashTables (7 Punkte) ==

@@ Zeile 1: / Zeile 1: @@
-== Aufgabe 1: Multiple Choice (10(?) Punkte) ==
+== Aufgabe 1: Multiple Choice (7 Punkte) ==
 Kreuzen Sie jeweils wahr bzw. falsch an:
@@ Zeile 9: / Zeile 9: @@
 <br>
-== Aufgabe 2: HashTables (>=5 Punkte) ==
+== Aufgabe 2: HashTables (7 Punkte) ==
 Hashtabelle der Größe 4.
@@ Zeile 32: / Zeile 32: @@
 <br>
-== Aufgabe 3: Suchbäume (>=10 Punkte) ==
+== Aufgabe 3: Suchbäume (11 Punkte) ==
 '''AVL-Bäume'''
 *Einfügen in AVL-Baum
@@ Zeile 54: / Zeile 54: @@
 <br>
-== Aufgabe 4: Graphen (>=9 Punkte) ==
+== Aufgabe 4: Graphen (10 Punkte) ==
 a) Baue eine Adjazenzmatrix zu folgendem Graphen:
@@ Zeile 73: / Zeile 73: @@
 [[Bild:Info3-ss2007-4e.png]]
-== Aufgabe 5: Übungsorganisation (>=8 Punkte) ==
+== Aufgabe 5: Übungsorganisation (4 Punkte) ==
 Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.
@@ Zeile 100: / Zeile 100: @@
 Ablauf:
-== Aufgabe 6: Dynamisches Programmieren (=4 Punkte) ==
+== Aufgabe 6: Dynamisches Programmieren (5 Punkte) ==
 [[Bild:Info3-ss2007-6.png]]
@@ Zeile 114: / Zeile 114: @@
 O( .... )
-== Aufgabe 7: Geld wechseln (=6 Punkte) ==
+== Aufgabe 7: Geld wechseln (6 Punkte) ==
 Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.