GladOSkar/IntroProgKlausur_WS_16_17.md

## IntroProgKlausur_WS_16_17.md

      
    Raw
  

              IntroProgKlausur_WS_16_17.md
            
          
    Grafische Version hier: https://gist.github.com/anonymous/7e5cbe027d51f0d3f11b5662008aa170
Gedächtnisprotokoll IntroProg WS 16/17 1

Aufgabe 1: Binäre Suchbäume (11 Punkte)

a) Binärbaum (2 Punkte)

Fügen Sie die folgenden Zahlen in der Reihenfolge in einen vorerst leeren Binärbaum ein:
4, 8, 3, 5, 1, 7
Zeichnen Sie den resultierenden Baum auf.
Geben Sie die Worst-Case-Laufzeit für das finden eines Elements an:
O(______)
b) Min-Heap von Hand (3 Punkte)

Fügen Sie die folgenden Zahlen in der Reihenfolge in einen vorerst leeren min-heap ein:
7, 8, 4, 1, 3, 2
Zeichnen Sie das Ergebnis als Baum sowie als Array.
Geben Sie die Worst-Case-Laufzeit für das finden eines Elements an:
O(______)
c) AVL Eigenschaften (1 Punkt)

Was unterscheidet einen AVL-Baum von einem Binärbaum?
d) AVL von Hand (5 Punkte)

i)
5
 \
  7
   \
    9

Wie müssen sie rotieren, damit der Baum die Bedingungen eines AVL-Baums erfüllt? Tragen sie die Schritte in die Tabelle ein und zeichnen Sie den Baum nach jeder Rotation.
         | Rotation 1 | Rotation 2 |

-------------|------------|------------|
Rechts/Links |            |            |
Knoten       |            |            |
ii)
  5
 / \
1   8
   /
  6
   \
    7

Wie müssen sie rotieren, damit der Baum die Bedingungen eines AVL-Baums erfüllt? Tragen sie die Schritte in die Tabelle ein und zeichnen Sie den Baum nach jeder Rotation.
         | Rotation 1 | Rotation 2 |

-------------|------------|------------|
Rechts/Links |            |            |
Knoten       |            |            |
Aufgabe 2: C-Code (16 Punkte)

a) C-Code (10 Punkte)

Implementieren sie die Binäre Suche auf einem Array aus Structs der folgenden Art:
struct {
	unsigned int nr;
	char* gericht;
	int preis;		// in Eurocent
} sk_eintrag

Vorgaben:


Das gegebene Array ist aufsteigend nach nr sortiert
Wenn die gesuchte nr gefunden wird,
Geben Sie <nr>: <gericht> <preis>\n aus.
Geben Sie den Preis zurück.
Wenn die gesuchte nr nicht gefunden wird,
Geben Sie <nr> nicht gefunden\n aus.
Geben Sie -1 zurück.

int binaere_suche(sk_eintrag array[], int l, int r, unsigned int nr) {
	
}

b) Worst-Case (2 Punkte)

Geben Sie den Worst-Case der Binärsuche in Big-O-Notation an.
c) Best-Case (2 Punkte)

Geben Sie den Best-Case der Binärsuche in Big-O-Notation an.
d) Unsortiertes Array (2 Punkte)

Terminiert der Algorithmus auch, wenn das Array unsortiert ist?
Ist das Ergebnis dann auch korrekt?
Begründen Sie!
Aufgabe 3: Sortieralgorithmen (15 Punkte)

Vorgaben


Benutzen Sie nur Algorithmen, die sie aus der Vorlesung kennen.
Wählen sie immer den "Effizientesten" (sic) Algorithmus

a) Zufallszahlen (3 Punkte)

Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert.
Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden.
Welchen Sortieralgorithmus würden sie wählen?
Begründen Sie!
b) Kreuzung (3 Punkte)

An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos.
Welchen Sortieralgorithmus würden sie für das Sortieren der Tage nach Verkehrsaufkommen wählen?
Begründen Sie!
c) Temperaturen (3 Punkte)

An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte.
Welchen Sortieralgorithmus würden sie für das aufsteigende Sortieren der Temperaturen wählen?
Begründen Sie!
d) Planeten (3 Punkte)

Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden.
Welchen Sortieralgorithmus würden sie wählen?
Begründen Sie!
e) Online-Shop (3 Punkte)

Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu.
Welchen Sortieralgorithmus würden sie wählen?
Begründen sie!
Aufgabe 4: Korrektheitsbeweise (8 Punkte)

Der Folgende Algorithmus soll bewiesen werden.
Addition ( Natürliche Zahlen x,y > 0 )
	resultat ← 0
	for i ← 1 to x do
		resultat ← resultat + 1
	for j ← 1 to y do
		resultat ← resultat + 1
	return resultat

a) Aussagen (2 Punkte)

Wählen Sie EINE kombination aus Tabelle 1 (s.u.), die eine korrekte Aussage über den Algorithmus ist.
Begründen Sie!
Tabelle 1:


#
Quantisierung
#
Aussage


A
keine Quantisierung
1
Addition(x,y) = (x-1)*(y-1)


B
∀k∈{0,...,i}
2
Addition(x,y) = (x-1)*y


C
∀k∈{1,...,i}
3
Addition(x,y) = (x-1)*(y+1)


D
∀k∈{2,...,i}
4
Addition(x,y) = x*(y-1)


E
∀k∈{0,...,(i-1)}
5
Addition(x,y) = x*y


F
∀k∈{1,...,(i-1)}
6
Addition(x,y) = x*(y+1)


G
∀k∈{2,...,(i-1)}
7
Addition(x,y) = (x+1)*(y-1)


H
∀k∈{0,...,(i+1)}
8
Addition(x,y) = (x+1)*y


I
∀k∈{1,...,(i+1)}
9
Addition(x,y) = (x+1)*(y+1)


J
∀k∈{2,...,(i+1)}
10
Addition(x,y) = (x-1)/(y-1)


K
∀k∈{0,...,j}
11
Addition(x,y) = (x-1)/y


L
∀k∈{1,...,j}
12
Addition(x,y) = (x-1)/(y+1)


M
∀k∈{2,...,j}
13
Addition(x,y) = x/(y-1)


N
∀k∈{0,...,(j-1)}
14
Addition(x,y) = x/y


O
∀k∈{1,...,(j-1)}
15
Addition(x,y) = x/(y+1)


P
∀k∈{2,...,(j-1)}
16
Addition(x,y) = (x+1)/(y-1)


Q
∀k∈{0,...,(j+1)}
17
Addition(x,y) = (x+1)/y


R
∀k∈{1,...,(j+1)}
18
Addition(x,y) = (x+1)/(y+1)


S
∀k∈{2,...,(j+1)}
19
Addition(x,y) = (x-1)+(y-1)


20
Addition(x,y) = (x-1)+y


21
Addition(x,y) = (x-1)+(y+1)


22
Addition(x,y) = x+(y-1)


23
Addition(x,y) = x+y


24
Addition(x,y) = x+(y+1)


25
Addition(x,y) = (x+1)+(y-1)


26
Addition(x,y) = (x+1)+(y+1)


27
Addition(x,y) = (x+1)+y


b) Schleifeninvariante 1 (3 Punkte)

Wählen Sie EINE kombination aus Tabelle 2 (s.u.), die eine korrekte Aussage über die erste Schleife ist.
Begründen Sie!
c) Schleifeninvariante 2 (3 Punkte)

Wählen Sie EINE kombination aus Tabelle 2 (s.u.), die eine korrekte Aussage über die zweite Schleife ist.
Begründen Sie!
Tabelle 2:


#
Quantisierung
#
Aussage


A
keine Quantisierung
1
resultat = i-1


B
∀k∈{0,...,i}
2
resultat = i


C
∀k∈{1,...,i}
3
resultat = i+1


D
∀k∈{2,...,i}
4
resultat = j-1


E
∀k∈{0,...,(i-1)}
5
resultat = j


F
∀k∈{1,...,(i-1)}
6
resultat = j+1


G
∀k∈{2,...,(i-1)}
7
resultat = i+j-1


H
∀k∈{0,...,(i+1)}
8
resultat = i+j


I
∀k∈{1,...,(i+1)}
9
resultat = i+j+1


J
∀k∈{2,...,(i+1)}
10
resultat = x+i-1


K
∀k∈{0,...,j}
11
resultat = x+i


L
∀k∈{1,...,j}
12
resultat = x+i+1


M
∀k∈{2,...,j}
13
resultat = x+j-1


N
∀k∈{0,...,(j-1)}
14
resultat = x+j


O
∀k∈{1,...,(j-1)}
15
resultat = y+j+1


P
∀k∈{2,...,(j-1)}
16
resultat = y+i-1


Q
∀k∈{0,...,(j+1)}
17
resultat = y+i


R
∀k∈{1,...,(j+1)}
18
resultat = y+i+1


S
∀k∈{2,...,(j+1)}
19
resultat = y+j-1


20
resultat = y+j


21
resultat = y+j+1
#	Quantisierung	#	Aussage
A	keine Quantisierung	1	Addition(x,y) = (x-1)*(y-1)
B	∀k∈{0,...,i}	2	Addition(x,y) = (x-1)*y
C	∀k∈{1,...,i}	3	Addition(x,y) = (x-1)*(y+1)
D	∀k∈{2,...,i}	4	Addition(x,y) = x*(y-1)
E	∀k∈{0,...,(i-1)}	5	Addition(x,y) = x*y
F	∀k∈{1,...,(i-1)}	6	Addition(x,y) = x*(y+1)
G	∀k∈{2,...,(i-1)}	7	Addition(x,y) = (x+1)*(y-1)
H	∀k∈{0,...,(i+1)}	8	Addition(x,y) = (x+1)*y
I	∀k∈{1,...,(i+1)}	9	Addition(x,y) = (x+1)*(y+1)
J	∀k∈{2,...,(i+1)}	10	Addition(x,y) = (x-1)/(y-1)
K	∀k∈{0,...,j}	11	Addition(x,y) = (x-1)/y
L	∀k∈{1,...,j}	12	Addition(x,y) = (x-1)/(y+1)
M	∀k∈{2,...,j}	13	Addition(x,y) = x/(y-1)
N	∀k∈{0,...,(j-1)}	14	Addition(x,y) = x/y
O	∀k∈{1,...,(j-1)}	15	Addition(x,y) = x/(y+1)
P	∀k∈{2,...,(j-1)}	16	Addition(x,y) = (x+1)/(y-1)
Q	∀k∈{0,...,(j+1)}	17	Addition(x,y) = (x+1)/y
R	∀k∈{1,...,(j+1)}	18	Addition(x,y) = (x+1)/(y+1)
S	∀k∈{2,...,(j+1)}	19	Addition(x,y) = (x-1)+(y-1)
	20	Addition(x,y) = (x-1)+y
	21	Addition(x,y) = (x-1)+(y+1)
	22	Addition(x,y) = x+(y-1)
	23	Addition(x,y) = x+y
	24	Addition(x,y) = x+(y+1)
	25	Addition(x,y) = (x+1)+(y-1)
	26	Addition(x,y) = (x+1)+(y+1)
	27	Addition(x,y) = (x+1)+y
#	Quantisierung	#	Aussage
A	keine Quantisierung	1	resultat = i-1
B	∀k∈{0,...,i}	2	resultat = i
C	∀k∈{1,...,i}	3	resultat = i+1
D	∀k∈{2,...,i}	4	resultat = j-1
E	∀k∈{0,...,(i-1)}	5	resultat = j
F	∀k∈{1,...,(i-1)}	6	resultat = j+1
G	∀k∈{2,...,(i-1)}	7	resultat = i+j-1
H	∀k∈{0,...,(i+1)}	8	resultat = i+j
I	∀k∈{1,...,(i+1)}	9	resultat = i+j+1
J	∀k∈{2,...,(i+1)}	10	resultat = x+i-1
K	∀k∈{0,...,j}	11	resultat = x+i
L	∀k∈{1,...,j}	12	resultat = x+i+1
M	∀k∈{2,...,j}	13	resultat = x+j-1
N	∀k∈{0,...,(j-1)}	14	resultat = x+j
O	∀k∈{1,...,(j-1)}	15	resultat = y+j+1
P	∀k∈{2,...,(j-1)}	16	resultat = y+i-1
Q	∀k∈{0,...,(j+1)}	17	resultat = y+i
R	∀k∈{1,...,(j+1)}	18	resultat = y+i+1
S	∀k∈{2,...,(j+1)}	19	resultat = y+j-1
	20	resultat = y+j
	21	resultat = y+j+1