Deutsch
Menü

Datenstrukturen und Algorithmen

Zeitkomplexität (O-Notation), Arrays und verkettete Listen, Stacks und Warteschlangen, Hashtabellen, binäre Suche, Ablauf und Stabilität der Sortierverfahren, binäre Suchbäume und Heaps, Suche in Graphen und kürzeste Wege sowie Rekursion, dynamische Programmierung und Greedy-Algorithmen, einschließlich ihres Bezugs zu Caches und GPUs, erarbeitet mit Multiple-Choice-Fragen.

10 Fragen übenZufällige Fragen aus diesem Thema · etwa 5 Minuten Dieses Thema übenAlle Fragen dieses Themas in zufälliger Reihenfolge Schwache FragenNur zuletzt falsch beantwortete Fragen erneut üben

Datenstrukturen und Algorithmen: Kernpunkte

Programme, die dasselbe Problem lösen, können sich bei wachsender Datenmenge je nach verwendeten Datenstrukturen und Algorithmen um Größenordnungen in der Geschwindigkeit unterscheiden. Mit der Zeitkomplexität abzuschätzen, wie der Aufwand wächst, und Strukturen zu wählen, die zur Nutzung der Daten passen, ist der Ausgangspunkt für schnelle Programme.

Behandelt werden grundlegende Datenstrukturen wie Arrays und verkettete Listen, Stacks und Warteschlangen, Hashtabellen, binäre Suchbäume und Heaps sowie die Darstellung von Graphen, dazu die binäre Suche, Sortierverfahren wie Bubblesort, Selectionsort, Insertionsort, Mergesort, Quicksort und Heapsort, Breitensuche, Tiefensuche und der Dijkstra-Algorithmus sowie Rekursion, dynamische Programmierung und Greedy-Algorithmen, überwiegend anhand von Rechenaufgaben, die jeden Schritt nachvollziehen; das hilft auch bei der Vorbereitung auf IT-Zertifizierungsprüfungen im Bereich Algorithmen. Außerdem geht es um den Bezug zur Hardwareleistung, etwa um cachefreundliche Datenanordnungen und paralleles Sortieren auf GPUs.

Alle Fragen zu Datenstrukturen und Algorithmen (40)
  1. Welche Zeitkomplexität hat bei einem Array mit n Elementen ein Verfahren, das jedes Paar zweier verschiedener Elemente genau einmal vergleicht (eine doppelte Schleife, die das i-te Element mit allen dahinterliegenden Elementen vergleicht und i schrittweise erhöht)?
  2. Ein Programm mit der Zeitkomplexität O(n²) benötigt für 1000 Datenelemente 0,5 Sekunden. Wie lange benötigt es etwa für 4000 Datenelemente?
  3. Eine lineare Suche vergleicht die Elemente eines Arrays mit 100 verschiedenen Werten der Reihe nach von vorn, um einen Zielwert zu finden. Der Zielwert ist immer im Array enthalten und steht mit gleicher Wahrscheinlichkeit an jeder Position. Wie viele Vergleiche sind im Mittel nötig?
  4. Welche Aussage beschreibt eine verkettete Liste (eine Liste, in der jedes Element einen Zeiger auf das nächste Element enthält) im Vergleich zu einem Array richtig?
  5. Auf einem leeren Stack werden nacheinander die Operationen push 1, push 2, pop, push 3, push 4, pop, pop ausgeführt. In welcher Reihenfolge werden die Werte durch pop entnommen?
  6. In eine leere Warteschlange (Queue) werden die Elemente A, B und C in dieser Reihenfolge eingefügt. Dann wird ein Element entnommen, D eingefügt und ein Element entnommen, E eingefügt und ein Element entnommen. In welcher Reihenfolge werden die Elemente entnommen?
  7. Der Ausdruck „3 4 + 2 * 5 −“ in umgekehrter polnischer Notation (Postfixnotation) wird ausgewertet, indem jede Zahl auf einen Stack gelegt wird und bei jedem Operator zwei Werte entnommen, verrechnet und das Ergebnis wieder abgelegt wird. Welches Ergebnis entsteht? Der linke Operand eines Operators ist der Wert, der früher abgelegt wurde.
  8. Welche Aussage beschreibt eine Kollision in einer Hashtabelle richtig?
  9. In einer Hashtabelle der Größe 7 (Positionen 0 bis 6) werden mit der Hashfunktion h(k) = k mod 7 die Schlüssel 10, 17, 24 und 3 in dieser Reihenfolge gespeichert. Kollisionen werden durch lineares Sondieren aufgelöst, das jeweils eine Position weiterrückt (nach 6 folgt 0), bis ein freier Platz gefunden ist. An welcher Position wird der Schlüssel 3 gespeichert?
  10. Welche Aussage vergleicht die Verkettung (Chaining: Elemente derselben Position werden in einer verketteten Liste verbunden) und die offene Adressierung (eine andere freie Position innerhalb der Tabelle wird gesucht) als Verfahren zur Kollisionsauflösung in Hashtabellen richtig? Der Belegungsfaktor ist die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße.
  11. Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?
  12. Auf 1000 verschiedene, aufsteigend sortierte Werte wird eine binäre Suche angewendet. Ein Vergleich liefert jeweils „gleich“, „kleiner“ oder „größer“. Wie viele Vergleiche sind höchstens nötig, erfolgreiche und erfolglose Suchen zusammengenommen?
  13. Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?
  14. Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?
  15. Das Array 29, 10, 14, 37, 13 wird mit Selectionsort aufsteigend sortiert: Das Minimum des unsortierten Teils wird gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Wie sieht das Array aus, nachdem dieser Schritt zweimal ausgeführt wurde?
  16. Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?
  17. Welches Sortierverfahren hat auch im schlechtesten Fall die Komplexität O(n log n) und sortiert fast ohne zusätzlichen Speicher wie ein Arbeitsarray?
  18. Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?
  19. In welchem typischen Fall benötigt Quicksort O(n²) Zeit?
  20. Bei Mergesort werden die beiden sortierten Folgen 1, 4, 7, 9 und 2, 3, 8, 10 zu einer zusammengeführt (Merge), indem wiederholt die vordersten Elemente verglichen und das kleinere ausgegeben wird. Ist eine Folge leer, wird der Rest der anderen ohne Vergleich ausgegeben. Wie viele Vergleiche werden durchgeführt?
  21. Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?
  22. Ein Max-Heap, in dem der Wert jedes Elternknotens mindestens so groß ist wie die Werte seiner Kinder, wird in einem Array mit der Wurzel in a[0] gespeichert. Zum Heap 50, 30, 40, 10, 20, 35 wird 45 hinzugefügt, indem es ans Ende gesetzt und dann mit seinem Elternknoten vertauscht wird, solange es größer als dieser ist. Wie sieht das resultierende Array aus?
  23. Wie sind die Werte der besuchten Knoten angeordnet, wenn ein binärer Suchbaum in In-Order (symmetrische Reihenfolge: erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum) durchlaufen wird? Alle Werte seien verschieden.
  24. Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. In welcher Reihenfolge werden die Knoten besucht, wenn der Baum in Post-Order (erst der linke Teilbaum, dann der rechte Teilbaum, dann der Knoten) durchlaufen wird?
  25. Die Werte 1, 2, 3, …, 1000 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt (ohne Rebalancierung). Mit wie vielen Knoten wird bei der Suche nach 1000, beginnend an der Wurzel, verglichen, bis der Wert gefunden ist?
  26. Was ist der Hauptgrund dafür, dass für Indizes in Datenbanken und Dateisystemen B-Bäume (einschließlich B+-Bäumen) statt binärer Suchbäume weit verbreitet sind?
  27. Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?
  28. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  29. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?
  30. In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?
  31. Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?
  32. Für die Aufgaben A bis E gelten die Reihenfolgebedingungen „A vor C“, „B vor C“, „C vor D“, „B vor E“ und „E vor D“. Welche Reihenfolge erfüllt alle Bedingungen (ein Ergebnis der topologischen Sortierung)?
  33. Eine Funktion f(x, y) ist definiert als „ist y gleich 0, gib x zurück; andernfalls gib f(y, x mod y) zurück“. Welchen Rückgabewert liefert der Aufruf f(84, 36), und wie oft wird f aufgerufen, den ersten Aufruf eingeschlossen?
  34. Eine Funktion fib(n) für die Fibonacci-Zahlen ist rekursiv definiert als „ist n kleiner oder gleich 1, gib n zurück; andernfalls gib fib(n−1) + fib(n−2) zurück“. Wie oft wird fib beim Aufruf von fib(5) aufgerufen, den ersten Aufruf eingeschlossen?
  35. 8 Yen sollen mit Münzen zu 1 Yen, 4 Yen und 6 Yen bezahlt werden. Welche Aussage über die Zahl der Münzen, die ein Greedy-Algorithmus wählt (der zuerst so viele der größten Münze wie möglich verwendet), im Verhältnis zur kleinstmöglichen Münzzahl ist richtig?
  36. Ein Rucksack mit der Kapazität 8 wird mit Gegenständen aus vier Gegenständen mit (Gewicht, Wert) (2, 3), (3, 4), (4, 5) und (5, 6) gefüllt. Jeden Gegenstand gibt es nur einmal, und Gegenstände lassen sich nicht teilen. Wie groß ist der höchste Gesamtwert bei einem Gesamtgewicht von höchstens 8?
  37. Welche Aussage beschreibt ein Merkmal des Boyer-Moore-Algorithmus zum Suchen eines Musters in einer Zeichenkette richtig?
  38. Ein dynamisches Array legt, wenn ein Element hinzugefügt wird, während es voll ist, einen neuen Bereich mit doppelter Kapazität an und kopiert alle Elemente dorthin. Wie viele Elementkopien entstehen insgesamt, wenn einem leeren Array mit der Kapazität 1 nacheinander 1000 Elemente hinzugefügt werden?
  39. Warum ist bei einer Hashtabelle mit vielen Elementen und einem Belegungsfaktor von etwa 0,5 die offene Adressierung mit linearem Sondieren am ehesten schneller als die Verkettung (Verbinden der Elemente durch verkettete Listen)?
  40. Für das Sortieren auf paralleler Hardware wie GPUs werden manchmal Sortierverfahren mit einer festen Folge von Vergleichs- und Tauschschritten (Sortiernetzwerke) wie Bitonic Sort verwendet. Warum?

Weitere Themen in Computersysteme