Arrays / Listen

Question 1

Tafelübung
Arrays

Problemen bei der Verwendung von
Standardarrays

Answer 1

Array zu klein:
Es kann ein Programmfehler auftreten

Array zu groß:
Verschwendung von Speicherplatz

Array vergrößern:
Hat i. d. R. Umkopieren des Speicherinhaltes zur Folge

Feste Itemreihenfolge:
Einfügen und Löschen ist mit viel Aufwand verbunden

Question 2

Tafelübung
Listen

Sonderfälle!

Answer 2

Mögliche Fälle (je nach Operation):

leere Liste

Einfügen/Löschen/. . .am Anfang der Liste

Einfügen/Löschen/. . . in der Mitte der Liste

Einfügen/Löschen/. . .am Ende der Liste

Question 3

Tafelübung
Listen

Vorteile

Answer 3

) Verkettete Listen . . .
. . . enthalten nicht mehr Elemente als nötig
. . . können beliebig wachsen
. . . können an beliebiger Stelle Elemente einfügen und löschen

Question 4

Tafelübung

Schleife über verkettete Liste

Answer 4

for (ListItem i = head; i != null; i = i.next) {
…
}

Question 5

Tafelübung

Einfügen ans Ende der Liste

Answer 5

for (ListItem i = head; i != null; i = i.next) {
    if (i.next == null) {
        i.next = newItem;
        return;    
    }
}

Wichtig IMMER mit return beenden sonst wächst Liste ja immer weiter.

Question 6

Tafelübung

Einfügen ans Ende der Liste mit TAIL

Answer 6

ListItem newItem = new ListItem();
newItem.value = 4;
tail.next = newItem;
tail = newItem;

keine Schleife mehr

Question 7

Tafelübung

Liste leer?

Answer 7

head == null, tail == null

Muss abgefangen werden

Question 8

Tafelübung

Entfernen aus Liste

Answer 8

Zusätzlicher Zeiger auf vorherigen:

ListItem prev = null;
noch abfangen, falls Liste leer ist...
for (ListItem i = head; i != null; i = i.next) {
    if...value stimmt...
    prev.next = i.next;
    prev = i;
}

Question 9

KLAUSURAUFGABE SS17

Welche Aussagen bzgl. verketteter Listen sind gültig?

1. Der Zugriff auf ein einzelnes Listenelement benötigt unabhängig von der Position des
   Listenelements immer O(n); n sei die Anzahl der Elemente in der Liste.
2. Das Löschen eines Listenelements hat dieselbe Komplexitätsklasse wie das Auffinden
   eines Elements.
3. Die Implementierung eines Stapels (Stack) ist ohne verkettete Listen nicht möglich.

Answer 9

Nur 2.

2. Das Löschen eines Listenelements hat dieselbe Komplexitätsklasse wie das Auffinden
   eines Elements.

Question 10

KLAUSURAUFGABE WS17

Welche Aussagen treffen auf unsortierte Listen zu?

In einer unsortierten Liste sind alle Elemente entweder aufsteigend oder
absteigend angeordnet.

Bei der Einbettung in ein Array ist der letzte gespeicherte Wert im Array
der kleinste in der unsortierten Liste gespeicherte Wert.

Die Laufzeitkomplexität bei der Entnahme des Extremwerts beträgt im
schlechtesten Fall (worst case) O(log n).

Answer 10

Alle FALSCH

Question 11

KLAUSURAUFGABE WS16

Welche Aussagen bzgl. verketteter Listen sind gültig?

Der Zugriff auf ein einzelnes Listenelement benötigt unabhängig von der Position des
Listenelements immer O􀀀n; n sei die Anzahl der Elemente in der Liste.

Das Löschen eines Listenelements hat dieselbe Komplexitätsklasse wie das Auffinden
eines Elements.

Die Implementierung eines Stapels (Stack) ist ohne verkettete Listen nicht möglich.

Answer 11

Nur 2.

Das Löschen eines Listenelements hat dieselbe Komplexitätsklasse wie das Auffinden
eines Elements.

Question 12

KLAUSURAUFGABE SS15

In einer unsortierten Liste sind alle Elemente entweder aufsteigend oder
absteigend angeordnet.

Bei der Einbettung in ein Array ist der letzte gespeicherte Wert im Array
der kleinste in der unsortierten Liste gespeicherte Wert.

Die Laufzeitkomplexität bei der Entnahme des Extremwerts beträgt im
schlechtesten Fall (worst case) O(log n).

Answer 12

Alle FALSCH

Question 13

Vorlesung

Listen VS Arrays

Speicherbedarf

Answer 13

Listen (einfach):
dynamische Anpassung an die Anzahl der enthaltenen Elemente

immer nur so viel, wie nötig
Overhead: Speicherbedarf für Zeiger

Arrays:
konstanter Speicherbedarf

Speicherplatzverschwendung bei überdimensioniertem Feld

Question 14

Vorlesung

Listen VS Arrays

Elemente suchen

Answer 14

Listen (einfach):

lineare Suche O(n)

Arrays:

binäre Suche (falls aufsteigend sortiert) O(logn)

Question 15

Vorlesung

Listen VS Arrays

Zugriff auf Element

Answer 15

Liste (einfach):

Liste vom Anfang bis zur gesuchten
Position durchlaufen

Arrays:

direkter Zugriff