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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesung-miniklausur-14 [14.01.2015 17:36] – xenexipruefungen:bachelor:aud:loesung-miniklausur-14 [20.07.2019 12:02] – Dbadtf_385
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
-  * TODO: Noch keiner. Falls 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);  
 +}
 </code> </code>