Algorithmen und Datenstrukturen: Übungsaufgaben und Prüfungsfragen

O-Notation, die Laufzeit gängiger Algorithmen und die Vor- und Nachteile von Arrays, verketteten Listen, Bäumen, Hashtabellen und Graphen.

Diesen Kurs kostenlos übenDiesen Kurs übenProbeklausur schreibenJeden Tag 5 kostenlose Aufgaben. Keine Kreditkarte nötig.

Lernpaket (PDF)Formelsammlungen, Lösungsschritte und Übungsaufgaben mit vollständigen Lösungen, druckfertig.

Themen in diesem Kurs

  1. Algorithmen & KomplexitätBegriffe und Fakten · Konzepte anwenden · Fälle und AnalyseMultiple Choice
  2. DatenstrukturenBegriffe und Fakten · Konzepte anwenden · Fälle und AnalyseMultiple Choice
  3. GraphentheorieGrade und Kanten · Euler-Wege und Bäume · kürzeste Wege und aufspannende BäumeRechenaufgaben

Prüfungstipps für Algorithmen und Datenstrukturen

  • Multipliziere bei verschachtelten Schleifen die Anzahl der Durchläufe; bei aufeinanderfolgenden Schleifen behältst du den größeren Term.
  • Kenne die Kosten von Suchen, Einfügen und Löschen für jede Datenstruktur.
  • Wird die Eingabe in jedem Schritt halbiert, ergibt sich eine logarithmische Laufzeit.

Beispielaufgaben

Algorithmen & KomplexitätLeicht

Welche Notation beschreibt eine obere Schranke für das Wachstum?

  1. AGroß-Omega (Big Omega)
  2. BKlein-Omega (Little omega)
  3. CGroß-O (Big O)
  4. DGroß-Theta (Big Theta)
Tipps anzeigen
  1. „Höchstens“.
  2. Zwei falsche Antworten sind jetzt durchgestrichen. Eine der beiden übrigen ist richtig.
Antwort und Erklärung anzeigen

Warum das die Antwort ist

O gibt eine obere Schranke an, Ω eine untere Schranke und Θ eine scharfe (asymptotisch exakte) Schranke.

Antwort

C · Groß-O (Big O)
DatenstrukturenMittel

Wie funktioniert extract-min in einem binären Min-Heap?

  1. ADas letzte Element des Arrays entfernen
  2. BDas letzte Element in die Wurzel verschieben und nach unten wandern lassen
  3. CDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
  4. DAlle Blätter nach dem neuen Minimum durchsuchen
Tipps anzeigen
  1. Halte den Baum vollständig und korrigiere dann die Ordnung.
  2. Zwei falsche Antworten sind jetzt durchgestrichen. Eine der beiden übrigen ist richtig.
Antwort und Erklärung anzeigen

Warum das die Antwort ist

Das letzte Element füllt die Lücke in der Wurzel und wird mit seinem kleineren Kind vertauscht, bis die Heap-Eigenschaft gilt; das kostet O(log n).

Antwort

B · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen

So funktioniert das Üben

  • „Diesen Kurs üben“ mischt Aufgaben aus allen Themen des Kurses, wie in einer echten Prüfung.
  • Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort.
  • Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
  • Probeklausuren haben ein Zeitlimit und keine Tipps, und am Ende bekommst du deine Punktzahl und eine vollständige Auswertung.

Verwandte Kurse

Grundlagen der InformatikDiskrete MathematikRechnernetze
Diesen Kurs kostenlos übenDiesen Kurs übenProbeklausur schreibenJeden Tag 5 kostenlose Aufgaben. Keine Kreditkarte nötig.