d&e
für Prüfung
für Prüfung
Kartei Details
| Karten | 17 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Scherzfragen |
| Stufe | Universität |
| Erstellt / Aktualisiert | 17.05.2022 / 06.07.2022 |
| Weblink |
https://card2brain.ch/box/20220517_de
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20220517_de/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
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?
Array
Was ist die Laufzeitkomplexität für die Methode find, in Abhängigkeit der Array Grösse n?
Zur Auswahl steht:
O(1)
O(1) amortisiert
O(n log n)
O(n)
O(log n)
Ordne zu!
Verkettete Liste: Zugriff auf beliebiges Element -> O(n)
Verkettete Liste: Einfügen am Anfang -> O(1)
Array: Zugriff auf beliebiges Element -> O(1)
Verkettete Liste: Einfügen am Ende (ohne Last Pointer) -> O(n)
Array: Einfügen am Anfang -> O(n)
Array: Einfügen am Ende -> O(1) amortisiert
Array: Löschen am Ende -> O(1) amortisiert
Verkettete Liste: Löschen am Ende -> O(n)
Verkettete Liste: Zusätzlich benötigter Speicher -> O(n)
Array: Löschen an beliebiger Position -> O(n)
Array: Zusätzlich benötigter Speicher -> O(1)
Verkettete Liste: Einfügen am Ende (mit Last Pointer) -> O(1)
Zur Auswahl stehen:
1) Dynamisches Array
2) Verkettete Liste
3) Verkettete Liste oder Dynamisches Array (beide sind gleich effizient)
Ordne diese zu Bag, Stack und Queue zu!
Bag = Verkettete Liste oder Dynamisches Array (beide sind gleich effizient)
Stack = Verkettete Liste oder Dynamisches Array (beide sind gleich effizient)
Queue = Verkettete Liste
Erkläre "voller Binärbaum"
Jeder Knoten hat 0 oder 2 Kinder
Erkläre "Vollständiger (oder kompletter) Binärbaum"
Alle Ebenen sind vollständig gefüllt ausser evtl. die letzte Ebene, wobei nur die Blätter rechts fehlen dürfen.
Erkläre "perfekter Binärbaum"
Alle internen Knoten haben genau 2 Kinder und alle Blätter sind auf der gleichen Ebene
Start bei Knoten 0 - Preorderreihenfolge
043125
Markieren Sie in den folgenden Graphen alle Kanten des induzierten Suchbaums einer Breitensuche die von Knoten 0 ausgeht.
siehe Bild
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].
