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:

Lösungsversuch WS 18/19

Aufgabe 1 (Wissensfragen)

a)

  1. To-Do
  2. To-Do
  3. To-Do
  4. To-Do

b)

  1. To-Do
  2. To-Do
  3. To-Do
  4. To-Do

c)

  1. To-Do
  2. To-Do
  3. To-Do
  4. To-Do

d)

  1. To-Do
  2. Falsch, der Graph enthält Zyklen, z.B. v0>v1>v3>v0
  3. To-Do
  4. Richtig

e)

  1. To-Do
  2. To-Do
  3. To-Do
  4. To-Do

f)

  1. To-Do
  2. To-Do
  3. To-Do
  4. 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

Aufgabe 6 (Radix-Exchange Sortierung)