Sie befinden sich hier: Termine » JRobots Programmierwettbewerb » forum   (Übersicht)

forum

Lösungsversuch

Aufgabe 1 - Wissensfragen (10P)

a) Da die Klasse AssertionError eine Unterklasse von java.lang.Error ist, können Ausnahmen dieser Art nicht abgefangen und daher nicht behandelt werden.

falsch: Alle Fehlertypen, auch java.lang.Error und davon abgeleitete können mit catch abgefangen werden, obwohl das u.U. nicht immer sinnvoll ist; Fehler die von java.lang.Error abgeleitet sind, haben meist ein schwerwiegendes Problem als Ursache, so dass es sinnvoller sein kann, das Programm zu beenden als unter unklaren Bedingungen zu versuchen weiterzuarbeiten.

b) Ein AssertionError tritt in einer seiteneffektfreien assert-Anweisung auf, wenn die Zusicherung während der Programmausführung nicht erfüllt ist, jedoch nur, falls das Prüfen von Zusicherungen durch die Java-VM beim Programmstart aktiviert wurde.

wahr.

c) Es kann kein Sortierverfahren für n Schlüssel existieren, das auf Vergleichen von Schlüsselpaaren beruht und dessen Laufzeitkomplexität besser als O(n · log2 n) ist.

wahr. Ich (dario) würde sagen, dass da log2 steht, prüft einfach nochmal ab, ob dem Prüfling klar ist dass O(log2 n) = O(log_a n) = O(log n)

d) FIXME: code eintragen f ∈ O(log n); g ∈ O(n log n);

e) Die Suche nach einem Element in einer sortierten doppelt-verketteten Liste der Länge n ohne wahlfreien Zugriff hat eine Laufzeitkomplexität von O(n).

wahr: „ohne wahlfreien Zugriff“ ⇒ man muss die Liste entlanglaufen, bis man das gesuchte Element gefunden hat, die Tatsache dass die Liste sortiert ist, hilft in demt Moment nicht allzuviel.

f) Verwendet man zum Einfügen in einen Streuspeicher (Tabellenlänge n) das sogenannte quadratische Sondieren, so hat die Operation eine Laufzeitkomplexität von O(log(n)).

falsch: Die Reihenfolge wie die Felder der Streutabelle sondiert werden, ist zwar unterschiedlich, insgesamt werden im worst case aber trotzdem alle Felder einmal besucht, also ist die Komplexität O(n).

g) In einem gerichteten Graphen G = (V, E) repräsentiert der Ausgangsgrad eines Knotens n ∈ V die Anzahl aller Knoten m ∈ V , für die es eine Kante (n, m) ∈ E gibt.

wahr.

h) Mehrfachvererbung von mehreren nicht-abstrakten Oberklassen ist in UML-Klassendia- grammen (genau wie in Java) verboten.

falsch: Da UML nicht Java-spezifisch ist, und z.B. in C++ Mehrfachvererbung möglich ist, ist auch in UML Mehrfachvererbung erlaubt.

i) Folgender Code verwendet Generics korrekt im Sinne der Sprache Java und ist daher gültig und ubersetzbar: FIXME: add code

wahr (ich (dario) kann keinen fehler erkennen ;)

Frage: Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? (Dank an dario für die guten Erklärungen)

Antwort: Man kann alle Methoden die der generische Typ hat Aufrufen. Im Fall von <T> waere das in der Tat nur Methoden von Object (weil in Java alle Klassen von Object automatisch erben). Hier steht aber <T extends Book>, d.h. es koennen auch Methoden der Klasse Book aufgerufen werden, da der generische Typ von Book erben muss.

Aufgabe 2 - Bäume (20P)

a)

Adjazenzmatrix
A B C D E F G
A - + - - - - +
B + - - + + + -
C - - - + - - -
D - + + - - - -
E - + - - - - -
F - + - - - - -
G + - - - - - -
Graphische Darstellung

b) Geben Sie zu jedem Knoten des neuen Baums X dessen Höhe in X an:

A B C D E F G
0 1 4 3 3 3 1

c) Betrachten Sie den neuen Baum X als sogenannten Out-Tree“ (bei dem die Kanten gerichtet von der Wurzel ausgehen) und geben Sie ihn in Mengenschreibweise an:

Mengenschreibweise X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r
V = {A, B, C, D, E, F, G}
E = {{AB}, {AG}, {BD}, {BE}, {BF}, {DC}}
r = A

d) Schreiben Sie eine Methode isUndirected, die feststellt ob eine Adjazenzmatrix amx einen ungerichteten Graphen darstellt.

Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl einen Eintrag (AB) als auch einen Eintrag (BA) hat.

/**
 * die idee is, einfach die ganze adjazenzmatrix durch zu gehen
 * und zu schaun ob alle einträge mit ihren "gegenüberliegenden"
 * - also an der diagonale gespiegelten (indices vertauscht) -
 * übereinstimmen. falls nicht, ist der graph gerichtet.
 **/
public boolean isUndirected(boolean[][] amx) {
	for(int i= 0; i < amx.length; i++) {
		for(int j= 0; j < amx[0].length; j++) {
			if(amx[i][j] != amx[j][i]) {
				return false;
			}
		}
	}
	return true;
}

(dario): ich geb zu, es is nicht der effizienteste code (wer will kann den mal dazuschreiben), aber in der klausur kommts erstmal drauf an, dass der code tut was er soll, und nicht ob er dass in O(n) oder O(n2) tut (abgesehen davon, dass es selbst wenn man nur die hälfte vergleicht noch O(n2) bleibt).

Aufgabe 3

a) 96

b) von hinten nach vorne

c)

Stelle Reihung
- de com es net ch ee
3 de es ch ee com net
2 de ee net ch com es
1 ch com de ee es net

d)

public static char getChar(String str, int pos){
		return (pos < str.length()) ? (str.charAt(pos)) : (char) 96;
	}
 
	public static void radixSort(String[] array){
		ArrayList<String>[] buckets = (ArrayList<String> []) new ArrayList[27];
 
		for(int i = 0; i < 3; ++i){
			for(int j = 0; j < 27; ++j){
 
				buckets[j] = new ArrayList<String>();
 
 
			}
			for(int j = 0; j < array.length; ++j){
				buckets[(int)getChar(array[j],2-i) - 96].add(array[j]);
 
			}
			int k = 0;
			for( int j = 0; j < 27; ++j){
				for(String str : buckets[j]){
					array[k++] = str;
 
				}
			}
		}
	}

Aufgabe 4

Aufgabe 5 - ADT (11 Punkte)

a) getPublishDate(createPost(s, 24.02.2011, b)

b) 01.01.1970

c) createPost(s, d, true)

d) ???

e) ???

f)

publish(setSeen(P,true), id2, F) wenn id1 == id2

publish(setSeen(P, id2, markSeen(id1, F)) falls id1 != id2

Aufgabe 6

Aufgabe 7

Aufgabe 8