Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Dies ist eine alte Version des Dokuments!


Forendiskussionen

  • TODO: Noch keiner. Falls welche angelegt, hier eintragen! :)

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) …erlaubt das Löschen des Listenkopfs in O(1)
…kann zur Umsetzung von Warteschlangen nach dem FIFO-Prinzip verwendet werden

b) …benötigt in der Regel eine Tabelle zur Speicherung von Zwischenergebnissen
…kann den Laufzeitaufwand beim Rucksackproblem signifikant reduzieren.

c) …final sein.
…aus Alpha geerbte Instanzmethoden unter Umständen überschreiben.

Aufgabe 2 (Gitter und Rechtecke)

class Rectangle {int width, height; }

a)

class Cover{
    static boolean isSolved(boolean[][] used){
        for(int i = 0; i < used.length; i++){
            for(int j = 0; j < used[i].length; j++){
                if(!used[i][j]){
                    return false; 
                }
            }
        }
        return true; 
    }
}

b)

static void toggleRectangle(boolean[][] used, int row, int column, Rectangle r){
    for(int i = 0; i < used.length; i++){
        for(int j = 0; j < used[i].length; j++){
            used[row + i][column + j] = !used[row + i][column + j]; 
        }
    }
}

c)

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;
}

d)

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;
}

Aufgabe 3 (Streutabellen)

2, 0, 4, 3, 4, 5, 3, 7

Aufgabe 4 (Bäume)

a) Minimal: O( ceil( log( 9n +1)/log(10) -1) ) = O( log(n) ) Maximal: O( n-1 ) = O( n )

b)

static int height(TenTree tree){
    if( tree == null ) throw new NullPointerException("");
 
    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;
}

c)

static int longest(Tentree tree){
 
 
    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 with = 0; 
 
    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, with);