Datenstrukturen at Hochschule Ostwestfalen-Lippe | Flashcards & Summaries

Select your language

Suggested languages for you:
Log In Start studying!

Lernmaterialien für Datenstrukturen an der Hochschule Ostwestfalen-Lippe

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Datenstrukturen Kurs an der Hochschule Ostwestfalen-Lippe zu.

TESTE DEIN WISSEN

Liste

Lösung anzeigen
TESTE DEIN WISSEN

- verkettete (lineare) Liste

- einfach/doppelt verkettete Liste

• Spezielle Kennzeichnung erforderlich für

• Listenanfang (Anker)

• Listenende

• leere Liste 

Lösung ausblenden
TESTE DEIN WISSEN

Skip Listen


Lösung anzeigen
TESTE DEIN WISSEN

• Ziel: Datenstruktur mit logarithmischem Aufwand für Suche, Einfügen und Löschen von Schlüsseln

• Prinzip: Verwendung sortierter verkettet gespeicherter Liste mit zusätzlichen Zeigern

• Elemente werden in Sortierordnung ihrer Schlüssel verkettet

• Führen mehrerer Verkettungen auf 2 oder mehreren Ebenen: Verkettung auf Ebene 0 verbindet alle Elemente; z. B. Verkettung auf Ebene 1 verbindet jedes zweite Element 

Lösung ausblenden
TESTE DEIN WISSEN

Datenstruktur: Binärbaum

Lösung anzeigen
TESTE DEIN WISSEN

• Elemente = Knoten

• Knoten besitzt 0 – 2 Nachfolger

• Oberster Knoten = Wurzel

• Besitzt ein Knoten keinen Nachfolger = Blatt

• Darstellung beginnt immer mit der Wurzel

• Verbindungen zwischen Knoten = Kanten

Kind / Eltern – Elemente

• Baumhöhe: Max(Kanten) bis zum untersten Blatt

• Tiefe: Anzahl Kanten bis zum gesuchten Knoten

Geordnet:

• Linke Kind-Elemente ≤ Eltern-Element

• Rechte Kind-Elemente ≥ Eltern-Element 

Lösung ausblenden
TESTE DEIN WISSEN

Priority-Queue Beispiele

Lösung anzeigen
TESTE DEIN WISSEN

1. Terminkalender

- Zugriff auf nächster Termin

- Einfügen neuer Termine

2. To-Do-Liste

- Priorisierung von Einträgen (Reihenfolge)

Lösung ausblenden
TESTE DEIN WISSEN

Vollständiger Binärbaum

Lösung anzeigen
TESTE DEIN WISSEN

Alle Blätter haben die gleiche Tiefe

Lösung ausblenden
TESTE DEIN WISSEN

Primitive Datentypen

Lösung anzeigen
TESTE DEIN WISSEN

• int, double, char, boolean 

- lassen sich in Strukturen zusammenfassen

Lösung ausblenden
TESTE DEIN WISSEN

Abstrakte Datentypen (ADTs)

Lösung anzeigen
TESTE DEIN WISSEN

• Gekapselt Daten (verbirgt tatsächliche Repräsentation)

• Zugriff erfolgt nicht direkt auf der Variable, sondern über Funktionen (  Schnittstellen )

• Instanziierung eines ADTs

• Konkrete Ausprägung eines ADT mit konkreten Daten

• OOP: ADT = Klasse, Instanziierung = Objekt der Klasse

• Beispiel:

• Stack

• Queue

• Liste 

Lösung ausblenden
TESTE DEIN WISSEN

Voller Binärbaum

Lösung anzeigen
TESTE DEIN WISSEN

- wenn jeder Knoten zwei Blätter besitzt

Lösung ausblenden
TESTE DEIN WISSEN

Stapel – Stack - Keller 


Lösung anzeigen
TESTE DEIN WISSEN

• LIFO-Prinzip (last in – first out)

• Zugriff nur auf den Anfang des Stapels

• Operationen:

• CREATE: Erzeuge leeren Stack

• PUSH(S, x): Fügt das Element x als oberstes Element von S ein

• POP(S): Löschen des Elementes, das als letztes in den Stack S eingefügt wurde

• TOP(S): Abfragen des Elementes, das als letztes in den Stack S eingefügt wurde

• EMPTY(S): Abfragen, ob der Stack S leer ist 

Lösung ausblenden
TESTE DEIN WISSEN

Stack - Implementierung

Lösung anzeigen
TESTE DEIN WISSEN

• Als Array oder Liste

• Max. Elementanzahl: n

• Einträge: A[1…n]

• Stackpointer top[A] verweist auf das zuletzt eingefügte Element

• Ist top[A] = 0, so ist der Stack leer

• A[top[A]] ist das oberste Element

• Achtung: Beim Array ist die Elementanzahl begrenzt; Bei einer Liste nicht. 

Lösung ausblenden
TESTE DEIN WISSEN

Queue 

Lösung anzeigen
TESTE DEIN WISSEN

• FIFO (First-In-First-Out)

• Spezielle Form der Liste

• Zugriff auf 1. Element 

Operationen:

• CREATE: Erzeugt die leere Schlange

• ENQUEUE (Q, x): Fügt das Element x am Ende der Schlange Q ein

• DEQUEUE (Q): Löschen des Elementes, das am längsten in der Schlange verweilt (erstes Element)

• FRONT (Q): Abfragen des ersten Elementes in der Schlange

• EMPTY (Q): Abfragen, ob die Schlange leer ist 

Lösung ausblenden
TESTE DEIN WISSEN

Perfekte Skip Liste

Lösung anzeigen
TESTE DEIN WISSEN

ABER: perfekte Skip-Listen zu aufwendig bezüglich Einfügungen und

• Löschvorgängen (vollständige Reorganisation erforderlich, Kosten O(n)) 

Lösung ausblenden
  • 16984 Karteikarten
  • 416 Studierende
  • 22 Lernmaterialien

Beispielhafte Karteikarten für deinen Datenstrukturen Kurs an der Hochschule Ostwestfalen-Lippe - von Kommilitonen auf StudySmarter erstellt!

Q:

Liste

A:

- verkettete (lineare) Liste

- einfach/doppelt verkettete Liste

• Spezielle Kennzeichnung erforderlich für

• Listenanfang (Anker)

• Listenende

• leere Liste 

Q:

Skip Listen


A:

• Ziel: Datenstruktur mit logarithmischem Aufwand für Suche, Einfügen und Löschen von Schlüsseln

• Prinzip: Verwendung sortierter verkettet gespeicherter Liste mit zusätzlichen Zeigern

• Elemente werden in Sortierordnung ihrer Schlüssel verkettet

• Führen mehrerer Verkettungen auf 2 oder mehreren Ebenen: Verkettung auf Ebene 0 verbindet alle Elemente; z. B. Verkettung auf Ebene 1 verbindet jedes zweite Element 

Q:

Datenstruktur: Binärbaum

A:

• Elemente = Knoten

• Knoten besitzt 0 – 2 Nachfolger

• Oberster Knoten = Wurzel

• Besitzt ein Knoten keinen Nachfolger = Blatt

• Darstellung beginnt immer mit der Wurzel

• Verbindungen zwischen Knoten = Kanten

Kind / Eltern – Elemente

• Baumhöhe: Max(Kanten) bis zum untersten Blatt

• Tiefe: Anzahl Kanten bis zum gesuchten Knoten

Geordnet:

• Linke Kind-Elemente ≤ Eltern-Element

• Rechte Kind-Elemente ≥ Eltern-Element 

Q:

Priority-Queue Beispiele

A:

1. Terminkalender

- Zugriff auf nächster Termin

- Einfügen neuer Termine

2. To-Do-Liste

- Priorisierung von Einträgen (Reihenfolge)

Q:

Vollständiger Binärbaum

A:

Alle Blätter haben die gleiche Tiefe

Mehr Karteikarten anzeigen
Q:

Primitive Datentypen

A:

• int, double, char, boolean 

- lassen sich in Strukturen zusammenfassen

Q:

Abstrakte Datentypen (ADTs)

A:

• Gekapselt Daten (verbirgt tatsächliche Repräsentation)

• Zugriff erfolgt nicht direkt auf der Variable, sondern über Funktionen (  Schnittstellen )

• Instanziierung eines ADTs

• Konkrete Ausprägung eines ADT mit konkreten Daten

• OOP: ADT = Klasse, Instanziierung = Objekt der Klasse

• Beispiel:

• Stack

• Queue

• Liste 

Q:

Voller Binärbaum

A:

- wenn jeder Knoten zwei Blätter besitzt

Q:

Stapel – Stack - Keller 


A:

• LIFO-Prinzip (last in – first out)

• Zugriff nur auf den Anfang des Stapels

• Operationen:

• CREATE: Erzeuge leeren Stack

• PUSH(S, x): Fügt das Element x als oberstes Element von S ein

• POP(S): Löschen des Elementes, das als letztes in den Stack S eingefügt wurde

• TOP(S): Abfragen des Elementes, das als letztes in den Stack S eingefügt wurde

• EMPTY(S): Abfragen, ob der Stack S leer ist 

Q:

Stack - Implementierung

A:

• Als Array oder Liste

• Max. Elementanzahl: n

• Einträge: A[1…n]

• Stackpointer top[A] verweist auf das zuletzt eingefügte Element

• Ist top[A] = 0, so ist der Stack leer

• A[top[A]] ist das oberste Element

• Achtung: Beim Array ist die Elementanzahl begrenzt; Bei einer Liste nicht. 

Q:

Queue 

A:

• FIFO (First-In-First-Out)

• Spezielle Form der Liste

• Zugriff auf 1. Element 

Operationen:

• CREATE: Erzeugt die leere Schlange

• ENQUEUE (Q, x): Fügt das Element x am Ende der Schlange Q ein

• DEQUEUE (Q): Löschen des Elementes, das am längsten in der Schlange verweilt (erstes Element)

• FRONT (Q): Abfragen des ersten Elementes in der Schlange

• EMPTY (Q): Abfragen, ob die Schlange leer ist 

Q:

Perfekte Skip Liste

A:

ABER: perfekte Skip-Listen zu aufwendig bezüglich Einfügungen und

• Löschvorgängen (vollständige Reorganisation erforderlich, Kosten O(n)) 

Datenstrukturen

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Datenstrukturen an der Hochschule Ostwestfalen-Lippe

Für deinen Studiengang Datenstrukturen an der Hochschule Ostwestfalen-Lippe gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Mehr Karteikarten anzeigen

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Datenstrukturen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Datenstrukturen