Alle Aufgaben zum Nachrechnen
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Unsere Klausur
Für alle, die nicht warten wollen, bis sie die Klausur runterladen können hab ich heute mal die Angaben abgeschrieben. Hier sind sie: (das blaue sind meine Antworten)
1. Aufgabe (15 Punkte)
a) formale Definition der Chomsky-Grammatik; zusätzliche Bedingung für kontextfreie C.-Grammatik
bla bla, siehe Skript
b) konstruiere kontextfreie C.-Grammatik für Sprache L(G) = { a[sup]n[/sup]c[sup]m+2[/sup]b[sup]3n[/sup] | n ≥ 0, m ≥ 0 }
G = ( {a, b, c}, {S, A}, {(S, aSbbb), (S, cA), (A, cA), (A, c)}, S)
c) Welche Sprache beschreibt die Grammatik:
T = {a, b, c}
N = {S, A}
P = {(S, aSaaa), (S, cA), (A, cAb), (A, b)}
L(G) = { a[sup]n[/sup]c[sup]m[/sup]b[sup]m[/sup]a[sup]2n[/sup] | n ≥ 0, m ≥ 1 }
2. Aufgabe (15 Punkte)
a) formale Definition eines Graphen
endliche Menge von Knoten, die durch Kanten (gerichtet oder ungerichtet) verbunden sein können
b) Nenne 2 Möglichkeiten, einen Graphen zu repräsentieren
Adjazenzmatrix, Adjazenzliste
c) i) beide anwenden auf den Graph: (Bild)
[color=blue]Matrix:
| 1 2 3 4 5 6
1 | x
2 | x x
3 | x
4 | x
5 |
6 | x
Liste:
1: 2
2: 3, 5
3: 5
4: 3
5: -
6: 5[/color]
ii) topologische Sortierung bestimmen
1, 2, 4, 3, 6, 5
3. Aufgabe (15 Punkte)
a) Folge 4, 9, 3, 2, 5, 1, 12, 7. Entweder mit Selectionsort oder Bubblesort sortieren
naja, malt man halt die Tabelle aus, ich hatte Selectionsort
b) Java-Methode für Verfahren aus (a) schreiben
siehe Skript…
c) Beschreibe kurz die Funktionsweise des Mergesort
[color=blue]1. Phase: rekursives Aufteilen der Menge in jeweils 2 Teile
2. Phase: sortiertes Zusammenfügen je zweier zuvor geteilter Mengen (zeichenweise)[/color]
d) Nenne weiteres Sortierverfahren mit “Teile und Herrsche”
Quicksort
4. Aufgabe (15 Punkte)
a) Binäre Bäume
i) Folge 7, 20, 30, 2, 14, 18, 9, 12, 4, 6, 16. In Suchbaum einfügen
(Bild)
ii) 7 löschen
(6 an die Stelle der 7 setzen)
b) Nenne beide Eigenschaften für binären Baum, damit er als Heap bezeichnet werden kann
[color=blue]Baum muss vollständig sein,
child-Elemente müssen kleiner bzw. größer als Knoten selbst sein (aber einheitlich)[/color]
c) B-Bäume, Ordnung 2: Gleiche Folge wie in (a) einfügen
[color=blue] 7 14
2 4 6 9 12 16 18 20 30[/color]
d) Hashing
i) Grundidee?
[color=blue]Direkter Zugriff auf unsortierte Daten,
Finden des Speicherplatzes durch Anwenden einer einfachen Funktion auf die Daten[/color]
ii) Was bedeutet Kollision…? (Frage siehe frähere Klausuren)
[color=blue]tritt auf, wenn Daten in einen Behälter der Hash-Tabelle gespeichert werden sollen, in dem bereits Daten gespeichert sind.
→ Liste aufbauen oder anderen Speicherplatz finden[/color]
5. Aufgabe (15 Punkte)
binärer Suchbaum in Java
class Tree
{
private TreeNode rootNode;
public TreeNode getMaximum();
}
class TreeNode
{
private TreeNode parent, left, right;
private Comparable nodeData;
TreeNode(Comparable newData, TreeNode parentNode)
{
nodeData = newData;
left = right = null;
parent = parentNode;
}
TreeNode getLeft()...
TreeNode getRight()...
TreeNode findDataNode(Comparable searchData);
int height();
}a) getMaximum schreiben
public TreeNode getMaximum() {[color=blue]
TreeNode n = rootNode;
while (n != null) n = n.getRight();
return n;
[/color]}
b) height schreiben
public int height() {[color=blue]
int l = getLeft() == null ? 0 : getLeft().height() + 1;
int r = getRight() == null ? 0 : getRight().height() + 1;
return Math.max(l, r);
[/color]}
c) findDataNode schreiben
public TreeNode findDataNode(Comparable searchData) {[color=blue]
int c = nodeData.compareTo(searchData);
if (c == 0) return this;
if (c < 0)
if (getRight() == null) return null;
else return getRight().findDataNode(searchData);
else
if (getLeft() == null) return null;
else return getLeft().findDataNode(searchData);
[/color]}
6. Aufgabe (15 Punkte)
verkettete Listen in Java
class ListenElement
{
private char inhalt;
private ListenElement naechstes;
ListenElement(char zeichen)
{
inhalt = zeichen;
naechstes = null;
}
public ListenElement getNaechstes()...
public void setNaechstes(ListenElement)...
}
class Liste
{
private ListenElement erstesElement;
public int size();
public void einfuegenAn(int position, char zeichen);
}a) size schreiben
public int size() {[color=blue]
ListenElement l = erstesElement;
int i = 0;
while (l != null)
{
l = l.getNaechstes();
i++;
}
return i;
[/color]}
b) einfuegenAn schreiben
position bezieht sich auf Ergebnisliste
- Element hat position 1
bei position < 1 oder position > size() Fehler ausgeben
public void einfuegenAn(int position, char zeichen) {[color=blue]
if (position < 1 || position > size())
{
System.out.println(“Falsche Position”);
return;
}
ListenElement neu = new ListenElement(zeichen);
if (position == 1)
{
neu.setNaechstes(erstesElement);
erstesElement = neu;
return;
}
position--;
ListenElement l = erstesElement;
for (int i = 1; i < position; i++) l = l.getNaechstes();
ListenElement a = l.getNaechstes();
l.setNaechstes(neu);
neu.setNaechstes(a);
[/color]}
wow, das ist ja ein service! ich haette da auch zu beitragen koennen, hatte naemlich auch zeit, alles abzuschreiben. aber wenn du es unbedingt machen musst ;]. vielleicht sollte man noch erwaehnen, dass jede aufgabe 15 punkte bringt, was teilweise eine komische aufteilung war, finde ich.
btw:
public TreeNode getMaximum() {
TreeNode n = rootNode;
while (n != null) n = n.getRight();
return n;
}das duerfte nicht gehen, weil er erst aus der whileschleife rausspringt, wenn n==null ist. d. h. er returnt immer null und nicht den letzten noch existierenden knoten. meiner meinung nach richtig:
public TreeNode getMaximum() {
TreeNode n = rootNode;
while (n.getRight() != null) n = n.getRight();
return n;
}hm, stimmt. oder
return n.getParent();(sowas gab’s doch auch, oder?)
sowas gabs schon, aber funktioniert trotzdem nicht 
.
wenn n=null ist, dann ist es auch kein TreeNode mehr und damit steht auch die methode parent () nicht mehr zur verfuegung :[.
hm, stimmt auch.
aber in deinem beispiel musst du definitiv noch ein if um das while machen, um einen leeren baum abzufangen. sonst würde da stehen ‘while (null.getRight()…’
ansonsten wird das wohl nicht so sehr viel ausmachen, denk ich. ich hoff mal, dass ich trotzdem bestanden hab! :anx:
jou, so hab ich’s in der klausur auch gemacht.
mal sehen, ob sie dich durchfallen lassen, weil du nur 99,9% richtig hast :].
public TreeNode getMaximum() {
TreeNode n = rootNode;
while (n.getRight() != null) n = n.getRight();
…
ich versteh nicht, wieso du das auf rootNode setzt, ich habe = this gemacht. damit brauch ich dann auch keine abfrage, ob this!=null…
danke für die ausführung der ganzen klausur hier, ich hatte die angaben auch abgeschrieben, aber so spar ich mir das tippen 
jetzt musste ich doch nochmal meine aufzeichnungen dazu rauskramen:
getMaximum () sollte man fuer die klasse Tree implementieren. deshalb, muss man den rootNode setzen. oder hab ich dich falsch verstanden?
ansonsten ist mir’s auch egal, hauptsache nicht mehr drueber nachdenken muessen…
Habs jetzt auch so in Erinnnerung dass man das für Tree und nicht TreeNode implementieren sollte. Ansonsten würde rootNode ja gar nicht als gültige Variable in dem Objekt existieren.
Egal! Hauptsache das ist erst mal vorbei; solange die korrektur noch nicht beendet ist, tangiert mich das jetzt alles erst mal nur peripher!
ich hab’s auch in den Node implementiert… und noch dazu mit 'ner falschen Fkt weil ich 'ne Hirnverdrehung hatte(glaub ich…)
aber was soll’s… 
Das geht? Ich dachte der Operator „==“ gilt vor „=“ … d.h. also du weißt einem int einen Wert des Typs Boolean zu? 
Korrigier mich wenn ich falsch liege …
… deine Angabe scheint nicht zu stimmen, oder?
P = {(S, aSaa), (S, cA), (A, cAb), (A, b)} war es doch oder kamen hinter dem S wirklich 3 "a"s?
Sonst alles in etwas gleich. EinfuegenAn hab ich etwas anders, aber es kommt auf’s gleiche hinaus. Und mein Maximum stimmt („yes, ich falle nicht durch!!!“)
Ach ich merk grad … die Höhe hab ich wohl falsch berechnet … ein Baum der nur aus der Wurzel besteht hat nicht zufälligerweise die Höhe 1? … naja, dann halt nicht …
Eigentlich muss man jetzt feiern gehen, weil OTRS2 und ALGO2 zu simpel waren
Grüße,
Sebbi
doch, das hat er zufaelligerweise schon. also richtig!
Sebbi:
int l = getLeft() == null ? 0 : getLeft().height() + 1;
Das ist eine abgekürzte If. Betrachte den zweiten Teil:
getLeft() == null ? 0 : getLeft().height() + 1;
zum Verständnis mach ich mal Klammern rum:
((getLeft() == null) ? 0 : getLeft().height() + 1);
vor das fragezeichen eine bedinung oder was auch immer, das boolean liefert. danach dann das resultat, das bei erfüllter bedingung entstehen soll, durch einen : abgetrennt mit dem resultat für else.
beim binären baum in den blättern dürfen nur mind. 2 werte stehen, richtig? das dachte ich bis gestern nachmittag auch… wurde aber eines “besseren” belehrt. habt ihrs wenigstens selbst richtig gemacht? 
Meint ihr, die lassen es mir durchgehen, dass ich bei dem Tree Zeug rekursive Hilfsprozeduren geschrieben habe? War ja nicht explizit verboten. bang
Ich habs auch rekursiv gemacht. Sollte eigentlich nicht verboten sein.
ich hab mir auch private hilfsmethoden geschrieben. muss gehen.
Hoffen wir das Beste.
Btw. kann es sein, dass Yves Vorschlag zur topologischen Sortierung nicht ganz stimmt, oder lese ich irgendwas falsch ab? Vielleicht hab ich in meinem Gedankenchaos auch wieder Unsinn verbockt, aber ich würde den Knoten 1,4,6 eine 1 zuweisen, da der Indegree 0 ist.
ich hab da keinen speziellen algorithmus drauf angewendet. ich bin einfach alle knoten der reihe nach durchgegangen und hab alle eingehenden kanten dabei aufgelöst.
das ganze indegree-zeugs ist mir zu kompliziert - zumindest wenn ich es mir erst selbst ausdenken muss (hab’s vorher nicht angeschaut…)
und außerdem sind topologische sortierungen eh nicht eindeutig, oder?
Nein!Sind sie nicht!
Du hast ja ne Menge von zeroin .Und wenn in der Menge mehrere Knoten sind kannst du dir den nächsten Knoten auswählen der dann z.B.order 3 erhält! :finger: