Informatik-Biber 2007

Aufgaben
Ab Stufe 11

Biber und Bisons

Biber sagen immer die Wahrheit, und Bisons lügen immer. Im Biber-und-Bison-Zeltlager wohnen insgesamt zehn Tiere. Ein blinder Maulwurf kommt vorbei und möchte wissen, wie viele Biber und wie viele Bisons anwesend sind. Darum fragt er jedes Tier: "Wie viele Biber gibt es hier?" Die zehn Antworten sind:

3, 4, 1, 4, 1, 1, 3, 4, 3, 2

Jetzt weiß der blinde Maulwurf genau Bescheid! Du auch?

Wie viele Biber sind im Biber-und-Bison-Zeltlager?

A) 1

B) 2

C) 3

D) 4

Primärschlüssel

In einer Datenbank wird ein Primärschlüssel verwendet, um die Datensätze eindeutig zu identifizieren. Im Folgenden ist eine Datenbank gegeben. Jede Zeile entspricht einem Datensatz. Die Schüler ID soll ein Primärschlüssel sein.

Welche der folgenden Tabellen enthält fehlerhafte Werte für die Schüler ID?

Falschgeld

Du hast 4 Münzen geschenkt bekommen, doch eine davon ist leider falsch. Die falsche Münze hat ein anderes Gewicht.

Aber wenn du eine Balkenwaage benutzt, kannst du mit nur zwei Vergleichen herausfinden, welche die falsche Münze ist. Gehe dazu nach dem unten abgebildeten Plan vor. In dem Plan steht G[1] für das Gewicht von Münze 1, G[2] für das Gewicht von Münze 2, usw. Zuerst wiegst du also Münze 1 gegen Münze 3 ab (obere Raute), im zweiten Schritt Münze 1 gegen Münze 2. Die unterste Zeile nennt dir dann die Nummer der falschen Münze, die sich ergibt, wenn die Vergleiche nach den Beschriftungen der Pfeile ausfallen. Jedoch sind die Felder gerade leer.

Welche Nummern müssen in den leeren Feldern stehen (von links nach rechts)?

A) 1, 2, 3, 4

B) 4, 3, 2, 1

C) 4, 2, 3, 1

D) 3, 2, 1, 4

Ungeschützter Computer

Tom hat einen Computer, mit dem er auch im Internet surft. Um den Computer zu benutzen, braucht er kein Passwort. Auf dem Computer gibt es keine Firewall (also keinen Schutz gegen Kontaktversuche durch andere ans Internet angeschlossene Computer) und auch kein Programm, das gegen Viren oder andere schädliche Programme schützt.

Für welche Computer besteht durch dieses leichtsinnige Verhalten die Gefahr, durch einen Computervirus oder durch ein anderes schädliches Programm angegriffen zu werden?

A) Für alle Computer, die mit Toms Computer im lokalen Netzwerk verbunden sind.

B) Nur für Toms eigenen Computer.

C) Für alle Computer auf der Welt, die mit dem Internet verbunden sind.

D) Für alle Computer auf der Welt.

Wertetausch

In einer Programmiersprache haben wir 2 Variablen X und Y, die nur ganze Zahlen als Wert annehmen können. Nun möchten wir die Werte von X und Y tauschen, ohne eine weitere Variable zu benutzen.
Der Operator := weist der Variablen auf der linken Seite den Wert auf der rechten Seite zu; die Zuweisungen werden nacheinander vorgenommen.

Welche Lösung führt zum gewünschten Ergebnis?

A)

X := Y 

B)

X := X + Y

C)

X := X + Y

Y := X

Y := X – Y

Y := X + Y

X := X – Y

X := X – Y

D) Das ist ohne eine weitere Variable nicht möglich.

Biberzahlen

Du weißt, wie man unsere gewohnten Dezimalzahlen als Binärzahlen aufschreibt? In der Tabelle wird es noch einmal gezeigt.

Biber hat eine weitere Schreibweise für Zahlen entwickelt. Er benutzt auch nur die Ziffern 1 und 0. Jedoch darf die Ziffer 1 höchstens so oft in einer Biberzahl vorkommen, wie der Biber Schneidezähne hat - also höchstens zweimal. Natürlich müssen alle Zahlen wieder unterschiedlich sein. Die Tabelle zeigt die Biberzahlen für die Dezimalzahlen 0 bis 10.

Beispiele:

1000100110 ist keine Biberzahl (zu viele Schneidezähne)
0000100100 ist keine Biberzahl (führende Nullen sind nicht erlaubt)

Dezimalzahl	Binärzahl	Biberzahl
0	0	0
1	1	1
2	10	10
3	11	11
4	100	100
5	101	101
6	110	110
7	111	1000
8	1000	1001
9	1001	1010
10	1010	1100

Wie lautet die Biberzahl für die Dezimalzahl 20?

A) 10100

B) 101000

C) 100100

D) Die Zahl gibt es nicht

Computervirus

Ein Computervirus breitet sich im Betriebssystem deines Computers aus und verursacht einen solchen Schaden, dass der Computer nicht mehr gestartet werden kann.
Der Computer ist nagelneu, so dass die Verkaufsgarantie noch gültig ist. Der Computervirus war allerdings nicht von Anfang an da, sondern ist erst nach ein paar Tagen aufgetaucht.

Wer übernimmt die Reparaturkosten?

A) Der Laden, in dem der Computer gekauft wurde.

B) Der Hersteller der Festplatte.

C) Der Hersteller des Betriebssystems.

D) Niemand. Du musst die Reparatur selbst bezahlen und dafür sorgen, dass das nicht noch einmal geschieht!

Morse-Code

In ESROM-Land gibt es nur fünf Buchstaben: E, S, R, O und M.
Die Buchstaben kommen in der ESROM-Sprache unterschiedlich häufig vor (in Prozent):

Ein Verein von Telegraphie-Freunden möchte Nachrichten in der ESROM-Sprache mit einem Morse-Code übermitteln, der mit möglichst wenigen Signalen auskommt und natürlich alle Wörter eindeutig kodiert.

Bei welchem Morse-Code für die ESROM-Buchstaben benötigt man im Schnitt die wenigsten Signale ("*" und "-") zur Nachrichtenübermittlung?

A)

E = ***

S = *-

R = -

O = -*

M = *

B)

E = - 

S = *

R = ***

O = -*

M = ---

C)

E = ** 

S = *-

R = *

O = -*

M = -

D)

E = *-

S = * 

R = -

O = -*

M = * 

Schnitzeljagd

Auf seinem Weg vom Start zum Ziel folgt Florian den Pfeilen, beliebig lange. Jedes Mal, wenn er einen Pfeil entlang gegangen ist, sammelt er den zugehörigen Buchstaben ein und verlängert damit eine Kette der gesammelten Buchstaben. Bei einigen Pfeilen kann er keinen Buchstaben einsammeln.

Welche der folgenden Buchstabenketten kann Florian auf seinem Weg vom Start zum Ziel nicht einsammeln?

A) abaabba

B) ba

C) abaaab

D) aab

Verschlüsselung von Buchstaben

Biber verschlüsselt Buchstaben mit nur zwei Ziffern 0 und 1 auf folgende Weise:

Mit diesem Schlüssel steht zum Beispiel "01011011" für die Zeichenkette "CAAB". Nun möchte Biber aber einen weiteren Buchstaben, "D", hinzufügen. Er braucht dazu einen Schlüssel, der keine Verwechslung zulässt, so dass der Code immer eindeutig entschlüsselt werden kann. Er kann dafür z.B. nicht "11" nehmen, weil dann "AAB" und "DB" mit dem selben Code "11011" verschlüsselt würden.

Auf welche Weise kann Biber den Buchstaben "D" eindeutig verschlüsseln?

A) 101

B) 110

C) 01110

D) 00

Endlos-Schleife

Ein Fluss-Diagramm beschreibt einen Algorithmus. Die verschiedenen Wege vom Start zum Ziel repräsentieren alle möglichen Wege, die der Algorithmus einschlagen kann. In den rechteckigen Kästen steht jeweils eine Folge von Befehlen. In der Raute soll eine Frage stehen; die Antwort auf die Frage bestimmt die Richtung, in die der Algorithmus weiter läuft. Der Operator := weist der Variablen auf der linken Seite den Wert auf der rechten Seite zu.

A) A = 16 ?

B) B = 100 ?

C) A < B ?

D) A > B * 100 ?

Labyrinth

Im Folgenden wird eine Methode erklärt, um ein Labyrinth aus einem Rechteck mit den Seitenlängen m und n zu erstellen (m, n beide größer als 2). Dafür werden zunächst Trennwände wie ein Gitter in das Rechteck gesetzt. Jedes Feld ist nun ein Raum und bekommt eine Nummer.

Erstellen eines Labyrinths:
Schritt 1: Verbinde zwei Räume, indem du eine Trennwand entfernst.
Schritt 2: Nummeriere den neuen, verbundenen Raum mit der niedrigeren Nummer der beiden gerade verbundenen Räume.
Schritt 3: Wiederhole Schritt 1 und Schritt 2 solange, bis nur noch ein Raum übrig ist. Dieser hat die Nummer 1.

Beispiel:

Nur einer der folgenden Raumpläne wurde mit der gerade erklärten Labyrinth-Methode erstellt. Welcher?

Netzwerkkabel

Ein Netzwerk besteht aus 7 Computern, die durch Kabel verbunden sind.
Die Kabel haben alle eine bekannte Länge (in Metern).

Wie viele Meter Netzwerkkabel braucht man mindestens, wenn man keinen Computer komplett abtrennen will?

A) 18

B) 20

C) 14

D) 16

POP und PUSH

Wir haben vier schmale Kellerräume, um Tonnen hintereinander zu lagern. Zur Belegungsplanung dieser Keller benutzen wir die Operation:

popush (X, Y)

mit der Bedeutung:

Falls der Keller X nicht leer ist und
der Keller Y nicht voll ist,
dann ziehe die vorderste Tonne aus dem Keller X (pop) und
schiebe sie so weit es geht in den Keller Y (push).

Wir wollen die Kellerbelegung unten links in die Kellerbelegung unten rechts ändern:

Mit welcher Folge von Operationen können wir das erreichen?

A) popush (B,D); popush (C,D); popush (A,A); popush (B,D); popush (B,D);

B) popush (C,D); popush (C,A); popush (B,D); popush (B,C); popush (B,C);

C) popush (C,A); popush (B,D); popush (B,C); popush (B,C); popush (A,C);

D) popush (B,D); popush (C,D); popush (B,C); popush (D,C); popush (B,C);

Verwandlung

Die Abbildung zeigt links eine Figur aus Punkten, die mit Linien verbunden sind. Diese Figur wird nach einer geheimen Vorschrift verwandelt; das Ergebnis ist rechts zu sehen:

Wenn du die folgende Figur nach der gleichen Vorschrift verwandelst, wie sieht dann das Ergebnis aus?