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

Dies ist eine alte Version des Dokuments!


1) Binärsuche

public boolean binarySearch(int[] x, int value) {
        int wert = (x.length-1)/2;
	while(wert!= 0 && wert!= x.length-1) {
		if(value == x[wert])
			return true;
		else if(value < x[wert])
			wert /=2;
		else
			wert += wert/2;
		if(wert==0 && x[0]==value 
                              || wert==x.length-1 && x[x.length-1]==value)
			return true;
	}
	return false;
}
	
 public static boolean binSuchRek(int[] x, int value) {
	return binHelper(x,value,(x.length-1)/2);
 }

 public static boolean binHelper(int[] x, int value, int marker) {

        if(marker ==0 && x[0]==value 
                || marker==x.length-1 && x[x.length-1]==value)
		return true;

	if( marker == 0 || marker == x.length-1)
		return false;

	if(value == x[marker])
		return true;

	else if(value < x[marker])
		return binHelper(x,value,marker/2);

	else
		return binHelper(x,value,marker + marker/2);
 }

2) Schleifeninvariante

a) F1: f = a! (logisch gedacht) F2: f = n! / a! (f=a*n logisch ausgeschlossen und F2 != F1)

F1: wp…. f*(a+1) = (a+1)! f*(a+1) = (a+1)*a! f = a! q.e.d.

F2: wp…. f*a = n! / (a-1)! f*a = n! / ( a! / a) f = n! /a! q.e.d.

b) xxx


3)

Z1: <del>private</del> = nur public oder abstract
Z8: float[] statt int
Z13: Rückgabewert der Funtkion nicht deklariert, int
Z13: } fehlt hinter geschwindigkeit;
Z17: <del>extends</del> -> implements
Z20: verdichtung ist nirgends deklariert worden
Z25: <del>private</del> = public 
Z29: <del>extends</del> -> ,
Z33: Rückgabewert int - returnt aber float

4a) Balancierter binärer Suchbaum, bei dem für jeden Knoten die Höhe der beiden Teilbäume sich höchstens um 1 unterscheidet.

Aufwand: Löschen, Suchen, Einfügen in O(log n)