Deutsch
Menü

Datenstrukturen und Algorithmen

Der Ausdruck „3 4 + 2 * 5 −“ in umgekehrter polnischer Notation (Postfixnotation) wird ausgewertet, indem jede Zahl auf einen Stack gelegt wird und bei jedem Operator zwei Werte entnommen, verrechnet und das Ergebnis wieder abgelegt wird. Welches Ergebnis entsteht? Der linke Operand eines Operators ist der Wert, der früher abgelegt wurde.

  1. A−9
  2. B6
  3. C9
Antwort und Erläuterung anzeigen

Antwort: C. 9

3 und 4 werden abgelegt; + entnimmt beide und legt 3 + 4 = 7 ab. Dann wird 2 abgelegt, und * legt 7 × 2 = 14 ab. Nach dem Ablegen von 5 zieht − den später abgelegten Wert 5 vom früher abgelegten Wert 14 ab: 14 − 5 = 9. In der Postfixnotation ist die Reihenfolge der Operationen durch die Anordnung festgelegt, daher sind keine Klammern nötig; der Ausdruck entspricht (3 + 4) × 2 − 5 in gewöhnlicher Schreibweise. −9 entsteht durch Vertauschen der Operanden der Subtraktion, 6 durch das Lesen als 3 + 4 × 2 − 5 ohne Klammern.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Welche Aussage beschreibt eine Kollision in einer Hashtabelle richtig?
  2. In einer Hashtabelle der Größe 7 (Positionen 0 bis 6) werden mit der Hashfunktion h(k) = k mod 7 die Schlüssel 10, 17, 24 und 3 in dieser Reihenfolge gespeichert. Kollisionen werden durch lineares Sondieren aufgelöst, das jeweils eine Position weiterrückt (nach 6 folgt 0), bis ein freier Platz gefunden ist. An welcher Position wird der Schlüssel 3 gespeichert?
  3. Welche Aussage vergleicht die Verkettung (Chaining: Elemente derselben Position werden in einer verketteten Liste verbunden) und die offene Adressierung (eine andere freie Position innerhalb der Tabelle wird gesucht) als Verfahren zur Kollisionsauflösung in Hashtabellen richtig? Der Belegungsfaktor ist die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße.
  4. Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?
  5. Auf 1000 verschiedene, aufsteigend sortierte Werte wird eine binäre Suche angewendet. Ein Vergleich liefert jeweils „gleich“, „kleiner“ oder „größer“. Wie viele Vergleiche sind höchstens nötig, erfolgreiche und erfolglose Suchen zusammengenommen?