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!


Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) ganz auf die Deklaration des Ausnahmetyps X verzichten

b) falsch

c) true

d) falsch

e) falsch

f) falsch, richtig: FIFO

g) O(n). Einfügen, nach Prüfen ob doppelt vorhanden: O(n). Um einen Wert zu löschen muss dieser erst gefunden werden: O(n). O(n) + O(n) = O(n).

h) falsch
(unsicher)

Wenn wir in eine Hashtabelle einen Wert einfügen wollen, aber die Stelle bereits belegt ist, haben wir eine Primärkollision. Wenn wir dann diese durch Sondierung auflösen und unseren Wert an einen neuen Ort anlegen wollen, dieser aber auch belegt ist, dann bekommen wir eine Sekundärkollision. Der Fall hier ist aber eine Doppelkollision (siehe auch Foliensatz 11 Folie 87)

i) class GenericContainer<E extends Comparable<E> >
Da in Zeile 6 auf die Methode „compareTo“ zwingend zugegriffen werden muss.

j) O(n log n)

k) falsch

l) falsch

m) O(n log n)

Aufgabe 2 (UML und OOP)

a)
ist unverdaulich
42
2
0.815 kg
4711
4711
Apfelringe
Birnenmus

b)

public interface Essbar {
    String menge = "0.815 kg";
    java.util.ArrayList<Vodka> digestif = new java.util.ArrayList<Vodka>();
    /* List ist besser als Array, denn so muessen wir nicht unbedingt die Groesse festlegen */
    String verdauen(int portionen);
}

c)

 public class MilchShake extends ObstGericht implements Trinkbar{
    static String menge = "1 Becher";
    String bananen = "Hola Chica";
    private boolean laktosefrei = false;
 
    public String verdauen(long portionen){
        return Long.toString(portionen);
    }
 
    public static String schaelen(long aepfel){
        return "Apfelmus";
    }
 
    public String schaelen(String birnen){
        return "Birnenmus";
    }
}

Aufgabe 3 (Abstrakte Datentypen)

Seien a, b vom Datentyp MathExpr und d vom Datentyp double.

a)

ops:
diff: MathExpr → MathExpr

axs:
diff(const(d)) = const(0)
diff(v) = const(1)
diff(add(a, b)) = add(diff(a), diff(b))

b)

ops:
sub: MathExpr x MathExpr → MathExpr
mul: MathExpr x MathExpr → MathExpr

axs:
diff(sub(a, b)) = sub(diff(a), diff(b))
diff(mul(a, b)) = add(mul(diff(a), b), mul(a, diff(b))

c)

axs:
diff(sin(a)) = mul(cos(a), diff(a))
diff(cos(a)) = sub(const(0), mul(sin(a), diff(a))) 

Aufgabe 4 (Streuspeicherung)

a)
i)

Buckets 0 1 2 3 4 5
Schlüssel V2 V4 V3 V1
V5 V6

ii) h’(VK) := 0

b)
i)

Buckets 0 1 2 3 4 5
Schlüssel V2 V4 V6 V5 V3 V1

ii) Lastfaktor = Eingetragene Schlüssel / Buckets = 6/6 = 1 = 100%

Aufgabe 5 (Rekursion)

a)

class MaxFlowMinCut {
 
    void erreichbareVerteiler(Verteiler v, List<Verteiler> ev){
        if(!ev.contains(v)){
            ev.add(v);
            for(Rohr r : v.rohre){
                this.erreichbareVerteiler(r.a, ev);
                this.erreichbareVerteiler(r.e, ev);
            }
        }
    } 

b)

double schnittDurchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite){
        double sum = 0;
        for(Verteiler v : quelleSeite){
            for(Rohr r : v.rohre){
                if((v.equals(r.e) && senkeSeite.contains(r.a)) || (v.equals(r.a) && senkeSeite.contains(r.e))){
                    sum += r.df;                    
                }
            }
        }
        return sum;
    } 

c)

double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){
	Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]);
	double df = schnittDurchfluss(quelleSeite, senkeSeite);
	for(Verteiler v : ssa){
		if(!v.equals(senke) && senkeSeite.contains(v)){
			quelleSeite.add(v);
			senkeSeite.remove(v);
			df = Math.min(df, this.schnittDurchfluss(quelleSeite, senkeSeite));
			senkeSeite.add(v);
			quelleSeite.remove(v);
		}
	}
	return df;		
}

Aufgabe 6 (Graphen)

a)

Q A B C D E F Queue
[0] x x x x x x Q
[1] 3 x 5 x x A, B, D
3 x 4 [2] x E, B, D
[3] x 4 10 B, D, F
7 [4] 10 D, C, F
6 [5] F, C
[6] C
0 1 3 6 4 2 5

b)
Q –> A –> D –> F (oder)
Q –> B –> D –> F

c)
(Q,A) (A,E) (B,D) (D,F) (D,C) (A,D)
9 Meter Kabel

Aufgabe 7 (Sortierverfahren)

a)

class GroessenVergleicher implements Comparator<Socke> {
 
    @Override
    public int compare(Socke o1, Socke o2) {
        if (o1.g < o2.g) {
            return -1;
        } else if (o1.g == o2.g) {
            return 0;
        } else {
            return 1;
        }
    }
} 

b)

public int compare(Socke o1, Socke o2) {
        return o1.m.compareTo(o2.m);
    }    
} 

c)

@Override
public int compare(Socke arg0, Socke arg1) {
   int c = gv.compare(arg0, arg1);
   return c != 0 ? c : mv.compare(arg0, arg1);
} 

d)

    private void mergeSort(int from, int to) {
        if (to <= from) {
            return;
        }
        int mitte = (from + to) / 2;
        mergeSort(from, mitte);
        mergeSort(mitte + 1, to);
        int links = from;
        int rechts = mitte + 1;
        int counter = from;
        for (int i = from; i <= to; i++) {
            sTmp[i] = s[i];
        }
        while (links <= mitte && rechts <= to) {
            if (v.compare(sTmp[links], sTmp[rechts]) <= 0) {
                s[counter++] = sTmp[links++];
            } else {
                s[counter++] = sTmp[rechts++];
            }
        }
        while (links <= mitte) {
            s[counter++] = sTmp[links++];
        }
        while (rechts <= to) {
            s[counter++] = sTmp[rechts++];
        }
    }