Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Dies ist eine alte Version des Dokuments!


Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) Falsch, alle Throwables können mit catch abgefangen werden, das heißt auch java.lang.Error und davon abgeleitete Klassen.
Ob ein Abfangen sinnvoll ist oder unter Umständen fehlschlagen kann (beispielsweise bei einem OutOfMemoryError unter Umständen denkbar), ist an dieser Stelle nicht gefragt.

b) Richtig, das Argument für die VM lautet „-ea“ (für „enable assertions“).

c) Richtig, Beweis siehe Vorlesung.

d)

  • f ∈ O(log n)
  • g ∈ O(n log n);

e) Richtig, denn ohne wahlfreien Zugriff muss die verkettete Liste bis zum gesuchten Element durchlaufen werden. Dass sie sortiert ist, ändert daran nichts, da besser Suchverfahren wie Binary Search wahlfreien Zugriff voraussetzen.

f) Falsch, im worst-case werden alle Felder nur genau einmal besucht, die Komplexität liegt also in O(n)

g) Richtig

h) Falsch, UML ist nicht Java-spezifisch. In andere Programmiersprachen wie beispielsweise C++ ist die Mehrfachvererbung möglich.

i) Richtig

Datei zum selber Testen: :pruefungen:bachelor:aud:rack.java.txt

Zusatzinfo:
Frage: Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? 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

a)

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

b)

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

c)

  Mengenschreibweise:

  X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r 
  V = {A, B, C, D, E, F, G} 
  E = {(A,B), (A,G), (B,D), (B,E), (B,F), (D,C)} 
  r = A 

d)

Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl den Eintrag (A,B) als auch einen Eintrag (B,A) aufweist. Das heißt: Die Adjazenzmatrix ist an der Diagonale symmetrisch (vergleiche Adjazenzmatrix oben).

Grundlegende Idee für die Funktion isUndirected:
Die Matrix komplett durchgehen und überprüfen, ob jeder Eintrag matrix[i][j] mit dem an der Diagonale gespiegeltem Wert matrix[j][i] identisch ist. Sollte das nicht der Fall sein, ist der zugehörige Graph gerichtet.

public boolean isUndirected(boolean[][] amx) {
	for(int i = 0; i < amx.length; i++) {			// Zeilen
		for(int j = 0; j < amx[0].length; j++) {	// Spalten
			if(amx[i][j] != amx[j][i])
				return false;
		}
	}
 
	return true;
}

Geringfügig optimierte Version, die nur eine Dreiecksmatrix durchiteriert:

public boolean isUndirected(boolean[][] amx) {
	for(int i = 0; i < amx.length; i++) {		// Zeilen
		for(int j = 0; j < i; j++) {		// Spalten
			if(amx[i][j] != amx[j][i])
				return false;
		}
	}
 
	return true;
}

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

e)

public static boolean allReachable(boolean[][] ug, int node) {
	boolean[] visited = new boolean[ug.length];
 
	visited[node] = true;
	visitAll(ug, visited, node);
 
	for(int i = 0; i < visited.length; i++) {
		if(!visited[i])
			return false;
	}
 
	return true;
}
 
private static void visitAll(boolean[][] ug, boolean[] visited, int node) {
	for(int i = 0; i < ug.length; i++) {
		if(ug[node][i]) {
			if(!visited[i]) {
				visited[i] = true;
				visitAll(ug, visited, i);
			}
		}
	}
}

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

Aufgabe 3 - Sortieren

a) 96 oder kleiner

b)

  • von Vorne nach Hinten: Falsch
  • von Hinten nach Vorne: Richtig

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++) {			// Pro Stelle ein Durchgang
		for(int j = 0; j < 27; j++) {
			buckets[j] = new ArrayList<String>();
		}
 
		for(int j = 0; j < array.length; j++) {
			int bucketNumber = (int) getChar(array[j], 2 - i) - 96;
			buckets[bucketNumber].add(array[j]);
		}
 
		int k = 0;
		for(int j = 0; j < 27; j++) {
			for(String str : buckets[j]) {
				array[k++] = str;
			}
		}
	}
}

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

Aufgabe 4 - Rekursion

a) Kaskadenartige Rekursion

b)

public static long[] pascalNiceRek(int n) {
	long[] result = new long[n+1];		
	long[][] dd = new long[n+1][n+1];
 
	for(int k = 0; k <= n; k++) {
		result[k] = pascalNiceRekH(dd, n, k);
	}
 
	return result;
}
private static long pascalNiceRekH(long[][] dd, int n, int k) {
	if(n < 0 || k < 0 || k > n) {
		return 0;
	} else if(n == 0 && k == 0) {
		return 1;
	}
 
	if(dd[n][k] == 0) {
		dd[n][k] = pascalNiceRekH(dd, n - 1, k - 1) + pascalNiceRekH(dd, n - 1, k);
	}
 
	return dd[n][k];
}

c)

public static long[] pascalNextLine(long[] current) {
	long[] result = new long[current.length + 1];
 
	result[0] = 1;
	result[result.length - 1] = 1;
 
	for(int i = 1; i < result.length - 1; i++) {
		result[i] = current[i - 1] + current[i];
	}
 
	return result;
}

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

Aufgabe 5 - ADT

a) Ergebnis: 24.02.2011

b) Ergebnis: 01.01.1970

c) setSeen(createPost(s, d, b), v) = createPost(s, d, v)

d) getUrl(publish(P, id, F)) = getURL(F);

e)

revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F))
revoke(id_1, publish(P, id_1, F)) = F

f)

revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F))
revoke(id_1, publish(P, id_1, F)) = F
markSeen(id_1, publish(P, id_2, F)) = publish(P, id_2, markSeen(id_1, F))
markSeen(id_1, publish(P, id_1, F)) = publish(setSeen(P, true), id_1, F)

Aufgabe 6 - Graphen

a)

[A] -> [B,9] -> [C,6]
[B] -> [A,9] -> [E,3] -> [C,21] 
[F] -> [E,4] -> [K,2] -> [G,10]
[Z] -> [H,5] -> [K,3]

b)

A B C D E F G H K Z
[0]
0 9 [6]
0 9 6 [9]
0 [9] 6 15 19 9
0 9 6 15 [12] 19 9
0 9 6 [15] 12 16 9
0 9 6 15 12 [16] 9 17
0 9 6 15 12 16 9 [17] 18
0 9 6 15 12 16 9 17 [18] 22
0 9 6 15 12 16 9 17 18 [21]
0 9 6 15 12 16 9 17 18 21

c)

Lösung: (D,H), (F,K), (B,E), (C,G), (K,Z), (D,E), (E,F), (A,C), (D,G)

Wie viele Meter Kabel werden verlegt: 33

Aufgabe 7 - wp-Kalkül

a)

LO: Falsch
	Hier werden erst alle einzelnen Werte aufsummiert, dann der Betrag gebildet.

RO: Richtig

LU: Falsch
	Hier werden erst alle einzelnen Werte aufsummiert, dann der Betrag gebildet.

RU: Falsch
	i < n darf nicht gelten, da sonst die Schleife nie terminieren würde

b)

wp("n = a.length; s = 0; i = 0;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =
(0 = ∑{from 0 to 0 - 1} |a_j| ∧ 0 ≤ a.length) =
(0 = 0 ∧ 0 ≤ a.length) =
(true)

c)

Zu zeigen: {I ∧ b} => wp(A, I)

wp(A, I) =
wp("if (a[i] > 0) {s = s + a[i];} else {s = s - a[i]}", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =
[(a[i] > 0) ∧ wp("s = s + a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp("s = s - a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] =
[(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp(s - a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] =
[(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] =

Überlegung:
(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] positiv, dann wird a[i] auf s addiert
(a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] negativ, dann wird -a[i] auf s addiert, also der Betrag von a[i]

Man kann somit vereinfachen:
= (s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)

{I ∧ b} => wp(A, I)
{(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∧ (i < n)} => wp(A, I) =
¬(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∨ ¬(i < n) ∨ wp(A, I) =
(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i > n) ∨ (i ≥ n) ∨ wp(A, I) =
(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ wp(A, I) =
(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ [(s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i ≤ n - 1)] =

Überlegung:
(i ≥ n) und (i ≤ n - 1) decken für den Integer den Zahlenstrahl ab, das heißt:
Ist (i ≥ n) nicht erfüllt, dann ist (i ≤ n - 1) erfüllt und umgekehrt

(s + |a[i]| = ∑{from 0 to i} |a_j|) =
(s = ∑{from 0 to i} |a_j| - |a[i]|) =
(s = ∑{from 0 to i - 1} |a_j|)

und dies ist das Komplement zu
(s ≠ ∑{from 0 to i - 1} |a_j|)

Somit kann man schlussfolgern, dass die Invariante erfüllt ist!

d)

(unsicher)

V = n - i

i = 0; n = a.length;
i++; in jedem Schleifendurchlauf

Aufgabe 8 - UML

class Firma {
	String name;
	Person geschaeftsfuehrer;
	Person[] mitarbeiter;
 
	Integer gibAnzahlMitarbeiter() {	// Achtung: Objekt vom Typ Integer, nicht der primitive Datentyp int
		// ...
	}
}
 
class Person {
	String name;
	Integer gebJahr; 
 
	Person vorgesetzter;
	Person[] unterstellteMitarbeiter;
 
	Person[] gibAlleUnterstelltenMitarbeiter() {
		// ...
	}
}