Grundlegende Datenstrukturen

Question 1

Nenne beide Varianten zur Realisierung von linearen Listen

Answer 1

1. Sequenziell
2. Verkettet

Question 2

Nenne Vorteile der Sequenziellen Realisierung von linearen Listen

Answer 2

schneller Zugriff

Question 3

Nenne Nachteile der Sequenziellen Realisierung von linearen Listen

Answer 3

langsames Einfügen

Question 4

Wie implementiert man eine Queue sequenziell?

Answer 4

Question 5

Nenne Vorteile der verketteten Realisierung von linearen Listen

Answer 5

schnelles Einfügen

Question 6

Nenne Nachteile der verketteten Realisierung von linearen Listen

Answer 6

langsamer Zugriff, höherer
Speicherbedarf

Question 7

Lineare Listen: Sequenzielle Speicherung

Komplexität Zugriff

Answer 7

O(1)

direkt über Index p: L.element[p]

Question 8

Lineare Listen: Sequenzielle Speicherung

Komplexität Suchen

Answer 8

O(N)

durchlaufe die Liste bis x gefunden wurde

Question 9

Lineare Listen: Sequenzielle Speicherung

Komplexität Einfügen

Answer 9

O(N)

verschiebe Elemente p+1,…,n um eine Position nach hinten

Question 10

Lineare Listen: Sequenzielle Speicherung

Komplexität Entfernen

Answer 10

O(N)

verschiebe Elemente p+1,…,n um eine Position nach vorne

Question 11

Lineare Listen: Sequenzielle Speicherung

Komplexität Verketten

Answer 11

O(N)

füge die Elemente von Liste 2 hinter Liste 1 ein

Question 12

Lineare Listen: (Doppelt-)verkettete Speicherung

Komplexität Zugriff

Answer 12

O(N) [O(1)]
durchlaufe die Liste bis Position p

[ ] : falls pos-Zeiger bereits an Position p

Question 13

Lineare Listen: (Doppelt-)verkettete Speicherung

Komplexität Suchen

Answer 13

O(N)

durchlaufe die Liste bis x gefunden wurde

Question 14

Lineare Listen: (Doppelt-)verkettete Speicherung

Komplexität Einfügen

Answer 14

O(N) [O(1)]
erzeuge neues Element, ‚verbiege‘ Zeiger

[ ] : falls pos-Zeiger bereits an Position p

Question 15

Lineare Listen: (Doppelt-)verkettete Speicherung

Komplexität Entfernen

Answer 15

O(N) [O(1)]
verbiege‘ Zeiger, lösche das Element

[ ] : falls pos-Zeiger bereits an Position p

Question 16

Lineare Listen: (Doppelt-)verkettete Speicherung

Komplexität Verketten

Answer 16

O(1)
next-Zeiger des letzten Elements der Liste 1 zeigt
auf erstes Element der Liste 2

Question 17

Doppelt-verkettete Listen

Wie löst man das Problem, dass ein spezieller Code für das Einfügen und Löschen am Listenanfang / -ende
notwendig ist?

Answer 17

Man nutzt einen Wächter vor dem Listenkopf

Question 18

Nenn Elementare Datentypen

Answer 18

• Integer
• Real
• Boolean
• Char

Question 19

Nenn strukturierte Datentypen

Answer 19

• Array
• Record/Struct
• Enum
• Union

Question 20

Welche wichtigen Methoden definiert ein Stack?

Answer 20

• head
• push
• pop

Question 21

Auf welche Weisen kann man einen Stapel implementieren?

Answer 21

Sequenziell oder verkettet

Question 22

Wie kann man wohlgeormte Klammerausdrücke mit einem Algorithmus, welcher einen Stapel benutzt erkennen?

Answer 22

• für jede offene Klammer packt man den Index auf den Stapel und für jede schließende löscht man das oberste Element
• Ist der Stapel am Ende leer, ist der Ausdruck wohlgeformt

Question 23

Welche wichtigen Methoden definiert eine Queue?

Answer 23

• head
• enqueue
• dequeue

Question 24

Wie lautet die Nomenklatur für eine lineare Liste?

Answer 24

L = 〈a1, a2, a3, …, an〉
leere Liste: 〈〉

Question 25

Nenn Grundoperationen einer linearen Liste

Answer 25

Question 26

Nenn weiterführende Operationen einer linearen Liste

Answer 26

Question 27

Wie wird eine Lineare Liste verkettet implementiert?

Answer 27

Question 28

Wie wird eine Lineare Liste doppelt verkettet implementiert?

Answer 28

Question 29

Was ist die Höhe eines Baumes?

Answer 29

Anzahl an Ebenen unter der Wurzel (max. Höhe eines Teilbaums)

Question 30

Was ist die Tiefe eines Knotens?

Answer 30

Anzahl der Kanten von k bis zur Wurzel

Question 31

Was ist das Niveau/die Ebene eines Baumes?

Answer 31

Question 32

Wie viele Knoten hat ein vollständiger Binärbaum auf Ebene i?

Answer 32

2^i

Question 33

Wie viele Blätter hat ein vollständiger Binärbaum?

Answer 33

2^h

Question 34

Wie viele Knoten hat ein vollständiger Binärbaum?

Answer 34

Question 35

Laufzeit zur Speicherung von |K| Knoten in einem Binärbaum der Höhe

Answer 35

Question 36

Wie stellt man einen binären Baum dar?

Answer 36

Question 37

Wie stellt man einen Baum mit unbeschränktem Grad dar?

Answer 37