vl 13 - Stack/Queue, Sortieren

Question 1

Beschreibe den Stack, das Prinzip

+ einfügen und entfernen Befehl

Answer 1

Last In - First Out

immer das was oben auf dem Stapel lieg nehmen

+ push

• pop

Question 2

Beschreibe die Queue, das Prinzip

und die Befehle

einfügen, entfernen

Answer 2

First In - First Out

immer ans Ende anfügen

+ enqueue( E element);

• dequeue();

Question 3

Komplexität eines Sortierverfahrens erklären.

die beiden “Formeln” zur Berechnung der oberen Schranke

Answer 3

Anzahl der Schritte die zum Sortieren benötigt werden

O(n log n)

O(n^2)

Question 4

3 vergleichsbasierte Sortierverfahren nennen

Answer 4

vertauschen (Bubble Sort),

Einfügen (Shell sort) sortierte Teilfolge

Auswahl (Heap Sort) kleinstes suchen, etc

Question 5

Erkläre das Prinzip von Quick Sort

Wann gut einzusätzen?

Answer 5

Aufteilen in Teilmengen (Teile und Herrsche)

jeweil immer Untergruppen der Elemente bilden bis Größe = 1

+ sehr schnell und auch gut bei großen Mengen

Question 6

Was ist das Prinzip beim Bubble Sort?

Wann ist es gut geeignet?

Answer 6

vertasucht Elemente der Reihe nach mit dem Test größer kleiner

sehr hoher Rechenaufwand, leicht zu Implementieren, nur für kleine Sammlungen