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!

forum

Lösungsversuch

Aufgabe 1 - Rucksackproblem

a)

0 1 2 3 4 5 6 7 8 9 10 11 12
1 - + / / / / / / / / / / /
4 - - / / [+] + / / / / / / /
7 - - / / - - / + + / / + +
8 - - / / - - / - [+] + / - [+]

b) 8, 4 In Tabelle von a) mittels [] eingekreist.

c) 

for(int i = 1; i < n; i++) {            // Zeilen
    for(int j = 0; j < m + 1; j++) {    // Spalten
        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht
            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben.
            if(j + k[i+1] <= m)
                tab[i+1][j+k[i+1]] = MIT;
        }
    }
}

Aufgabe 2 - ADT

a) 

create, add, remove, removeAll

b) 

A1: contains(x, create) = 0
A2: contains(x,add(y,M)) = {1+contains(x,M)     falls x = y
                           {0+contains(x,M)     sonst

c) 

A3: remove(x, create) = create
A4: remove(x,add(y,M)) = M                      falls x==y
                         add(y, remove(x, M))   sonst

d) 

A5: removeAll(x,create) = create
A6: removeAll(x,add(y,M)) = add(y, removeAll(x, M))     falls x!=y
                            removeAll(x, M)            sonst

Aufgabe 3

a)

  • statisch: A, dynamisch: A
  • statisch: A, dynamisch: AA
  • statisch: B, dynamisch: B

b) Nein, nein, ja, ja, ja, nein, nein, nein

c) 6, 8

Aufgabe 4 - Hashes

a)

x = 7 26 27 4 47 9 6 36 17 57 56 42 10 77
(3x+2)%10 = 3 0 3 4 3 9 0 0 3 3 0 8 2 3
Bucket verkettete Liste
0 26 → 6 → 36 → 56
1
2 10
3 7 → 27 → 47 → 17 → 57 → 77
4 4
5
6
7
8 42
9 9

b) Nein, diese hat eine schlechte Verteilung und erzeugt somit viele Kollisionen.

c)

  • Ja
  • Ja
  • Ja??
  • Ja

d)

x = 4 7 26 27 47 42 10 56 9
(3x+2)%10 = 4 3 0 3 3 8 2 0 9
1 + 2  (x%2) = 1 3 1 3 3 1 1 1 3
Bucket Inhalt Kollisionstyp
0 26 -
1 56 P
2 10 -
3 7 -
4 4 -
5 9 S
6 27 P
7
8 42 -
9 47 S

Aufgabe 5

    // a) wie bei Mergesort, der Mergeteil:
    private static Photo[] combinePhotos(Photo[] p1, Photo[] p2){
        Photo[] m = new Photo[p1.length + p2.length];
        int l = 0;
        int r = 0;  
        int k = 0;
        while (l < p1.length && r < p2.length){
            if (p1[l].compareTo(p2[r]) < 0){ 
                m[k++] = p1[l++];
            }   
            else {
                m[k++] = p2[r++];
            }   
        }   
        while(l < p1.length){
            m[k++] = p1[l++];
        }   
        while(r < p2.length){
            m[k++] = p2[r++];
        }   
        return m;
    }   
    // b)
    public Photo[] getAllPhotosSorted(){
        Photo[] result = myPhotos;
        for (int i = 0; i < myAlbums.length; i++){
            result = combinePhotos(result, myAlbums[i].getAllPhotosSorted());
        }   
        return result;
    }

Aufgabe 6

    // a)
    private static int findPhotoForDate(Date d, Photo[] p, int start, int end){
        // kann Date nicht finden
        if (end > start) {
            return -1; 
        }   
        int mid = (end+start) / 2;
        if (d.equals(p[mid].date)){
            return mid;
        } else if (d.compareTo(p[mid].date) < 0){ 
            return findPhotoForDate(d, p, start, mid-1);
        } else {
            return findPhotoForDate(d, p, mid+1, end);  
        }   
    }   
    // b) hier suchen wir linear nach dem start und end index, das koennte
    // man natuerlich auch mit binary search implementieren, dann waers O(log n), 
    // aber war nicht verlangt
    public static Photo[] findAllPhotosForDate(Date d, Photo[] p){ 
        int index = findPhotoForDate(d, p); 
        if (index == -1) {
            return new Photo[0];
        }   
        // suche startindex
        int start = index; 
        while (start >=0 && p[start].date.equals(d)) {
            start--;
        }   
        // suche endindex
        int end = index+1;
        while (end < p.length && p[end].date.equals(d)) {
            end++;
        }   
        Photo[] result = new Photo[end-start];
        System.arraycopy(p, start, result, 0,  end-start);
        return result;
    }
  • c) O (log n)
  • d) Nein, Ja

Aufgabe 7

a)

  • nein
  • ja
  • nein
  • nein
  • nein
  • ??

b)

B C D E G H I J K
∞ ∞ ∞ ∞ ∞ ∞ ∞ [0] ∞
10 ∞ ∞ [7] ∞ ∞ ∞ 0 ∞
[10] ∞ 25 7 ∞ ∞ ∞ 0 ∞
10 ∞ 25 7 53 ∞ ∞ 0 ∞
10 23 [18] 7 53 ∞ ∞ 0 ∞
10 22 18 7 53 53 [24] 0 ∞
10 22 18 7 53 [44] 24 0 ∞
10 22 18 7 53 44 24 0 60

c)

  • Nein
  • Ja
  • Nein

d)

  • K → B → D → I → H → K
  • G → E → J

e) CD, AB, ID, EJ, BJ, AC, HG, KH, Ef, HI

f) CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK

Aufgabe 9

  • a)
    • O(n)
    • O(n^2)
    • O( n^2)
    • O(n log n)
    • O(n)
  • b)
    • O(1)
    • O(n)
    • O(2^n) sollte nicht O(n) stimmen??