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

--- pruefungen:bachelor:aud:loesung-miniklausur-14 [13.01.2015 21:15] – angelegt Alicen
+++ pruefungen:bachelor:aud:loesung-miniklausur-14 [20.07.2019 15:59] (aktuell) – Dbadtf_385
@@ Zeile 1: / Zeile 1: @@
 ===== Forendiskussionen =====
-  * TODO: Noch keiner. Falls welche angelegt, hier eintragen! :)
+ https://fsi.cs.fau.de/forum/thread/12250-Miniklausur-loesungen
 ===== Lösungsversuch =====
@@ Zeile 7: / Zeile 7: @@
 ==== 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\\
@@ Zeile 41: / Zeile 40: @@
 **b)**
 <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>
 **c)**
 <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>
 **d)**
 <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>
 ==== Aufgabe 3 (Streutabellen) ====
-TODO
+, 0, 4, 3, 4, 5, 3, 7
 ==== Aufgabe 4 (Bäume) ====
-TODO
 **a)**
-Minimal: O()
+Minimal: O( ceil( log( 9n +1)/log(10) -1) ) = O( log(n) )
-Maximal: O()
+Maximal: O( n-1 ) = O( n )
 **b)**
 <code java>
 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>
@@ Zeile 82: / Zeile 130: @@
 <code java>
 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;
+    for( int i = 0; i < 10; ++i )
+    {
+        if( children[i] != null )
+        {
+            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);
+}
-int with = 0;
+/*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.
-TODO
+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);
+}
-return Math.max(without, with);
 </code>