ALG20 TOK 02.03.2024

[Nordmann_Loki]

Hier die Klausur vom 02.03.2024

Die Aufzeichnungen und Fragestellungen zu der Klausur sind vollständig und ich hoffe es hilft manchen.
Vielen Dank auch an alle die vorab hier ihre Aufgaben geteillt haben.

Komplexaufgaben

1.1 Was ist ein Graph 4P
1.2 Was ist ein Baum 4P
1.3 Was ist ein binärer Baum 4P

2 Was ist das Halteproblem 6P

3.1 Was ist eine doppelt verkettete Liste 6P
3.2 Welche Informationen hat ein Element der doppelt verketteten Liste 6P
3.3 Was muss beim löschen eines Elementes der doppelt verketteten Liste beachtet werden 4P

4 Was ist ein randomisierter Algorithmus 6P

----------------------------
Detailaufgaben

-- Binäre Suchbäume ----------------------------------------------------------------------------------------------------------------------------------------

1.1 Was ist ein Binärer Suchbaum 6P
1.2 Warum heisst er binärer Suchbaum 4P
1.3 Drei binäre sind gegeben, welche der Bäume sind binäre Suchbäume 4P

2 Es ist der "Algorithmus der Suche in einem binären Suchbaum" gegeben (Weicker s89 Alg 4.14)

2.1 Erklären sie den Algorithmus in eigenen Worten 10P
2.2 Es ist ein binärer Suchbaum gegeben. 6P
Geben Sie "el" für jeden Durchlauf an. ("el" ist in dem Algorithmus zu finden)
Geben Sie auch die Anzahl der Schlüsselvergleiche an.
2.3 Was ist die Laufzeit des binären Suchbaums im WORST CASE 2P

3 Wie fügt man ein Element in einem Binären Suchbaum ein 8P

-- Sortieren in verketteter Liste --------------------------------------------------------------------------------------------------------------------------

1 Warum kann man bei der Liste nicht wie bei einem Feld/Array direkt auf ein Element zugreifen 4P

2 Was ist ein Blindelement und was bringt es 8P

3 Wie unterscheiden sich Laufzeit einer sortierten Liste zu einer unsortierten Liste,
Vergleichen Sie auch die Datenstrukturen hinsichtlich, dass das Element nicht in der Liste enthalten ist 6P

4 Der "Algorithmus zum Einfügen in eine Liste mit Blindelementen " ist gegeben (Weicker s74 Alg 4.6 ) 4P
Was passiert in Zeile 2 und 3 4P
2: While el.nächtes ungleich 0 & el.nächstes.wert < neu.wert
3: do el -> el.nächtes

5 Was macht der Befehl "allokiere" in Zeile 5 2P

6 Der "Algorithmus zum Suchen in in sortierter Liste mit Blindelementen" ist gegeben (Weicker s73 Alg 4.5 ) 12P
- Erklären sie den Algorithmus in eigenen Worten
- Erwähnen Sie auch das Blindelement
- Unter welchen 3 Bedingungen endet die Schleife

7 Was muss beim Löschen aus der SORTIERTEN verketteten Liste beachtet werden 2P

-- Spannbäume und Rundreise -----------------------------------------------------------------------------------------------------------------------------

1 Rundreise Allgemein
1.1 Wie oft sollen die Knoten bei der Rundreise besucht werden 6P
1.2 Welche von mehreren Rundreisen ist die Beste 4 (Hier waren keine Rundreisen gegeben, es geht wirklich um die allgemeine Aussage) 4P

2 Spannbäume
2.1 Definieren Sie "Was ist ein Spannbaum" 6P
2.2 Definieren Sie " Was ist ein minimaler Spannbaum" 4P

3 Spannbaum und Rundreise
3.1 Unter welchen Bedingungen kann man einen Spannbaum für die Lösung einer Rundreise nutzen 6P
3.2 Was sagen die Kosten des minimalen Spannbaums über die Kosten der kürzesten Rundreise aus 2P
3.3 Es ist der "Algorithmus Approximation einer kürzesten Rundreise anhand des minimalen Spannbaums" gegeben (Weicker S 130 Alg 5.6)
Was macht der Algorithmus 2P
3.4 Wie lautet die Fehlergarantie des Algorithmus 2P
3.5 Erklären Sie die Tiefensuche des Algorithmus ( Zeile 4 im Algorithmus)