Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch   (Übersicht)

Dies ist eine alte Version des Dokuments!


Lösungsversuch

Aufgabe 1 Wissensfragen

a) 1 und 2

b) 2 und 3

c) 2 und 4

d) 2 und 4

e) 1

f) 1 und 3

g) 3 und 4

h) 1 und 4

i) 1 und 2

j) 1 und 3

  • zu 4)
    • ⇒ Eine endrekursive Methode kann unmittelbar entrekursiviert werden.

Aufgabe 2 Suchen und O-Kalkül

a)

static int[] searchNaive(int[] a, int z) {
    int[] r = null;
    for(int i = 0; i < a.length; i++) {
        for(int j = i+1; j < a.length; j++) {
            if(a[i] + a[j] == z) {
                r = new int[] {i, j}; 
            }
        }
    }
    return r;
}

b)

static int[] searchLinear(int[] a, int z) {
    int i = 1, j = a.length - 1;
    while(i < j) {
        if(a[i] + a[j] == z) {
            return new int[] {i, j};
        } else if(a[i] + a[j] < z) {
            i++;
        } else {
            j--;
        }
    }
}

c)

static LinkedList<Integer> searchDuplicates(int[] a, int[] b) {
    LinkedList<Integer> ds = new LinkedList<>();
    AVLTree at = new AVLTree();
 
    for(int x : a) {
        at.insert(x);
    }
 
    for(int x : b) {
        AVLNode r = at.root;
 
        while(r != null) {
            if(x < r.data) {
                r = r.left;
            } else if(x > r.data) {
                r = r.right;
            } else {
                ds.add(x);
                break;
            }
        }
 
    }
    return ds;
}

Aufgabe 3 Bäume

a)

B1 B2 B3
Preorder: ∧∨ab∨cd ∨∧ab¬∨cd ∨¬a∧¬b∨¬cd
Inorder: (a∨b)∧(c∨d)) a∧b∨¬(c∨d) ¬a∨¬b∧(¬c∨d)
Postorder: ab∨cd∨∧ ab∧cd∨¬∨ a¬b¬c¬d∨∧∨

b)

LinkedList<KOp> toPrefix() {
    LinkedList<KOp> r = new LinkedList<>();
 
    r.add(o);
    for(KTree c : cs) {
        r.addAll(c.toPrefix());
    }
 
    return r;
}