Ich brauche hilfe für meine Klausur

[chemical20]

Hallo zusammen. Nächsten Dienstag schreibe ich eine Info Klausur. Eine Probeklausur wurde schon durchgeführt. Von der habe ich paar theoretische Fragen mit denen ich leider nicht klar komme. Wäre nett wenn jemand mir weiterhelfen könnte.

Die Fragen:

Markieren Sie alle zutreffenden Aussagen:

Binäre Suche erfordert O(n) vergleiche auf unsortierten Feldern

Mit einem Stack kann man z.B. feststellen, ob ein Ausdruck korrekt geklammert ist.

Die abstrakte Datenstruktur Queue lässt sich nicht mit einfach verketteten Listen realisieren.

Quicksort ist auf vorsortierten Feldern besonders schnell.

Mergesort benötigt auf allen Feldern der Länge 2^m immer die gleiche Anzahl an Vergleichen.

Selecktionsort benötigt auf allen Feldern der Länge 2^m immer die gleiche Anzahl an Vergleichen.

Binäre Bäume der Tiefe n haben mindestens n-1 und höchstens 2^n-1 innere Knoten.

Felder sind nicht als Grundlage der abstrakten Datenstruktur Stack geeignet.




Vielen dank im voraus

 

[Meniskusschaden]

Es bringt dir wahrscheinlich am meisten, wenn du noch deine Antwort mit einer kurzen Begründung dazu schreibst. Dann kann man auch vernünftig darauf eingehen.

 

[Xyz1]

Die abstrakte Datenstruktur Queue lässt sich nicht mit einfach verketteten Listen realisieren.

Ich würde sagen, schon aber mit erheblichen Umständen.
Normalerweise hat so eine Queue einen Tick entweder anfangs oder ends.
Mit erheblichen Umständen könnte man den Tick entgegen der Iterationsrichtung.
Dann dauert das entweder Einfügen oder Entfernen sehr lange.
Also ja aber "ungünstig".

Vergleichbare Klausuren bei uns waren wesentlich mehr von Beweisen geprägt und keinesfalls so schwer.
Schreibe zu allem mal eine Begründung.

 

[mrBrown]

Die abstrakte Datenstruktur Queue lässt sich nicht mit einfach verketteten Listen realisieren.

Ich würde sagen, schon aber mit erheblichen Umständen.
Normalerweise hat so eine Queue einen Tick entweder anfangs oder ends.
Mit erheblichen Umständen könnte man den Tick entgegen der Iterationsrichtung.
Dann dauert das entweder Einfügen oder Entfernen sehr lange.
Also ja aber "ungünstig".

Deine Sätze sind zum Großteil unvollständig und völlig unverständlich.

Eine verkettete Liste ist der übliche Datentyp für eine Queue, die lässt sich wunderbar damit umsetzen.
Einfacher als mit Arrays und nicht "ungünstiger"

Vergleichbare Klausuren bei uns waren wesentlich mehr von Beweisen geprägt und keinesfalls so schwer.
Schreibe zu allem mal eine Begründung.

Leichter als das, aber mit Beweisen? Musstest ihr Beweisen, das ihr euren Namen schreiben könnt oder was?

 

[Manuel.R]

Bei Selection Sort habe ich mal gelernt, dass er immer die Komplexität von O(n^2) besitzt.... und Merge Sort vielleicht O(n) (glaube ich...)

 

[Manuel.R]

Ich gehe davon Aus, dass Felder = Array?

wenn ja..., dann sollte das Feld gerade der geeignete Datentyp für einen Stack sein.

 

[Xyz1]

@mrBrown : Geh dich doch verbuddeln irgendwo...

Eine verkettete Liste ist der übliche Datentyp für eine Queue

Nein

die lässt sich wunderbar damit umsetzen

Nein

und nicht "ungünstiger"

Nein

Noch Fragen?

 

[Manuel.R]

http://openbook.rheinwerk-verlag.de...13_007.htm#mj0cdc7b3eb6a6b4dcdd7ac41f265dad03

ZITAT:

Spannende Queue-Klassen sind:

• ConcurrentLinkedQueue: Thread-sichere Queue, durch verkettete Listen implementiert

• DelayQueue: Queue, der die Elemente erst nach einer gewissen Zeit entnommen werden können

• ArrayBlockingQueue: Queue mit einer maximalen Kapazität, abgebildet auf ein Feld

• LinkedBlockingQueue: Queue beschränkt oder mit maximaler Kapazität, abgebildet durch eine verkettete Liste

 

[Xyz1]

@Manuel.R : Ja ich kenne alle. Aber das besagt ja noch nicht die geeignetste Wahl.

Geh dich doch auch verbuddeln... (wenn das mit genau so frech ist wie @mrBrown ) 😛

 

[Robat]

Geh dich doch auch verbuddeln

Versuch doch einfach deine Aussagen zu begründen anstatt hier so ein Schwachsinn zu schreiben 😉

 

[Meniskusschaden]

Noch Fragen?

Ja. Hast du eine Idee, warum Oracle so viele LinkedList-basierte Queue-Implementierungen im JDK ausliefert? Ich verstehe deren Motivation überhaupt nicht, wenn das so ungeeignet ist. Du weißt da doch sicher Rat.

 

[Xyz1]

warum Oracle so viele LinkedList-basierte Queue-Implementierungen im JDK ausliefert?

Einfach verkettete Lists liefern die gar nicht aus...

Daher wird die korrekte Antwort sogar Jaein sein... Und das stört mich, wenn Aufgaben nicht eindeutig gestellt werden, dass man sie nich beantworten kann. Möglich ja, aber viel zu teuer.

Zudem wird der Dozent nicht hocherfreut sein, wenn hier sie Klausur besprochen wird.

 

[Meniskusschaden]

Einfach verkettete Lists liefern die gar nicht aus...

Die genannten Queues basieren auf einer Node-Klasse, deren Objekte jeweils auf den nächsten Node verweisen. Also eine einfach verkettete Liste.

Daher wird die korrekte Antwort sogar Jaein sein... Und das stört mich, wenn Aufgaben nicht eindeutig gestellt werden, dass man sie nich beantworten kann. Möglich ja, aber viel zu teuer.

Was ist an der Frage denn mehrdeutig? Die ist doch ganz klar formuliert und kann eindeutig beantwortet werden. Aber "Jaein" wäre definitiv falsch.

Zudem wird der Dozent nicht hocherfreut sein, wenn hier sie Klausur besprochen wird.

Wenn ihn das stört, hätte er nicht Dozent werden sollen.

 

[mrBrown]

Einfach verkettete Lists liefern die gar nicht aus...

Ist für diesen Fall vollkommen egal und falsch, die genannten sind einfach verkettete Listen.

Daher wird die korrekte Antwort sogar Jaein sein... Und das stört mich, wenn Aufgaben nicht eindeutig gestellt werden, dass man sie nich beantworten kann. Möglich ja, aber viel zu teuer.

Nein, die Antwort ist ganz eindeutig: Ja, ist möglich.
Egal, ob einfach oder doppelt verkettet, die relevanten Operationen sind O(1).

Zudem wird der Dozent nicht hocherfreut sein, wenn hier sie Klausur besprochen wird.

Warum fängst du dann mit sowas an? 😉


(Um schon mal den Rest des Threads vorwegzunehmen:
D: Beleidigungen
A: Argumente
D: Bullshit und Beleidigungen
A: Argumente
D: Schweigen)