2. Test 22.05.2002

[Kasper]

Meine LSG fürs Quadratische Sondieren:

Platz: 00|01|02|03|04|05|06|07|08|09|10
-------------------------------------------
Wert: 08|12|00|09|18|00|00|23|07|33|00

[koali]

Bei mir steht der 18er beim 6er. hab ich mich verrechnet?

[Stella]

Der 18er steht auch bei mir an Position 6, sonst hab ichs genauso.

[Petzi]

@koali

nein, du hast dich nicht verrechnet
der 18er gehört auf den 6er
hab ich auch so


MfG Petzi

[Merlin]

hab mir mal den Avl-Baum angeschaut...wie würdet ihr ihn rebalancieren?

ich habs so gemacht:

_______________13
____________3______15
__________1__5________19
_______________7

habt ihr das auch so?

[lanschi]

Hast du von diesem Test A oder C gemacht?

[lanschi]

also .. falls es A ist hab ichs ein bisschen anders!

---------- 13 -------------
------7----------15-------
---3-----9-----------19---
-1---5--------------------

[Merlin]

stimmt, den 9 er hab ich irgendwo vergessen...
ich hab A gemacht...
könntest du mir nur erklären, wie du das gemacht hast...

laut Buch ist das doch der Fall 1.2, oder? also eine Doppelrotation linksrechts...

verwirrt mich alles irgendwie..

[keito]

Ne, es ist eine einfache Rotation. Du arbeitest bei Ungleichgewichten von unten nach Oben. Also du brauchst nur den Ast mit 1,3,5 betrachten und die 3 an die Spitze rotieren, dannach ist alles wieder in Balance ^^

[lanschi]

also ich habs mit einer links - rechts rotation gemacht!!!

weil der Knoten hat -2 und der untere hat +1 --> dh. links rechts rotation!!

[keito]

Ja, mein ich eh. ist ja nur eine Rotation oder?
Verwirrung. Na wurscht, ich komm jedenfalls aufs Selbe also wirds schon stimmen.

[wilth]

Ich bekomme als Endergebnis:

------------13--------------
------7-----------19-------
---3-----9-----15----21----
-----5----11-----17----------

b) B-Bäume, Begründung wie im Skriptum

[wilth]

Meine LSG fürs Quadratische Sondieren:

Platz: 00|01|02|03|04|05|06|07|08|09|10
-------------------------------------------
Wert: 08|12|00|09|18|00|00|23|07|33|00

Hab ich auch so.

c) keine primären Häufungen

[bybablz]

skript seite 118 (zu quadratischem sondieren) : "wie beim linearen sondieren gibt es nur m veschiedene sondierungsfolgen. dieser effekt wird sekundäre häufung genannt"

edit: verlesen

[Swoncen]

1.A)

Als erstes RightLeftRotate: An 1 und dann an 3:
---------- 13 -------------
------7----------15-------
---3-----9-----------19---
-1---5--------------------

Endergebnis genau wie wilth:
------------13-------------
------7-----------19-------
---3-----9-----15----21----
-----5----11-----17--------


2.A)

Platz: 00|01|02|03|04|05|06|07|08|09|10
------------------------------------------
Wert: 08|12|00|09|00|00|18|23|07|33|00

Keine Häufungen bei Punkt b)


3.A)


Adjazenz(G)
{
für alle v aus G
{
v.mark = 0;
}
für alle v aus G
{
falls(v.mark==0)
{
DFS(G, v);
}
}
}

DFS(G, v)
{
Liste p = neue Liste(); // lokale Liste für jeden Knoten
falls(v.mark==1)
{
return;
}
andernfalls (v.mark==0)
{
v.mark=1;
für alle w = N(v)
{
p.add(w);
DFS(G, w);
}
}
ausgabe(v); // Knoten "v" ausgeben
ausgabe(p); // Adjazente Knoten von "v" ausgeben
neue_Zeile();
return;
}


Aufwand: O(|V| + |E|)

[Sepp13]

ich weiß nicht ob ichs ganz richtig verstanden hab aber, ich hab das 3.b so gelöst, dass am scluss die komplett matrix ausgegeben wird

Hier mal mein versuch

Matrix(G)
Globalees Array[n,n]

für alle v aus G
v.mark=0;
für alle v aus G
falls v.mark ==1;
DFS(G,v);

gib array aus

DFS(G,v)
falls v.mark==1
return
falls v.mark==0
v.mark=1;
für alle w aus N(v)
Matrix.Array[v,w]=1
DFS(G,w)

[Gregor]

ich habe bei 3a folgendes:

Alg: adjazenzliste(G)
für alle Knoten v € V {
start(G,v);
neue Zeile;
}


Alg: start(G,s)
initialisierung: setze markiert[v]=0 für alle v
DFS(G,s);
ausgeben(s);
für alle Knoten v € V {
falls markiert[v]==1 && v!=s dann {
ausgabe(v);
}
}


Alg: DFS(G,v)
markiert[v]=1;
für alle Knoten w aus N(v) {
falls markiert[w]==0 dann {
DFS(G,w);
}
}

[tibela]

@Kapsper, Wilth
Platz: 00|01|02|03|04|05|06|07|08|09|10
------------------------------------------
Wert: 08|12|00|09|18|00|00|23|07|33|00
Wie kommt bei euch 18 auf Platz 4?

h (18,0) = (3*18-2) mod 11 = 52 mod 11 = 8 besetzt
h (18,1) = (8 + 2*1+4*1) mod 11 = 14 mod 11 = 3 besetzt
h (18,2) = (8 + 2*2+4*4) mod 11 = 28 mod 11 = 6

also Platz 6 tät ich sagen!

[blackx_zero]

muss man unbedingt markieren bzw. gehört das sozusagen zu DFS? .. weil ich seh in dem fall keine verwendung dafür..


Eingabe: Graph G=(V,E), Startknoten v

Liste(){
DFS(G,v,null);
für alle Listen l {
für jedes Element der Liste l {
Gib aus Knotennummer;
Gib aus Element der List l;
}
Neue Zeile;
}
}

DFS(Graph G=(V,E),v,father){
Erzeuge neue Liste l für Knoten v.
für alle w aus N(v)\father {
l.add(w);
DFS(G,w,v);
}
}