Ferienübungsblatt

Moderator: AI 2

m_flaig
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Ferienübungsblatt

Beitrag von 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ß :wink: ,
M.Flaig

annabel
Neuling
Neuling
Beiträge: 5
Registriert: 12. Mai 2014 20:31

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 21
Registriert: 18. Mai 2014 12:15

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 16
Registriert: 20. Okt 2013 11:38

Re: Ferienübungsblatt

Beitrag von 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 :P

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 :mrgreen:

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 :roll: Dürfen wir das in der Klausur dann auch machen oder sollen wir es casten? :P

Gruß Martin

Goelz_M
Erstie
Erstie
Beiträge: 16
Registriert: 20. Okt 2013 11:38

Re: Ferienübungsblatt

Beitrag von Goelz_M »

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

Goelz_M
Erstie
Erstie
Beiträge: 16
Registriert: 20. Okt 2013 11:38

Re: Ferienübungsblatt

Beitrag von 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
Neuling
Neuling
Beiträge: 5
Registriert: 12. Mai 2014 20:31

Re: Ferienübungsblatt

Beitrag von 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
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 14
Registriert: 30. Apr 2014 16:35

Re: Ferienübungsblatt

Beitrag von 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
Neuling
Neuling
Beiträge: 2
Registriert: 27. Aug 2014 16:07

Re: Ferienübungsblatt

Beitrag von 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
Neuling
Neuling
Beiträge: 3
Registriert: 27. Aug 2014 22:36

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 16
Registriert: 20. Okt 2013 11:38

Re: Ferienübungsblatt

Beitrag von 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
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Ferienübungsblatt

Beitrag von m_flaig »

abcdefg hat geschrieben: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
Neuling
Neuling
Beiträge: 3
Registriert: 28. Aug 2014 17:20

Re: Ferienübungsblatt

Beitrag von msssm »

m_flaig hat geschrieben: 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
Neuling
Neuling
Beiträge: 3
Registriert: 27. Aug 2014 22:36

Re: Ferienübungsblatt

Beitrag von wac »

Danke Goelz :) !!

Antworten

Zurück zu „AI 2“