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

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungss19 [19.06.2020 11:47] – angelegt kat04pruefungen:bachelor:aud:loesungss19 [25.06.2020 15:48] (aktuell) – 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 115: Zeile 121:
  
 ====   Aufgabe 4 (Maximale Teilsummen in Listen mit Sortierung)==== ====   Aufgabe 4 (Maximale Teilsummen in Listen mit Sortierung)====
-=== a,b,c im unteren Code ===+=== a,b,c,d im unteren Code ===
 <code=java> <code=java>
  
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 
 +                                stack.pop();
  }else {  }else {
- for(E e : vor) {+ for(E e : nach) {
  stack.push(e);  stack.push(e);
  }  }
Zeile 294: Zeile 299:
 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 317:
 <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 319: Zeile 324:
 </code> </code>
 ____________________________________________________________________ ____________________________________________________________________
-====   Aufgabe 6 (Backtracking)====+====   Aufgabe 7 (Backtracking)====
 === a) === === a) ===
 <code=java> <code=java>
 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 359:
  // 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