WorksheetsIntroprog 6. Tutorium
Total questions: 19
Worksheet time: 10mins
Was ist die Worst-Case Laufzeitkomplexität von Insertionsort?
O(1)
Welcher Sortieralgorithmus vergleicht wiederholt benachbarte Elemente und vertauscht diese, wenn sie in der falschen Reihenfolge sind?
Insertionsort
Selectionsort
Bubblesort
Countsort
Welche Schlüsseloperation wird in der äußeren Schleife von Insertionsort durchgeführt?
Ein Element an seine richtige Position einfügen
Das kleinste oder größte Element auswählen
Die Elemente aufsummieren
In welchem Fall ist Selectionsort am effizientesten?
Wenn die Eingabe...
schon richtig sortiert ist
falschherum sortiert ist
gar nicht sortiert ist
alle Fälle sind gleich effizient
In welchem Fall ist Insertionsort am effizientesten?
Wenn die Eingabe...
schon richtig sortiert ist
falschherum sortiert ist
gar nicht sortiert ist
alle Fälle sind gleich effizient
Wie kann Bubblesort so optimiert werden, dass der Algorithmus in einigen Fällen vorzeitig beendet wird?
Durch Erhöhen der Anzahl der Iterationen
Durch Rekursion
Indem der Algorithmus abbricht, wenn in einem Durchgang keine Elemente getauscht werden
Indem die Anzahl der Durchläufe auf die Quadratwurzel der Arraygröße reduziert wird
Wieso ist Stabilität von Sortierverfahren wichtig?
Dadurch kann in O(n) sortiert werden
Dadurch wird der Speicherplatzverbrauch von Algorithmen reduziert
Es ist wichtig für Anwendungen, bei denen die Reihenfolge von Daten mit gleichem Schlüssel relevant ist
Es ist für keinen praktische Anwendung relevant
Was ist die Speicherplatzkomplexität von Insertionsort?
(wie viel Speicherplatz braucht Insertionsort zusätzlich)
O(1)
O(log n)
O(n)
O(n²)
Welche asymptotische Laufzeitkomplexität ist effizienter?
O(1.000 n)
O(n²)
beide sind gleich effizient
Welche asymptotische Laufzeitkomplexität ist effizienter?
O(n log n)
O(n²)
beide sind gleich effizient
Welche asymptotische Laufzeitkomplexität ist effizienter?
O(n)
O(n + log n)
beide sind gleich effizient
Welche Zeitkomplexität hat der Zugriff auf ein Element in einem Array über seinen Index?
O(1)
O(log n)
O(n)
O(n²)
Was ist der primäre Vorteil von linked-lists über Arrays?
schnellerer Zugriff auf Elemente über den Index
dynamische Größe
benötigt weniger Speicherplatz
Elemente können in konstanter Zeit durchlaufen werden
Welche Laufzeit wird benötigt, um einen Knoten am Anfang einer einfach verketteten Liste einzufügen?
O(1)
O(log n)
O(n)
O(n²)
Welches zusätzliche Attribut hat eine doppelt-verkettete Liste im Vergleich zu einer einfach-verketteten Liste?
eine ID-Nummer
einen Vorgänger-Pointer
einen Nachfolger-Pointer
einen Pointer zum Listenkopf
Welche Laufzeit wird für das Löschen eines Elements in einer doppelt-verketteten Liste benötigt?
(ein Pointer zu diesem Element ist gegeben)
O(1)
O(log n)
O(n)
O(n²)
Welche Laufzeit wird für das Löschen eines Elements in einem binären Suchbaum (BST) in Abhängigkeit von der Anzahl der Knoten n benötigt?
(ein Pointer zu diesem Element ist gegeben)
O(1)
O(log n)
O(n)
O(n²)
An welche Stelle würde ein Knoten mit dem Schlüssel 20 eingefügt werden?
A
B
C
D
An welche Stelle würde ein Knoten mit dem Schlüssel 30 eingefügt werden?
A
B
C
D
