I85PREP
⌘ K
MV Abitur Computer Science study materials
MV Abitur Computer Science study resources

MV Abitur Computer Science: Datenstrukturen und Datenbanken

MV Abitur Computer Science · Work through your exam, one topic at a time.

All guide sections

Datenstrukturen und Datenbanken

Dieser Bereich prüft, ob du lineare und hierarchische Datenstrukturen nach ihren Operationen und Kosten auswählst und relationale Datenbanken sauber modellierst und abfragst. Erwartet werden Begriffe der Relationenalgebra, Normalformen und korrektes SQL.

Lineare Strukturen

  • Array: fester Platz, Zugriff über Index in O(1), Einfügen/Löschen in der Mitte in O(n).
  • Verkettete Liste: Knoten aus Daten und Zeiger; Einfügen in O(1) bei bekanntem Vorgänger, Zugriff in O(n).
  • Stack: LIFO, Operationen push, pop, top; Anwendungen: Undo, Call-Stack, Klammerprüfung.
  • Queue: FIFO, Operationen enqueue, dequeue; Anwendungen: Warteschlangen, Breitensuche.

Bäume

Ein Binärbaum hat höchstens zwei Kinder je Knoten. Ein Binärer Suchbaum erfüllt: alle Werte links sind kleiner, alle rechts größer. Traversierungen: preorder (Wurzel-links-rechts), inorder (links-Wurzel-rechts, liefert beim Suchbaum die sortierte Folge), postorder (links-rechts-Wurzel). Die Höhe bestimmt die Kosten: balanciert O(log n), entartet O(n).

Relationale Datenbanken

Eine Relation ist eine Tabelle aus Tupeln (Zeilen) über Attributen (Spalten). Der Primärschlüssel identifiziert ein Tupel eindeutig; der Fremdschlüssel verweist auf einen Primärschlüssel einer anderen Relation und sichert referenzielle Integrität. Normalformen: 1NF – alle Attribute atomar; 2NF – 1NF und kein Nichtschlüsselattribut ist nur von einem Teil des Schlüssels abhängig; 3NF – 2NF und keine transitiven Abhängigkeiten zwischen Nichtschlüsselattributen.

Durchgerechnetes Beispiel

Gesucht: Name und Mitarbeiterzahl jeder Abteilung mit mehr als zwei Mitarbeitern.

SELECT a.Name, COUNT(*) FROM Abteilung a JOIN Mitarbeiter m ON m.AbtID = a.PK GROUP BY a.PK, a.Name HAVING COUNT(*) > 2;

Begründung: Der JOIN verbindet über den Fremdschlüssel AbtID; GROUP BY fasst Zeilen je Abteilung zusammen; COUNT(*) zählt die Zeilen der Gruppe; HAVING filtert Gruppen, während WHERE einzelne Zeilen vor der Gruppierung filtert. In strengem SQL müssen alle nicht aggregierten SELECT-Attribute in GROUP BY stehen.

Typische Fallen

  • WHERE statt HAVING für Aggregatbedingungen verwenden.
  • JOIN ohne ON-Bedingung: ungewolltes Kreuzprodukt.
  • Primär- und Fremdschlüsselrichtung vertauschen.
  • COUNT(*) und COUNT(spalte) verwechseln: NULL wird bei letzterem nicht gezählt.
  • Stack und Queue vertauschen; preorder mit inorder verwechseln.
  • 3NF mit 2NF begründen: transitiv ≠ partiell.