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!
forum
Lösungsversuch
Aufgabe 1 - Wissensfragen
a) falsch
b) 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) 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)
- nach B: 4
- nach C: 5
- nach D: 6
- nach E: 5
- nach F: 10
Aufgabe 3 - Java
a) Java Datei zum selber testen: :pruefungen:bachelor:aud:test.java.txt
Zeile | Bildschirmausgabe bzw. keine Ausgabe |
---|---|
23 | BA |
24 | AB |
27 | keine Ausgabe |
31 | BB |
38 | CC |
39 | AA |
b)
Zeile | Begrundung |
---|---|
7 | Compiler: f implementiert nicht die Methode f des Interfaces |
19 | Compiler: keine cast von double auf int im return Statement |
34 | Compiler: Instanzvariablen können nicht über den statischen Typ angesprochen werden (nicht A sondern a) |
40 | Compiler: Man kann nicht von der Ober- auf die Unterklasse konvertieren, nur andersherum |
44 | Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen |
Aufgabe 4 - ADT
a) A4: contains(x, create) = false
A5: contains(x, append(y,l))= 1+contains(x,l) //falls x=y contains(x,l) //falls x!=y
b) A → D → create
c) VORSICHT! nicht wirklich sicher!
A1: append(head(append(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; else return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100); }
b)
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; else { return lin(b,c,1+(((c-b)*a)%100),steps-1); } }
c)
public static int f(int n) { int a = 1, b = 2, c = 3; while (n > 0) { int tmp = a; a = b; b = c; c = 1 + (((b-a)*tmp)%100); n--; } return a; }
Aufgabe 6 - Suchbäume
a)
27 / \ 23 42 / / \ 7 32 64 \ 81
b) Schlusselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 Kosten: O (n²)
Schlusselfolge für minimale Höhe: 32, 64, 42, 81, 23, 7, 27 Kosten: O (n * log n)
c)
d)
Rotation an: 64
Einfachrotation, da 81 und 64 links gedreht werden.
Aufgabe 7 - Heap
a) Für jeden Knoten außer der Wurzel gilt A[Vater[i]] >= A[i]
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-1)/2; }
e)
//keine garantie! public void add (int priority) { array[n] = priority; while( j !=0) { int i = n; int j = parentIndex(n); if( priority > array[j] ) { array[i] = array[j]; array[j] = priority; } else { break; } } n++; }
f) O(log n)
Aufgabe 8 (wp)
a) a > b-5 && true ⇒ a > b-5