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:12] – 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 62: Zeile 61:
     {     {
         for( int j = 0; j < r.width; ++j)         for( int j = 0; j < r.width; ++j)
-            if( used[ row + i ][ column + j ] ) return false;+            if( used[ row + i ][ column + j ] )  
 +                return false;
      }      }
      return true;      return true;
Zeile 70: Zeile 70:
 **d)** **d)**
 <code java > <code java >
-TODO+static boolean solveHelper( boolean[][] used, LinkedList< Rectangle > rects) 
 +{ 
 +    if( isSolved( used ) ) 
 +        return true; 
 +    else if( rects.isEmpty() ) 
 +        return false; 
 +         
 +    Rectangle r = rects.pollFirst(); 
 +    if( solveHelper( used, rects ) ) 
 +        return true; 
 +    rects.addFirst( r ); 
 +     
 +    for( int row = 0; row < used.length; ++row ) 
 +    { 
 +        for( int column = 0; column < used[row].length; ++column ) 
 +        { 
 +            Rectangle r = rects.pollFirst(); 
 +            if( fits( used, row, column, r ) 
 +            { 
 +                toggleRectangle( used, row, column, r ); 
 +                if( solveHelper( used, rects) ) 
 +                    return true; 
 +                toggleRectangle( used, row, column, r ); 
 +            } 
 +            rects.addFirst( r ); 
 +        } 
 +    } 
 +    return false; 
 +}
 </code> </code>
  
 ==== Aufgabe 3 (Streutabellen) ==== ==== Aufgabe 3 (Streutabellen) ====
  
-TODO+2, 0, 4, 3, 4, 5, 3, 7
  
 ==== Aufgabe 4 (Bäume) ==== ==== Aufgabe 4 (Bäume) ====
  
-TODO 
  
 **a)** **a)**
-Minimal: O() +Minimal: O( ceil( log( 9n +1)/log(10) -1) ) = O( log(n) ) 
-Maximal: O()+Maximal: O( n-1 ) = O( n )
  
 **b)** **b)**
 <code java> <code java>
 static int height(TenTree tree){ static int height(TenTree tree){
-    TODO+    if( tree == null ) throw new NullPointerException(""); 
 +     
 +    int max = 0, tmp = -1; 
 +    for( int i = 0; i < 10; ++i ) 
 +    { 
 +        if( children[i] != null ) 
 +            max = Math.max(max, height(children[i])+1); 
 +    } 
 +    return max;
 } }
 </code> </code>
Zeile 95: Zeile 130:
 <code java> <code java>
 static int longest(Tentree tree){ static int longest(Tentree tree){
 +    // Basisfall
 +    if (tree == null) {
 +      return 0;
 +    }
  
-TODO+    int without = 0;  
 +    int tmp = 0; 
 +    for ( int i = 0; i < 10; ++i ) 
 +    { 
 +        tmp = longest( children[i] ); 
 +        if( without < tmp ) 
 +            without = tmp; 
 +     } 
 +   
  
-int without = 0; +    int with = 0; 
  
-TODO +    int n = 0; 
- +    tmp = 0; 
-int with = 0;  +    for( int i = 0; i < 10; ++i ) 
- +    { 
-TODO +        if( children[i] != null ) 
- +        { 
-return Math.max(without, with); +            tmp = height( children[i] ); 
 +            if( with < tmp ) { 
 +                n = with; 
 +                with = tmp; 
 +            } else if( n < tmp ) { 
 +                n = tmp; 
 +            } 
 +        } 
 +    } 
 +    if (n != 0) { // Mindestens zwei Pfade gefunden 
 +      with += n + 2; 
 +    } else { 
 +      with = 0; // zB nur ein Pfad => auf 0 zurücksetzen 
 +    } 
 +    return Math.max(without, with);  
 +}
 </code> </code>