Deutsch
Menü

Grundlagen der Programmierung (Pseudocode nachverfolgen)

Die folgende Prozedur bubble ist ein Bubblesort, der das ganzzahlige Array data aufsteigend sortiert. swap(data, j, k) ist eine Prozedur, die die Werte von data[j] und data[k] vertauscht. Die Array-Indizes beginnen bei 1. Was gehört an die Stelle von 【a】 im Programm?

○bubble(integer array: data)
  integer: n ← length(data)
  for (i from n down to 2 step 1)
    for (j from 1 to 【a】 step 1)
      if (data[j] > data[j + 1])
        swap(data, j, j + 1)
      endif
    endfor
  endfor
  1. Ai
  2. Bn − i
  3. Ci − 1
Antwort und Erläuterung anzeigen

Antwort: C. i − 1

Das äußere i ist die Position, an die jeder Durchgang den größten verbleibenden Wert befördert (vom Ende her n, n − 1, …, 2). Die innere Schleife vergleicht data[j] mit data[j + 1]; mit dem Endwert i − 1 für j werden daher benachbarte Paare bis data[i] verglichen, ohne das Array zu verlassen. Der erste Durchgang mit i = n befördert den größten Wert nach data[n], der nächste reicht bis data[n − 1] usw.; der Bereich wird jedes Mal um eins kleiner. Mit i an der Stelle von 【a】 würde der erste Durchgang data[n + 1] lesen.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Programmierung (Pseudocode nachverfolgen)

  1. ÷ 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?
  2. 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?
  3. 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?
  4. 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?
  5. 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?