b&e
für Prüfung
für Prüfung
Kartei Details
| Karten | 67 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 06.06.2022 / 17.09.2022 |
| Lizenzierung | Keine Angabe |
| Weblink |
https://card2brain.ch/box/20220606_be
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20220606_be/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?
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)
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)
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)
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
