Klausurvorbereitung

Aufgabe 1

Unten findest du die ersten Schritte eines Sortieralgorithmus. Führe den Algorithmus für in der Notation wie unten zuende. Erläutere den Algorithmus und nenne seinen Namen.

a)

[]     [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
                                            ^
[ 6 ]     [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 20, 29 ]
  #                                 ^
[ 6, 8 ]     [ 25, 17, 32, 56, 25, 19, 66, 29, 20, 29 ]
     #             ^

b)

[]     [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
         ^
[ 25 ]     [ 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
  #          ^
[ 17, 25 ]     [ 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
  #              ^

c)

[ 92, 95, 84, 25, 70, 45, 27 ]
  ^   ^
[ 92, 95, 84, 25, 70, 45, 27 ]
      *   *
[ 92, 84, 95, 25, 70, 45, 27 ]
          *   *

d)

[ 25   17   32   56   25   19    8   66   29    6   20   29 ]
   ^

[ 17   19    8    6   20 ] [ 25 ] [ 32   56   25   66   29   29 ]
   ^                                 ^

[ 8    6 ] [ 17 ] [ 19   20 ] [ 25 ] [ 25   29   29 ] [ 32 ] [ 56   66 ]
  ^                  ^                  ^                       ^

Aufgabe 2

Diskutiere, welchen Algorithmus du in den folgenden Fällen anwenden würdest. Gehe dabei auf die Vor- und Nachteile in Frage kommender Algorithmen ein und begründe deine Wahl.

Ein unsortiertes Adressverzeichnis soll nach "Max Mustermann" durchsucht werden.
Ein sortiertes Adressverzeichnis soll nach "Max Mustermann" durchsucht werden.
Ein sehr großer Datensatz (> 1 Mio. Einträge) von Dateien soll nach Größe sortiert werden.
Ein sehr kleiner Datensatz (< 100 Einträge) von Dateien soll nach Größe sortiert werden.
In einem Labor sollen neue Messdaten in eine bestehende, sortierte Messdatenliste einsortiert werden.
Eine größtenteils vorsortierte Liste von Zahlen soll sortiert werden.

Aufgabe 3

Gegeben ist folgender JavaCode. Erstelle ein passendes Struktogramm und erläutere den Algorithmus. Welcher Algorithmus wird hier dargestellt?

a)

aufgabe3a.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int sortiertBisIndex = 0;
 
while (sortiertBisIndex < daten.length) {
  int kleinstesElementIndex = sortiertBisIndex;
 
  for (int index = sortiertBisIndex; index < daten.length; index++) {
    if (daten[index] < daten[kleinstesElementIndex]) {
      kleinstesElementIndex = index;
    }
  }
 
  int temp = daten[sortiertBisIndex];
  daten[sortiertBisIndex] = daten[kleinstesElementIndex];
  daten[kleinstesElementIndex] = temp;
 
  sortiertBisIndex++;
}
 
printArray(daten);

b)

aufgabe3b.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int sortiertBisIndex = 1;
 
while (sortiertBisIndex < daten.length) {
  int neuesElement = daten[sortiertBisIndex];
 
  for (int index = 0; index < sortiertBisIndex; index++) {
    if (neuesElement < daten[index]) {
      int temp = daten[sortiertBisIndex];
      daten[sortiertBisIndex] = daten[index];
      daten[index] = temp;
    }
  }
 
  sortiertBisIndex++;
}
 
printArray(daten);

c)

aufgabe3c.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int sortiertAbIndex = daten.length;
 
while (sortiertAbIndex > 0) {
  for (int index = 1; index < sortiertAbIndex; index++) {
    if (daten[index - 1] > daten[index]) {
      int temp = daten[index];
      daten[index] = daten[index - 1];
      daten[index - 1] = temp;
    }
  }
 
  sortiertAbIndex--;
}
 
printArray(daten);

d)

aufgabe3d.pde

int[] daten = new int[] { 5, 6, 8, 9, 9, 14, 17, 18, 30, 33, 38, 39, 52, 65, 69, 72, 78, 82, 83, 84, 86, 89, 95, 98, 99 };
 
int gesucht = 72;
boolean abbruch = false;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (!(abbruch || gefunden) && position < daten.length - 1) {
  anzahlSchritte++;
 
  if (daten[position] == gesucht) {
    gefunden = true;
  } else if (daten[position] > gesucht) {
    abbruch = true;
  } else {
    position++;
  }
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}

e)

aufgabe3e.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int gesucht = 72;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (!gefunden && position < daten.length - 1) {
  anzahlSchritte++;
 
  if (daten[position] == gesucht) {
    gefunden = true;
  } else {
    position++;
  }
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}

f)

aufgabe3f.pde

int[] daten = new int[] { 5, 6, 8, 9, 9, 14, 17, 18, 30, 33, 38, 39, 52, 65, 69, 72, 78, 82, 83, 84, 86, 89, 95, 98, 99 };
 
int gesucht = 18;
int linkeGrenze = 0;
int rechteGrenze = daten.length - 1;
boolean gefunden = false;
int position = -1;
int anzahlSchritte = 0;
 
while (!gefunden && rechteGrenze > linkeGrenze) {
  anzahlSchritte++;
 
  int pivotIndex = linkeGrenze + (rechteGrenze - linkeGrenze) / 2;
  int pivotElement = daten[pivotIndex];
 
  if (gesucht < pivotElement) {
    rechteGrenze = pivotIndex - 1;
  } else if (gesucht > pivotElement) {
    linkeGrenze = pivotIndex + 1;
  } else {
    gefunden = true;
    position = pivotIndex;
  }
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}

Aufgabe 4

Gegeben ist folgendes Struktogramm. Erstelle den passenden Java-Code und erläutere den Algorithmus. Welcher Algorithmus wird hier dargestellt?

a)

b)

c)

Aufgabe 5

Erstelle Struktogramme und Java-Code für die folgenden Algorithmen:

Bestimmen des Minimums / Maximums / Durchschnittswerts einer Liste von Zahlen
Suchen eines bestimmten Elements mit der Brute-Force / Linearen / Binären Suche
Sortieren einer Liste mit SelectionSort / InsertionSort / BubbleSort / QuickSort