APSP-Algorithmen haben die Komplexität Theta(n^2)
Falsch
Die untere Schranke für vergleichsbasierte Sortieralgorithmen gilt nicht für Count Sort
wahr
Divide and Conquer Algorithmen haben immer eine Laufzeit von Theta (n log n)
falsch, quicksort hat im worst case n^2
Bubble Sort und Quicksort haben die gleiche Worst-Case Komplexität
wahr, n^2
Die Rekursionsgleichung von Merge Sort lautet T(1) = 1, T(n) = T(n/2) + n^2
Falsch, T(n/2) + n log n
Ein entarteter AVL-Baum hat die Höhe Theta(n)
Falsch, es gibt keine entarteten AVL-Bäume -> Rotieren
Aus g(n) = O (f(n)) folgt sofort f(n) = Theta(g(n))
Wahr
Bei der Tiefensuche auf einen schwarzen Knoten zu treffen bedeutet, dass der Graph einen Zyklus enthält
Ein Graph mit n Knoten und genau n-1 Kanten ist ein Baum
Jede Primzahl kann mit dem Sieb des Eratosthenes gefunden werden
Falsch, nur bis zu dem Wert k den wir angeben (Prinzip: Streichen der Vielfachen der aktuellen Primzahlen)
Eine Schlange arbeitet nach dem FIFO-Prinzip
Für alle positiven Zahlen a gilt a f(n) = Theta(f(n))
Ja da a = Konstante
Quicksort ist immer besser als Insertion Sort
Worst-Case anschauen, also falsch, da beide n^2
Binäre Suche funktioniert nur mit sortierten Daten in O(log n)
Die Funktion BuildHeap hat eine Komplexität von Omega (n log n) —> Untere Schranke
Falsch, er kann nicht schneller sein weil er für jedes Element n einen Teilbaum ablaufen muss mit log n
Die Inorder Darstellung eines Heaps liefert eine sortierte Folge
Falsch, ein Heap hat keine Suchbaum Eigenschaften
Rotieren in einem AVL-Baum hat eine Laufzeit von Theta(log n)
Falsch, bei n=3 Knoten muss jeder Knoten einmal verschoben werden also Laufzeit n (vorausgesetzt nur rotation wird betrachtet)
Ein B-Baum der Ordnung 7 kann Blätter mit 2 Werten haben
Falsch, 7/2 - 1 = 2,5 —> Aufgerundet min = 3
Die Anzahl der Schlüssel beim Hashing mit Verkettung ist durch die Größe der Hashtabelle beschränkt
Falsch, keine Kollisionsauflösung -> wird erweitert
Nach welchem Funktionsprinzip arbeitet ein Stack
LIFO
Geben Sie die größte natürliche untere Schranke für die Berechnung einer maximalen 2D-Teilsumme für n x n Zahlen im O-Kalkül an
O(n^3)
Kann Insertion Sort eine quadratische Laufzeit haben?
Ja, Worst/Average Case —> n^2
Best-Case —> n
Nicht vorsortierte Eingabe
Kann Count Sort eine schlechtere Laufzeit als Bubble Sort haben?
Ja, bei einer sehr sehr hohen Eingabenlänge
Geben Sie an wie viele Werte n ein Heap der Höhe h maximal haben kann
h^2 —> vollbesetzer Heap
Wie viele unterschiedliche minimale AVL-Bäume der Höhe 4 gibt es?
Formel: n(0) = 1, N(2) = 2 n(n) = … rekursive Formel
Nennen Sie die Worst-Case Suchzeit bei Hashing mit offener Adressierung mit n Werten
Theta(n) -> n werte in hashtabelle
Können B-Bäume entarten?
Nein, Knoten mit n elementen muss n+1 nachfolger haben
Sei G = (v,e) ein graph mit n knoten, geben sie die laufzeit des dijkstra algorithmus bei min heap an
n log n, wie sonst auch bei heap aufbau
Jeder Graph mit n Knoten hat Untere Schranke Omega(n^2) viele Kanten
Falsch, obere Schranke wäre richtig
Mergesort und quicksort haben im worst-case die gleiche laufzeit
Falsch,
Es gibt funktionen f mit f(n) O(n^3) und f(n) Theta(n^2)
wahr, es gibt eine obere schranke n^2 aber dann kann es ja trzd noch eine obere schranke n^3 geben
Wenn ExtractMin eine Laufzeit O(n) hat, hat HeapSort laufzeit O(n log n^2)
Falsch, n^2 log n
Ein vollständiger 5-ärer Baum der Höhe h hat (5^(h+1) -1) / 4 viele Knoten
Falsch, 5^h
Es gibt nicht mehr binäre Bäume als Inorder Darstellungen
Ja
Hashing mit offener Adressierung garantiert eine Suchzeit von O(log n)
Falsch, O(n)
Jeder kürzeste Weg in einem Graph hat Anzahl V-1 Kanten
Beim Sieb des Erastothenes bleiben durch 3 Teilbare Zahlen übrig
Falsch, vielfache von 3 werden gestrichen
Die AC_laufzeit ergibt sich aus WC-laufzeit + bc-laufzeit / 2
Nein, komplizierte formel
Für alle positiven Zahlen k gilt: log basis k (n) = Theta(logn)
Ja, Zielbasistausch formel und konstanten sind irrelevant
Es gibt Heaps die nicht in linearer Zeit konstruiert werden können
Ja, heaps werden in n log n laufzeit konstruiert
Die Summe der Rotationen beim Einfügen eines wertes in einen Avl-baum hat komplexität O(1)
Die postorder darstellung eines avl baums liefert eine absteigend sortierte zahlenfolge
Nein, nur bei inorder
die anzahl minimaler avl bäume einer bestimmten höhe ist immer durch 2 teilbar
Wegen formel 2* vor dem rekursiven part also durch 2 teilbar
Ein heap hat 54 knoten, wie viele knoten sind in der tiefsten ebene?
formel mit vollbesetzung knoten h^2 -> probieren 7^2 = 49 8^2 = 64 > 54, daher 54-49 = 5 knoten in der letzten ebene
Last changed5 months ago