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:loesung-miniklausur-14 [14.01.2015 17:36] xenexipruefungen:bachelor:aud:loesung-miniklausur-14 [20.07.2019 15:59] (aktuell) Dbadtf_385
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
-  * TODONoch keinerFalls welche angelegt, hier eintragen! :)+ https://fsi.cs.fau.de/forum/thread/12250-Miniklausur-loesungen
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 7: Zeile 7:
 ==== Aufgabe 1 - Wissensfragen ==== ==== Aufgabe 1 - Wissensfragen ====
  
-TODO: Mit der Korrektur vergleichen/verbessern, falls ausgebessert -> Diesen Kommentar löschen. +**a)** ...erlaubt das Löschen des Listenkopfs in O(1) \\ 
- +...kann zur Umsetzung von Warteschlangen nach dem FIFO-Prinzip verwendet werden \\ \\
-**a)** ...erlaubt das Löschen des Listenkopfs in O(1) \\ \\+
  
 **b)** ...benötigt in der Regel eine Tabelle zur Speicherung von Zwischenergebnissen\\ **b)** ...benötigt in der Regel eine Tabelle zur Speicherung von Zwischenergebnissen\\
Zeile 41: Zeile 40:
 **b)** **b)**
 <code java> <code java>
-static void toggleRectangle(boolean[][] used, int row, int column, Rectangle r){ + static void toggleRectangle(boolean[][] used, int row, int column, Rectangle r){ 
-    for(int i = 0; i < used.length; i++){ +      for(int i = 0; i < r.height; i++){ 
-        for(int j = 0; j < used[i].length; j++){ +          for(int j = 0; j< r.width; j++){ 
-            used[row + i][column + j] = !used[row + i][column + j];  +              used[row + i][column + j] = !used[row + i][column + j];  
-        }+           } 
 +       }
     }     }
-} 
 </code> </code>
  
Zeile 110: Zeile 109:
  
 **a)** **a)**
-Minimal: O( ceil( log( 9n +1)/log(10) -1) ) +Minimal: O( ceil( log( 9n +1)/log(10) -1) ) = O( log(n) ) 
-Maximal: O( n-1 )+Maximal: O( n-1 ) = O( n )
  
 **b)** **b)**
Zeile 122: Zeile 121:
     {     {
         if( children[i] != null )         if( children[i] != null )
-            tmp = height( children[i] )+            max Math.max(max, height(children[i])+1);
-        if( max < tmp max = tmp;+
     }     }
-    if( tmp == -1 ) return 0; +    return max;
-    else return max + 1;+
 } }
 </code> </code>
Zeile 133: Zeile 130:
 <code java> <code java>
 static int longest(Tentree tree){ static int longest(Tentree tree){
-  +    // Basisfall 
 +    if (tree == null) { 
 +      return 0; 
 +    }
  
     int without = 0;      int without = 0; 
     int tmp = 0;     int tmp = 0;
-    for( int i = 0; i < 10; ++i )+    for ( int i = 0; i < 10; ++i )
     {     {
-        if( children[i] != null ) +        tmp = longest( children[i] );
-            tmp = longest( children[i] );+
         if( without < tmp )         if( without < tmp )
             without = tmp;             without = tmp;
Zeile 156: Zeile 155:
             tmp = height( children[i] );             tmp = height( children[i] );
             if( with < tmp ) {             if( with < tmp ) {
-                n = with+                n = with;
                 with = tmp;                 with = tmp;
             } else if( n < tmp ) {             } else if( n < tmp ) {
Zeile 163: Zeile 162:
         }         }
     }     }
-    with += n + 2; +    if (n != 0) { // Mindestens zwei Pfade gefunden 
-return Math.max(without, with); +      with += n + 2; 
 +    } else { 
 +      with = 0; // zB nur ein Pfad => auf 0 zurücksetzen 
 +    } 
 +    return Math.max(without, with);  
 +
 + 
 +/*Anmerkung anderer Student: 
 +Ich bin mir nicht wirklich sicher, ob der obige Code korrekt alle Corner Cases abgedeckt. Wuerde man z.B. die Methode auf einem TenTree ausfuehren, der nur aus Wurzel und einer einzigen Kante in children[0] besteht, dann gibt diese Methode 0 zurueck, das richtige Ergebnis waere aber (falls ich die Aufgabe richtig verstanden habe) 1, da eine Kante hierbei die laengste Distanz im Baum darstellen wuerde. 
 + 
 +Anbei meine Loesung: */ 
 +static int longest (TenTree tree) { 
 +    //Basisfall 
 +    if(tree == null) return 0;  
 +    //Fall1: Wurzel ist *nicht* Teil des laengsten Pfads 
 +    int without = 0; 
 +    for(int i = 0; i<tree.children.length;i++) { 
 +        if(tree.children[i]!= null) { 
 +     without = Math.max(without,  longest(tree.children[i])); 
 +
 +    } 
 +  
 +    //Fall 2: Wurzel *ist* Teil des laengsten Pfads 
 +    int with = 0; 
 +    int tmpmax = 0; 
 +    int cnt = 0; 
 +    for(int i = 0; i<tree.children.length;i++) { 
 +        if(tree.children[i]!= null) { 
 +     cnt ++; 
 +     for(int j = i+1; j< tree.children.length;j++) { 
 +         if(tree.children[j] != null) { 
 +         // 2. Pfad gefunden: Pruefe ob die Distanz zwischen den Blaettern der beiden Pfade maximal ist 
 +             tmpmax = Math.max(tmpmax, height(tree.children[i]) + height(tree.children[j])); 
 +         } 
 +            } 
 +       } 
 +    } 
 +    //es wurden min. 2 Pfade gefunden: Zum laengsten Pfad muessen jetzt noch die zwei Kanten addiert werden, 
 +    //welche die Verbindung zur aktuellen Wurzel darstellen 
 +    if(cnt>1) { 
 +        with = tmpmax +2; 
 +    } else { 
 +    // es gab nur 0-1 Pfade von dieser Wurzel aus. Die Laenge ist demnach 0 oder 1 
 +        with = cnt;  
 +    } 
 +    return Math.max(with, without); 
 +
 </code> </code>