Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Algorithmen und Datenstrukturen > Sortieren > Flashcards

Sortieren Flashcards

Test

1
Q

Wann spricht man von einer partiellen Ordnung R?

A
  • reflexiv: es gilt a R a
  • antisymmetrisch: a R b und b R a folgt a = b
  • transitiv: a R b und b R c folgt a R c
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Wann spricht man von einer totalen Ordnung R?

A
  • R ist partielle Ordnung
  • für alle a,b gilt: a R b oder b R a
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Wie werden Zugriffsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?

A

c_z

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

Wie werden Vergleichsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?

A

c_v

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

Wie werden Datenaustauschsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?

A

c_d

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

Welche Operationen gibt es beim Sortieren?

A
  • Zugriffsoperation
  • Vergleichsoperationen
  • Datenaustauschoperationen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Beschreibe in-place Verfahren

A

Ein Sortieralgorithmus arbeitet ‘in place’, wenn es außer dem zu sortierenden Datenarray nur konstant viel Speicherplatz benötigt.

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

Wann ist ein Sortierverfahren stabil?

A

Ein Sortieralgorithmus ist ‘stabil’, wenn bei Gleichheit der zu sortierenden Objekte die Eingabereihenfolge erhalten bleibt

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

Durch welche Eigenschaften kann man einen Soriteralgorithmus beschreiben?

A
  • Effizienz
  • Speicherbedarf
  • Stabilität
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Welche Laufzeit hat Sortieren durch Auswahl?

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

Wie funktioniert Sortieren durch Auswahl?

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

Wie viele Datenaustauschoperationen benötigt man für den Selectionsort?

A

max. N-1

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

Ist der Selectionsort stabil und in-place?

A

Ja, stabil und in-place

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

Welche Laufzeit Insertionsort?

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

Ist der Insertionsort in-place und stabil?

A

Ja, in-place und stabil

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

Wie funktioniert Sortieren durch Einfügen?

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

Welche Laufzeit hat der Bubblesort?

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

Ist der Bubblesort stabil und in-place?

A

Ja, stabil und in-place

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

Wie funktioniert der Bubblesort?

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

Wie funktioniert der Mergesort?

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

Beschreib den 2-Wege-Merge

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

Welche Laufzeit hat die Merge Operation?
für die Listen L und R

A

O(|L|+|R|) = O(N)

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

Ist die Merge Operation mit Listen stabil und in-place?

A

Ja, stabil und in-place

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

Ist die Merge Operation mit Arrays stabil und in-place?

A

Nein, stabil aber nicht in-place (linear abhängige Arrays als zwischenspeicher)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Welche Laufzeit hat der Mergesort?
26
Welchen Speicherbedarf hat der Mergesort?
27
Was passiert mit der Laufzeit, wenn man nicht 2 sondern k Listen bei dem Mergesort verwendet?
28
Was ist die Heap-Bedingung?
Objekte liegen auf einer Halde, ein Objekt ist immer mindestens so groß wie die darunter liegenden Objekte
29
Welche Operationen sind auf einem Heap definiert?
* BUILD-MAX-HEAP: baue eine Halde aus einer Menge von Elementen * HEAP-EXTRACT-MAX: nehme das größte Element von der Halde * MAX-HEAPIFY: stelle die Heap- Bedingung nach Entnahme wieder her
30
Auf welche Datenstruktur basiert ein Heap?
Auf einem binären Baum
31
Was bedeutet linksvollständig?
alle Ebenen bis auf die letzte sind vollständig, in der letzten folgen die Elemente von links nach rechts.
32
Wie wird ein Heap durch ein Array repräsentiert?
33
Wie berechnet man den Index des Parent Elements in einem Heap?
34
Welche Höhe hat ein Heap der Größe N maximal?
35
Wie berechnet man den Index des Linken Kind Elements in einem Heap?
36
Wie berechnet man den Index des Rechten Kind Elements in einem Heap?
37
Wie geht man bei Heapify vor?
Nehme Max Child der kaputten Stelle i und vertausche die Elemente Wiederhole an der alten Stelle des Max Child falls immer noch kaputt
38
Welche Laufzeit hat Max-Heapify?
O(log n)
39
Welche Laufzeit hat Build-Max-Heap?
O(n log n)
40
Hat man ein unsortiertes Array und möchte ein Heap erstellen, was gilt für den Heap nach dem einfügen der Daten, welche Knoten sind dann auf jeden Fall schon Heaps? | Wie berechnet man den Index des ersten Knotens, der kein Heap darstellt
Die Blätter
41
Welche Operationen sind auf eine Priority Queue definiert?
42
Mit welcher Sortierstruktur kann eine Priority Queue realisiert werden?
Durch einen Heap
43
Wie und für welche Zahlen funktioniert der Counting Sort?
44
Mit welcher Laufzeit für die Operationen insert, delete, increase, decrease und extract-max kann eine Priority-Queue mit einem Heap realisiert werden?
O(log N)
45
Wie funktioniert Heap-Increase-Key?
46
Wie wird der Counting Sort stabil realisiert?
Am Ende den Array von hinten nach vorne durchlaufen
47
Ist der Counting Sort in-place?
Nein
48
Wie funktioniert Heap-Insert? | Der Priority-Queue
49
Wie funktioniert der Quicksort?
50
Wie funktioniert die Partition Funktion?
51
Wie funktioniert die Partition Funktion mit nur einer Schleife?
52
Was ist die Rekurrenzgleichung für Quicksort?
53
Was ist die Laufzeit vom Quicksort? Pivot-Element liegt in der Mitte
O(N log N) | auch average case
54
Wie hoch ist mein Rekursionsbaum, wenn der größere Teil immer 9/10 der Daten annimmt?
55
Was ist die Laufzeit vom Quicksort? (Worst Case)
## Footnote Pivot ist Maximum
56
Wie funktioniert der Trivial Sort und für welche Daten?
ganzzahlige Zahlen
57
Wie und für welche Zahlen funktioniert der Counting Sort?
58
Laufzeit Trivial Sort?
O(N)
59
Laufzeit Counting Sort?
60
Wie wird der Counting Sort stabil realisiert?
Am Ende den Array von hinten nach vorne durchlaufen
61
Wie wird ein m-adischer Schlüssel repräsentiert?
Durch einen Vektor
62
Beschreibe den Radix Sort
63
Laufzeit vom Radix Sort Fall 1: d= O(1), m = O(N)
O(N)
64
Laufzeit vom Radix Sort Fall 2: Alle Schlüssel verschieden: d ≥ log_m N :
O(N log N)
65
Ist der Radix Sort stabil / in-place?
stabil, aber nicht in-place
66
Ist der Counting Sort stabil / in-place?
stabil, aber nicht in-place
67
Ist der Trivial Sort stabil / in-place?
stabil und in-place
68
Beschreibe den Bucketsort
69
Laufzeit Bucketsort (Worst Case)
O(N^2)
70
Laufzeit Bucketsort (Average Case)
O(N)
71
Welche Laufzeit hat eine binäre Suche?
O(log N)
72
Beschreibe die Exponentielle Suche
73
Laufzeit Exponentielle Suche
O(log k)
74
Laufzeit Exponentielle Suche (Worst Case)
O(log N)
75
Was bedeutet output-sensitiv?
Laufzeit hängt vom Resultat der Suche ab
76
Beschreib den Trivial-Select(A, i) | Laufzeit?
## Footnote o(N^2)
77
Beschreib den Sort-Select(A, i) | Laufzeit?
## Footnote o(n log n)
78
Beschreib den Rand-Select
79
Welche Laufzeit hat der Rand-Select? (Worst Case)
80
Wie hoch ist die erwartete Laufzeit des Rand-Select?
81
Was ist der Vorteil von Sortieren durch Einfügen?
ist vorteilhaft, wenn die Eingabe nahezu sortiert ist
82
Welchen Vorteil hat der Mergesort?
eignet sich gut für große Datenbestände auf Sekundärspeichern
83
Was ist die erwartete Laufzeit des randomisierten Verfahrens des Quicksorts?
O(n log n)
84
Wie kann ein Quicksort in der Praxis weiter beschleunigt werden?
Indem ein rekursiver Aufruf durch eine Iteration ersetzt wird (Endrekursion)
85
Wie viele Vergleichsoperationen benötigt jedes Sortierverfahren im Worst Case?
86
Gibt es einen Algorithmus der das i-te größte Element eines Arrays in linearer Laufzeit findet?
Ja
87
Beschreib den Select-IDX Algorithmus
88
Beschreib den Select-IDX5 Algorithmus
89
Wie lautet die Rekurrenzgleichung des Select-Algorithmus?
90
Skizziere, wie man k bestimmt

Algorithmen und Datenstrukturen (9 decks)

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