b&e

Was ist die Laufzeitkomplexität für die Methode get, in Abhängigkeit von der Arraygrösse n?

Was ist die Laufzeitkomplexität für die Methode set(n, v) in Abhängigkeit der Grösse des
Arrays?

Was ist die Laufzeitkomplexität für die Methode find, in Abhängigkeit der Array Grösse n?

Ordne zu! Zur Auswahl stehen:

O(1)

O(1) amortisiert

O(n log n)

O(n)

O(log n)

Bag, Stack und Queue können effizient mit ... implementiert werden?

1) Dynamisches Array

2) Verkettete Liste

3) Verkettete Liste oder Dynamisches Array (beide sind gleich effizient)

Erkläre "voller Binärbaum"

Erkläre "Vollständiger (oder kompletter) Binärbaum"

Erkläre "perfekter Binärbaum"

Start bei Knoten 0 - Traversierung in Preorderreihenfolge

Markieren Sie in den folgenden Graphen alle Kanten des induzierten Suchbaums einer Breitensuche die von Knoten 0 ausgeht.

Sei v ein Knoten eines Graphen G. Stimmt es, dass eine von v ausgehende Tiefensuche in G genau die gleichen Knoten besucht wie eine von v ausgehende Breitensuche in G? Nur eine Antwort

Wir haben in dem Algorithmus für kürzeste Pfade eine Breitensuche verwendet und ihn auf
gerichtete Graphen ohne Kantengewichte angewendet.
Ist das alles so notwendig? Welche der folgenden Aussagen sind wahr?
(Bei gewichteten Kanten ist ein kürzester Pfad, ein Pfad, der eine minimale Summe der
Kantengewichte aufweist.)

Bei der Berechnung einer topologischen Sortierung berechnen wir eine Folge P_1,..., P_k, wobei
jedes P_i die umgekehrte Postorderreihenfolge der i-ten Tiefensuche darstellt. Die
Aneinanderreihung Pk, ..., P_1 ergibt dann eine topologische Sortierung.
Ich schlage hiermit ein alternatives Vorgehen vor: führe die gleiche Folge von Tiefensuchen durch,
berechne aber in der i-ten Suche die (nicht umgekehrte) Postorderreihenfolge R_i. Reiht man diese
in der Reihenfolge R_1,...,R_k aneinander und dreht das Gesamtergebnis um, erhält man ebenfalls
eine topologische Sortierung des Graphen. Stimmt das?

Könnte man im Konstruktor von ConnectedComponents statt der Tiefensuche auch eine
Breitensuche verwenden?

Kann man die umgekehrte Postorderreihenfolge in Kosarajus Algorithmus auch mit einer
Breitensuche bestimmen?

Kann man im zweiten Teil von Kosarajus Algorithmus (die Explorationen im Originalgraphen) auch
eine Breitensuche verwenden?

Welche der folgenden Aussagen über Äquivalenzklassen sind wahr?

Ist a in [c] und b in [c], so ist a in [b].

Ist a in [b], so ist [a] = [b].

Ist a in [c] und b in [a], so gilt nicht immer, dass b~c ist.

Ist a in [b], so ist auch [b] in [a].

Markieren Sie in folgendem Graphen alle Kanten des induzierten Suchbaums einer Tiefensuche, die
von Knoten 0 ausgeht. Bei mehreren Nachfolgern betrachten Sie sie bitte wieder in aufsteigender
Reihenfolge ihrer Knotennummer.

QuickUnion, RankedQuickUnion und RankedQuickUnion mit Pfadkompression verwalten intern alle
einen Wald von Bäumen, wobei jeder Baum eine Zusammenhangskomponente repräsentiert.
Mal angenommen, du rufst für jede der Klassen den Konstruktor (für die gleiche Graphengrösse) und
die gleiche Sequenz von union-Operationen, jedoch keine anderen Operationen auf. Wie
unterscheiden sich dann die erzeugten Wälder?

Nur eine Antwort!

Markieren Sie in folgendem Graphen alle Kanten, die in dem von Knotenmenge {0, 1, 4} induzierten Schnitt liegen.

Die roten Kanten sind bereits akzeptiert. Welche Kante nimmt Kruskals Algorithmus als nächstes in den Baum auf?

Die roten Kanten wurden bereits akzeptiert. Markiere alle Kanten, aus denen Prims Algorithmus im nächsten Schritt diejenige mit minimalen Kosten auswählt.

Ordnen Sie die Sortierverfahren ihrer grundlegenden Funktionsweise zu.

Behauptung zu Sortieralgorithmus:

Klicke die richtigen an:

Welche der folgenden Verfahren arbeiten in-place (haben also nur konstanten zusätzlichen Speicherbedarf)?

Klicke die korrekten Aussagen an.

Welche Aussage ist sicher wahr (ankreuzen) und welche ist nicht unbedingt wahr?

Sei f1 € 0 (g1) und f2 € 0 (g2) dann gilt:

Richtig oder falsch?

• Mit Breitensuche kann man bei azyklischen Graphen eine topologische Sortierung bestimmen.

Richtig oder falsch?

• Mit Hilfe mehrerer Breitensuchen kann man die schwachen Zusammenhangs- komponenten von gerichteten Graphen bestimmen.

Richtig oder falsch?

• Dijkstras Algorithmus erfordert, dass alle Kantengewichte positiv (> 0) sind.

Richtig oder falsch?

• Der Bellman-Ford-Algorithmus erfordert azyklische Graphen.

Richtig oder falsch?

•  Quick-Union-Strukturen konnen zur Berechnung von Aquivalenzklassen

  verwendet werden.

Richtig oder falsch?

• Der Quick-Find-Algorithmus repräsentiert Zusammenhangskomponenten durch eine (implizite) Baumstruktur.

Richtig oder falsch?

• Prims Algorithmus baut einen minimalen Spannbaum von einem beliebigen Knoten ausgehend auf.

Richtig oder falsch?

• Die Lazy-Version von Prims Algorithmus hat eine schlechtere asymptotische Laufzeit als Kruskals Algorithmus.

Gibt es in einem ungerichteten Graphen einen Pfad von Knoten u zu Knoten v, gibt es auch einen Pfad von v zu u.

Richtig oder falsch?

Gibt es in einem gerichteten Graphen einen Pfad von Knoten u zu Knoten v, gibt es auch einen Pfad von v zu u

Richtig oder falsch?

In einem azyklischen gerichteten Graphen mit n Knoten kann es n(n-1) Kanten geben.

Richtig oder falsch?

Gibt es in einem azyklischen ungerichteten Graphen einen Knoten u, von dem es zu jedem anderen Knoten einen Pfad gibt, hat der Graph genau n-1 Kanten.

richtig oder falsch?

Ordne zu:

1) Vorteil Adjazenzmatrix

2) Vorteil Adjazenzliste