Üben für den 2. Test am 11.01.2007

  • Hmm, eine Frage die mir vielleicht jemand beantworten könnte:
    "Ist beim Einfügen mittels Double Hashing in eine Hashtabelle die Anzahl der auftretenden Kollisionen abhängig von der Reihenfolge der eingefügten Datensätze?"


    Lg

  • denke schon dass es abhängig ist, denn wenn du 2 zahlen hast, die bei der ersten funktion den selben Hashwert bekommen, dann ist das unabhängig davon, ob die erste oder zweite zuerst kommt, 1 kollision. bei der zweiten funktion kommt die erste zahl auf eine andere position als die zweite, und wenn die position besetzt ist, dann kommt eine kollision dazu, die bei der zweiten zB. nicht da ist, somit hat sich die Anzahl geändert. habe es jedoch nicht mit allen zahlen probiert...

  • ich denke nicht dass es abhängig ist.
    blackDiamond:
    wenn bei der 2ten funktion die position noch nicht besetzt ist (diese position aber später noch kommt) so kommt es halt einfach später zu der kollision, also bleib zum schluss die anzahl der kollisionen gleich
    edit: wenn bei der 2ten funktion die position bereits besetzt ist, dann gibts diese kollision halt gleich....

  • Hätte eine Frage zu folgendem Beispiel:
    http://www.ads.tuwien.ac.at/te…rchiv/186114/20050525.pdf


    Bsp 1.A b


    Hierbei wird aus einem B-Baum ein Knoten entfernt, sodass sich nicht mehr alle Blätter auf der selben Ebene befinden.
    Nun soll der Baum wieder so reorganisiert werden, dass wieder ein gültiger B - Baum entsteht.
    Habe aber weder im Skriptum noch sonst irgendwo ein Beispiel gefunden, wie das gemacht wird.


    Hat da vielleicht irgendwer eine Idee?
    Wär über eine Antwort sehr dankbar :)

    :devil: Carpe Diem! :devil:
    :thumb: Manche Arbeiten muß man dutzende Male verschieben, bevor man sie endlich vergißt. :thumb:


  • folgendes kommt raus:

    Code
    1. 8 | 10
    2. / | \
    3. 2|5 9| 12|21


    mit folgendem tool geprüft
    http://www.hs-augsburg.de/~mweiss/applets/bTree.shower2.html
    musst dir das folgendermaßen überlegen!
    durchs löschen vom 20er wird der 10er runtergezogen und dann musst das reorganisieren damit alles wieder passt!


    lg jacko


  • 2B.3 ist imho falsch, a-b-c-d-i-f-e-h-g
    Wenn du bei f ankommst, nimmt der algo auf grund der alphabetischen reihenfolge e und nicht g zuerst. nach e folgt das noch umarkierte h, anschließend wird bis nach h terminiert und das verbliebene g markiert.


    lg

  • Vonwegen Double-Hashing: Die Reihenfolge beim Einfügen spielt natürlich eine Rolle, wie man leicht an einem Beispiel sieht:
    angenommen 3 Zahlen (a, b, c) werden in ein Feld der Länge 3 eingefügt und deren Werte für h1 sind (1, 1, 3) und für h2 (1, 2, 1):
    1. Reihenfolge (a, b, c): a an Position 1, b an Position 3 (1 Kollision), c an Position 2 (2 Kollisionen) = 3 Kollisionen
    2. Reihenfolge (b, a, c): b an Position 1, a an Positon 2 (1 Kollision), c an Position 3 (0 Kollisionen) = 1 Kollision

  • ad 3A: (Prüfung 20050525)
    Wird wohl schwierig das anders zu überprüfen als alle:
    G' = G - {v} zu erzeugen und mittels Tiefensuche oder Breitensuche nachzusehen, ob sie zusammenhängend sind. Man könnte die ganze Sache noch etwas verbessern:
    Sobald ein Knoten vorhanden ist, der < 2 Nachbarn hat, ist er auf jeden Fall nicht 2 zusammenhängend. (Nachbarn entfernen ...)

  • Wie kommt ihr auf das ergebnis von 2B.3)? wie gehe ich da genau vor?


    du gehst rekursiv vor
    du nimmst vom startknoten ein kind(alphabetische rangfolge beachten), von diesem kind nimmst du wieder ein kind (wenn 2 wieder das was im alphabet vorher ist) usw...die besuchten knoten markieren, die kannst du dann vergessen, und das ist alles

  • Du mußt einfach die Idee von Tiefensuche an dem Graph anwenden:
    Sprich so weit in die Tiefe gehen, bis es nicht mehr geht & dann den Pfad wieder zurück bis du zu einem Knoten kommst, der noch Nachbarn hat, bei denen du noch nicht warst.


    Das ganze wird alphabetisch gereiht ... Startknoten = a


    --> {a}


    Du stehst am Knoten a und schaust dir die Nachbarknoten an (e oder b) ... b ist im Alphabet vor a --> b kommt hinzu
    --> {a,b}


    Nachbarn von b = h, c --> c hinzu
    --> {a,b,c}


    Nachbarn von c = i,d --> d hinzu
    --> {a,b,c,d}


    Bei d geht es nicht weiter --> max. Tiefe erreicht & du gehst den Pfad zurück bis zu einem Knoten der noch Nachbarn hat wo du noch nicht warst --> bis c
    --> i kommt hinzu
    --> {a,b,c,d,i}


    Nachbarn von i = h,f,g --> f hinzu
    --> {a,b,c,d,i,f}


    Nachbarn von f = e,g --> e hinzu
    --> {a,b,c,d,i,f,e}


    Nachbarn von e (wo wir noch nicht waren) = h --> h kommt hinzu
    {a,b,c,d,i,f,e,h}
    h hat nun keine Knoten mehr wo wir nich zuvor schon waren --> zurück zu e ... e hat ebenfalls alle Nachbarknoten schon markiert --> zurück zu f
    Nachbar von f = g --> g hinzu
    --> {a,b,c,d,i,f,e,h,g}
    Fertig


    Brustvergrößerung durch Handauflegen!
    Mache auch Hausbesuche- rund um die Uhr!
    Näheres bitte bei PM!
    :shinner: