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!
Inhaltsverzeichnis
Forendiskussionen
Lösungsversuch
Aufgabe 1 Wissensfragen
a) 1 und 3
b) 2 und 3
c) 2 || Ziemlich sicher, dass auch 1 richtig ist.
- zu 1) (2. Meinung: „(stimmt hier nicht auch 1?)“) ⇒ wenn man bei der linearen Suche („< oder “=„) überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen.
- zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt.
- zu 3) unsicher, ob das hier eine Rolle spielt ( 2.Meinung: „Denke ich nicht“)
- zu 4) scheidet aus, weil 2 richtig ist
d) 3
e) 1 und 4
- Man spricht nur bei „ungerichteten“ Graphen von „Grad“, bei gerichteten unterscheidet man Eingangs- und Ausgangsgrad. Wenn ein Knoten ein Grad 0 hat, dann gibt es keine Kante auf ihn. Der Graph ist also bereits ab einem Knoten mit Grad 0 nicht mehr zusammenhängend. Vorausgesetzt der Graph besteht aus mehr als einem Knoten. Da nichts anderes Korrekt scheint, muss dass also so passen.
- Ein stark zusammenhängender Graph hat zyklen, womit der Graph kein DAG mehr sein kann
f) 2 und 4
- „löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.“: Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht.
g) 2 (Meiner Meinung nach: 1 und 4 sind richtig!)
- unsicher
- Ich denke 4 müsste stimmen
- Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.
Aufgabe 2 Streuspeicherung
a) Liste
- 0 E
- 1 A
- 2
- 3 B → C → D
- 4
- 5
- 6
b) (P)→ entspricht dem Pfeil mit P und (S) dem Pfeil mit S
- A 1
- B 3
- C 3 (P)→ 4
- D 3 (P)→ 4 (S)→ 0
- E 0 (S)→ 1 (P)→ 4 (S)→ 2
Aufgabe 3 Binäre Suche
<T> int suche(T[] ts, T t, Comparator<T> c1, Comparator<T> c2){ int a=0, m, z=ts.length -1; //Anfang, Mitte, Ende while(z >= a){ m= (a+z)/2; if(c1.compare(t, ts[m]) < 0){ z=m-1; }else if(c1.compare(t, ts[m]) == 0){ if(c2.compare(t, ts[m]) < 0){ z=m-1; }else if(c2.compare(t, ts[m]) == 0){ return m; }else{ a=m+1; } }else { a=m+1; } } return -1; }
Aufgabe 4 Halden
a) Min Heap
- 0
- 2 3
- 7 6 5 4
- 8 9 10 11 12
b) ⇒ Min-Halde
2 | 6 | 3 | 7 | 10 | 5 | 4 | 8 | 9 | 12 | 11 |
---|
c) ⇒ Min-Halde
0 | 2 | 1 | 7 | 6 | 3 | 4 | 8 | 9 | 10 | 11 | 12 | 5 |
---|
Aufgabe 5 Sortieren
a)
L * | A1 | B1 | F | A2 | B2 |
---|---|---|---|---|---|
A1 | L* | B1 | F | A2 | B2 |
A1 | B1 | L* | F | A2 | B2 |
A1 | B1 | F | L* | A2 | B2 |
A1 | A2 | B1 | F | L* | B2 |
A1 | A2 | B1 | B2 | F | L* |
void sortierenDurchEinfuegen(String[] a) { String tmp; for (int n = 1; n < a.length; n++) { tmp = a[n]; // entnommenes Element merken int i = n - 1; while (i >= 0 && tmp.compareTo(a[i]) < 0) { a[i + 1] = a[i]; i--; } a[i + 1] = tmp; // entnommenes Element // einsetzen } }
Aufgabe 6 Dynamische Programmierung
a)
- kaskadenartige
b) Quelle
long a(int n) { if (n <= 1) { // Basisfall: return 1; } else { // Rekursion: long an = a(n-1); for(int i = 1; i < n; i++){ an+= a(i)*a(n-i); } return an; } }
c)
long aDP(int n){ if(mem == null || n >= mem.length){ long[] oldMem=mem; mem=new long[n+1]; if(oldMem != null){ for(int i=0; i < oldMem.length;i++) mem[i]=oldMem[i]; } } if(n <= 1){ mem[n]=1; }else if(mem[n] == 0){ mem[n]=aDP(n-1); for(int i=1; i<n; i++) mem[n] += aDP(i)*aDP(n-i); } return mem[n]; }
Aufgabe 7 Graphen
public class GraphWS15 { void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { if (!bes.contains(k)) { verb.add(k); bes.add(k); for (int i = 0; i < am[k].length; i++) { if (am[k][i]){ sammle(am, i, verb, bes); } } for (int i = 0; i < am.length; i++) { if (am[i][k]){ sammle(am, i, verb, bes); } } } } List<Set<Integer>> mszt(boolean[][] am) { // Ergebnisliste: List<Set<Integer>> ergebnis = new LinkedList<>(); // Menge besuchter Knoten: Set<Integer> bk = new HashSet<>(); // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: for (int k = 0; k < am.length; k++) { if (!bk.contains(k)){ // falls k noch nicht besucht => sammle mit k verbundene Knoten Set<Integer> verb = new HashSet(); sammle(am,k,verb, bk); ergebnis.add(verb); } } return ergebnis; } void itg(boolean[][] am, Set<Integer> vs) { for (int i=0;i<am.length;i++){ for (int j=0;j<am[i].length;j++){ if (am[i][j]){ if (!(vs.contains(i) && vs.contains(j))){ am[i][j] = false; am[j][i] = false; } } } } } public static void main(String[] args){ //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph GraphWS15 g = new GraphWS15(); boolean[][] am = {{false, true, false, true, false, false}, {false, false, false, true, false, false}, {false, false, false, false, true, false}, {false, true, false, false, false, false}, {false, false, false, false, false, false}, {false, false, false, false, false, false}}; //Set<Integer> verb = new HashSet(); List<Set<Integer>> n = g.mszt(am); System.out.println(n.size()); System.out.println(n.get(0).size()); System.out.println(n.get(1).size()); System.out.println(n.get(2).size()); } }
Aufgabe 8 ADT
TODO
a)
- collect(Node(g, n)) = add(collect(g), n)
- collect(Edge(g, a, b)) = add(add(collect(g), a), b)
b)
- path(Node(g, n), x, y) = path(g, x, y)
- path(Edge(g, a, b), x, y) = true falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x)) ; path(g, x, y) sonst
c)
- isRoot(Edge(g, a, b), x) = isRoot(g,x) falls x!=b
false sonst