Ferienübungsblatt

[m_flaig]

Das lang ersehnte Übungsblatt zur Klausurvorbereitung ist nun online in moodle (Übungsordner unter "Zusätzliche Übungen") zu finden =)

Hinweis: Eine intensive Bearbeitung der Aufgaben wird sehr empfohlen, da Formulierungen wie in der Klausur gewählt wurden. Dies ist für das Verständnis der Klausuraufgaben sehr hilfreich. Neben diesem Übungsblatt dient der Klausurvorbereitung natürlich auch das Wiederholen von Vorlesungsstoff sowie der Übungen.

Der Übersichtlichkeit halber stellen Sie Fragen zu dem Ferienübungsblatt bitte hier (anstelle von zig neuen Themen..).

Viele Grüße und viel Spaß ,
M.Flaig

[annabel]

Ich habe ein paar Fragen zum Ferienübungsblatt...

Frage zu 1.1 Selection Sort: Welcher Schritt ist mit der Iteration 6 gemeint, der Schritt von 12 zu 12 oder von 12 zu 20? Im ersten Fall würde ja nichts passieren, ausser dass der Iterator weitergeht.

Frage zur Aufgabe 1.3 Quicksort: Muss man bei der Aufgabe den Pivotwert selbst bestimmen? Falls ja, wie macht man das? (meine Lösung: int pivot=array[array.length/2]
Muss man in der Klausur zwischen Quicksort und Quicksort in-place unterscheiden, oder reicht es, wenn man sich einen Weg merkt?

Frage zu Aufgabe 3: Beim Schritt (5) ist mir nicht klar, welcher Schlüsselwert wohin verschoben werden muss. Steht an der Wurzel des Baumes am Ende die 180?

Frage zu Aufgabe 4: Muss man die zwei Listen zuerst zusammenfügen, und dann sortieren? Fall ja, darf man in der Klausur Methoden wie addAll(list) verwenden? Gibt es irgendwo einen guten Beispielcode für das Sortieren von ArrayListen? Im Internet wird es oft mit sort(list) gelöst und ich kann keine Implementation finden!
Oder darf man in der Klausur auch Collections.sort(liste); verwenden, um die Liste zu sortieren...?

Das wars vorerst;)

[Holly19]

Hi,
zu deiner ersten Frage bezüglich Selectionsort: Der Algorithmus von Selectionsort funktioniert iterativ. Mit der 6.Iteration ist daher denke ich die 6.Ausführung der Schleife gemeint, die man bei Selectionsort implementiert. Das Ganze hat meiner Meinung nach daher nichts mit dem Iterator zu tun

[Goelz_M]

Hey annabel,

ich würde für die Sortieralgorithmen einfach die aus der Musterlösung von Übung 8 nehmen... die sind richtig und wenn man sie nachvollzieht hat man mehr davon, als wenn man welche schreibt und dann tagelang Fehler sucht und eventuell niemals findet.

Zu deiner Frage zu Aufgabe 3: Nein, denn die 180 wurde doch im Schritt zuvor gelöscht! Ich bin mir ziemlich sicher, dass in der Wurzel die 100 stehen sollte

Zu deiner Frage zu Aufgabe 5: Es geht hier glaube ich weniger um das Sortieren als um das Benutzen von Iteratoren. Deshalb kannst du das mit Sortieren einfach mit Collections.sort(ArrayList<T>) lösen. Diese Methode sortiert das automatisch. Wie gesagt, das Benutzen von Iteratoren steht im Vordergrund, deshalb ist gerade das Einfügen in die Liste wichtig. Zu beachten ist ja laut Aufgabenstellung, dass du eben keine Werte doppelt einfügst. Dazu werden mehrere Iteratoren benötigt. AddAll könnte man wahrscheinlich verwenden, um eine Teilliste anzuhängen (hab das schnell in meinem Code ausprobiert, seltsamerweise tritt die 7 im result dann 2x auf, obwohl alles andere doppelte einfach auftritt). Es geht aber auch ohne addAll... da du ja irgendwie überprüfen musst, ob schon etwas in der Liste ist, kannst du diesen Code einfach zwei mal analog erst für die erste Teilliste und dann für die zweite Teilliste verwenden, du musst nur ein bisschen was ändern. Ich glaub wenn ich noch mehr ins Detail gehe wird mein Text hier gelöscht

Und nun zu meinem Beitrag zum Ferienblatt:
Es ist mal wieder einiges falsch..

Bei Aufgabe 4 im result fehlt auf dem Aufgabenblatt die 64.

Außerdem wollte ich zur 5.) mal was fragen, was mir schon in den Übungen aufgefallen ist: Java erlaubt nicht, Arrays von Typparametern bzw. generischen Datentypen einzurichten, dazu muss ein Object Array eingerichtet und nach T[] beziehungsweise dem generischen Datentypen gecastet werden. In den ML zur Übung habt ihr das auch gemacht, leider jedoch kommentarlos stehen gelassen. Jetzt hier im Code bei Aufgabe 5 macht ihr das nicht, ich habs mal so eingetippt wie ihr es habt -> Fehlermeldung Dürfen wir das in der Klausur dann auch machen oder sollen wir es casten?

Gruß Martin

[Goelz_M]

PS: Hab ich eben übersehen: in der Signatur des Konstruktors hat der Typparameter nix zu suchen..

[Goelz_M]

PPS: Ich sollte mal alles zu Ende lesen.. der ganze Konstruktor funktioniert nicht.

So wäre es beispielsweise machbar:

Code: Alles auswählen

public BBaumNode(T initialKey){
		theKeys[0]=initialKey;
		for(int i =1; i<theKeys.length;i++){
			theKeys[i]=null;
		}
		for(int i =0; i<nodes.length;i++){
			nodes[i]=null;
		}
	}

Allerdings glaube ich, dass die Arrays auch ohne Initialisierung auf null verweisen oder? Deshalb wäre meiner Meinung nach

Code: Alles auswählen

public BBaumNode(T initialKey){
		theKeys[0]=initialKey;
	}

völlig ausreichend.

[annabel]

Danke, das hab ich dann ungefähr verstanden!
Habe aber noch ein Problem mit Aufgabe 2. Was genau ist i und K? Geht i in unserem Fall 0 bis 12 (also der key) und ist K die Werte, die eingesetzt werden sollen(also 52,11,68 usw)?
Muss ich beim ersten Durchlauf f(0,13,52) anwenden? Und beim zweiten Durchlauf f(1,13,11) usw.?

[m_flaig]

Hallo,

K nimmt die Werte an, die in die HashTabelle eingefügt werden sollen. Also K = 52,11,68,7,...
i = 1 ,2 ,3.. gibt an, der wievielte Versuch, einen freien Platz zu finden, das jetzt ist.

Viele Grüße,
M.Flaig

[ratatam]

Hallo,
ich verstehe auch nicht genau, wie in Aufgabe 4 vorgegangen werden soll.
Die Aufgabenstellung macht nur unspezifische Vorgaben.. (Hoffe die Klausuraufgaben werden präziser gestellt sein.) Mein Ansatz: Die Einzellisten zunächst mit Collections.sort(list) sortieren und dann analog zu merge() bei mergesort() mischen. Allerdings ist die vorgabe, einen iterator zu benutzen fürs mischen etwas hinderlich, da mit diesem über iterator.next() ja stets nur einmal ein bestimmtes element der liste zurückgegeben werden kann und für den vergleich mitunter merhmals auf bestimmte elemente zugegriffen werden muss.
PS: Eine baldige Veröffentlichung der Musterlösung wäre sinnvoll!

Grüße

[abcdefg]

Hallo,
dazu mal eine Frage: ist es eigentlich erlaubt Methoden wie Collections.sort() in der Klausur zu benutzen? Dadurch werden Aufgaben wie 4. aus dem Ferienblatt doch stark vereinfacht...
lg

[wac]

Hallo , ich hätte mal eine Frage zu Aufgabe 3 und zwar : In der Vorlesungsfolien steht , u.a dass ein Vielwegsuchbaum genau ein B Baum der Ordnung M ist wenn jeder Knoten außer der Wurzel mindestens M-1 Werte enthält !! Aber das letzte Blatt rechts enthält nur die Zahl 500 !! Sollte dieser Knoten nichts mindestens 2 Werte enthalten ??? Danke im Voraus!

[Goelz_M]

Hallo, ich hätte eine Antwort auf deine Frage zu Aufgabe 3 und zwar:

M-1 = 2-1 = 1!!!!

Bitteschön

[m_flaig]

Hallo,
dazu mal eine Frage: ist es eigentlich erlaubt Methoden wie Collections.sort() in der Klausur zu benutzen? Dadurch werden Aufgaben wie 4. aus dem Ferienblatt doch stark vereinfacht...
lg

Ich verweise auf eine ähnliche Frage mit folgender Antwort

VG,
M.Flaig

[msssm]

Ich verweise auf eine ähnliche Frage mit folgender Antwort

VG,
M.Flaig

In der Antwort steht aber nur, dass man alles, was zur Lösung benötigt wird, angegeben bekommt.
Daraus kann man hingegen nicht ableiten, dass man gewisse grundlegende Methoden wie Collections.sort() nicht benutzen kann.

Gruß
msssm

[wac]

Danke Goelz !!