Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


14. Elementare Suchmethoden



Übungen

  1. Implementieren Sie einen sequentiellen Suchalgorithmus, der sowohl für erfolgreiches als auch für erfolgloses Suchen durchschnittlich ungefähr N/2 Schritte benötigt, wobei die Datensätze in einem sortierten Feld gespeichert werden.
  2. Geben Sie die Reihenfolge der Schlüssel an, nachdem Datensätze mit den Schlüsseln E A S Y Q U E S T I O N mit search and insert unter Verwendung der selbstorganisierenden heuristischen Suchmethode in eine ursprünglich leere Tabelle eingesetzt wurden.
  3. Geben Sie eine rekursive Implementation der binären Suche an.
  4. Es gelte a[i]=2i für 1 <= i <= N. Wie viele Tabellenpositionen werden bei einer Interpolationssuche während der erfolglosen Suche nach 2k - 1 untersucht?
  5. Skizzieren Sie den binären Suchbaum, der entsteht, wenn in einen ursprünglich leeren Baum Datensätze mit den Schlüsseln E A S Y Q U E S T I O N eingefügt werden.
  6. Schreiben Sie ein rekursives Programm zur Berechnung der Höhe eines binären Baumes, d. h., des längsten Abstands von der Wurzel bis zu einem äußeren Knoten.
  7. Nehmen wir an, daß wir im voraus schätzen können, wie oft auf Suchschlüssel in einem binären Baum zugegriffen wird. Sollten die Schlüssel in wachsender oder fallender Reihenfolge der zu erwartenden Zugriffshäufigkeit in den Baum eingefügt werden? Warum?
  8. Modifizieren Sie die Suche in einem Binärbaum so, daß gleiche Schlüssel zusammen im Baum angeordnet werden. (Falls im Baum andere Knoten existieren, die den gleichen Schlüssel haben wie ein gegebener Knoten, so sollte entweder sein Vorgänger oder einer seiner Nachfolger den gleichen Schlüssel haben.)
  9. Schreiben Sie ein nichtrekursives Programm zur Ausgabe der Schlüssel eines binären Suchbaums in der richtigen Reihenfolge.
  10. Skizzieren Sie den binären Suchbaum, der entsteht, wenn in einen ursprünglich leeren Baum Datensätze mit den Schlüsseln E A S Y Q U E S T I O N eingefügt werden und danach das Q gelöscht wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]