FSI-Zimmer: geschlossen
Sie befinden sich hier: Termine » 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 gezeigt.
| Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
pruefungen:bachelor:aud:loesungss19 [19.06.2020 13:47] kat04 angelegt |
pruefungen:bachelor:aud:loesungss19 [25.06.2020 17: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 | ||