Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen, bei Fragen bitte:
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Forendiskussionen, bei Fragen bitte:
- Allgemeiner Thread: https://fsi.cs.fau.de/forum/post/160770;nocount
- Aufgabe 1 (Wissensfragen): https://fsi.cs.fau.de/forum/post/160771;nocount
- Aufgabe 2 (Dynamische Programmierung):https://fsi.cs.fau.de/forum/post/160772;nocount
Lösungsversuch WS 18/19
Aufgabe 1 (Wissensfragen)
a)
- To-Do
- To-Do
- To-Do
- To-Do
b)
- To-Do
- To-Do
- To-Do
- To-Do
c)
- To-Do
- To-Do
- To-Do
- To-Do
d)
- To-Do
- Falsch, der Graph enthält Zyklen, z.B. v0>v1>v3>v0
- To-Do
- Richtig
e)
- To-Do
- To-Do
- To-Do
- To-Do
f)
- To-Do
- To-Do
- To-Do
- To-Do
Aufgabe 2 (Dynamische Programmierung)
a)
b)
public static int maxPathDP(int[][] a) { int n = a.length; int best = 0; //Feld initialisieren und letzte Spalte befüllen int[][] mem = new int[n][n]; for(int row = n-1; row >=0; row--) { mem[row][n-1] = a[row][n-1]; } int b = 0; //von der vorletzten Spalte bis zur vordersten for(int col = n-2; col >= 0; col--) { //Suche den Grössten Nachbarn in der rechten Spalte in einer Reihe //darüber, darunter oder gleicher Reihe und speichere dessen Wert in b for(int row = n-1; row >= 0; row--) { if (row == 0) { b = Math.max(mem[row][col+1], mem[row+1][col+1]); } else if(row == n-1) { b = Math.max(mem[row][col+1], mem[row-1][col+1]); } else { for(int r = row-1; r <= row+1; r++) { b = Math.max(mem[r][col+1], b); } } //Der neue Wert in mem ist der alte in a plus b mem[row][col] = a[row][col] + b; } } //Suche das Maximum in der ersten Spalte for( int i = 0; i < mem.length; i++) { if(mem[i][0] > best) { best = mem[i][0]; } } return best; }
Aufgabe 3 (Streuspeicherung)
a)
Fach | k (verkettete Liste, zuletzt eingetragener Schlüssel rechts) |
---|---|
0 | E ⇒ K |
1 | |
2 | ? ⇒ |
3 | |
4 | Y ⇒ ! ⇒ A |
5 | B ⇒ |
6 | |
7 | D ⇒ |
b)
k | sondierte Fächer und Art der Kollision |
---|---|
B | 5 |
Y | 4 |
E | 0 |
! | 4 (P)⇒ 5 (P)⇒ 6 |
A | 4 (P)⇒ 5 (P)⇒ 6 (S)⇒ 7 |
U | 0 (P)⇒ 1 |
D | 7 (S)⇒ 0 (P)⇒ 1 (S)⇒ 2 |
? | 2 (S)⇒ 3 |
c)
Fach | k | Streufunktion (i) |
---|---|---|
0 | E | 0 |
1 | A | 1 |
2 | U | 1 |
3 | ! | 1 |
4 | Y | 0 |
5 | B | 0 |
6 | ? | 2 |
7 | D | 0 |
Aufgabe 4 (Artikulationspunkte)
Aufgabe 5 (Abstrakte Datentypen)
a)
push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y ), x, y+1), x-1, y ), x, y-1 )
b)
paintHLine(c, x, y, n, nc) = To-Do
c)
getCol(New,x,y) = White getCol(Paint(c, a, b, col), x, y) = To-Do
d)
floodH(c,Empty,oc,nc) = c oc = FoldC, nc = FnewC, FoldC ̸= FnewC floodH(c,Push(ts,x,y),oc,nc) =To-Do