- Bitte um Forenthreads erweitern!

a) Falsch, geschlossenes Hashing bedeutet lediglich, dass es pro Behälter eine Obergrenze b an Schlüsseln gibt. Diese Grenze ist meistens 1, kann aber auch beliebig hoch (jedoch fest!) sein. Für eine fest Obergrenze b ergibt sich allgemein: Die Hashtabelle kann m * b Schlüssel aufnehmen.

b) Falsch, jUnit ist ein TestCase-Framework. Behälterdatentypen werden über das Collections Framework bereitgestellt.

c) 4. Antwort ist richtig: keines davon. Der Entscheidungsgehalt H errechnet sich als: ceil(log_2 (n))

d)

• Passt
• Passt
• Passt nicht, die Vererbungsbeziehung geht in die andere Richtung
• Passt nicht, die Methode +byby(a:A) hat keinen Returntyp
• Passt

e) 3. Antwort: n

f) (unsicher)

• 2. Antwort: O(n log(n))
• 3. Antwort: O(log(n * m))
• 3. Antwort: O(2^abs(n))

a)

b)

Ja

c)

Die fehlende Kante: (0 → 2)

a)

b)

Graph:

(Allgemeine Bemerkung: Der Algorithmus von Floyd erzeugt jede Kante, die es vorher noch nicht gab, bzw. „verbessert“ die Gewichte von bestehenden Kanten.
Sollte der Graph in dieser Aufgabe vollständig gezeichnet werden oder sollen wirklich nur die Kanten enthalten sein, die durch die obige Tabelle ermittelt wurden?

a)

public static int locateRow(int[][] keys, int key) {
	int start = 0;
	int end = keys.length - 1;
 
	do {
		int mid = (start + end) / 2;
 
		// erster Wert der Zeile ist kleiner oder gleich
		// => gesuchter Wert kann in der aktuellen Zeile oder in den Zeilen darunter vorkommen
		if(keys[mid][0] <= key) {
			// falls die nächste Reihe nicht existiert
			// => gesuchter Wert kann nur in der aktuellen Zeile sein
			if(mid + 1 >= keys.length) {
				return mid;
			} else {
				// falls die nächste Reihe existiert, ihr erster Wert aber größer als der gesucht ist
				// => gesuchter Wert kann nur in der aktuellen Zeile sein
				if(keys[mid + 1][0] > key) {
					return mid;
				} else {
					start = mid + 1;
				}
			} 
 
		// erster Wert der Zeile ist echt größer
		// => gesuchter Wert kann nur in den Zeilen darüber vorkommen
		} else {
			end = mid - 1;
		}
	} while(start <= end && start >= 0 && end <= keys.length);
 
	return -1;
}

b)

public static int[] search(int[][] keys, int key) {
	int row = locateRow(keys, key);
 
	if(row == -1)
		return null;
 
	int start = 0;
	int end = keys[row].length - 1;
 
	do {
		int mid = (start + end) / 2;
 
		if(keys[row][mid] == key)
			return new int[]{row, mid};
 
		if(keys[row][mid] < key) {
			start = mid + 1;
		} else {
			end = mid - 1;
		}
 
	} while(start <= end && start >= 0 && end < keys[row].length);
 
	return null;
}

Programm zum selber Testen: :pruefungen:bachelor:aud:doublebinarysearch.java.txt

a)

b)