Vorbemerkung:
Das was hier aufgeschrieben ist, ist alles andere wie
vollstaendig und
soll nur einen groben Ueberblick ueber den Verlauf der
Teilpruefungen darstellen.
(Besser zuviel Trash wie zuwenig *g* )
Viel Spass beim Lesen!
Vordiplomsklausur Info1 und Info2 vom Mi.28.Maerz 2001
Gesamtdauer: 180min
Info1 Teil:
- Geg: (statischen Semantik)
"Delta","Gamma" |- code.toUppercase().charAt(0) : char
a) Erklaeren Sie das Urteil
b) Geben Sie passendes "Delta" an
c) Geben Sie passendes "Gamma" an (fuer beide
Methoden: String.toUppercase und String.charAt() )
d) Geben Sie die Regeln an, mit denen das Urteil
hergeleitet werden kann.
- Erklaeren Sie die Begriffe "VB" und
"NB" von Methoden und Klassen.
- Gegeben war ein Stueck Programmcode bestehend aus
while-Schleife und darin ein IF-Statement.
Gegeben war die Schleifeninvariante und
ges. war ein vollstaendiges Hoarekalkuel.
(Die SchleifenInvariante war riesig!)
- Gegeben sind folgende zwei Java-Klassen:
public class A
{ void p() {System.out.println("A.p()");}
void q() {System.out.println("A.q()");
q(); }
}//A
public class B extends A
{ void q() {System.out.println("B.q()");}
void r() {System.out.println("B.r()");
super.q(); }
}//B
Was steht auf dem Bildschirm nach Ausfuehrung
folgender vier Programme:
a) public static void main(String[] args)
{ B b = new B();
b.p();}
b) public static void main(String[] args)
{ B b = new B();
b.q();}
c) public static void main(String[] args)
{ B b = new B();
b.r();}
d) public static void main(String[] args)
{ A a = new A();
a.r();}
- Gesucht war eine neue Klasse, in der man Variablen
deklarieren musste. Die Variablen wurden gegeben,
man musste diese nur richtig in die Klasse eintragen.
(War sehr einfach! Nichts extremes!)
- Es war der Rumpf einer neuen Klasse gegeben welche
auf Variablen der alten Klasse aus der vorherigen
Aufgabe zurueckgriff, und damit rechnete.
(Fuer jemanden der ein bissl mit Java gespielt hat
war die Aufgabe auch sehr einfach!)
- Im Haskellteil ist folgender Induktionsbeweis zu fuehren:
geg: rev[] = []
rev(h:t) = rev t++[h]
map f [] = []
map f (h:t) = (f h):map f t
Zeige: Fuer alle (endlichen) Listen l und k gilt:
a) map f (l++k) = (map f l)++(map f k)
b) map f (rev l) = rev (map f l)
(Tip: fuer b) kann man Teil a) benutzen.)
- Definieren Sie einen Datentyp fuer binaere Baeume,
fuer den gilt:
die inneren Knoten eines Baumes sind jeweils mit
einer Zeichenkette beschriftet
und die Blaetter sind ganze Zahlen.
- Zu Patternmatching:
Welche der folgenden Haskell-Ausdruecke sind typkorrekt?
Geben Sie dann den Typ an.
a) f1 x y = x
b) f2 x y = x == y
c) f3 x = x x
d) f4 x y = if x y then y else not y
e) f5 x = map (==x)
- Ges: Haskell Ausdruck der eine unendliche Lazy-Liste
darstellt, in der das k-te Element die Summe der
Zahlen 1 bis einschliesslich k ist.
Info2 Teil:
- Gegeben sei folgende Zahlenreihe:
7 , 2 , 6 , 3 , 5 , 8 , 9 , 1 , 4
Sortieren Sie die Zahlen mit dem Quicksort-Algorithmus
und geben Sie die Zwischenergebnisse jeweils beim
Ueberkreuzen der Zeiger an.
- Hashing:
Gegeben sei eine leere, 13 Felder umfassende Hashtabelle
und folgende Schluessel:
18 , 23 , 17 , 10 , 5 , 21 , 8
Dazu seien folgende zwei Hashfunktionen gegeben:
h(x) = x mod 13 und h'(x) = 1 + (x mod 11)
a) Fuegen Sie diese Schluessel mittels Double-Hashing
in die Tabelle ein.
b) Was ist der Vorteil von Double-Hashing gegenueber
- Linearem Sondieren?
- Quadratischem Sondieren?
- Folgendes Array sei gegeben:
1 , 4 , 7 , 16 , 32 , 54 , 83 , 172
Geben Sie den detaillierten Verlauf nach der Suche des
Schluessels 44 , wenn:
a) Exponentielle Suche mit anschliessender Linearer Suche
angewandt wird.
b) Binaere Suche angewandt wird.
- Gegeben sei folgende Zahlenreihenfolge:
1 , 3 , 7 , 8 , 2 , 9 , 6
Stellen Sie einen Max-Heap in Array und in
Baumdartellung her.
Geben Sie die Anzahl der Schluesselvergleiche an.
- Gesucht ist ein AVL-Baum, in dem folgende Schluessel
der Reihe nach eingefuegt werden:
9 , 6 , 8 , 7 , 3 , 1
a) Geben Sie die Anzahl der durchgefuehrten Rotationen an.
b) Welche Arten von Rotationen wurden durchgefuehrt?
- Gegeben ist folgender Suchbaum: (siehe Grafik)
a) Geben Sie folgende Sortierreihenfolge an
- preorder : (loesg: 30,24,11,12,13,28,25,32)
- inorder : (loesg: 11,12,13,24,25,28,30,32)
- postorder : (loesg: 13,12,11,25,28,24,32,30)
[Wenn Ihr die Grafik nicht sehen koennt,
dann koennt Ihr mit Hilfe der Sortierreihenfolgen
den Baum rekonstruieren *g*]
b) Fuegen Sie die Schluessel 31 und 26 in den Baum ein.
c) Entfernen Sie nun die Schluessel 32 und 24.
- Was ist die Laufzeit von Quicksort, Heapsort, Mergesort?
So! Das wars! An mehr kann ich mich nicht mehr erinnern. ;-)
Achja, vielleicht noch folgendes:
Das kam meines Wissens "nicht" dran im Info1 VD Maerz 2001:
Vielleicht kommt das in Eurem Vordiplom dran? ;-)
- Haskell: Succ Zero Datentyp
- Haskell: Listcomprehension
- Haskell: Hoarekalkuel
- Turingmaschine
- Regulaerer Ausdruck, Registermaschinen Programm
- While-Statements instead of for,if,switch..
- Erklaerung funktionaler/imperativer Programmierung
- Kein IEEE, 2CP, BV
- Stapel/Schlange
- Struktogramm
- Def. Algorithmus
- Model View Controller
- Arrays
- Eager/Lazy Auswertung
Und das kam nicht dran im Info2 VD
- Double Hashing nach Brent (uff!)
- Rekursionsgleichungen loesen (schade *g*)
[...]
(neue verbesserte Version vom 4.Mai 2001) |
