Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » loesungss06 (Übersicht)
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: private = nur public oder abstract edit: & Z.7 das selbe Z8: float[] statt int Z13: Rückgabewert der Funtkion nicht deklariert, int Z13: } fehlt hinter geschwindigkeit; Z17: extends -> implements Z20: verdichtung ist nirgends deklariert worden - edit: und methode muss public sein Z25: private = public Z27: holeLeistung() muss überschrieben werden Z29: extends -> , Z31: : Doppelpunkt darf nicht sein!? 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)