Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Imperative Programmierung > Dynamische Datenstrukturen in Pascal > Flashcards

Dynamische Datenstrukturen in Pascal Flashcards

1
Q

Unterschied zwischen statischen und dynamischen Datenstrukturen

A

Speicheplatzbedarf steht bei statischen Datenstrukturen schon bei der Übersetzung fest.
Bei dynamischen Datenstrukturen wird Speicherplatz erst während der Laufzeit (Standardprozedur new()) angelegt bzw. (Standardprozedur deipose()) wieder freigegeben.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Standad-Verbundobjekt als Listenelement

A

record
info : type;
next : tRefListe;
end;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Nachteile Linearer Listen gegenüber Feldern

A
  • Liste kann nur entlang der Verzeigerung durchlaufen werden
  • Suchen und “Anwählen” eines Objektes sowie damit jede darauf zurückgrufende Funktion (Löschen eines bestimmten Elements etc.)
    => einfach aber zeitaufwändig
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Unterschied zwischen Zeigervariable und Variable

A
  • Zeigervariable enthält Verweis (Speicheradresse) des zugehörigen Objekts
  • Variable enthält Wert des Objekts direkt
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Dereferenzierung

A

Zugriff auf ein Objekt über Zeigervariable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wie wird ein Zeigertyp definiert?

A

tRefTyp = ^tTyp;
tTyp ist beliebiger Datentyp; Wertemenge für tReftyp sind alle Verweise auf Objekte vom Typ tTyp.

Beispiel:
tRefListe = ^tListe;
tListe = record
                 info : integer;
                 next : tRefListe;
             end;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Wie wird ein Objekt durch eine Zeigervariable angesprochen?

A

var
Zeig : tRefTyp;
[…]
Zeig^;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Wie wird eine Info-Komponente eines Objekts durch eine Zeigervariable ausgelesen?

A

var
Zeig : tRefTyp;
[…]
Zeig^.info;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was macht dieser Befehl?

Zeig1 := Zeig2

A

Zeig1 verweist anschließend auf das gleiche Objekt wie Zeig2.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was macht dieser Befehl?

Zeig1^ := Zeig2^

A

Das Objekt, auf das Zeig1 verweist, hat anschließend den gleichen Wert wie jenes, auf das Zeig2 verweist. Die Zeiger zeigen immernoch auf zwei verschiedene Objekte.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was macht die Standardprozedur new ?

A

new(Zeig) legt ein neues Objekt vom Wertetyp von Zeig an und weist Zeig die Referenz auf dieses Objegt zu. Der Wert von Zeig^ ist bis zur initialisierung undefiniert.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wie wird ein “Zeigerobjekt” initialisiert?

A

Normale Zuweisung:

Zeig^ := WERT;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was macht die Standardprozedur dispose ?

A

dispose(Zeig) löscht das Detenobjekt, auf das Zeig verweist. Zeig^ ist anschließend undefiniert, ebenso wie alle anderen Zeigervariablen, die auf Zeig^ verwiesen haben.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Wann ist Zeig1 = Zeig2 true?

A

Wenn Zeig1 und Zeig2 auf das gleiche Datenobjekt verweisen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Wann ist Zeig1^ = Zeig2^ true?

A

Wenn die Datenobjekte, auf die die Zeigervariablen verweisen, den gleichen Wert haben, unabhängig davon, ob sie auf das gleiche oder zwei verschiedene Objekte zeigen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Was ist der Vorteil einer Linearen Liste gegenüber einem Feld?

A

Da der Speicherplatz dynamisch zugewiesen wird, wird kein solcher verschwendet.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Welche Schritte sind zur Initialisierung einer Liste zu ergreifen?

A
  • Definition Zeigertyp (type)
  • Definition Listenelementtyp (gleich unter Zeigertyp)
  • Deklaration Anker (var)
  • Initialisierung im Programmrumpf (:= nil)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Wie funktionieren Lineare Listen?

A
  • Anfangszeiger zeigt auf erstes Objekt
  • Objekt besteht aus Wert-Komponente und
  • Verweis auf zweites Objekt
  • usw.
  • letztes Objekt verweist auf nil
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Code: Listenelement am Listenanfang einfügen

A

Zeiger^.next := RefAnfang;

RefAnfang := Zeiger;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Code: Referenz auf Wert in Liste suchen

A 
if Zeiger <> nil then
{ Liste nicht leer }
begin
    while (Zeiger^.next <> nil) and (Zeiger^.info <> Wert) do
        Zeiger := Zeiger^.next;
    if Zeiger^.info <> Wert then
    { Listenende }
        Zeiger := nil;
Ausgabe := Zeiger;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Typisches Vorgehen bei der Bearbeitung von Linearen Listen

A
  • Sonderfälle abdecken:
    • leere Liste
    • Operation am Listenanfang
  • Normalfall
  • evtl. Sonderfall: Operation am Listenende
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Algorithmus: sortiert in Liste einfügen

A 
if RefAnfang = nil
{ Liste leer }
Listenelement am Anfang einfügen
else if RefAnfang^.info > Neuer Wert
{ Operation am Listenanfang }
Listenelement am Anfang einfügen
else
{ Position suchen }
gefunden := false;
Hilfszeiger := RefAnfang;
Referenz auf Wert in Liste suchen; modifiziert durch Vergleich; gefunden true setzen
if gefunden then
Listenelement in der Mitte einfügen
else
Listenelement am Ende anhängen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Code: Listenelement in der Mitte einfügen

A
  • Hilfszeiger zeigt auf Element vor dem neuen Element

NeuerZeiger^.next := Hilfszeiger^.next;
Hilfszeiger^.next := NeuerZeiger;

24
Q

Code: Listenelement am Listenende anhängen

A
  • Hilfszeiger zeigt auf letztes Element

Hilfszeiger^.next := NeuerZeiger;
NeuerZeiger^.next := nil;

25
Q

Code: Listenelement löschen

A

Hilfszeiger := ZuEntfernenZeiger;
ZuEntfernenZeiger := ZuEntfernenZeiger^.next;
dispose(Hilfszeiger);

26
Q

Algorithmus: Element mit gesuchtem Wert löschen

A

if RefAnfang = nil then
{ Liste leer }
nicht gefunden
else

Element mit Wert suchen

  • Hilfszeiger auf Anfangszeiger;
  • while (Hilfszeiger^.next <> nil) do
  • entlanghangeln bis Wert im Feld hinter Hilfszeiger gefunden
    (if Hilfszeiger^.next^.info = Wert then)
  • Listenelement hinter Hilfszeiger löschen
    (Hilfszeiger^.next wird nil; Ende while-Schleife)
  • else
    Zeiger := Zeiger^.next;
27
Q

Liste oder Baum als Parameter an Funktion übergeben

A

übergeben wird der Anfangszeiger bzw. Zeiger auf die Wurzel

28
Q

Transposition Rule

A

Durch Vertauschen eines gesuchten gefundenen Elementes mit seinem Vorgänger rutschen häufig gesuchte Elemente immer weiter nach vorne. Dadurch sinkt der durchschnittliche Zeitaufwand für Suchen.

29
Q

Wurzel

A

Startknoten eines Baumes

30
Q

Sohn / Kind

A

Nachfolger eines Baumknotens

31
Q

Vater

A

Vorgänger eines Baumknotens

32
Q

innerer Knoten

A

Knoten mit Vorgänger und Nachfolger

33
Q

Blatt

A

Knoten ohne Nachfolger

34
Q

Teilbaum

A

Jeder Knoten eines Baumes öffnet einen Teilbaum mit aus ihm entspringenden Knoten.

35
Q

Eigenschaften eines Baumes mit nichtleerer Knotenmenge

A
  • Hat genau einen Knoten ohne Vorgänger (Wurzel)

- Von der Wurzel aus ist jeder andere Knoten durch genau eine Folge von Kantewn erreichbar.

36
Q

binärer Baum

A

Jeder Knoten hat maximal zwei Nachfolger (links, rechts).

37
Q

Wie wird der Typ binär Baum implementiert?

A

type
tRefBinBaum = ^tBinBaum;
tBinBaum = record
info : type;
links : tRefBinBaum;
rechts : tRefBinBaum;
end;

38
Q

binärer Suchbaum

A
  • die Werte im linken Teilbaum eines Knotens sind alle kleiner als der Wert des Wurzelknotens
  • die Werte im rechten Teilbaum eines Knotens sind alle größer als der Wert des Wurzelknotens
  • kein Wert kommt doppelt vor (genau so viele Knoten wie Werte)
39
Q

Suchpfad

A

Folge der Knoten, die zu einem gesuchten Wert führen

40
Q

Tiefe

A
  • Ebene des gesuchten Knotens

- Menge der Knoten auf Suchpfad

41
Q

Höhe

A

Länge des längsten auftretenden Suchpfades in einem Suchbaum

42
Q

Berechnung minimaler Höhe eines Suchbaumes

A

|’ log(tief2) (n+1) ‘|

n = Anzahl der enthaltenen Werte

43
Q

natürlicher Suchbaum

A

Suchbaum, der durch iteriertes Einfügen einer Zahlenfolge in einen anfangs leeren Baum entsteht.
Jede mögliche Eingabefolge für eine Wertemenge ergibt einen natürlichen Suchbaum.

44
Q

degenerierte Suchbaum

A

zu Liste degenerierter Suchbaum der Höhe n bei n = Anzahl der enthaltenen Werte

45
Q

vollständiger Suchbaum

A

Suchbaum mit minimaler Höhe, bei dem die Tiefe der Blätter um maximal eins abweicht

46
Q

Rekursion

A

Rückgriff einer Funktion etc. auf sich selbst

47
Q

Welche Voraussetzungen müssen beim Einsatz einer Rekursion unbedingt erfüllt werden?

A
  • Problemverkleinerung

- Abbruchbedingung

48
Q

rekursive Datenstrukturen

A

andere Bezeichnung für Listen und Bäumen, da diese sich hervorragend rekursiv bearbeiten lassen.

49
Q

Laufzeitstack

A

Stapel, die der Compiler bei Bedarf während der Laufzeit (bspw. bei Rekursionen) zur Verfügung stellt.

50
Q

Rekursionstiefe

A

Menge der gleichzeitig nicht abgeschlossenen Rekursionen

51
Q

Wann ist ein rekursiver Ansatz einem iterativen Ansatz vorzuziehen?

A
  • IMMER, wenn die iterative Variante auf einen Stapel zurückgreifen müsste (Laufzeitstapel günstiger)
  • u.U. auch dann, wenn er die Programmkomplexität stark verringert
52
Q

LIFO

A

Last In First Out:

iteratives Einlesen und anschließendes Auslesen einer Liste am Listenanfang

53
Q

Code: rekursive Suche in Liste

A

function ListenElementSuchen (inRefAnfang : tRefListe; inWert : tType)

var
Zeiger : tRefListe;

begin
    Zeiger := inRefAnfang;
    if inRefAnfang <> nil then
        if inRefAnfang^.info <> inWert
            ListenElementSuchen (inRefAnfang^.next, inWert);
    ListenElementSuchen := Zeiger;
end;
54
Q

preorder (Erklärung)

A

Hauptreihenfolge

Folge der Knoten nach Zweig und Stufe in einem Baum

55
Q

Durchlaufen preorder (rekursiver Algorithmus)

A
  1. Ist der Baum leer, dann STOP, sonst:
  2. Betrachte Wurzel
  3. Durchlaufe linken Teilbaum der Wurzel preorder
  4. Durchlaufe rechten Teilbaum der Wurzel preorder
56
Q

inorder (Erklärung)

A

symmetrische Reihenfolge

Folge der Knoten von links nach rechts. Ergibt für einen Suchbaum die Werte in sortierter Reihenfolge.

57
Q

Durchlaufen inorder (Algorithmus)

A
  1. Ist der Baum leer, dann STOP, sonst:
  2. Durchlaufe linken Teilbaum der Wurzel inorder
  3. Betrachte Wurzel
  4. Durchlaufe rechten Teilbaum der Wurzel inorder

Imperative Programmierung (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions