Schauer Übung Rd5

[Steff100]

Hier meine Beispiele:


Welche der folgenden Aussagen über die Schreibweise arithmetischer Ausdrücke sind richtig?


Die postfix-Schreibweise beginnt immer mit einem Operator.
Die postfix-Schreibweise benötigt keine Klammern.
Die prefix-Schreibweise beginnt immer mit einem Operator.
Die infix-Schreibweise benötigt keine Klammern.
2, 3 richtig!



Welche der folgenden Aussagen über das Traversieren von binären Sortierbäumen sind richtig, wenn die Schlüsselwerte in den Knoten steigend sortiert angeordnet sind?


Die inorder-Reihenfolge entspricht immer der Sortierreihenfolge.
Die postorder-Reihenfolge endet immer mit dem grössten Schlüssel.
Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der levelorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.
Die levelorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.
1,3 richtig!



Gegeben sei folgender infix-Ausdruck:
(x+y-1)/2

Wie lautet seine postfix-Darstellung?
xy+1-2/ richtig!



Ein binärer Baum der Höhe h stellt einen arithmetischen Ausdruck dar. Wieviele Operatoren muss dieser Ausdruck mindestens enthalten?


h + 1
h
2h - 1
2h-1 nicht richtig


In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim levelorder-Traversieren werden sie in der Reihenfolge
fdgbeac
besucht. Wie lautet die preorder-Reihenfolge?

fdgbeac richtig!



Mit einem Serienaddierwerk soll die Summe z = x + y berechnet werden.

x, y und z werden in Registern der Wortlänge von 8 bit dargestellt wobei negative Zahlen durch das 2er Komplement ihres Betrages repräsentiert werden.


Wie lautet die 8 bit Darstellung von x, y und z für
x = 23 und y = -30 ? ( z = -7)

X = 00010111
Y = 11100010
Z = 11111001
Alle richtig J

[Newbie0815]

lol hat der heut in der VO so viel gesagt über postfix, etc..?
@ steffi: wäre extrem nett, wenn du evtl deine Mitschrift von heute bzw. die Informationen, wie man das zeug da löst als anhang oder so hier posten könntest :thumb: ... ich glaub ich bin eingeschlafen in der heutigen GDI Vo - wie immer lol

mfg

EDIT:

DIese Frage kapier ich irgendwie nicht:

Ein binärer Baum der Höhe h stellt einen arithmetischen Ausdruck dar. Wieviele Operatoren muss dieser Ausdruck mindestens enthalten?
h + 1
h
2h - 1
2h-1 nicht richtigdas heißt die ersten 3 sind richtig, oder? ... ajo und was ist die höhe eines binärbaums? .. und weiso stimmt h+1?

danke für antworten schon im voraus

[Steff100]

Nein, 2^(h+1) ausgewählt und falsch getippt. Wer also die Frage bekommt, darf das nicht ankreuzen, da das falsch war. Hier kann nur 1 richtig sein, welches weiß ich nicht.:confused:

Bezüglich meiner Mitschrift würde ich es auch angepasst finden, wenn jetzt nicht der Großteil in der VO pennt, sondern auch was tut. Sich ev. auf meine Mitschrift verlassen ist vielleicht nicht gerade kollegial. Hab nämlich heut' die Leute beobachtet. Ist aber jetzt nicht auf dich, Newbie0815, bezogen. Soll nur ein allgemeiner Hinweis sein. :borg:

PS: Bezüglich meines Nicknames möchte ich betonen, dass ich männlich bin und Steffi darum nicht so gern hab. :eek2:

[Newbie0815]

ich dachte du hast alles richtig ... :P najo egal ... und das mit der mitschrift versteh ich schon, aber ich hab dir nicht die anweisung gegeben das du das tun sollst, sonder nur gefragt ... und wenn du das nicht willst ist es auch ok

bezüglich deines Nicknames: hab mich verlesen hab den 1er als ein i identifiziert lol ... sry :D aber nun nach genauerem betrachten sticht dann doch steff hervor öÖ

[Vater Gans]

Nein, 2^(h+1) ausgewählt und falsch getippt. Wer also die Frage bekommt, darf das nicht ankreuzen, da das falsch war. Hier kann nur 1 richtig sein, welches weiß ich nicht.:confused:

Bezüglich meiner Mitschrift würde ich es auch angepasst finden, wenn jetzt nicht der Großteil in der VO pennt, sondern auch was tut. Sich ev. auf meine Mitschrift verlassen ist vielleicht nicht gerade kollegial. Hab nämlich heut' die Leute beobachtet. Ist aber jetzt nicht auf dich, Newbie0815, bezogen. Soll nur ein allgemeiner Hinweis sein. :borg:

PS: Bezüglich meines Nicknames möchte ich betonen, dass ich männlich bin und Steffi darum nicht so gern hab. :eek2:

Hehe, versteh die Leute irgendwie auch nicht, die "mit dem Vorsatz" in die Vorlesung gehen, einschlafen zu müssen. Meinerseits ist das die einzige Vorlesung die ich regelmäßig besuche, und dass obwohl ich den gesamten Stoff schon 1:1 von der Schule weiß. Und mal ehrlich, besser als mit Käfern kann man die Informatik nicht erklären oder? ;)

Das mit preodrer, inorder und postorder ist übrigens bei wikipedia ziemlich gut beschrieben, in der Vorleung wars ja gestern nicht so ausführlich, wie für die Übung vorausgesetzt (meine Einschätzung zumindest).

lg

[Steff100]

Hab's nicht als Anweisung interpretiert, finde es nur witzig, wenn ich auf Laptops meine Mitschrift sehe und dann in der VO geschlafen oder gespielt wird. Das hat mich gestört.

Für alle, die darauf warten: Meine Mitschrift stell' ich wieder online. Denn können muss es sowieso jeder und ich lern' schon alleine beim Schreiben. Hoffe, dass alles nötige für die Prüfung drinsteht. :devil:

[mdk]

Hab's nicht als Anweisung interpretiert, finde es nur witzig, wenn ich auf Laptops meine Mitschrift sehe und dann in der VO geschlafen oder gespielt wird. Das hat mich gestört.


das gibt sich nach dem ersten semester, da schlafen/spielen die leute dann nicht mehr in der VO, sondern gehen gar nicht mehr in die VO. :D

[hochi]

anbei die "Mithilfe" der Übungsrunden
mfg Hochi

[hochi]

h+1 -könnt richtig sein

weil wenn h=2 n=7
und bei 7 brauch mindestens 3 operatoren

da h=2

3=2+1

was hält ihr davon??

[Newbie0815]

ich versteh nicht ganz: was ist überhaupt die Höhe? Anzahl der Stufen von der Wurzel bis zum untersten Element?
Aja ich hab auch noch eine Frage zum Infogehalt: Was ist der Infogehalt einer 7 stelligen Telefonnr.
2. Wie groß ist die Redundanz, wenn eine 8-stellige ganze Dezimalzahl MIT Vorzeichen, in einem binär Code der Länge 32 Bit dargestellt wird.
3. Wieviele Dezimalzahlen mit Vorzeichen können bei 24 Bit dargestellt werden?

mfg und danke schon im voraus für evtl. antworten ...

[hochi]

Bewertung: min. 0.0 / max. 1.0
Welche der folgenden Aussagen über die Schreibweise arithmetischer Ausdrücke sind richtig?

Wählen Sie alle korrekten Antworten!
- Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Blättern.
- Die infix-Schreibweise beginnt immer mit einer Variablen oder einer Konstanten.
- Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Knoten.
- Die prefix- und die postfix-Schreibweise können unterschiedlich lang sein.
2&3 ist Richtig
---------------------
Welche der folgenden Aussagen über das Traversieren von binären Sortierbäumen sind richtig, wenn die Schlüsselwerte in den Knoten steigend sortiert angeordnet sind?

Wählen Sie alle korrekten Antworten!

-Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der postorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren. ?
-Die inorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel. ?
-Ein binärer Sortierbaum hat immer eine ungerade Anzahl von Knoten. ?
-Die preorder- und die postorder-Reihenfolgen können unterschiedlich lang sein.
1 und 3 ist Falsch
---------------------
Bewertung: min. 0.0 / max. 1.0
Gegeben sei folgender prefix-Ausdruck:

*a*x-x1

Wie lautet seine infix-Darstellung?

Geben Sie Ihre Antwort nur mit nötigen Klammern und ohne Leerschläge ein!
(a*x*x)-1 Falsch
---------------------
Wie gross kann die Höhe eines binären Baumes mit n Knoten höchstens sein?

Wählen Sie die korrekte Antwort!
ld (n + 1) - 1 ?
ld n ?
n ?
n - 1
1 Stimmt nicht!
---------------------
Bewertung: min. 0.0 / max. 1.0
In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim preorder-Traversieren werden sie in der Reihenfolge

fbadceg

besucht. Wie lautet die postorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!
adegbcf ist falsch

---------------------
Bewertung: min. 0.0 / max. 5.0
Mit einem Serienaddierwerk soll die Summe z = x + y berechnet werden.

x, y und z werden in Registern der Wortlänge von 8 bit dargestellt wobei negative Zahlen durch das 2er Komplement ihres Betrages repräsentiert werden.


Wie lautet die 8 bit Darstellung von x, y und z für
x = 24 und y = -31 ?

x = 00011000
y = 11100001
z = 11111001

Richtig!!!!!!

[freudi]

Für die letzte Übung hilft das:


Komplement-Darstellung: Um von einer Zahl zu dem negativen Gegenstück zu kommen, wandle alle 1-Bits in 0-Bits bzw. umgekehrt
2er-Komplement: zunächst wie Komplement-Darstellung, dann 1 addierenhttp://www.hrz.uni-dortmund.de/Kurse/Java/Mitschrift_2005-04-22.html

[Vater Gans]

Für alle die noch immer nicht durchsehen und die Fragen dieser Übung mit den richtigen Antworten zusammengefasst haben wollen, können ja mal ins wiki der Schweizer WInf-Studenten sehen:

http://uni.koechlin.info/wiki/index.php?title=Fgdi_ue7

lg

[revolverheld]

Hallo!

Kann mir jemand erklären wie ich bei der 8bit Zahlendarstellung vorgehen soll?

Hab mir diverse Seiten dazuangeschaut und Folien aber ich blick das einfach nicht durch.

-----

Habs mir einfach zu kompliziert vorgestellt. Danke Hochi! :)

[hochi]

z.B.: Die Deziamalzal 31 in Binär


128 64 32 16 8 4 2 1

0 0 0 1 1 1 1 1 = 1*16+1*8+1*4+1*1=31



Nun zum Einserkomplement:

einfach alles negieren!
also von

0 0 0 1 1 1 1 1
ist das Einserkomplement
1 1 1 0 0 0 0 0


und das Zweierkomplement:

1 1 1 0 0 0 0 1
also genau um 1 höher als das Einserkomplement

[aMigO_]

Aja ich hab auch noch eine Frage zum Infogehalt:
1. Was ist der Infogehalt einer 7 stelligen Telefonnr.
2. Wie groß ist die Redundanz, wenn eine 8-stellige ganze Dezimalzahl MIT Vorzeichen, in einem binär Code der Länge 32 Bit dargestellt wird.
3. Wieviele Dezimalzahlen mit Vorzeichen können bei 24 Bit dargestellt werden?

ad 1. ld 10 * 7 = 23.25 bit

ad 2. mit Vorzeichen: R = (32 - 8 * ld 10-1) bit
ohne Vorzeichen: R = (32 - 8 * ld 10) bit

ad 3. mit Vorzeichen: 6
ohne Vorzeichen: 7

[Newbie0815]

ok danke für die antwort ... najo ich hätte noch fragen zur UE 3 u UE5 ... ich versteh diese Frage nicht: "Wieviele Schaltfunktionen sind bei 3 Eingängen selbst dual" .. Wie geht man da vor bzw. wie kommt man da überhaupt auf ein ergebnis...?

Ajo und bei UE5:

In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim levelorder-Traversieren werden sie in der Reihenfolge
fdgbeac
besucht. Wie lautet die preorder-Reihenfolge?

fdgbeac richtig!

was habt ihr da für einen Gedankengang? Schreibt ihr euch den Baum da auf, oder ...? Ich habs versucht durch AUfzeichnung eines Baums, aber es kommt ein falsches Ergebnis heraus ... wäre froh wenn mir das jmd erklären könnte..

aja und noch eine Frage zur Bitdarstellung: wenn ich nun -12 haben will: 12 = 00001100, 1er Kompl = 11110011, 2er Kompl ist dann + 1, das heißt... = 11110100
mfg

[Poseidon]

Ein binärer Baum der Höhe h stellt einen arithmetischen Ausdruck dar. Wieviele Operationen muss dieser Ausdruck mindestens enthalten

2^(h-1)
h+1
(2^h)-1
h

Richtig: h

mfg

[Vater Gans]

Ein binärer Baum der Höhe h stellt einen arithmetischen Ausdruck dar. Wieviele Operationen muss dieser Ausdruck mindestens enthalten

2^(h-1)
h+1
(2^h)-1
h

Richtig: h

mfg

Das versteh ich jetzt nicht, wenn ich zb. 3 + 4 habe, dann ist meine Höhe 2, es ist aber nur ein Operator oder? :confused:

lg

[hochi]

Bei einem "perfekten binären Baum höhe 2 müssens " h+1 sein
Bei einem "perfekten" Höhe 1 = h!
und bei einem nicht "perfekten" h => mindestens h

[Vater Gans]

Bei einem "perfekten binären Baum müssens " h+1 sein
und bei einem nicht "perfekten" h => mindestens h

Ok, was ist jetzt eigentlich mit Operationen gemeint?

lg

[hochi]

Ok, was ist jetzt eigentlich mit Operationen gemeint?

lg

Eine binäre Operation besteht ja immer aus 3 Dingen! 2 + 2

naja wennst 7 Blätter kannst ja nicht nur Operanden eingeben.

also du brauchst ja immer auch Operatoren!

BSP.: 1 + 3 + 4 + 4 bei einem Baum mit 7 Knoten (richtiggestellt)

und ein "perfekter" 7 knotiger *g* Baum ist ja 2^n
aber er kann ja auch nicht "perfekt sein!"
zeichne dir einfach ein Beispiel auf!
mfg Hochi

[Vater Gans]

Also dein Beispiel sieht bei mir so aus:



+
/ \
1 +
/ \
3 +
/ \
4 4

Da sehe ich 3 Operatoren, bei einer Höhe von 4 und auch nur 4 Blätter. Oder wie ist das gemeint?

lg

[hochi]

Also dein Beispiel sieht bei mir so aus:



+
/ \
1 +
/ \
3 +
/ \
4 4

Da sehe ich 3 Operatoren, bei einer Höhe von 4 und auch nur 4 Blätter. Oder wie ist das gemeint?

lg

ja nur hast einen kleinen "Denkfehler!"
Die Höhe ist bei diesem Beispiel = 3!!!!
siehe Schauer Sktiptum Seite 9 (des vom lezten TEst)

Die Wurzel zählt nicht!

[Vater Gans]

Ok danke Hochi, mit der Höhe war ich mir schon immer nicht ganz sicher.

Der Baum hat aber, wies ich verstanden habe, trotzdem gerade 4 Blätter oder, du meintest wahrscheinlich 7 Knoten??

lg

[hochi]

Ok danke Hochi, mit der Höhe war ich mir schon immer nicht ganz sicher.

Der Baum hat aber, wies ich verstanden habe, trotzdem gerade 4 Blätter oder, du meintest wahrscheinlich 7 Knoten??

lg
ja hab mich vertan

[Vater Gans]

Ok, und zählt der Baum auch als "pefekter" Baum?



+
/ \
1 3

Da wär die Höhe ja 1, aber auch nur 1 Operator...

lg

[hochi]

ja dies ist auch ein perfekter Baum

[Vater Gans]

ja dies ist auch ein perfekter Baum

:wein:Tut mir leid, aber irgendwie steh ich noch immer auf der Leitung, die Operatoren sind ja dann hier nicht h+1 oder?

lg

[hochi]

:wein:Tut mir leid, aber irgendwie steh ich noch immer auf der Leitung, die Operatoren sind ja dann hier nicht h+1 oder?

lg

ja! stimmt! darum h!!
Hab ich scheiße erklärt! es ist immer h!
nur bei einem Baum h=2 sind die Operationen h+1



weil bei einem perfekten Baum

Höhe Operationen
1 1
2 3
3 7


+
/ \
1 3 1 Operation

*
/ \
+ -
/\ /\
1 2 3 4 3 Operation

*
/ \
+ -
/\ / \
- + - +
/\ /\ /\ /\
12 34 56 78 7 Operation

[Vater Gans]

Ok, vielen Dank für deine Geduld! Genug der dummen Fragen ;)

lg

[navyseal]

In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim levelorder-Traversieren werden sie in der Reihenfolge
fdgbeac
besucht. Wie lautet die preorder-Reihenfolge?

fdgbeac richtig!



glaub da is dir ein fehler unterlaufen ....

weil da kommt ja das gleiche raus ;) oder hab ich das nur falsch gelesen .... auf jedenfall

levelorder = fdgbeac <--- > preorder = fdbaceg .... alle elemente nur einmal nehmen

[navyseal]

hab eine frage zur postorder ... wie rekonstruiere ich den baum?!

also hab eh ein gutes bsp gefunden ....acegfdb is in postorder wie geht man vor? verkehrt anfangen zu zeichnen oder zu lesen ? :D kann mir das bitte jemand vllt kurz erklären ??

[Poseidon]

also.... gegeben: acegfdb

-b steht ganz hinten, also muss b die Wurzel sein.
-vor b kommt nur a also ist a der linke Zweig von b und an a hängt auch nichts dran (sonst würds nicht als erstes im postorder sein)
-das vorletzte ist d also ist d der rechte Zweig von b
-was kann jetzt linker ast von d sein? alles was kleiner ist. a und b sind aber schon weg also bleibt nur noch c übrig. c ist im postorder das 2. also hängt auch nichts mehr dran
-und was gibts jetzt als rechter ast von d? das dritte von hinten, nämlich f.
-wenn wir jetzt schon mal versuchen, den Käfer krabbeln zu lassen, stellen wir sofort fest, dass der linke ast von f nur e sein kann, und dann bleibt als rechter ast nur g übrig.


b
/ \
a d
/ \
c f
/ \
e g

korrigierts mich wenn ich mir irre. Ich hoffe es gibt irgendwen außer mir, der bei meinen konfusenn Gedankengängen mitkommt.

mfg

[Vater Gans]

Ja, sieht gut aus so...

lg

[fakeplastic]

ab+2/x* postfix-ausdruck

((a+b)/2)*x infix-ausdruck ...falsch...warum?

[Vater Gans]

ab+2/x* postfix-ausdruck

((a+b)/2)*x infix-ausdruck ...falsch...warum?

Das 2. Klammernpaar ist überflüssig, deshalb...

lg

[fakeplastic]

vielen dank!

[Vater Gans]

So, jetzt hätt ich wieder eine Frage *g*

Zählt die Wurzel vom Baum als Knoten mit?

lg

[flowboarder]

Um das Eis für die fünfte Übung zu brechen bin ich in einer kleinen Kamikaze-Aktion die erste Runde durchgeflitzt:

:omg: Für das WS 2007/08 gibt es anscheinend zwei neue Fragen (Prädikatenlogik / Arrays) - siehe Screenshots.

OLAT ist um 2:00 Nachts einfach in einen Backup-Modus gegangen ist und hat den Test unterbrochen. Achtung also vor langen Nächten!

[flowboarder]

Ressourcen zur Prädikatenlogik

Algorithmen und Datenstrukturen Übung 3 (Universität Zürich WS2004)
http://www.uniwiki.ch/index.php/Algorithmen_und_Datenstrukturen_%C3%9Cbung_3_(Univ ersit%C3%A4t_Z%C3%BCrich_WS2004) (http://www.uniwiki.ch/index.php/Algorithmen_und_Datenstrukturen_%C3%9Cbung_3_%28Un iversit%C3%A4t_Z%C3%BCrich_WS2004%29)

Assessment-Prüfung - Formale Grundlagen der Informatik I
http://www.ifi.uzh.ch/ee/fileadmin/user_upload/download/recent_tests/Assessm_FGdInfI_Feb05_ML.pdf

Prädikatenlogik Folien (Schauer)
http://www.ifi.uzh.ch/ee/teaching/ws06_07/form_grund/Praedikatenlogik.pdf

[Polleh]

hatte grad 2 postfix, präfix und infix beispiele. eins davon mal klar verhaut, finde natürlich wieder nichts in den unterlagen darüber -.-

[flowboarder]

Hi Polleh, könntest du deine Prädikatenlogik Beispiele posten?

[Polleh]

die beispiele hab ich leider nicht mehr im kopf, hänge jetzt allerdins grad bei:

Für welche Werte des Arrays a ist die Zusicherung

( All i : 1 ≤ i < 5 : a ≤ a[i] )

erfüllt?

[I]Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!
+-
a=[0,1,2,3,4] a=[5,4,3,2,1] a=[2,3,5,7,11] a=[0,1,0,1,0]

-------

lösung ist, +-+-

=)

komisch übrigens, ich hatte 5 fragen zu je 2 punkten, obwohl links nur 4 aufgaben standen?

[almostready]

Die letzten beiden Beispiele:

Gegeben sei folgendes Array:

a[0..(N-1)]

Welche Bedeutung hat die Zusicherung
(( Anz i, j : 0 ≤ i < j < N : a = a[j] ) = 0 )?

[I]Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

- Alle Elemente des Arrays a sind gleich.
+ Alle Elemente des Arrays a sind verschieden.
- Im Array a gibt es mindestens zwei gleiche Elemente.
- Im Array a gibt es genau zwei gleiche Elemente.


Gegeben sei folgendes Array:

a = {1, 2, 3, 4, 5}

Welche der folgenden Zusicherungen treffen für a zu?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

All i : 1 ≤ i < 5 : a[0] ≥ a[i]
All i : 0 ≤ i < 5 : a[i] = i
not ( Ex i : 1 ≤ i < 5 : a[i-1] > a[i] )
( Anz i : 1 ≤ i < 5 : a[i-1] ≥ a[i] ) = 0

Ich habe -+++ ausgewählt, aber einen Punkt abzug bekommen.
Schätze aber, das -+ auf jeden Fall stimmen.

[PolitikerNEU]

Naja, das 2. dürfte nicht stimmen: i geht nämlich nicht von 1 - 5, sondern von 0 - 4, also müsste der Array bei a[i] = i lauten: {0,1,2,3,4}
Deswegen glaube ich, dass es eher --++ ist.

[leonard]

Nochn paar:

Gegeben sei folgendes Array:

a[0..(N-1)]

Welche Aussage folgt aus der Zusicherung
(( All i : 0 ≤ i < N : a[i] = 0 ) )?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!


Mindestens ein Element des Arrays a hat den Wert seines Index.
Alle Elemente des Arrays a sind gleich.
Mindestens ein Element des Arrays a hat den Wert 0.
Alle Elemente des Arrays a sind gerade.


ich denke alle sind richtig, bin mir aber ned ganz sicher. hab null punte bekommen als ich gsagt hab 1 und 4 is falsch und einen punkt als ich gsagt hab 1 is falsch und die anderen richtig

wenn i=0 dann stimmt 1
da a[i] immer 0 is stimmt 2 und 3
und scheinbar is 0 auch ne gerade zahl :D dann stimmt 4


Gegeben sei folgendes Array:

a[0..(N-1)]

Welche der folgenden Zusicherungen beschreiben den Sachverhalt, dass die Elemente von a eine Permutation aller Indizes enthalten?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

All i : 0 ≤ i < N : ( Ex j : 0 ≤ j < N : a[j] = i )
All i, j : 1 ≤ i < j < N : a[i] = j
not ( Ex i : 1 ≤ i < N : a[i] ≠ i )
( Anz i, j : 1 ≤ i, j < N : a[i] = j ) = N

keine lösung

Für welche Werte des Arrays a ist die Zusicherung

( Ex i, j : 0 ≤ i < j < 5 : a[i] = a[j] )

erfüllt?

a=[0,1,2,3,4]
a=[5,4,3,2,1]
a=[2,3,5,7,11]
a=[0,1,0,1,0]

lösung 4 richtig, die anderen falsch

und

acegfdb in postorder entspricht badcfeg in preorder beim bsp. 3

[Mane]

Für welche Werte des Arrays a ist die Zusicherung

( Ex i, j : 0 ≤ i < j < 5 : a[i] = a[j] ) erfüllt?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

+ -
a=[0,1,2,3,4] -
a=[5,4,3,2,1]
a=[2,3,5,7,11]
a=[0,1,0,1,0]



Bewertung: min. 0.0 / max. 2.0


Für welche Werte des Arrays a ist die Zusicherung

( Ex i, j : 0 ≤ i < j < 5 : a[i] ≠ a[j] ) erfüllt?


Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

+ -
a=[0,1,2,3,4]
a=[5,4,3,2,1]
a=[2,3,5,7,11]
a=[0,0,0,0,0]



Für welche Werte des Arrays a ist die Zusicherung

( All i : 0 ≤ i < 4 : a[i] = i ) erfüllt?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

+ -
a=[0,1,2,3]
a=[4,3,2,1]
a=[2,3,5,7]
a=[0,0,0,0]


Gegeben sei folgendes Array:

a[0..(N-1)]

Welche Aussage folgt aus der Zusicherung
(( All i : 0 ≤ i < N : a[i] = 0 ) )?

Wählen Sie alle korrekten Antworten (+) und alle falschen Antworten (-)!

+ -
Mindestens ein Element des Arrays a hat den Wert seines Index.
Alle Elemente des Arrays a sind gleich.
Mindestens ein Element des Arrays a hat den Wert 0.
Alle Elemente des Arrays a sind gerade.


Ich verstehe nicht, wie das funktioniert, konnte leider nicht an der Vorlesungen teilnehmen... :confused:
Könnte mir das jemand, bitte, erklären ?

Danke

[flowboarder]

levelorder: fdgbeac
=> postorder: acbedgf


(All i : 0 <= i <= 4 : a[i] = i)
a=[0,1,2,3] RICHTIG
a=[4,3,2,1] FALSCH
a=[2,3,5,7] FALSCH
a=[0,0,0,0] FALSCH


Bei der nachfolgenden Aufgabe wurde ein Punkt abgezogen, die RICHTIGEN Antworten sind also teilweise falsch!
( All i, j : 0 <= i < j < 5 : a[i] != a[j] )
a=[0,1,2,3,4] RICHTIG
a=[5,4,3,2,1] RICHTIG
a=[2,3,5,7,11] RICHTIG
a=[0,1,0,1,0] RICHTIG

[PolitikerNEU]

Das letzte [0,1,0,1,0] dürfte falsch sein - wählt man z. B. i = 0 und j = 2, hat man 0 != 0 - das ist aber falsch.

[Bl4cky]

---------------------
Wie gross kann die Höhe eines binären Baumes mit n Knoten höchstens sein?

Wählen Sie die korrekte Antwort!
ld (n + 1) - 1 ?
ld n ?
n ?
n - 1
1 Stimmt nicht!
---------------------


2 Stimmt auch nicht

[staatsfeind_nr1]

@Bl4cky: die richtige Lösung wäre n-1

wer die übung noch nicht geschafft hat, das wiki zu gdi von den schweizern deckt so ziemlich alle fragen ab, unsere R5 besteht aus ihren Uebungen 4 & Ue7
link wurde zwar schon gepostet, aber hier noch mal: http://uni.koechlin.info/wiki/index.php?title=Grundlagen_der_informatik

[andionline]

Gegeben sei folgender prefix-Ausdruck:

*a*x-x1

Wie lautet seine infix-Darstellung?
a*x*(x-1) war richtig


------------


Welche der folgenden Aussagen über das Traversieren von binären Sortierbäumen sind richtig, wenn die Schlüsselwerte in den Knoten steigend sortiert angeordnet sind?

Wählen Sie alle korrekten Antworten!
Ein binärer Sortierbaum hat immer eine ungerade Anzahl von Knoten.
Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der postorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren. (wahr)
Die inorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel. (wahr)
Die preorder- und die postorder-Reihenfolgen können unterschiedlich lang sein.
--> Lösung richtig


----


Welche der folgenden Aussagen über das Traversieren von binären Sortierbäumen sind richtig, wenn die Schlüsselwerte in den Knoten steigend sortiert angeordnet sind?

Wählen Sie alle korrekten Antworten!
Die inorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel. (wahr)
Die preorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.
Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der inorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.
Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der levelorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren. (wahr)
war richtig


-----------------
Wie gross kann die Höhe eines binären Baumes mit n Knoten höchstens sein?

Wählen Sie die korrekte Antwort!
n - 1
ld n
n
ld (n + 1) – 1


n – 1 stimmt. Vorsicht: Beim binären Baum hat jeder Knoten max. 2 Teilbäume. Nicht verwechseln mit perfektem binären Baum, der immer genau zwei Teilbäume besitzt!
Einfach aufzeichnen, dann ist die Lösung offensichtlich!



----




In einem binären Sortierbaum sind die Schlüssel steigend sortiert.

Beim preorder-Traversieren werden sie in der Reihenfolge

dbacfe

besucht. Wie lautet die levelorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!

dbface


--> richtig


----
In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim preorder-Traversieren werden sie in der Reihenfolge

fbadceg

besucht. Wie lautet die postorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!
acedbgf ==> richtig.

[wiesa]

kann auf das wiki der schweizer nicht zugreifen. meldung "forbidden"
You don't have permission to access / on this server.

[krohrer]

In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim preorder-Traversieren werden sie in der Reihenfolge

fbadceg

besucht. Wie lautet die postorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!
acedbgf ==> richtig.


könntest du vl kurz den Baum dazu posten?
Weil ich bekomm da ganz was andres raus und fürchte, dass ich wieder mal heftigst auf der Leitung steh :omg:

danke schon mal :)

[andionline]

könntest du vl kurz den Baum dazu posten?
Weil ich bekomm da ganz was andres raus und fürchte, dass ich wieder mal heftigst auf der Leitung steh :omg:

danke schon mal :)


Der Baum sollte so aussehen:
http://www.falschparken.at/uni/baum.gif

vg, andi

[Philipp H.]

Hier sind meine Fragen mit den richtigen Antworten



Aufgabe 1

Bewertung: min. 0.0 / max. 2.0
Welche der folgenden Aussagen über die Schreibweise arithmetischer Ausdrücke sind richtig?

Wählen Sie alle korrekten Antworten!
Die postfix-Schreibweise beginnt immer mit einem Operator.
Die prefix-Schreibweise beginnt immer mit einem Operator. - richtig
Die postfix-Schreibweise benötigt keine Klammern. - richtig
Die infix-Schreibweise benötigt keine Klammern.


Aufgabe 2

Bewertung: min. 0.0 / max. 2.0

Welche der folgenden Aussagen über die Schreibweise arithmetischer Ausdrücke sind richtig?

Wählen Sie alle korrekten Antworten!
Die infix-Schreibweise beginnt immer mit einer Variablen oder einer Konstanten. - richtig
Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Knoten. - richtig
Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Blättern.
Die prefix- und die postfix-Schreibweise können unterschiedlich lang sein.

Aufgabe 3

Bewertung: min. 0.0 / max. 2.0

Gegeben sei folgender postfix-Ausdruck:

ab+2/x*

Wie lautet seine infix-Darstellung?

Geben Sie Ihre Antwort nur mit nötigen Klammern und ohne Leerschläge ein!
Antwort: (a+b)*2/x

Aufgabe 4

Bewertung: min. 0.0 / max. 2.0
In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim preorder-Traversieren werden sie in der Reihenfolge

fbadceg

besucht. Wie lautet die postorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!
Antwort: acedbgf


Aufgabe 5

Bewertung: min. 0.0 / max. 2.0
In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim levelorder-Traversieren werden sie in der Reihenfolge

fdgbeac

besucht. Wie lautet die postorder-Reihenfolge?

Geben Sie Ihre Antwort ohne Leerschläge ein!
Antwort: acbedgf


Viel Spaß bei der Übung ;)

LG. Philipp