Themen

Struktogramme
Rekursion - Iteration
Listen: Einfach / Doppelt Verkettet
Baum Traversieren
Suchbaum aufbauen
2,3,4 Baum
Hashing
Liste zu Suchbaum
Sondieren: linear / quadratisch
Komplexität eines Algorithmus
Sortierverfahren

Theorie

backtracking / divideconqr fehlt

Nennen sie 3 Eigenschaften von Algorithmen
Wann ist ein Algorithmus terminierend? Wann ist er deterministisch?
Hat jeder deterministische Algorithmus auch ein deterministisches Ergebnis?
Erklären sie kurz die Vorteile Digitaler Suchverfahren anhand des Radix-Exchange Sorts
Was ist der Vorteil von Hashing gegenüber Bäumen?
Wieso sind Suchbäume besser als Listen?
Wann sollte eine Binäre Suche einer Linearen Suche vorgezogen werden und umgekehrt?
Wieso ist es manchmal von Vorteil Algorithmen mit schlechten Komplexitäten Algorithmen vorzuziehen, die “bessere” Komplexitäten haben?
Was ist der Unterschied zwischen Präzisität und Effizienz eines Algorithmus?
Was ist der Unterschied zwischen Komplextiät und Laufzeit?
Worin besteht der Sinn von Divide and Conquer? Geben sie 2 Algorithmen an die Divide and Conquer benutzen
Was ist eine Datenstruktur? Wozu wird sie genutzt?
Welche Schnittstellen enthält ein Keller und nach welchem Prinzip verfährt er?
Was ist der Vorteil von Double Linked Lists gegenüber einfach verketteten Listen?
Was ist die minimale Höhe eines Binärbaums mit 925 Knoten?
Wann können Bäume entarten? Wieso stellt Entartung ein Problem dar?
Was sind AVL Bäume und B-Bäume?
Kann es bei einem bijektiven Hashing zu Kollisionen kommen?
Sollte eine Hashing Funktion immer bijektiv/surjektiv oder injektiv sein?
Was ist die Höhe eines Fast Vollständingen Baums mit Höhe 40?
Was ist die Höhe eines Vollständingen Baums mit Höhe 40?




Anwendung

Gegeben ist die Funktion f(n) = n+1(-3n+5n-5/2)*sqrt(81). Zeigen sie mit Hilfe von T element von O(f), dass diese Funktion ab einem n0 langsamer, als f(n) = 100n wächst.
Terminiert folgender Algorithmus?
Komplexität dieses Algorithmus?
Erstellen sie zu diesem Algorithmus zusätzlich ein Struktogramm
Formen sie diesen rekursiven Algorithmus in einen iterativen um.
Formen sie einen anderen iterativen in einen rekursiven Algorithmus
Fügen sie in zwei Hashing Tabellen die folgenden Zahlen ein: 0, 2, 67,13,17,88,12,3,7 indem sie die Funktion h(x) = x % 13 verwenden und einmal quadratisch und linear sondieren. Geben sie die Anzahl der Kollisionen an.
Fügen sie folgende Buchstaben mit Hilfe des Top Down Verfahrens in einen 2,3,4 Baum ein: s, l , r, a ,t , z , y, q, r, e, t, v, o
Bilden sie zu diesem 2,3,4 Baum den entsprechenden Rot Schwarz Baum und geben sie dessen Höhe an.
Geben sie zusätzlich die Komplexität an die ein Suchen in diesem Baum erfordern würde.
Welches Niveau hat der Buchstabe q?
Welchen Grad besitzt der Baum?
Fügen sie diesem Rot-Schwarz Baum noch die Buchstaben z,i,n,m hinzu und balancieren sie diesen aus.
Geben sie den Pfad von der Wurzel zu z an.
Führen sie nun eine Rechts Links Rotation um z aus.
Sortieren sie die folgenden Zahlen mit Hilfe von Selection, Insertion, Bubble, Merge und QuickSort: 109,25,6,78,2,8,0,33,678,35
Geben sie bei jedem Sortierverfahren die Komplexität im Worst und Best Case an
Gegeben ist eine Tabelle mit 2 Attributen und ein Maximum was einen der beiden Werte aufnehmen kann. Benutzen sie das Greedy Verfahren um das beste Verhältnis zu erhalten
Traversieren sie durch ihren Rot Schwarz Baum mit Hilfe von Pre / Post / In und Level Order und fügen sie die erhaltenen Werte wieder in einen 2,3,4 Baum
Ist dieser Baum identisch mit dem Rot Schwarz Baum?
Was ist die minimale Höhe des Baumes der Pre Order?
Erstellen sie einen BinärBaum der die minimale Höhe enthält




Backtracking fehlt
Rekursion - Divide and Conquer fehlt




Advanced

Implementieren sie eine Double Linked List Add Methode, die immer das vor-vor Letzte Element zurückgibt
Erstellen sie eine weitere Methode die das Element in der Mitte der Liste zurückgibt
Implementieren sie eine iterative Such Methode in einem BinärBaum
Implementieren sie nun auch eine Lösch Methode insbesondere für den Fall, dass ein innerer Knoten gelöscht werden soll
Formen sie ihre iterative Such Methode in eine rekursive um
Gegeben ist ein Min Heap Baum. Entfernen sie die Elemente q, r und fügen sie p und x hinzu