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
Forendiskussion
Lösungsversuch
Aufgabe 1 - Wissensfragen (16)
Teilaufgabe | Lösungsmöglichkeit 1 | Lösungsmöglichkeit 2 | Lösungsmöglichkeit 3 | Lösungsmöglichkeit 4 |
---|---|---|---|---|
a | X | X | ||
b | X | X | ||
c | X | |||
d | X | X | ||
e | X | X | ||
f | X | X | ||
g | X | X | ||
h | X | X |
Aufgabe 2 - Sortieren durch Zählen (12)
a - c)
public class CountingSort { public static void sort(char[] in) { int[] count = new int[256]; //a) for(int i = 0; i < in.length; i++) { //b) count[in[i]] += 1; } char c = 0; //current char (Teilaufgabe c) int index = 0; //write index do { for(int i = 0; i < count[c]; i++) { in[index++] = c; } c++; } while (index < in.length); } }
d) O(n)
e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein vergleichsbasiertes Sorierverfahren handelt (Wo bitte schön soll der Vergleich sein?)
Aufgabe 3 - Prim vs. Kruskal (10)
a) (A,B) – (B,D) – (B,C)
b) (B,D) – (A,D) – (D,C)
c) NEIN
Aufgabe 4 - Streuspeicherung (18)
a)
Bucket → | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
1st key | D | A | E | B | |
2nd key | F | G | C |
b)
class HashSet<K> { 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 { //b) for(int i = 0; i < map[pos].length; i++) { if(map[pos][i] == null) { map[pos|[i] = k; return null; } else if(map[pos][i].equals(k)) { K kold = map[pos][i]; map[pos][i] = k; return kold; } pos += c; pos %= map.length; } } while (pos != hk); throw new IllegalArgumentException(); } }
Aufgabe 5 - Dynamische Programmierung (20)
a)
long b(int n, int m) { if(m >= 1 && m <= n-1) { return (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n; } else if((n<m) || (m == 0 && n != 0)) { return 0; } else if(n == m) { return 1; } else { throw new IllegalArgumentException(); } }
b)
long bDP(int n, int m) { long[][] mem = new long[n + 1][m + 1]; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if((n<m) || (m == 0 && n != 0)) { mem[i][j] = 0; } else if(n == m) { mem[i][j] = 1; } else { mem[i][j] = (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n; } } } return mem[n][m]; }
Aufgabe 6 - Abstrakte Datentypen (15)
a)
axs peek(empty) = null peek(push(s, n)) = n pop(empty) = empty pop(push(s,n)) = s
b)
axs nat2bin(zero) = push(empty, zero) nat2bin(n) = push(nat2bin(div(n, succ(succ(zero)))), mod(n, succ(succ(zero))))
c)
axs bin2nat(empty) = null bin2nat(push(s,n)) = ????
Aufgabe 7 - Doppelverkettung (29)
a+b)
class DLNode<V> { DLNode<V> a; //Referenz auf Vorgänger V v; //Aktuelles Element DLNode<V> z; //Referenz auf Nachfolger boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List DLNode<V> d = this, c = this.a; //drag/current pointers boolean searchedEverything = false; while(!searchedEverything) { if(!(d.z.a == d && d.a.z == d)) { return false; } d = d.z; if(d == this || d == null || (d.z == null && d.a.z == d)) { searchedEverything = true; break; } } d = this; searchedEverything = false; while(!searchedEverything) { if(!(d.z.a == d && d.a.z == d)) { return false; } d = d.a; if(d == this || d == null || (d.a == null && d.z.a == d)) { searchedEverything = true; break; } } return true; } boolean isLoopedDLL() { //Aufgabe (b), checks if this node is part of a Looped DLL DLNode<V> c = this.a; if(!isDLL()) { return false; } else { while(c != this) { c = c.a; if(c == null) { return false; } } c = this.z; while(c != this) { c = c.z; if(c == null) { return false; } } return true; } } }
c+d)
class PriorityDeque<V extends Comparable<V>> { DLNode<V> h; //highest prio node (null if empty) V get(boolean high) { //Aufgabe (c) DLNode<V> r = h; //will finally point to requested node //list is empty if(h == null) { throw new NoSuchElementException("[Error] List is empty!"); } //list has only on single node - just empty the deque else if(h.a == null && h.z == null) { h = null; } //user requested head - reconfigure internal head pointer else if(high) { h = h.z; } //user requested node that preceeds head - retarget r else { r = h.a; } //unlink requested node r and return its value r.a.z = r.z; r.z.a = r.a; return r.v; } void put(V v) { //Aufgabe (d) DLNode<V> c = h; //current node (drag) DLNode<V> n = new DLNode<V>(); n.v = v; n.a = n.z = n; if(c == null || c.v.compareTo(v) < 0) { //n becomes new head h = n; } else { //search node c that immediately succeeds n do { c = c.z; } while (c.v.compareTo(v) >= 0 && c != h); } //insert/link n before c, if c exists if(c != null) { c.a.z = n; n.a = c.a; n.z = c; c.a = n; } } }