WorksheetsInformatik 2: Sortierverfahren
Total questions: 24
Worksheet time: 11mins
Das hier ist eine Testfrage :)
1+1=?
1
2
3
4
Bitte runterscrollen
...
...
... und es können mehrere Antworten richtig sein ...
...
...
Was ist korrekt?
Heute ist Freitag.
Es ist 2023.
Info 2 macht Spaß.
Welche der Sortierverfahren sind vergleichsbasiert?
Bucket Sort
Heap Sort
Merge Sort
Counting Sort
Sortierverfahren heißen in-place, wenn die Reihenfolge von Elementen mit gleichem Sortierschlüssel nicht verändert wird.
wahr
falsch
Welcher der folgenden Sortieralgorithmen bietet in seiner typischen Implementierung die beste Laufzeit, wenn er auf ein sortiertes oder fast sortiertes Array angewendet wird?
Quick Sort
Heap Sort
Merge Sort
Insertion Sort
Welches Sortierverfahren ist hier am Werk?
Bubble Sort
Merge Sort
Insertion Sort
Heap Sort
Was ist die Laufzeit von Insertion Sort, wenn die Eingabe vorsortiert ist?
O(n2)
O(n)
O(n⋅logn)
O(logn)
Dieses Array ist ein Max-Heap.
wahr
falsch
Welche der Sortierverfahren arbeiten stabil?
Bubble Sort
Selection Sort
Insertion Sort
Alle uns bekannten Verfahren!
Welches Sortierverfahren ist hier am Werk?
Merge Sort
Quick Sort
Heap Sort
Insertion Sort
Counting-Sort arbeitet nach dem divide&conquer Prinzip.
wahr
falsch
Welches Sortierverfahren könnten hier (rein theoretisch) am Werk sein?
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Betrachten Sie eine Situation, in der ein Tauschvorgang sehr kostspielig ist. Welcher der folgenden Sortieralgorithmen sollte bevorzugt werden, damit die Anzahl der Tauschoperationen im Allgemeinen minimiert wird?
Heap Sort
Selection Sort
Insertion Sort
Merge Sort
Von welchem Verfahren ist hier die Rede
Insertion Sort
Bubble Sort
Selection Sort
Quick Sort
Selection Sort sucht im bereits sortierten Teil des Feldes, Insertion Sort hingegen im unsortierten Teil.
wahr
falsch
Ein Sortierverfahren heißt in-place, wenn der zusätzliche Speicherbedarf unabhängig von n ist, und damit konstant.
wahr
falsch
Welches Sortierverfahren ist hier am Werk?
Quick Sort
Insertion Sort
Heap Sort
Merge Sort
Welche der Sortierverfahren arbeiten in-place?
Insertion Sort
Heap Sort
Merge Sort
Quick Sort
Welche der Sortierverfahren haben im worst case eine bessere Laufzeit als das hier abgebildete Verfahren?
Insertion Sort
Heap Sort
Quick Sort
Merge Sort
Welche der Sortierverfahren arbeiten stabil?
Heap Sort
Radix Sort
Merge Sort
Quick Sort
Was ist im worst case die Rekurrenz für Quick Sort?
T(n)=T(n−2)+O(n)
T(n)=T(n−1)+O(n)
T(n)=2T(2n)+O(n)
Hier arbeitet Merge Sort
wahr
falsch
Dieses Array ist ein Min-Heap.
wahr
falsch
Angenommen, wir haben einen Algorithmus mit einer Zeit von O(n), der den Median eines unsortierten Arrays findet.
Betrachten wir nun eine QuickSort-Implementierung, bei der wir zuerst den Median mit dem obigen Algorithmus finden und dann den Median als Pivot verwenden.
Wie hoch ist die Zeitkomplexität dieses modifizierten QuickSort im schlimmsten Fall?
O(n2⋅logn)
O(n2)
O(n⋅logn⋅logn)
O(n⋅logn)
