Informatik Test: Algorithmen und Sortieren
- Algorithmen und Sortieren
- 10 Fragen
- 15 Minuten
Zehn Fragen zu Suchverfahren, Sortieralgorithmen und einfachen Abläufen. Tipp: Spiele Algorithmen mit einer kleinen Beispielliste auf Papier Schritt für Schritt durch, statt nur im Kopf zu raten.
Tippe auf eine Antwort, um sie zu markieren. Du kannst sie ändern oder dieselbe Antwort noch einmal antippen, um die Frage leer zu lassen. Wenn du den Test beendest, siehst du die richtigen Antworten und Erklärungen.Tippe auf eine Antwort; tippst du sie noch einmal an, bleibt die Frage leer.
Dein Ergebnis
- 0 richtig
- 0 falsch
- 0 leer
-
Frage 1
Was beschreibt der Begriff Algorithmus am besten?
Richtige Antwort: C
Ein Algorithmus ist eine genau festgelegte Abfolge von Schritten. Ob er als Text, Ablaufdiagramm oder in einer Programmiersprache aufgeschrieben wird, ist zweitrangig.
-
Frage 2
Du suchst per binärer Suche eine Zahl in einer sortierten Liste mit 1000 Einträgen. Wie viele Vergleiche brauchst du höchstens?
Richtige Antwort: A
Jeder Vergleich halbiert den Suchbereich: 1000, 500, 250, ... Nach spätestens 10 Schritten bleibt nur noch ein Eintrag übrig, denn 210 = 1024. Die lineare Suche bräuchte im ungünstigsten Fall 1000 Vergleiche.
-
Frage 3
Beim Bubblesort läufst du von links nach rechts durch die Liste und vertauschst zwei Nachbarn, wenn der linke größer ist. Wie sieht die Liste [5, 2, 4, 1] nach genau einem solchen Durchlauf aus?
Richtige Antwort: A
Die 5 wandert Schritt für Schritt nach rechts: erst vor die 2, dann vor die 4, dann vor die 1. Nach einem Durchlauf steht das größte Element ganz hinten, die Liste ist aber noch nicht sortiert.
-
Frage 4
Beim Sortieren durch Auswählen (Selection Sort) wird in jedem Schritt das kleinste Element des unsortierten Rests nach vorn getauscht. Wie sieht [29, 10, 14, 37, 13] nach zwei Schritten aus?
Richtige Antwort: D
Schritt 1 tauscht die 10 mit der 29, Schritt 2 tauscht die 13 mit der 29 an Position 2. So entsteht [10, 13, 14, 37, 29]. Fertig sortiert ist die Liste noch nicht.
-
Frage 5
Welche Bedingung muss erfüllt sein, damit die binäre Suche funktioniert?
Richtige Antwort: B
Die binäre Suche verwirft nach jedem Vergleich eine Hälfte, und das ist nur erlaubt, wenn die Reihenfolge bekannt ist. Ob das Element vorkommt, spielt keine Rolle; die Suche meldet dann einfach, dass es fehlt.
-
Frage 6
Der Algorithmus soll die größte Zahl einer Liste finden:
1. Setze max auf 0.
2. Gehe die Liste durch; ist eine Zahl größer als max, setze max auf diese Zahl.
3. Gib max aus.
Was gibt er für die Liste [-5, -2, -8] aus?Richtige Antwort: D
Keine der Zahlen ist größer als der Startwert 0, deshalb bleibt max bei 0, obwohl 0 gar nicht in der Liste steht. Besser ist es, mit dem ersten Listenelement zu starten.
-
Frage 7
Ein Algorithmus setzt s = 0 und i = 1. Solange i kleiner als 10 ist, addiert er i zu s und erhöht danach i um 3. Welchen Wert hat s am Ende?
Richtige Antwort: A
Die Schleife läuft mit i = 1, 4 und 7 durch (danach ist i = 10 und sie endet): 1 + 4 + 7 = 12. Mit der 10 würdest du auf 22 kommen, aber die Bedingung i < 10 schließt sie aus.
-
Frage 8
Der euklidische Algorithmus ersetzt wiederholt die größere Zahl durch den Rest der Division. Welcher größte gemeinsame Teiler (ggT) ergibt sich für 48 und 18?
Richtige Antwort: C
48 mod 18 = 12, dann 18 mod 12 = 6, dann 12 mod 6 = 0, der letzte Rest ungleich 0 ist 6. Die 12 teilt zwar 48, aber nicht 18.
-
Frage 9
Mergesort teilt die Liste immer wieder in zwei Hälften, sortiert die Teile und fügt sie zusammen. Welches allgemeine Entwurfsprinzip steckt dahinter?
Richtige Antwort: B
Ein großes Problem wird in kleinere gleichartige Probleme zerlegt, die einzeln gelöst und am Ende kombiniert werden. Backtracking (Ausprobieren und zurückgehen) wäre ein anderes Prinzip.
-
Frage 10
Du verdoppelst die Anzahl der Einträge in einer unsortierten Liste und suchst darin linear nach einem Wert, der im ungünstigsten Fall ganz hinten steht. Wie ändert sich die Zahl der Vergleiche?
Richtige Antwort: D
Bei der linearen Suche wächst der Aufwand im ungünstigsten Fall proportional zur Listenlänge. Doppelt so viele Einträge bedeuten doppelt so viele Vergleiche; bei der binären Suche käme nur ein Vergleich hinzu.
Leer gelassene Fragen zählen nicht als falsch.