Deutsch
Menü

Grundlagen der Programmierung (Pseudocode nachverfolgen)

÷ ist die Division; wird das Ergebnis einer ganzzahligen Variablen (auch einem Funktionsargument) zugewiesen, wird der Nachkommaanteil abgeschnitten. Das folgende Programm ermittelt in lo den Index des ersten Werts, der mindestens x ist, im aufsteigend sortierten ganzzahligen Array data (die Indizes beginnen bei 1). x ist nicht größer als das letzte Element von data. Was gehört an die Stelle von 【a】 im Programm?

integer: lo ← 1, hi ← length(data), mid
while (lo < hi)
  mid ← (lo + hi) ÷ 2
  if (data[mid] < x)
    lo ← 【a】
  else
    hi ← mid
  endif
endwhile
  1. Amid
  2. Bmid − 1
  3. Cmid + 1
Antwort und Erläuterung anzeigen

Antwort: C. mid + 1

Gilt data[mid] < x, sind data[mid] und alle Elemente davor kleiner als x; die Antwort liegt also bei mid + 1 oder dahinter. Andernfalls gilt data[mid] ≧ x, und die Antwort liegt bei mid oder davor, daher hi ← mid. Mit lo ← mid + 1 wird der Bereich in jedem Durchlauf kleiner, und die Antwort liegt dort, wo lo = hi gilt. Mit lo ← mid ist bei benachbartem lo und hi mid = lo; gilt dann data[mid] < x, wird der Bereich nicht kleiner, und die Schleife endet nie.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Programmierung (Pseudocode nachverfolgen)

  1. Ein Stack wird durch das ganzzahlige Array st mit 5 Elementen und die ganzzahlige Variable top dargestellt. Alle Elemente von st sind anfangs 0, und top beginnt bei 0. push(v) addiert 1 zu top und führt dann st[top] ← v aus; pop() gibt den Wert von st[top] zurück und subtrahiert dann 1 von top (die Elemente von st werden nicht verändert). Welche Werte haben top und st, nachdem das folgende Programm ausgeführt wurde?
  2. Eine Warteschlange verwendet das Zeichenketten-Array q mit 4 Elementen als Ring. head und tail beginnen bei 1. enq(v) führt q[tail] ← v und dann tail ← tail mod 4 + 1 aus; deq() gibt den Wert von q[head] zurück und führt dann head ← head mod 4 + 1 aus. In welchem Element von q wird „E“ gespeichert, wenn das folgende Programm ausgeführt wird?
  3. Das folgende Programm gibt eine verkettete Liste aus, deren Elemente über das Array next verbunden sind, indem es ihr ab dem Element mit Index 1 folgt. Die Array-Indizes beginnen bei 1. Der next-Wert 0 markiert das Ende der Liste. Welche Folge von Werten wird ausgegeben?
  4. Das folgende Programm fügt „F“ aus val[6] direkt hinter „C“ (Index 3) in die verkettete Liste A → C → E → D → B ein, die über das Array next verbunden ist, und gibt die Liste dann ab dem Element mit Index 1 aus. Die Array-Indizes beginnen bei 1. Der next-Wert 0 markiert das Ende der Liste. Was gehört an die Stelle von 【a】, damit die Ausgabe A, C, F, E, D, B lautet?
  5. Die folgende for-Schleife erhöht ihre Laufvariable jeweils um 5. Welchen Wert hat c nach der Ausführung?