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

Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) Falsch, es muss sortiert sein

b) Nummer 3: eine Schleife korrekt ist

c) Richtig

d) Richtig

e) Bucketsort, Mergesort

f) 1 - exakt n-1 Kanten

g) 4 - O(n² * log n)

h) 2 - O(n*(log n)²)

i) 1 - kontextsensitiven Grammatiken

Aufgabe 2 - Graphen

a)

A B C D E F Prioritäts-Warteschlange
[0] A
0 [4] 5 B,C
0 4 [5] 5 C,E
0 4 5 7 [5] E,D
0 4 5 [6] 5 10 D,F
0 4 5 6 5 [10] F
0 4 5 6 5 10

b) Pfade von Knoten A nach …

Kosten Pfad
B 4 A → B
C 5 A → C
D 6 A → B → E → D
E 5 A → B → E
F 10 A → B → E → F

Aufgabe 3 - Java

a)

ZeileBildschirmausgabe bzw. keine Ausgabe
23 BA
24 AB
27 keine Ausgabe
31 BB
38 CC
39 AA

Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test.java.txt

b)

ZeileBegrundung
7 Compiler: A implementiert die Methode f() des Interfaces I nicht (korrekt)
19 Compiler: fehlender Cast von double zu int im return-Statement
21 Compiler: die Sichtbarkeit von A geerbte public Methode g() kann in der Unterklasse nicht eingeschränkt werden
34 Compiler: Statischer Zugriff auf Instanzvariablen (Beachte Unterschied: A ↔ a)
40 Compiler: Cast von Ober- auf Unterklasse nicht möglich (andersherum jedoch schon)
44 Compiler: Interface I definiert keine Methode g()

Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test-07-08_2.java.txt

Aufgabe 4 - ADT

a)

contains(x, create) = false
contains(x, append(x, L)) = true
contains(x, append(y, L)) = contains(x, L)

b) A → D

c)

append(head(append(D, create), append(A, create)) = 
A1
= append(head(prepend(D, create), append(A, create)) = 
A1
= append(head(prepend(D, create), prepend(A, create)) = 
A3
= append(D, prepend(A, create)) = 
A2
= prepend(A, append(D, create)) = 
A1
= prepend(A, prepend(D, create))

Aufgabe 5 - Pseudo-Zufallszahlen

a)

public static int f(int n) {
	if (n < 3)
		return n + 1;
 
	return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
}

b)

Vorüberlegungen:

public static int f(int n) {
	return lin(1, 2, 3, n);
}
private static int lin(int a, int b, int c, int steps) { ...

Die Basisfälle der Funktion sind für n < 3 gegeben:
f(0) = 1
f(1) = 2
f(2) = 3

Aus dem gegebenen Aufruf (mit 1,2,3) und dieser Basisfälle lässt sich schließen:
a = 1 = f(0) –> entspricht f(n - 3)
b = 2 = f(1) –> entspricht f(n - 2)
c = 3 = f(2) –> entspricht f(n - 1)

Das Wichtige an dieser Aufgabe ist sich bewusst zu machen, wie die Werte im angegebenem Aufruf, mit den Basisfällen bzw. f(n-3), f(n-2), f(n-1) in der angegebenen Formel korrespondieren. Das Ziel ist ja diese Werte der Formel in Java-Code auszudrücken.

Somit wissen wir:
lin(a, b, c, steps) → lin(f(n - 3), f(n - 2), f(n - 1), steps)

Wir starten also am Basisfall n < 3 (⇒ Bottom-Up), weshalb nur noch der „sonst“-Teil beachtet werden muss.

Nächster „step“: n + 1

lin(f(n - 2), f(n - 1), f(n), steps - 1) (*)

f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden.
f(n) berechnet sich wie in Aufgabe a), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c:

f(n) = 1 + (((c - b) * a) % 100) (* *)

(* *) in (*) eingesetzt ergibt:

lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)

public static int f(int n) {
	return lin(1, 2, 3, n);
}
 
private static int lin(int a, int b, int c, int steps) {
	if (steps == 0)
		return a;
 
	return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
}

Warum steht das Ergebnis gerade in a?

Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift:
f(0) = 1
f(0) = lin(1, 2, 3, 0)
Das Ergebnis steht in Variable a.

c)

public static int f(int n) {
	int a = 1;
	int b = 2;
	int c = 3;
 
	while(n > 0) {
		int fn = 1 + (((c - b) * a) % 100);
		a = b;
		b = c;
		c = fn;
		n--;
	}
 
	return a;
}

Aufgabe 6 - Suchbäume

a)

     27
    /  \
  23	42
 /     /  \
7     32  64
             \
             81

b)
Für die maximale Höhe müssen die Werte in auf- oder absteigend sortiert in den Baum eingefügt werden.
Schlüsselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81
Kosten: O(n)

Für einen perfekt balancierten Baum fügt man immer das mittlere Element der sortierten Reihe ein, teil die Reihe in zwei Restreihen auf und fährt mit diesen genauso fort.
Schlüsselfolge für minimale Höhe: 32, 23, 7, 27, 64, 42, 81
Kosten: O(log n)

c)

Verwendete Definitionen:

  • Höhe eines Blatts: 0
  • Daraus folgt die Höhe des leeren Baums: -1
  • Balancefaktor: (Höhe des linken Teilbaums) - (Höhe des rechten Teilbaums)

:pruefungen:bachelor:aud:ws08-6-c.png

d)

:pruefungen:bachelor:aud:ws08-6-d.png

  • Rotation an Knoten: 64
  • Einfachrotation gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind

e)

:pruefungen:bachelor:aud:ws08-6-e.png

Aufgabe 7 - Heap

a) Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.

b)

        13
      /     \
    6        9
  /   \     /
 2     5  8

c)

public int leftChildIndex (int parentIndex) {
	return parentIndex * 2 + 1;
}

d)

public int parentIndex (int childIndex) {
	return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2;
        //Oder auch einfach nur
        // return childIndex/2;
}

e)

//keine garantie!
public void add (int priority) {
	array[n] = priority;
	int p = parentIndex(n);
 
	while(p >= 0 && array[p] < array[n]) {
		// swap ohne temporäre Variable, da immer nur priority nach oben geswappt wird
		array[n] = array[p];
		array[p] = priority;
 
		n = p;
		p = parentIndex(n);
	}
 
	n++;
}

f) O(log n)

Aufgabe 8 - wp-Kalkül

a)

wp("if (a > b - 5) {a = b++ - 4;}", a = b - 5) =
[(a > b - 5) ∧ wp("a = b++ - 4;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] =
[(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] =
[(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ wp("a = b - 4;", a = b + 1 - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ (b - 4 = b + 1 - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ (b - 4 = b - 4)] ∨ (a = b - 5) =
[(a > b - 5) ∧ true] ∨ (a = b - 5) =
(a > b - 5) ∨ (a = b - 5) =
(a ≥ b - 5)

b)

i)

Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0

ii)

Zu zeigen: P => wp(A,I)

Nachweis:
wp(A,I) =
wp("x = i; y = 0; r = false;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = i; y = 0;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = i;", (x mod 2) = (i mod 2) ∧ 0 ≥ 0) =
(i mod 2) = (i mod 2) ∧ 0 ≥ 0 =
true ∧ true =
true

P => wp(A,I) =
((i ≥ 0) => true) =
(¬(i ≥ 0) ∨ true) =
true

iii)

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

Nachweis:
wp(A,I) =
wp("x = x - 2; y = y + 1;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = x - 2;", (x mod 2) = (i mod 2) ∧ y + 1 ≥ 0) =
(x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0

{I ∧ b} => wp(A,I) = 
{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} => ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = 
¬{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = 
(x mod 2) != (i mod 2) ∨ (y < 0) ∨ (x ≤ 1) ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) =

(y + 1 ≥ 0) gilt immer, da y vor der Schleife immer 0 ist, und in der Schleife immer wieder inkrementiert wird.
(y < 0) ist aus selbigem Grund immer falsch.

(x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2)

Da das Axiom "a mod 2 = (a - 2) mod 2" für a ≥ 2 gilt:
aus   ¬(x ≤ 1)   folgt   (x > 1)
und daraus über das Axiom, dass
(x - 2 mod 2) = (i mod 2) = true

Das heißt:
(x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) =
true