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

Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesung-miniklausur-14 [13.01.2015 21:15] – angelegt Alicenpruefungen: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>
  
 **c)** **c)**
 <code java> <code java>
-TODO+static boolean fits( boolean[][] used, int row, int column, Rectangle r ) 
 +{ 
 +    assert ( row >= 0 && column >= 0 ); 
 +    if( used.length - row - r.height < 0 ||  
 +        ( used.length > 0 && used[0].length - column - r.width < 0 ) ) 
 +        return false; 
 +         
 +    for( int i = 0; i < r.height; ++i ) 
 +    { 
 +        for( int j = 0; j < r.width; ++j) 
 +            if( used[ row + i ][ column + j ] )  
 +                return false; 
 +     } 
 +     return true; 
 +}
 </code> </code>
  
 **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 82: 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>