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

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); 
}
 
/*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.
 
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);
}