Kapitel 2: Elementare Datenstrukturen Flashcards Preview

Algorithmen und Datenstrukturen SS2018 > Kapitel 2: Elementare Datenstrukturen > Flashcards

Flashcards in Kapitel 2: Elementare Datenstrukturen Deck (21):
1

Definition (Dynamische Datenmengen)

Datenmengen, die in Algorithmen verwendet werden, können anwachsen, sich verringern oder über die Laufzeit auch verändern. Dies wird als dynamische Daten bezeichnet.

2

Definition (Dynamische Datenstrukturen)

Dynamische Datenmengen für Algorithmen und grundlegende Operationen, um auf die Daten zuzugreifen (Abfrage Methoden) und modifizierende Methoden.

3

Definition (Array)

Ein Feld (Array) a besteht aus einer festen Anzahl von Datenobjekten gleichen Typs, die über einen Index i über einen direkten Zugriff selektiert werden können. Der benötigte Speicherplatz für das Array ist zusammenhängend.

4

Wie werden INSERT Operationen auf dem Stack genannt ?

PUSH

5

Wie werden DELETE Operationen auf dem Stack genannt ?

POP

6

Definition (Queue)

Eine Warteschlange (Queue) ist eine lineare Liste, bei der Listenelemente nur an einem Ende (tail) eingefügt und nur am anderen Ende (head) entnommen werden.

7

Was bedeutet FIFO ?

In einer Queue wird immer dasjenige Element als nächstes gelöscht, das am längsten in der Queue vorhanden ist.
Prinzip: First-In, First-Out (FIFO)

8

Wann ist die Queue voll ?

head == tail

9

Was gibt Start und Ende der Queue vor ?

head und tail

10

Wann ist die Queue leer ?

(head+1) mod n == tail

11

Wann ist der Stack voll ?

top == n-1

12

Wann ist der Stack leer ?

top == -1

13

Was ist die Leseposition beim Ringpuffer ?

head

14

Was ist die Schreibposition beim Ringpuffer ?

tail

15

Welche Queue Indezes gibt es ?

q[head+1] bis q[tail]

16

Definition (Priority Queue)

Eine Prioritätswarteschlange ist eine Datenstruktur von Elementen mit Prioritäten (Schlüsseln), die zwei grundsätzliche Operationen unterstützen:
- Einfügen eines neuen Elementes und
- Entfernen des Elementes mit der größten Priorität (Schlüssel).

17

Definition (Verkettete Liste)

Eine Menge von Datenobjekten, bei der jedes Objekt die
Informationen enthält, um zum nächsten Element zu gelangen.

18

Der wesentliche Unterschied zwischen einer doppelt- und einer einfach verketteten Liste ?

bei der Doppelt verketteten Liste referenziert jeder Knoten nicht nur auf seinen Nachfolgeknoten (next) sondern auch auf den davorigen (prev).

19

Vorteil Verkettete Liste

- Dynamisches Wachsen oder Schrumpfen
- Größe der Liste muss vorab nicht bekannt sein

20

Nachteil Verkettete Liste

- Kein direkter, nur sequentieller Zugriff
- Knoten liegen ohne Physikalische Reihenfolge im Speicher

21

Wie macht man aus einer Klasse eine Template Klasse ?

- vor "class xyz{" wird "template " geschrieben
- Datentypen (z.b. jedes "int") mit "T" tauschen