Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesung-miniklausur-14 [13.01.2015 21:15] – angelegt Alicen | pruefungen:bachelor:aud:loesung-miniklausur-14 [24.03.2015 17:45] – xenexi | ||
---|---|---|---|
Zeile 7: | Zeile 7: | ||
==== Aufgabe 1 - Wissensfragen ==== | ==== Aufgabe 1 - Wissensfragen ==== | ||
- | TODO: Mit der Korrektur vergleichen/ | + | **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 52: | Zeile 51: | ||
**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; | ||
+ | } | ||
+ | | ||
+ | } | ||
</ | </ | ||
**d)** | **d)** | ||
<code java > | <code java > | ||
- | TODO | + | static boolean solveHelper( boolean[][] used, LinkedList< |
+ | { | ||
+ | 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; | ||
+ | { | ||
+ | for( int column = 0; column < used[row].length; | ||
+ | { | ||
+ | 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; | ||
+ | } | ||
</ | </ | ||
==== 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 ) |
**b)** | **b)** | ||
<code java> | <code java> | ||
static int height(TenTree tree){ | static int height(TenTree tree){ | ||
- | | + | |
+ | |||
+ | int max = 0, tmp = -1; | ||
+ | for( int i = 0; i < 10; ++i ) | ||
+ | { | ||
+ | if( children[i] != null ) | ||
+ | tmp = height( children[i] ); | ||
+ | if( max < tmp ) max = tmp; | ||
+ | } | ||
+ | if( tmp == -1 ) return 0; | ||
+ | else return max + 1; | ||
} | } | ||
</ | </ | ||
Zeile 82: | Zeile 132: | ||
<code java> | <code java> | ||
static int longest(Tentree tree){ | static int longest(Tentree tree){ | ||
+ | | ||
- | TODO | + | int without = 0; |
+ | int tmp = 0; | ||
+ | for( int i = 0; i < 10; ++i ) | ||
+ | { | ||
+ | if( children[i] != null ) | ||
+ | tmp = longest( children[i] ); | ||
+ | if( without < tmp ) | ||
+ | without = tmp; | ||
+ | } | ||
+ | |||
- | int without = 0; | + | |
- | + | ||
- | TODO | + | |
- | + | ||
- | 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; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | with += n + 2; | ||
return Math.max(without, | return Math.max(without, | ||
</ | </ |