Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forum (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungss07 [20.02.2012 14:08] – Guanta | pruefungen:bachelor:aud:loesungss07 [04.03.2020 13:26] (aktuell) – kat04 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
=== Forum === | === Forum === | ||
- | * [[https:// | + | * [[https:// |
+ | * [[https:// | ||
==== Lösungsversuch ==== | ==== Lösungsversuch ==== | ||
Zeile 28: | Zeile 28: | ||
richtig | richtig | ||
- | falsch | + | falsch |
falsch | falsch | ||
Zeile 35: | Zeile 35: | ||
**k)** falsch | **k)** falsch | ||
+ | |||
+ | === Aufgabe 2 - Java (12P) === | ||
+ | |||
+ | - Beispiel: c: Test | ||
+ | - a: Test | ||
+ | - b: 42 | ||
+ | - c: 0 | ||
+ | - f: 0 | ||
+ | - Compiler-Fehler: | ||
+ | - e: 23 | ||
+ | |||
+ | === Aufgabe 3 - Spannbäume (20P) === | ||
+ | |||
+ | **a)** Adjazenzmatrix | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | **d)** Halde - Begründung??? | ||
+ | |||
+ | **e)** | ||
+ | |||
+ | * genau n | ||
+ | * genau n - 1 | ||
+ | * genau 1 | ||
+ | * O (|V| * log |V| + |E|) | ||
+ | |||
+ | |||
+ | === Aufgabe 4 - Suchbaum und Streutabelle (15P) === | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | * Bester Fall: 1 | ||
+ | * Schlechtester Fall: n - 1 | ||
+ | |||
+ | **c)** 6, 4, 8, 2, 5, 7, 1 | ||
+ | |||
+ | **d)** | ||
+ | * Preorder | ||
+ | * Inorder (produziert im binären Suchbaum sortierte Liste) | ||
+ | * Postorder | ||
+ | |||
+ | **e)** | ||
+ | |||
+ | 3|7(3)|-|1|4|-|2|5|6(4)|-| | ||
+ | | ||
+ | === Aufgabe 6 - QuickSort === | ||
+ | |||
+ | public class QuickSort { | ||
+ | |||
+ | public static void main(String[] args) { | ||
+ | |||
+ | int[] array = { 20, 35, -15, 7, 55, 1, -22, | ||
+ | System.out.println(quickSelect(array, | ||
+ | quickSort(array); | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | } | ||
+ | |||
+ | // v e r t a u s c h t zwei Positionen e i n e r Reihung | ||
+ | static void swap(int a[], int i, int j) { | ||
+ | int t = a[i]; | ||
+ | a[i] = a[j]; | ||
+ | a[j] = t; | ||
+ | } | ||
+ | |||
+ | // s o r t i e r t di e komplette Reihung | ||
+ | static void quickSort(int a[]) { | ||
+ | quickSortAuf(a, | ||
+ | |||
+ | } | ||
+ | |||
+ | // s o r t i e r t den Bereich von s t a r t b i s end ( i n k l u s i v e ) | ||
+ | static void quickSortAuf(int a[], int start, int end) { | ||
+ | |||
+ | if (start >= end) { | ||
+ | return; | ||
+ | } | ||
+ | int pivot = a[start]; | ||
+ | int i = start; | ||
+ | int k = end; | ||
+ | while (i < k) { | ||
+ | while (i < k && a[i] < pivot) | ||
+ | i++; | ||
+ | while (i < k && a[k] > pivot) | ||
+ | k--; | ||
+ | if (i < k) { | ||
+ | swap(a, i, k); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | quickSortAuf(a, | ||
+ | quickSortAuf(a, | ||
+ | } | ||
+ | |||
+ | static int quickSelect(int a[], int r) { | ||
+ | int[] tmp = new int[a.length]; | ||
+ | System.arraycopy(a, | ||
+ | return quickSelect(tmp, | ||
+ | |||
+ | } | ||
+ | |||
+ | // sucht im Bereich von s t a r t b i s end ( i n k l u s i v e ) | ||
+ | // nach dem rg r o e s s t e n Element | ||
+ | static int quickSelect(int a[], int start, int end, int r) { | ||
+ | System.out.println(Arrays.toString(a)); | ||
+ | if(r> | ||
+ | int pivot = a[start]; | ||
+ | int i = start; | ||
+ | int k = end; | ||
+ | while (i < k) { | ||
+ | while (i < k && a[i] < pivot) | ||
+ | i++; | ||
+ | while (i < k && a[k] > pivot) | ||
+ | k--; | ||
+ | if (i < k) { | ||
+ | swap(a, i, k); | ||
+ | } | ||
+ | } | ||
+ | quickSelect(a, | ||
+ | quickSelect(a, | ||
+ | } | ||
+ | return a[r]; | ||
+ | |||
+ | } | ||