Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesung-miniklausur-15 [23.02.2016 20:37] – gaku | pruefungen:bachelor:aud:loesung-miniklausur-15 [01.04.2019 10:27] (aktuell) – SpeedyGonzalez | ||
---|---|---|---|
Zeile 5: | Zeile 5: | ||
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
==== Aufgabe 1 - Wissensfragen ==== | ==== Aufgabe 1 - Wissensfragen ==== | ||
+ | a) 1 und 4\\ | ||
+ | b) 2 und 4\\ | ||
+ | c) 2 und 3\\ | ||
+ | |||
==== Aufgabe 2 - Rekursion ==== | ==== Aufgabe 2 - Rekursion ==== | ||
<code java> | <code java> | ||
- | public | + | static List< |
- | List< | + | List< |
- | if(n==0){ | + | if (n <= 0) { |
- | pm.add( new ArrayList< | + | // Basisfall |
+ | pm.add(new ArrayList< | ||
+ | } else { | ||
+ | // Rekursion | ||
+ | List< | ||
+ | // Ergebnisse zusammenfuehren | ||
+ | for (List< | ||
+ | List< | ||
+ | mitN.add(n); | ||
+ | pm.add(mitN); | ||
+ | pm.add(ohneN); | ||
} | } | ||
- | else{ | ||
- | List< | ||
- | for(List< | ||
- | List< | ||
- | mitN.add(n); | ||
- | pm.add(mitN); | ||
- | pm.add(ohneN); | ||
- | } | ||
- | } | ||
- | return pm; | ||
} | } | ||
+ | return pm; | ||
+ | } | ||
</ | </ | ||
==== Aufgabe 3 - ADT ==== | ==== Aufgabe 3 - ADT ==== | ||
+ | < | ||
+ | isBlack(new, | ||
+ | |||
+ | isBlack(flip(cv, | ||
+ | !isBlack(cv, | ||
+ | isBlack(cv, x2, y2) sonst | ||
+ | |||
+ | bottom(new) = 0 | ||
+ | bottom(flip(cv, | ||
+ | y1 falls y1 < bottom(cv) && !isBlack(cv, | ||
+ | bottom(cv) | ||
+ | </ | ||
+ | |||
==== Aufgabe 4 - Dynamische Programmierung ==== | ==== Aufgabe 4 - Dynamische Programmierung ==== | ||
<code java> | <code java> | ||
- | private long pLR(int n, long[] ps){ | + | private long pLR(int n, long[] ps) { |
- | ps[1] = 2; | + | ps[1] = 2; |
- | if( ps[n] == 0 ){ | + | if (n >= 2) { |
- | ps[n] = pLR(n-1, | + | ps[n] = pLR(n - 1, ps); |
- | int i =0 ; | + | int i = 0; |
- | do{ | + | do { |
- | ps[n]++; | + | ps[n]++; |
- | for(i=1; i<n && ps[n]%ps[i] != 0; i++){ | + | for (i = 1; i < n && ps[n] % ps[i] != 0; i++) { |
- | } | + | } |
- | } while( i!=n ); | + | } while (i != n); // kleineren Teiler gefunden? |
- | } | + | |
- | return ps[n]; | + | |
} | } | ||
+ | return ps[n]; | ||
+ | } | ||
</ | </ | ||
==== Aufgabe 5 - Streuspeicherung ==== | ==== Aufgabe 5 - Streuspeicherung ==== | ||
Diese Aufgabe entspricht 1:1 [[https:// | Diese Aufgabe entspricht 1:1 [[https:// | ||
+ | |||
+ | Nein, nicht ganz. Hier muss im Gegensatz zur großen Klausur nicht das alte Objekt zurückgegeben werden, falls man auf dieses an der zu besetzenden Stelle trifft. Das erkennt man auch daran, dass in der Miniklausur der return-type " | ||
+ | |||
+ | < | ||
+ | class HashSet< | ||
+ | K[][] map; | ||
+ | int s, b, c; | ||
+ | |||
+ | HashSet(int s, int b, int c) { | ||
+ | assert 0 < c && c < s; | ||
+ | this.s = s; //size of map | ||
+ | this.b = b; //bucket size | ||
+ | this.c = c; //collision increment | ||
+ | map = (K[][]) new Object[s][b]; | ||
+ | } | ||
+ | |||
+ | K put(K k, int hk) { | ||
+ | assert k != null && 0 <= hk && hk < s; | ||
+ | int pos = hk; //current position during exploration | ||
+ | do { | ||
+ | for(int i = 0; i < b; i++) { //Für jede Stelle b des Buckets | ||
+ | if(map[pos][i] == null) { | ||
+ | map[pos|[i] = k; | ||
+ | return; | ||
+ | } | ||
+ | pos += c; | ||
+ | pos %= s; //hiermit wird sichergestellt, | ||
+ | } while (pos != hk); //pos wird im do-Block geaendert, wenn es also wieder gleich hk werden wuerde, liegt ein Zyklus vor | ||
+ | |||
+ | throw new IllegalArgumentException(); | ||
+ | } | ||
+ | } | ||
+ | </ |