Altklausur

Question 1

Welche Aussagen sind richtig? MergeSort…
1. …benötigt für das Sortieren von n Elementen im besten Fall O(n log n) Vergleiche.
2. …benötigt für das Sortieren von n Elementen im schlechtesten Fall Θ(n²) Vergleiche.
3. …sortiert rekursiv.
4. …’s Laufzeit ergibt sich als T(n) = T(2n) + T(2n)

Answer 1

Nummer 1 und 3 sind richtig.

Question 2

Randomized QuickSort

Welche Aussagen sind richtig? Wir betrachten Randomized-QuickSort. Durch die zufällige Wahl des Pivot-Elements…
1. …kann für das Sortieren von n Elementen im besten Fall 1 Vergleich ausreichen.
2. …ist die erwartete Laufzeit für jede Eingabe O(n log n).
3. …verbessert sich die worst-case-Laufzeit auf O(n).
4. …sind im schlechtesten Fall Θ(n³) Vergleiche notwendig.
5. …kann die Laufzeit jeweils unterschiedlich sein, wenn der Algorithmus mit der gleichen Eingabe mehrfach aufgerufen wird.

Answer 2

Die Nummer 2 und 5 ist richtig.

Question 3

Welche Aussagen sind richtig? Randomized-QuickSort…
1. …nutzt die Prozedur Randomized-Partition.
2. …nutzt die Prozedur Randomized-Sort.
3. Randomized-Partition wählt ein zufälliges Pivot-Element.
4. Randomized-Sort sortiert andere Elemente zufällig vor oder hinter das Pivot-Element.

Answer 3

Nummer 1 und 3 sind richtig.

Question 4

Welche Aussagen sind richtig? Zu den Eigenschaften von Rot-Schwarz-Bäumen gehört:
1. Die Wurzel ist rot.
2. Alle Blätter sind schwarz.
3. Wenn ein Knoten rot ist, dann sind seine Kinder schwarz.
4. Auf allen Pfaden von der Wurzel aus zu jedem Blatt ist die Anzahl roter Knoten immer die gleiche.

Answer 4

Nummer 2 und 3 sind richtig.

Question 5

Welche Aussagen sind richtig? Wir kennen einen Algorithmus, der Dynamisches Programmieren nutzt, um das Problem effizient zu lösen:
1. Produktionsband-Zeitplannung
2. Längste gemeinsame Teilsequenz
3. Rundreise
4. Rucksackproblem

Answer 5

Nummer 1 und 2 sind richtig.

Question 6

Welche Aussagen sind richtig? Wir kennen einen greedy Algorithmus, der das Problem effizient löst:
1. Stabzerlegung
2. Längste gemeinsame Teilsequenz
3. Rundreise
4. Minimaler Spannbaum

Answer 6

Nummer 4 ist richtig.

Question 7

Welche Aussagen sind richtig? Binäre Suche…
1. …in einem sortierten Feld der Länge n benötigt im besten Fall 1 Vergleich.
2. …in einem sortierten Feld der Länge n benötigt maximal O(log n) Vergleiche.
3. …angewandt auf eine sortierte einfach verkettete Liste hat im schlechtesten Fall Laufzeit O(log n).
4. …kann in einem nicht sortierten Feld nicht sinnvoll angewendet werden.

Answer 7

Nummer 1, 2 und 4 sind richtig.

Question 8

Welche Aussagen sind richtig? Wenn in einem vollständig binären Baum mit Höhe > 2 von der Wurzel aus gesucht wird, dann gilt:
1. Die ersten beiden mittels Tiefensuche erreichten Knoten (nach der Wurzel) befinden sich in derselben Ebene.
2. Die ersten beiden mittels Breitensuche erreichten Knoten (nach der Wurzel) befinden sic in derselben Ebene.
3. Tiefensuche erreicht ein Blatt, bevor der zweite Nachfolger der Wurzel betrachtet wird.
4. Breitensuche erreicht ein Blatt, bevor der zweite Nachfolger der Wurzel betrachtet wird.

Answer 8

Nummer 2, 3 und 4 sind richtig.

Question 9

Welche Aussagen sind richtig? CountingSort…
1. …benötigt für das Sortieren von n Elementen mindestens O(n log n ) Vergleiche.
2. …benötigt für das Sortieren von n Elementen O(n) Vergleiche.
3. …‘sLaufzeit hängt davon ab, wie groß das Größte zu sortierende Element ist.
4. … ist stabil.

Answer 9

Die Nummer 3 und 4 sind richtig.

Question 10

Welche Aussagen sind richtig?
1. Ein binärer Suchbaum mit n Knoten hat immer die Höhe Theta(lg n)
2. Ein binärer Suchbaum mit n Knoten hat im schlechtesten Fall Höhe O(sqrt(n))
3. Die erwartete Tiefe eines zufälligen binären Suchbaums ist O(lg n)
4. Die Laufzeit für das Einfügen eines neuen Knoten ist Theta(1)

Answer 10

Die Nummer 3 ist richtig.

Question 11

Wahr oder Falsch?
Ein Angreifer kann RandomizedQuickSort mit einem Array der Länge n füttern, dass den Algorithmus zu einer Laufzeit von w(n lg n) zwingt.

Answer 11

Falsch, RandomizedQuickSort hat weiterhin eine worst-case Laufzeit von O(n²).

Question 12

Wahr oder Falsch?
HeapSort kann als Hilfssortieralgorithmus in RadixSort verwendet werden.

Answer 12

Falsch, RadixSort nutzt CountingSort als Hilfsalgorithmus.

Question 13

Wahr oder Falsch?
Für f(n) = n gilt g(n) = O(sqrt(n)).

Answer 13

Falsch, sqrt(n) = n^(1/2) und der exponent 1/2 < 1, daher passt n nicht in O(sqrt(n)).

Question 14

Wahr oder Falsch?
Durch die zufällige Wahl des Pivot-Elements bei RandomizedQuickSort verbessert sich die wort-case Laufzeit auf O(n).

Answer 14

Falsch, die Randomisierung verbessert nur die erwartete Laufzeit, verändert die worst-case Laufzeit also nicht. Diese bleibt weiterhin bei O(n²).

Question 15

Wahr oder Falsch?
Die Wurzel von Schwarz-Rot-Bäumen ist rot?

Answer 15

Falsch, die Wurzel ist immer schwarz.

Question 16

Welche Aussagen sind richtig? Wir betrachten die asymptotische O-Notation. Für f(n) = n² gilt:
1. f(n) = O(n²)
2. f(n) = o(n²)
3. f(n) = Omega(n)
4. f(n) = Theta(3n² - 15n + 100)

Answer 16

Die Nummer 1, 3 und 4 sind richtig.

Question 17

Welche(r) der folgenden Sortieralgorithmen benötigt/benötigen auf jedem beliebigen Array der Länge n höchstens O(n lg n) Vergleiche?
1. MergeSort
2. InsertionSort
3. QuickSort
4. RandomizedQuickSort

Answer 17

Die Nummer 1 ist richtig.

Question 18

Welche Aussagen sind richtig? HeapSort…
1. … sortiert, indem das betrachtete Array durch Aufrufe von BuildHeap abwechselnd als Max-Heap und als Min-Heap organisiert wird.
2. … sortiert, indem abwechselnd das letzte Element von einem Max-Heap entnommen und dann auf dem verbliebenen Array Max-Heapify aufgerufen wird.
3. … hat eine worst case Laufzeit von O(n lg n).
4. … sortiert in-place.

Answer 18

Nummer 2, 3 und 4 sind richtig.

Question 19

Welche Aussagen sind richtig? Ein gerichteter Graph, der n Knoten und m Kanten enthält…
1. … kann durch eine Adjazenzmatrix der Größe n x n dargestellt werden.
2. … kann durch eine Adjazenzmatrix der Größe n x m dargestellt werden.
3. … kann durch eine Adjazenzmatrix der Größe m x m dargestellt werden.
4. … kann durch eine Adjazenzliste dargestllt werden, deren Speicherbedarf Theta(n + m) ist.

Answer 19

Die Nummer 1 und 4 sind richtig.

Question 20

Wahr oder Falsch?
Sei T der minimale Spannbaum von G. Dann gilt für alle Paare von Knoten s und t, dass der kürzeste Pfad zwischen s und t in T enthalten ist.

Answer 20

Falsch, denn die Eigenschaft von MST sind nicht kürzeste Wege, sondern ein allgemein niedriges Gewicht des Baums.

Question 21

Wahr oder Falsch?
Sei S eine Menge von n ganzen Zahlen. Dann kann man eine Datenstruktur für S entwerfen, die es ermöglicht in O(1) zu bestimmen, ob x zur Menge S gehört.

Answer 21

Wahr

Question 22

Wahr oder Falsch?
MergeSort’s Rekursionsgleichung ergibt sich aus T(n) = 2T(n/2) + n

Answer 22

Wahr

Question 23

Welche Aussagen sind richtig? Wir betrachten die asymptotische O-Notation. Für f(n) = n gilt:
1. f(n) = O(sqrt(n))
2. f(n) = O(n³)
3. f(n) = Theta(n log n)
4. f(n) = Theta(n^4 - 7n²)

Answer 23

Nummer 2 ist richtig.

Question 24

Welche Aussagen sind richtig? QuickSort…
1. … benötigt für das Sortieren von n Elementen im schlechtesten Fall O(n lg n) Vergleiche.
2. … nutzt die Prozedur Partition, die alle größeren Elemente hinter und alle anderen vor das Pivot-Element sortiert.
3. … sortiert in-place.
4. … ist stabil.

Answer 24

Nummer 2 und 3 sind richtig.

Question 25

Wahr oder Falsch?
Gemäß dem Master-Theorem, ist T(n) = Theta(n lg n) die Lösung der Rekurrenz T(n) = 3T(n/3) + lg n.

Answer 25

Falsch, diese Rekurrenz passt zu Fall 1 des Master-Theorem, somit ist die Lösung Theta(n).

Question 26

Wahr oder Falsch?
Jeder binäre Suchbaum mit n Knoten hat die Höhe O(lg n).

Answer 26

Falsch, die wort-case Höhe von BST ist O(n).

Question 27

Wahr oder Falsch?
Sei ein Graph G = (V,E) gegeben mit entsprechenden Kosten auf jeder Kante und einer Menge S ist Teilmenge von V. Sei (u,v) die Kante mit den minimalen Kosten, zwischen jeder Kante aus S und jeder Kante aus V - S. Dann muss der MST von G die Kante (u,v) enthalten.

Answer 27

Falsch

Question 28

Wahr oder Falsch?
Das Array <20 15 18 7 9 5 12 3 6 2> ist ein Max-Heap.

Answer 28

Wahr

Question 29

Wahr oder Falsch?
Angenommen ein Array enthält n Werte, jeder davon ist -1, 0 oder 1. Dieses Array kann im Wort-Case in linearer Zeit, also O(n), sortiert werden.

Answer 29

Wahr

Question 30

Wahr oder Falsch?
Es existiert ein Vergleichssortierverfahren, dass für 5 Zahlen im Wort-Case 6 Vergleiche benötigt.

Answer 30

Falsch, das Vergleichssortierverfahren mit bester worst-case Laufzeit ist MergeSort/HeapSort mit O(n lg n).

Question 31

Sei F(k) die k-te Fibonaccizahl. Dann kann die n²-te Fibonaccizahl F(n²) in O(lg n) berechnet werden.

Answer 31

Wahr

Question 32

Gegeben sei eine Hashtabelle mit Kollisionsbehandlung durch Verkettung von n Schlüsseln und mit einem Belegungsfaktor von alpha = 1/lg n. Unter der Annahme von gleichförmigem Hashing ist die erwartete Suchzeit für einen Schlüssel in O(1/lg n).

Answer 32

Falsch, die Suchzeit ist O(1 + alpha), also O(1), da 1/lg n < 1.