Lernziel · Gymnasiallehrplan
GYM INF 1 — Obligatorisches Fach: Informatik.
Vorschau der Fragen
1Eine Liste mit 250 Namen ist nicht sortiert. Eine lineare Suche vergleicht den gesuchten Namen mit jedem Element. Wie viele Vergleiche braucht es, um zu behaupten, dass ein fehlender Name nicht…
Zahl als Antwort eingeben.
2Warum lässt sich eine binäre Suche nicht auf eine Liste zufällig geordneter Namen anwenden?
Weil sie die Position des gesuchten Namens im Voraus kennen muss.Weil der Vergleich mit dem mittleren Namen dann nichts über den Rest verrät.Weil sie nur Zahlen vergleichen kann, niemals Text.Weil sie eine Liste verlangt, deren Länge eine Zweierpotenz ist.
3Ordne die Schritte einer binären Suche in einer sortierten Liste.
In die richtige Reihenfolge bringen:
Den gesuchten Wert mit dem mittleren Element vergleichenDen Index der Mitte zwischen den beiden Grenzen berechnenEine Grenze verschieben, um nur eine Hälfte zu behaltenWiederholen, solange sich die Grenzen nicht kreuzenZwei Grenzen setzen: Anfang und Ende der Liste
4Eine sortierte Liste hat 100 Werte. Jeder Vergleich einer binären Suche scheidet die Hälfte der noch möglichen Kandidaten aus. Wie viele Vergleiche genügen im schlimmsten Fall für eine Antwort?
Zahl als Antwort eingeben.
5Ein Sortierverfahren in n² vergleicht etwa n × n Werte. Bei 100 000 Karteikarten beendet ein Computer, der 100 Millionen Vergleiche pro Sekunde schafft, diese Sortierung in weniger als einer Sekunde.
RichtigFalsch
6Eine Liste enthält n Werte. Ordne jede Operation nach der Zahl der Schritte, die sie im schlimmsten Fall braucht.
Kategorien:
Etwa log nEtwa nEtwa n²
Zu ordnende Begriffe:
Alle Werte der Liste addierenBinär in einer sortierten Liste suchenDen grössten Wert der Liste findenDie Liste bis auf ein Element halbierenDie Liste mit Bubblesort sortierenJeden Wert mit allen anderen vergleichen
7n = 12 zaehler = 0 for i in range(n): for j in range(n): zaehler = zaehler + 1 Welchen Wert hat zaehler am Ende?
Zahl als Antwort eingeben.
8Eine Liste mit 1000 Werten wächst auf 2000 Werte. Ordne jedem Aufwand die gerundete Zahl der Vergleiche zu, die sich ergibt.
Paarweise zuordnen:
n Vergleichelog n Vergleichen² Vergleichen × log n Vergleiche
20004 000 000etwa 11etwa 22 000
9Zwei sortierte Hälften mit je 4 Werten werden zusammengeführt: Man vergleicht ihre ersten übrigen Elemente, behält das kleinere. Ist eine Hälfte leer, geht der Rest ohne Vergleich durch. Wie viele…
4 Vergleiche5 Vergleiche7 Vergleiche8 Vergleiche
10Bubblesort durchläuft die Liste und vertauscht zwei falsch geordnete Nachbarn. Man wendet einen vollständigen Durchgang auf die Liste [5, 1, 4, 2] an. Welche Aussagen stimmen?
Die Liste ist nun [1, 4, 2, 5].Der grösste Wert steht auf dem letzten Platz.Die Liste ist jetzt vollständig sortiert.Es wurden drei Nachbarvergleiche gemacht.Es war keine Vertauschung nötig.Der kleinste Wert wurde ans Ende geschoben.
11while start <= ende: m = (start + ende) // 2 if t[m] < ziel: ??? Die Liste t ist sortiert. Welche Anweisung ersetzt die Fragezeichen korrekt?
start = m + 1ende = m - 1start = m - 1ende = len(t) - 1
12Eine Verwaltungssoftware hält ihre 500 000 Karteikarten nach Namen sortiert, nicht in der Reihenfolge ihres Eingangs. Welchen Hauptvorteil bringt ihr das?
Sie braucht viel weniger Platz auf der Festplatte der Maschine.Sie fügt eine neue Karte ein, ohne je die anderen zu verschieben.Sie schützt die Karten vor Tippfehlern des Personals.Sie findet eine Karte binär, statt alles zu durchlaufen.
Die richtigen Antworten entdeckst du beim Spielen.
