Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws07 [16.02.2013 08:28] – Dawodo | pruefungen:bachelor:aud:loesungws07 [27.05.2014 23:10] – yef | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forum== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 10: | Zeile 10: | ||
* [[https:// | * [[https:// | ||
- | ====Lösungsversuch==== | + | ===== Lösungsversuch |
- | ===Aufgabe 1 - Binärsuche=== | + | ==== Aufgabe 1 - Binärsuche |
**a)** O(n) | **a)** O(n) | ||
Zeile 57: | Zeile 57: | ||
**c)** O(log n) | **c)** O(log n) | ||
- | ===Aufgabe 2 - Graphen=== | + | ==== Aufgabe 2 - Graphen |
**a)** | **a)** | ||
* **Ja** | * **Ja** | ||
Zeile 97: | Zeile 97: | ||
BD, BC, DG, BA, FI, GE, GI, FH | BD, BC, DG, BA, FI, GE, GI, FH | ||
- | ===Aufgabe 3 - Java=== | + | ==== Aufgabe 3 - Java ==== |
**a)** | **a)** | ||
Java Datei zum Ausprobieren: | Java Datei zum Ausprobieren: | ||
Zeile 126: | Zeile 126: | ||
- | === Aufgabe 4 - Arithmetische Ausdrücke - Grammatik === | + | ==== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik |
(nicht mehr Stoff aktueller Semester) | (nicht mehr Stoff aktueller Semester) | ||
- | ===Aufgabe 5 - ADT=== | + | ==== Aufgabe 5 - ADT ==== |
**a)** | **a)** | ||
* number | * number | ||
Zeile 173: | Zeile 173: | ||
</ | </ | ||
- | === Aufgabe 6 - Rucksackproblem === | + | ==== Aufgabe 6 - Rucksackproblem |
**a)** | **a)** | ||
^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ | ^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ | ||
Zeile 223: | Zeile 223: | ||
* **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu | * **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu | ||
- | === Aufgabe 7 - Binäre Bäume === | + | ==== Aufgabe 7 - Binäre Bäume |
**a)** | **a)** | ||
Der Binärbaum muss eine totale Ordnung aufweisen: | Der Binärbaum muss eine totale Ordnung aufweisen: | ||
Zeile 295: | Zeile 295: | ||
* **Nein**, man muss eines Tiefensuche vewenden | * **Nein**, man muss eines Tiefensuche vewenden | ||
- | === Aufgabe 8 - Sortieren === | + | ==== Aufgabe 8 - Sortieren |
**a)** | **a)** | ||
Zeile 435: | Zeile 435: | ||
- | === Aufgabe 9 - Aufwände, O-Kalkül === | + | ==== Aufgabe 9 - Aufwände, O-Kalkül |
**a)** | **a)** | ||
* **O(log n)** | * **O(log n)** | ||
- | * **O(1)**, da k eine Konstante ist | + | * **O(n)**, da k * n/2 |
* **O(n²)** | * **O(n²)** | ||
* **O(n)** | * **O(n)** |