Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 - Wissensfragen   (Übersicht)

Keine Garantie für Korrektheit. Falls etwas nicht passen sollte, einfach ausbessern.

Aufgabe 1 - Wissensfragen

a) Falsch (MergeSort geht auch in-situ)
EDIT: Ich denke die Antwort hier wäre eher richtig. Nach einiger Recherche bin ich auf keine Beispielimplementierung gestoßen, die in situ arbeitet. Viele lehnen komplett ab, dass MergeSort in irgendeiner Weise in situ implementiert werden kann, andere verweisen auf sehr, sehr aufwändige und kaum mehr durchschaubare Varianten, die pseudo-in-situ arbeiten, beispielsweise mit einer „Work-Area“ innerhalb eines Arrays, die man wohl in 99% der Fälle erstmal selbst anlegen muss (Was den Aufwand noch höher treibt auf n²*log(n) und somit die komplette Implementierung, sofern das Array nicht bereits mit Work-Area inklusive an die Methode übergeben wird, völlig schwachsinnig macht.).
EDIT 2: MergeSort wird in der Regel nicht in-situ durchgeführt (Quelle: Vorlesungsfolien WS17/18)

b) Falsch (O(n²))

c) Falsch (O(k * n))

d) Falsch (Direkt erreichbaren)

e) Wahr

f) Falsch (O(n), irrelevant ob einfach oder doppelt verkettet)

g) Falsch

h) Falsch

i) Falsch (Rechter Ast, B über D)

j) Wahr

k) Wahr (aber nur Konstanten)

Aufgabe 2 - Streuspeicherung

a)

Buckets 0 1 2 3 4
Schlüssel B A
D C
E

b)

Buckets 0 1 2 3 4
Schlüssel B0 A0 D1 C1 E4

c)

class Streutabelle {
     LinkedList<String>[] buckets; 
 
     Streutabelle(int size) {
         buckets = new LinkedList[size]; 
     }
 
     void insert (String s, int hs){
         assert s != null && 0 <= hs && hs < buckets.length;
 
         if(buckets[hs] == null){
             buckets[hs] = new LinkedList<String>(); 
         }
 
         if(!buckets[hs].contains(s)){
             buckets[hs].addLast(s); 
         }
     }
}   


Bessere Lösung (statt nur den übergebenen Streuwert zu überprüfen, werden hier alle Streuwerte durchgegangen und geprüft ob sich der String s in irgendeiner LinkedList befindet, weil in der Aufgabenstellung steht „Beachten Sie bitte, dass jeder Schlüssel höchstens einmal in der Streutabelle vorkommen darf“):

import java.util.LinkedList;
 
class Streutabelle {
    LinkedList<String>[] buckets;
 
    Streutabelle (int size) {
        buckets = new LinkedList[size];
    }
 
    void insert (String s, int hs) {
        assert s != null && 0 <= hs && hs < buckets.length;
 
        for (LinkedList<String> list : buckets) {
            if (list != null && list.contains(s)) {
                return;
            }
        }
 
        if (buckets[hs] == null) {
            buckets[hs] = new LinkedList<String>();
        }
 
        buckets[hs].addLast(s);
    }
}
//Anmerkung: hier wird allerdings immer der gleiche hashcode fuer einen String s verwendet, den ich mehrfach einfuege.
//Heisst wenn ich String x (...equals(s)) einfuege, bleibt hs gleich, also landen gleiche Strings immer im gleichen Bucket!!! Wodurch 
//sollte der String in einem anderen Bucket landen? Bedeutet erstere Implementierung reicht fuer diese Anwendung voellig aus!
//Ausserdem wuerde der platz auch kaum reichen auf der Angabe fuer eine Implementierung mit dieser Fehlerbeachtung

Aufgabe 3 - Graphalgorithmen

a) s → (a,1) → (b,6)
a → (b,4) → (c,7)
b → (c,6) → (d,5) → (e,13)
c → (d,1) → (f,7)
d → (e,3)
e → (f,1)
f → (,)

b)

s a b c d e f
0
1s 6s
5a 8a
8a 10b 18b
9c 18b 15c
12d 15c
13e

c) s → a → c → d → e → f

d)

s 0
a [s,a] 1
b [s,b] 6
c [a,b] 4 [b,c] 6 [d,c] 1
d [a,c] 7 [b,d] 5
e [b,e] 13 [d,e] 3 [d,e] 3
f [c,f] 7 [e,f] 1

⇒ [s,a], [a,b], [b,d], [d,c], [d,e], [e,f]

e) true

Aufgabe 4 - Bäume

a)

public class Trie{
 
  Trie[] children = new Trie['Z'-'A'+1];
  String myString;
 
  void insert(String s){
    assert s != null;
    for(char c : s.toCharArray())
      assert c >= ’A’ && c <= ’Z’;
    Trie curr = this;
 
    for(char c : s.toCharArray(){
      if(curr.children[c - 'A'] == null){
            curr.children[c-'A'] = new Trie();
      }
      curr = curr.children[c - 'A'];
    }
 
    curr.myString = s;
  }
}


oder

public class Trie {
    // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben:
    Trie[] children = new Trie['Z' - 'A' + 1];
    String myString; // null, wenn keine Zeichenkette zu speichern ist
 
    void insert(String s) {
        assert s != null;
 
        for (char c : s.toCharArray()) {
            assert c >= 'A' && c <= 'Z';
        }
 
        Trie curr = this;
 
        for (int i = 0; i < s.length(); i++) {
            int charIndex = s.charAt(i) - 'A';
 
            if (curr.children[charIndex] == null) {
                curr.children[charIndex] = new Trie();
            }
            curr = curr.children[charIndex];
        }
        curr.myString = s;
    }
}

b) O(n)

c)

void printSorted() {
    Trie curr = this;
 
    if (curr.myString != null) {
        System.out.println(curr.myString);
    }
 
    for (int i = 0; i < curr.children.length; i++) {
        if (curr.children[i] != null) {
            curr.children[i].printSorted();
        }
    }
}

Aufgabe 5 - Dynamische Programmierung

a)

void initDP() {
   dp = new int[g.length][k+1];
 
   //erste Spalte initialisieren
   for(int i = 0; i < dp.length; i++) {
      dp[i][0] = 0;
   }
}

b)

void fillSingle(int i, int restk) {
   if(i == 0) { 
      /* ... */ 
   } else {
 
      int without = dp[i-1][restk];
 
      int with = 0;   
      if (g[i] <= restk){
         with = dp[i-1][restk-g[i]] + w[i];
      }
 
       dp[i][restk] = Math.max(with, without);
   }
}

c)

void solve() {
   initDP();
   for(int i = 0; i < g.length; i++) {
      // <=, da dp[i] jeweils von 0 bis k (inklusive) reicht
      for(int restk = 0; restk <= k; restk++) {
         fillSingle(i, restk);
      }
   }
 
   return dp[g.length - 1][k];
}

Aufgabe 6 - Abstrakte Datentypen

a)

ops:
	head: FunList 	-> T
	tail: FunList 	-> FunList
axs:
	head(nil) = null;
        head(cons(t, l)) = t;
        tail(cons(t, l)) = l;
        tail(nil) = nil;

b)

Vorschlag:

ops:
	concat: FunList x FunList 	-> FunList
axs:
        // ggf. die folgenden beide nochmal trennen in
        // anyFunList = cons(e, l) und anyFunList = nil
        // Sollte so aber eigtl. passen, auch wenn (nil, nil) auf beide
        // matcht, da in beiden Fällen dasselbe (nil) rauskommt
	concat(nil, anyFunList) = anyFunList
        concat(anyFunList, nil) = anyFunList
        
        concat(cons(elem1, list1), cons(elem2, list2)) =
              cons(elem1, concat(list1, cons(elem2, list2)))        

c)

Entnommen aus dem Tafelfoliensatz zur Übung 9, Folie 7 / 44: https://www2.cs.fau.de/teaching/WS2015/AuD/uebungen/secure/uebung09_handout.pdf

ops
	filter: Pred x FunList	-> FunList
axs
	filter(p, nil) = nil
	filter(p, cons(t, l)) = { cons(t, filter(p, l)) falls apply(p, t)
                                  filter(p, l)          sonst

Aufgabe 7 (Backtracking)

a)

boolean isSolved(int[][] sq){
    int n = sq.length;
    int checkSum = ((n * n * n) + n) / 2;
    int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            rowSum += sq[i][j];
            colSum += sq[j][i];
        }
        if(rowSum != checkSum || colSum != checkSum){
            return false;
        }
        else {
            rowSum = colSum = 0;
        }
    }
    for(int i = 0; i < n; i++){
            diag1Sum += sq[i][i];
            diag2Sum += sq[n - 1 - i][i];
    }
    if(diag1Sum != checkSum || diag2Sum != checkSum){
        return false;
    }
    return true;
}

b)

boolean solve(int [][] sq, int pos, boolean [] used) {
    int n = sq.length;
    int col = pos % n;
    int row = (pos - col) / n;
    if(pos >= used.length){
         return isSolved(sq);
    }
    else {
         for(int i = 1; i <= used.length; i++){
              if(used[i-1] == false){
                   sq[col][row] = i;
                   used[i-1] = true;
                   if(solve(sq, pos+1, used)){
                        return true;
                   }
                   sq[col][row] = 0;
                   used[i-1] = false;
              }
         }
    }
    return false;
}

Aufgabe 8 - Schreibtischlauf

Zeilennummer Fehlerbeschreibung
4 Mehrfachvererbung existiert in Java nicht
12 Kein explizites Casting von double nach int
14 final-Werte sind konstant, hier wird versucht ein final-Wert zu überschreiben
16 Zuweisung ist kein Boolean-Wert, kann somit nicht in der if-Abfrage stehen
20 nicht-statische Variable kann nicht aus statischem Kontext aufgerufen werden
24 Es existiert keine Variable k (mehr)
25 : fehlt im tenären Operator
28 switch fehlt (Herrenloses case)
34 double zurückgegeben, int erwartet (→ selber Fehler wie in Zeile 12)
38 Exception muss via throws MyException deklariert werden, kann nicht so wie hier einfach so geworfen werden
41 abstrakte Methode in nicht abstrakter Klasse