Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
Code: Listenelement löschen
Hilfszeiger := ZuEntfernenZeiger; ZuEntfernenZeiger := ZuEntfernenZeiger^.next; dispose(Hilfszeiger);
26
Algorithmus: Element mit gesuchtem Wert löschen
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
Liste oder Baum als Parameter an Funktion übergeben
übergeben wird der Anfangszeiger bzw. Zeiger auf die Wurzel
28
Transposition Rule
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
Wurzel
Startknoten eines Baumes
30
Sohn / Kind
Nachfolger eines Baumknotens
31
Vater
Vorgänger eines Baumknotens
32
innerer Knoten
Knoten mit Vorgänger und Nachfolger
33
Blatt
Knoten ohne Nachfolger
34
Teilbaum
Jeder Knoten eines Baumes öffnet einen Teilbaum mit aus ihm entspringenden Knoten.
35
Eigenschaften eines Baumes mit nichtleerer Knotenmenge
- Hat genau einen Knoten ohne Vorgänger (Wurzel) | - Von der Wurzel aus ist jeder andere Knoten durch genau eine Folge von Kantewn erreichbar.
36
binärer Baum
Jeder Knoten hat maximal zwei Nachfolger (links, rechts).
37
Wie wird der Typ binär Baum implementiert?
type tRefBinBaum = ^tBinBaum; tBinBaum = record info : type; links : tRefBinBaum; rechts : tRefBinBaum; end;
38
binärer Suchbaum
- 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
Suchpfad
Folge der Knoten, die zu einem gesuchten Wert führen
40
Tiefe
- Ebene des gesuchten Knotens | - Menge der Knoten auf Suchpfad
41
Höhe
Länge des längsten auftretenden Suchpfades in einem Suchbaum
42
Berechnung minimaler Höhe eines Suchbaumes
|' log(tief2) (n+1) '| | n = Anzahl der enthaltenen Werte
43
natürlicher Suchbaum
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
degenerierte Suchbaum
zu Liste degenerierter Suchbaum der Höhe n bei n = Anzahl der enthaltenen Werte
45
vollständiger Suchbaum
Suchbaum mit minimaler Höhe, bei dem die Tiefe der Blätter um maximal eins abweicht
46
Rekursion
Rückgriff einer Funktion etc. auf sich selbst
47
Welche Voraussetzungen müssen beim Einsatz einer Rekursion unbedingt erfüllt werden?
- Problemverkleinerung | - Abbruchbedingung
48
rekursive Datenstrukturen
andere Bezeichnung für Listen und Bäumen, da diese sich hervorragend rekursiv bearbeiten lassen.
49
Laufzeitstack
Stapel, die der Compiler bei Bedarf während der Laufzeit (bspw. bei Rekursionen) zur Verfügung stellt.
50
Rekursionstiefe
Menge der gleichzeitig nicht abgeschlossenen Rekursionen
51
Wann ist ein rekursiver Ansatz einem iterativen Ansatz vorzuziehen?
- 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
LIFO
Last In First Out: | iteratives Einlesen und anschließendes Auslesen einer Liste am Listenanfang
53
Code: rekursive Suche in Liste
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
preorder (Erklärung)
Hauptreihenfolge | Folge der Knoten nach Zweig und Stufe in einem Baum
55
Durchlaufen preorder (rekursiver Algorithmus)
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
inorder (Erklärung)
symmetrische Reihenfolge | Folge der Knoten von links nach rechts. Ergibt für einen Suchbaum die Werte in sortierter Reihenfolge.
57
Durchlaufen inorder (Algorithmus)
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.
© 2025 Bold Learning Solutions. Terms and Conditions