Probeklausur Datenstrukturen und Algorithmen SS06

Aus Infostudium Wiki

Alle Angaben ohne Gewähr. Fragen, Anregungen, Verbesserungen? Registrieren und schreiben!

Basiert auf den Aufgaben der Probleklausur SS06.

Inhaltsverzeichnis 1 Aufgabe 1 1.1 a) 1.2 b) 1.3 c) 1.4 d) 1.5 e) 2 Aufgabe 2 2.1 a) 2.2 b) 2.3 c) 2.4 d) 3 Aufgabe 3 4 Aufgabe 4 4.1 a) 4.2 b) 4.3 c) 5 Aufgabe 5 5.1 a) MergeSort 5.2 b) HeapSort 5.3 c) InsertionSort 6 Aufgabe 6 6.1 a) 6.2 b) 6.3 c) 6.4 d) 7 Aufgabe 7 7.1 a) 7.2 b) 7.3 c) 8 Aufgabe 8 - Rucksackproblem 8.1 a) 8.2 b) 8.3 c) 8.4 d) 9 Aufgabe 9 - Das Trolldorf 10 Aufgabe 10

Aufgabe 1

a)

isse korrekt

Aussage:

Beweis:

Sei

b)

Siehe Gegenbeispiel fuer 1c. .

c)

Die Aussage ist falsch. Gegenbeispiel:

f(n) = n falls n gerade, 1 sonst.

g(n) = n falls n ungerade, 1 sonst.

aber O(f) = O(1) = O(g).

d)

nöööö

Begründung: Sobald f(n) eine höhere Komplexität g(n) besitzt, passt es nicht mehr.

Beispiel: f(n) = x⁴ und g(n) = x². (Also nicht immer zumindestens)

e)

ja

1.

2.

Wähle

Aufgabe 2

a)

T(n) = 4T(n − 2) + 3

b)

O(n²)

c)

Korrigierte Aufgabenstellung:

, daraus folgt: 2. Fall

d)

a = 2,b = 2,γ = 2

= > O(n²)

Aufgabe 3

Visualisierungsansatz:

         links                                       rechts
-----------|--------------------------------------------|------------------
                             breite

i =        |-----------------------|
j =                     |---------------------|
k =                                |--------------------|

Man kann erkennen, dass die Methode 3 mal aufgerufen wird und die Breite jedesmal durch 2 dividiert wird.

Da angegeben ist, dass die Operationen +,-,*,/ konstant sind ( O(1) ) muss man nur noch in der Methode die Schleife berücksichtigen. Diese hat immer die Größe der Breite der abzuarbeitende Strecke. Die Breite wird dann als n bezeichnet.

Das führt zu folgender Gleichung:

Nun das Master-Theorem anwenden:

a = 3
b = 2
d(n) = n
γ = 1

3 > 21

Anmerkung: Auf dem Blatt stand, dass Operationen +,-,*,/ konstant sind ( O(1) ). Keine Ahnung, ob es dann nicht heißen müsste.

Aufgabe 4

a)

Das geschlossene Hashing verzichtet auf Listen als Array-Item. Mehrfache Einträge werden mit Hilfe des Sondierungsverfahrens an eine andere freie Speicherstelle im Hash-Array verschoben.

Merkhilfe: Das offene Hashing ist in die 2. Dimension erweiterbar. Das geschlossene ist nur ein eindimensionaliges Array.

b)

Position	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Schlüssel k	90	16	61	12	4	80	6						87	43	57

Zu den Sondierungsschritten gehören nicht nur die linearen Sondierungsschritte, die ein Element auf den nächsten freien Platz verschiebt, sondern auch die Schritte, die ein Element an einen freien Platz setzt und überprüft, ob ein Element dort schon vorhanden ist.

Anzahl Sondierungsschritte: 20

c)

15 ist keine Primzahl.

Begründung:

Aufgabe 5

a) MergeSort

Sortieren nach dem Divide-and-conquer-Prinzip. Siehe MergeSort.

6	16	61	87	90	4	43	57
Die Menge immer in zwei Hälften teilen, bis nur noch Einzelelemente übrig sind
Nun die ehemaligen Gruppen sortiert wieder zusammenfügen.
6	16	61	87	4	90	43	57
6	16	61	87	4	43	57	90
4	6	16	43	57	61	87	90

b) HeapSort

Alles zu HeapSort unter http://de.wikipedia.org/wiki/Heapsort

1. Array in einem Max-Heap überführen. Die Liste wird so behandelt, als sei sie die Ausgabe eines Level-Order-Durchlaufs. Am besten man schreibt die Liste in Form eines Baumes auf und sortiert anschließend die Knoten.

06 16 61 87 90 04 43 57

       6
     /   \
   16     61
  /  \   /  \
 87  90  4   43
 /
57

In Heap überführt: 90,87,61,57,43,04,16,06

      90
     /   \
   87     61
  /  \   /  \
 57  43  4   16
 /
6

2. Sortieren

06 87 61 57 43 04 16|90  Die 6 versickern
87 61 57 43 04 16 06|90
61 57 43 04 16 06|87 90

..........

x. 04,06,16,43,57,61,87,90

---

Version aus http://whiskey.dyndns.org/wiki/index.php/DaStru_Probeklausur_SS_2006

H = Zahlenfolge nachdem Heap-Eigenschaft hergestellt ist.

T = Zahlenfolge nachdem getauscht wurde.

	6	16	61	87	90	4	43	57
H 	90	87	61	57	16	4	43	6
T 	6	87	61	57	16	4	43	90
H 	87	57	61	6	16	4	43
T 	43	57	61	6	16	4	87	90
H 	61	57	43	6	16	4
T 	4	57	43	6	16	61	87	90
H 	57	16	43	6	4
T 	4	16	43	6	57	61	87	90
H 	43	16	4	6
T 	6	16	4	43	57	61	87	90
H 	16	6	4
T 	4	6	16	43	57	61	87	90
H 	6	4
T 	4	6	16	43	57	61	87	90

c) InsertionSort

Siehe unter InsertionSort

unsortierte Eingabemenge: [ 6 16 61 87 90 4 43 57 ]

Rechts neben dem | die Eingabemenge. Links vor dem | die Ausgabemenge.

Das erste Element rechts neben dem | sortiert in die rechte Ausgabeliste kopieren.

[ | 6 16 61 87 90 4 43 57 ]

[ 6 | 16 61 87 90 4 43 57 ]

[ 6 16 | 61 87 90 4 43 57 ]

[ 6 16 61 | 87 90 4 43 57 ]

[ 6 16 61 87 | 90 4 43 57 ]

[ 6 16 61 87 90 | 4 43 57 ]

[ 4 6 16 61 87 90 | 43 57 ]

[ 4 6 16 43 61 87 90 | 57 ]

[ 4 6 16 43 57 61 87 90 | ]

Aufgabe 6

a)

• Die Dimension der jeweiligen Folgen bestimmen
• Da die Dimension jeweils 11 beträgt und es sich um linksvollständige Binärbäume handelt, muss man erst folgendes berechnen:

Ebene 1: 1 Knoten

Ebene 2: 2 Knoten

Ebene 3: 4 Knoten

Ebene 4: 8 Knoten (und hier wären wir schon mit 15 Knoten über der Dimension, also passt der Kram hinein)

Also haben wir 4 Ebenen. Folglich sehen die Bäume, die von links aufgefüllt werden, wie folgt aus:

(i)

            (61)
          /       \
      (12)          (6)
     /     \       /   \
  (87)     (80)  (16)  (57)
  /  \     /  \
(5) (43) (90) (4)

(ii)

             (61)
          /         \
      (12)          (87)   
    /     \         /   \
  (5)     (43)    (80)  (90)
 /  \     /  \
(4) (6) (16) (57)

b)

zu (i):

Kein Sortierungsalgorithmus erkennbar.

zu (ii):

Der links Nachfolger-Knoten ist vom Wert her kleiner als der Vorgängerknoten und der rechte Nachfolger-Knoten ist größer.

c)

Es handelt sich nicht im Max-Heaps.

Die Bedingung für Max-Heaps: Der Wert des Vorgänger-Knotens ist größer als die jeweiligen Werte der Nachfolger-Knoten.

Im ersten Baum ist diese Bedingung offensichtlich in den Knoten "12","6" und "80" verletzt.

Im zweiten Baum ist diese Bedingung in den Knoten "61","87","5","43" verletzt.

d)

Einem Breitendurchlauf (Level-Order-Durchlauf)

Aufgabe 7

a)

Grafik aus http://whiskey.dyndns.org/wiki/images/3/3c/Graph1.png

b)

c)

• Spanisch(3)Französisch(4)
• Spanisch(3)Englisch(2)Französisch(4)
• Spanisch(3)Niederländisch(5)
• Spanisch(3)Englisch(2)Niederländisch(5)
• Französisch(4)Niederländisch(5)
• Französisch(4)Deutsch(1)Niederländisch(5)

Aufgabe 8 - Rucksackproblem

a)

Gesuchte Problemstellung: Es handelt sich um das 0/1 Rucksackproblem (Hinweis: "...wollen Sie kein Geschenk doppelt vergeben.")

Modifizierung: Anstatt teure Geschenke, will man möglichst sparsam aus der Angelegenheit heraus kommen. Also ansstatt max wird im Algorithmus min verwendet.

b)

Gesuchte Rekursionsformel:

c)

Graph folgt noch

(Dieser ist nach der Übungsblatt-Aufgabe 12.2 (b) erstellt worden. Lösung kann man auf der Vorlesungsseite herunterladen.)

d)

Folgende Geschenke-Kombinationen sind möglich:

Faltschirm,Hemd = 17€

Heilwasser, Hemd, Tageszeitung = 17€

Aufgabe 9 - Das Trolldorf

Habe das Programm auf die Schnelle geschrieben. Muss noch überprüft werden.

Anmerkung: Der Graph hat so wie er dargestellt ist zu wenig Relationen, man kann/müsste von jedem Troll zu jedem eine Relation herstellen. Dies dürfte aber nichts an dem Programm ändern.

public static boolean walker(House house) {

  // das erste haus färben
  if (house.color == null) house.color = Color.red;
  
  for (int i =0; i < house.relationships.length; i++) {
    Relationship relationship = house.relationships[i];
    House neighbour = relationship.neighbour;
   
    if (neighbour.color == null) {
      // nachbarhaus einfären:
      // wenn freund, dann in der selben farbe färben
      if (relationship.friend) {
        // Freund
        neighbour.color = house.color;
      } else {
        // Feind
        if (house.color == Color.gray) neighbour.color = Color.red;
        if (house.color != Color.gray) neighbour.color = Color.gray;
      }
      // Nur wenn eine Nachbarhaus einen Fehler meldet, abbrechen
      if (!walker(neighbour)) return false;
    } else if (house.color == neighbour.color && !relationship.friend) {
      // verfeindet
      System.out.println("Fehler!");
      return false;
    } else if (house.color != neighbour.color && relationship.friend) {
      // Da ist was schiefgelaufen. Trolle sind Freunde, haben aber verschiedene Farben
      System.out.println("Fehler!");
      return false;
    } else {
      // Nachbarhaus hat schon eine Färbung, die ok ist -> Haus ignorieren
    }
  }
  // Keine Konflikte oder dieses Haus hat keine weiteren Nachbarn
  return true;
}

import java.awt.Color;

public class House {
  
  public Relationship[] relationships = new Relationship[0];
 
  public Color color = null;

  public House() {
  }

}

public class Relationship {

  public House neighbour;

  public boolean friend = true;

  public Relationship() {
  }
 
}

Aufgabe 10

Hier ein Lösungsversuch:

x = Die Buchstaben, die nur das erste Wort hat
y = Die Buchstaben, die beide gemeinsam haben (Bei LCS betrifft das nur die korrekte Sequenz.)
z = Die Buchstaben, die nur das zweite Wort hat

I = x + y
J = z + y

LCS = y

SCS = x + y + z

SCS = I + J - LCS (diese nun durch x,y und z ersetzen)

x + y + z = x + y + z + y - y
x + y + z = x + y + z => korrekt

Würde mich interessieren, ob das immer korrekt ist. Vielleicht müsste man das noch ausbauen.