Alpii ZK - asdfasdfa. asdcasdf asdf a asfd asfdl,,ü,erf wef lmöeflmafa PDF

Preview

Summary

asdfasdfa. asdcasdf asdf a asfd asfdl,,ü,erf wef lmöeflmafa...

Description

ALP II Objektorientierte Programmierung SS 2010 Prof. Dr. Margarita Esponda

Zwischenklausur Name: ................................. Vorname:.................................. Matrikel-Nummer:.............. Ich bin mit der Veröffentlichung der Klausurergebnisse mit Matrikel-Nummer und Note im Internet einverstanden: ฀ ja

฀ nein

Unterschrift:........................................... Die maximale Punktzahl ist 26. Zum Bestehen der Klausur sind 13 Punkte erforderlich. Aufgabe

A1

A2

A3

A4

A5

Summe

Note

Punkte

Viel Erfolgt! 1. Aufgabe (1 Punkte) Was ist ein dynamisches Typsystem im Kontext von Programmiersprachen? 2. Aufgabe ( 9 Punkte) Eine Annährung der Zahl

π kann mit Hilfe der Leibniz-Reihe wie folgt berechnet

werden: n

("1) k 1 1 1 1 = 4 $ (1" + " + "...) = % 3 5 7 9 k= 0 2k + 1

Rn = 4 #

a) Schreiben Sie unter Verwendung einer while-Schleife (keine for-Schleife) eine iterative Python-Funktion, die bei Eingabe von n das n-te Element der LeibnitzReihe berechnet und als Ergebnis zurückgibt. b) Schreiben Sie eine rekursive Python-Funktion, die das gleiche berechnet.

c) Welches Hauptproblem würden Sie in der Python Virtuellen Maschine mit ihrer rekursiven Lösung haben? 3. Aufgabe (4 Punkte) Betrachten Sie folgendes Array A = [5,3,2,0,9,7,4,1] Wenn sie die Zahlen mit Hilfe des Mergesort-Algorithmus sortieren und immer am Ende der merge-Funktion das Array A ausgeben, wie würde die Ausgabesequenz aussehen?

4. Aufgabe (5 Punkte) In der imperativen Implementierung des Quicksort-Algorithmus spielt das Umsortieren der Zahlen innerhalb der Partitionierungs-Funktion eine wesentliche Rolle, weil die Teilung der Zahlen in zwei Bereiche in dem Array selber stattfindet (sortieren „in-place“). Erläutern sie einen Durchgang des Partitionierungs-Teils des Algorithmus anhand folgender Zahlensequenz. A = [4,6,7,1,0,3] Ist der Quicksort-Algorithmus stabil? Begründen Sie Ihre Antwort. 5. Aufgabe ( 7 Punkte ) Gegeben sei das folgende Programm, das bei Eingabe einer natürlichen Zahl n die Summe der Zahlen zwischen 0 und n berechnet. n = int(input('n=')) assert n>=0 i=0 sum = 0 assert sum == (i*(i-1))//2 # INV while i n assert sum == (n*(n+1))//2 Zeigen Sie, dass INV

≡ sum = i " (i #1) 2

eine Invariante der while-Schleife des

Programms ist. Geben Sie die verwendeten Hoare-Regeln explizit an....