Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch SS 19   (Ü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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss19 [19.06.2020 11:52] – kat04pruefungen:bachelor:aud:loesungss19 [25.06.2020 08:49] – kat04
Zeile 37: Zeile 37:
   - Falsch, man muss ja trotzdem die Knoten mit in Betracht ziehen    - Falsch, man muss ja trotzdem die Knoten mit in Betracht ziehen 
   - Falsch, Dijkstra bestimmt nicht den minimalen Spannbaum, sondern die küzesten Wege   - Falsch, Dijkstra bestimmt nicht den minimalen Spannbaum, sondern die küzesten Wege
 +
 +=== g) ===
 +  - Richtig, Skript 15, Seite 15
 +  - Richtig
 +  - Falsch, immer O(n²)
 +  - Falsch, Definition für zerteilen / divisiv 
  
 ====   Aufgabe 2 (Dynamische Programmierung)==== ====   Aufgabe 2 (Dynamische Programmierung)====
Zeile 232: Zeile 238:
  }  }
  
- } + }//visitedAbfrage schließt 
- } + }//while schießt 
- if(visited.size()< allNodes.size()) { +             if(visited.size()!=allNodes.size()){ 
- // theoretisch müsste diese Abfrage reichen  +                  return false; // abfrage ist wichtig, weil es kann sein, dass zwei Knoten gegenseitig auf sich zeigen, damit haben sie beide Vor und Nachfolger aber die anderen Knoten werden nicht erreicht  
- //wenn ich nicht von meinem aktuellen knoten alle erreichen kann dann falsch + }  
- return false; + }//forschleife schließt
- } +
- }+
  return true;  return true;
  }  }
Zeile 265: Zeile 269:
  stack.add(node);  stack.add(node);
  while(!stack.isEmpty()) {  while(!stack.isEmpty()) {
- E akt = stack.pop();  + E akt = stack.peek(); //nicht rauslöschen!!!   
- List<E> vor = succs(akt); + List<E> nach = succs(akt); 
- if(vor.isEmpty()) {+ if(nach.isEmpty()) {
  //keine nachfolger = Blattknoten -> zu Euler hinzu  //keine nachfolger = Blattknoten -> zu Euler hinzu
- euler.add(akt);+ euler.addFirst(akt); //vorne anfügen
  }else {  }else {
- for(E e : vor) {+ for(E e : nach) {
  stack.push(e);  stack.push(e);
  }  }
Zeile 294: Zeile 298:
 ContainsAll(s1,Empty) = true  ContainsAll(s1,Empty) = true 
 containsAll(Empty,s2) = false  containsAll(Empty,s2) = false 
-containsAll(s1,Add(s2,e)) = ContainsAll(s1,Add(s2,e))+containsAll(s1,Add(s2,e)) = ContainsAll(s1,s2) && contains (s1,e)
 </code> </code>
  
Zeile 312: Zeile 316:
 <code=java> <code=java>
 sCH(Create, u, accu) = ... sCH(Create, u, accu) = ...
-... accu falls containsAll (accu, u)+... accu falls containsAll (setUnion(accu), u)
 ... create sonst ... create sonst
  
Zeile 324: Zeile 328:
 String getVerticalPrefix(int r, int c) { String getVerticalPrefix(int r, int c) {
   
- if(r<0 || g[r][c]=='#' || r> g.length || c > g[r].length) {+ if(r<0 || g[r][c]=='#' || r>= g.length || c >= g[r].length) {
  return "";  return "";
  }else {  }else {
Zeile 354: Zeile 358:
  // traverse g row by row and left to right  // traverse g row by row and left to right
  if(wsH.isEmpty()) {  if(wsH.isEmpty()) {
- // wenn ich alle horizontele Wörter platzieren konnte bin ich fertig 
- // die vertikalen werden unten schon geprueft 
  return true;   return true; 
  } else if(c>g[r].length) { // ende der Zeile  } else if(c>g[r].length) { // ende der Zeile