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

Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

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;
}