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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung
Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungss11 [28.03.2016 21:03] tomabrafixpruefungen:bachelor:aud:loesungss11 [20.06.2020 12:12] (aktuell) BierBaron69
Zeile 37: Zeile 37:
 Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\
 Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht. Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht.
 +
 +Anmerkung:
 +Es geht ja um den worst case. Ich denke, man kann ein Szenario konstruieren, in dem die Laufzeit O(n) beträgt. Wenn z.B. die gesamte Reihung nur aus diesem Element besteht, muss man nach Auffinden des ersten Eintrags, die gesamte Liste durchgehen, um alle Vorkommen zu finden und zu zählen.
  
 **i)** 2. Antwort ist richtig **i)** 2. Antwort ist richtig
Zeile 67: Zeile 70:
 } }
 </code> </code>
 +
 +?? oder vielleicht so: ??
 +\\
 +<code java>
 +boolean isSearchTree() {
 +    if (this.left == null && this.right == null) {
 +        return true;
 +    } else if (this.left == null) {
 +        if (this.right.getMin() > this.data) {
 +            return this.right.isSearchTree();
 +        }
 +        return false;
 +    } else if (this.right == null) {
 +        if (this.left.getMax() < this.data) {
 +            return this.left.isSearchTree();
 +        }
 +        return false;
 +    } else  {
 +        if (this.left.getMax() < this.data && this.right.getMin() > this.data) {
 +            return this.left.isSearchTree() && this.right.isSearchTree();
 +        }
 +        return false;
 +    }
 +}
 +</code>
 +
 +Zum Testen: https://pastebin.com/T6DbJ4iU
 +
  
 **c)** **c)**
Zeile 196: Zeile 227:
  }     }   
 }    }   
 +</code>
 +alternativ:
 +\\
 +<code java>
 +void resize(int h) {
 + urls.ensureCapacity(h);
 + ips.ensureCapacity(h);
 +}
 </code> </code>
  
Zeile 246: Zeile 285:
  
 <code java> <code java>
-public static long getPrimeDPHelper(int n, long primes[]) { +public static long getPrimeDPHelper(int n, long primes[]) throws ArrayIndexOutOfBoundsException  
- if(n <= 0)+ // ArrayIndexOutOfBoundsException detection (falls getPrimeDPHelper(..) falsch aufgerufen wird) 
 + if (n >= primes.length) { 
 + throw new ArrayIndexOutOfBoundsException("Uebergebenes Array zum Speichern der berechneten Primzahlen ist zu klein!"); 
 +
 +         
 +        if (n <= 0)
  return 2;  return 2;
  
  // Geforderte Primzahl wurde noch nicht berechnet  // Geforderte Primzahl wurde noch nicht berechnet
- if(primes[n] == 0) {+ if (primes[n] == 0) {
  // Berechne den vorherige Primzahl  // Berechne den vorherige Primzahl
  long p = getPrimeDPHelper(n - 1, primes);  long p = getPrimeDPHelper(n - 1, primes);
Zeile 282: Zeile 326:
 | 0 | 11 | 16 | 3 | 7 | 7 | [17] | | 0 | 11 | 16 | 3 | 7 | 7 | [17] |
 | 0 | 11 | 16 | 3 | 7 | 7 | 17 | | 0 | 11 | 16 | 3 | 7 | 7 | 17 |
 +
 +alternativ:
 +
 +^ Kara ^ A ^ B ^ C ^D ^E ^ Klee ^
 +| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
 +| | ∞ | 18<sub>Klara</sub> | [3<sub>Klara</sub>] | 7<sub>Klara</sub> | 9<sub>Klara</sub> | ∞ |
 +| | 13<sub>C</sub> | 18<sub>Klara</sub> | | 7<sub>Klara</sub> | [7<sub>C</sub>] | ∞ |
 +| | 11<sub>E</sub> | 18<sub>Klara</sub> | | [7<sub>Klara</sub>] | | ∞ |
 +| | [11<sub>E</sub>] | 18<sub>Klara</sub> | | | | 19<sub>D</sub> |
 +| | | [16<sub>A</sub>] | | | | 17<sub>A</sub> |
 +| | | | | | | [17<sub>A</sub>] |
 +| | | | | | | |
 +
 +Indizes rückwärts (von unten nach oben) durchgehen : [17<sub>A</sub>] -> [11<sub>E</sub>] -> [7<sub>C</sub>] -> [3<sub>Klara</sub>] -> [0]
 +
 +=> umdrehen: Klara -> C -> E -> A -> Klee
  
 **b)** **b)**
Zeile 420: Zeile 480:
 Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein. Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein.
 Die Invariante ist somit gültig. Die Invariante ist somit gültig.
 +</code>
 +
 +einfacher:
 +<code>
 +Zu zeigen: (I ∧ b) => wp(B, I)
 +
 +I: p = 2^(n - k - 1) ∧ k ≥ 0
 +b: (k > 0)
 +B: "p *= 2; k--" <=> "p = p * 2; k = k - 1;"
 +
 +(I ∧ b):
 +    p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0
 +    <=> p = 2^(n - k - 1) ∧ k > 0      (weil: (k ≥ 0 ∧ k > 0) <=> (k > 0))
 +
 +wp(B, I):
 +    wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - (k - 1) - 1) ∧ k - 1 ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - k) ∧ k ≥ 1)
 +    <=> wp(" ", p * 2 = 2^(n - k) ∧ k ≥ 1)
 +    <=> p * 2 = 2^(n - k) ∧ k ≥ 1
 +    <=> p = (1/2) * 2^(n - k) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * (1/2) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * 2^(-1) ∧ k ≥ 1      (weil: (1/2) = 2^(-1))
 +    <=> p = 2^(n - k - 1) ∧ k ≥ 1      (weil: 2^(n - k) * 2^(-1) = 2^(n - k - 1))
 +
 +(I ∧ b) => wp(B, I):
 +    p = (2^(n - k - 1) ∧ k > 0)   =>   (p = 2^(n - k - 1) ∧ k ≥ 1)
 +      -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp "long" und damit ganzzahlig (..., -2, -1, 0, 1, 2, ...)
 +
 +fertig
 </code> </code>