Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Dies ist eine alte Version des Dokuments!


Forendiskussionen

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 < r.height; i++){
          for(int j = 0; j< r.width; 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 )
            max = Math.max(max, height(children[i])+1);
    }
    return max;
}

c)

static int longest(Tentree tree){
    // Basisfall
    if (tree == null) {
      return 0;
    }
 
    int without = 0; 
    int tmp = 0;
    for ( int i = 0; i < 10; ++i )
    {
        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;
            }
        }
    }
    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); 
}