Datenstrukturen und Algorithmen I: Online-Quiz für Informatik-Studierende

Question 1

Welche der folgenden Datenstrukturen ist **linear angeordnet**?

Accepted Answer

Array

Answer

Baum

Answer

Graph

Answer

Hash-Tabelle

Question 2

Was ist die entscheidende Eigenschaft von Hash-Tabellen, die eine schnelle Suche ermöglicht?

Accepted Answer

Direkte Berechnung der Speicheradresse durch eine Hash-Funktion

Answer

Lineare Suche in sortierten Daten

Answer

Offene Adressierung zur Vermeidung von Kollisionen

Answer

Sortierung der Daten vor dem Einfügen in die Tabelle

Question 3

Welche Aussage über binäre Suchbäume ist korrekt?

Accepted Answer

Die Höhe eines binären Suchbaums mit n Knoten ist immer kleiner oder gleich log2(n).

Answer

Binäre Suchbäume erlauben doppelte Einträge.

Answer

Die Suche nach einem Schlüssel in einem binären Suchbaum hat eine Zeitkomplexität von O(n).

Answer

Binäre Suchbäume sind nicht geeignet, um sortierte Daten zu speichern.

Question 4

Warum ist ein Basisfall in einer rekursiven Funktion notwendig?

Accepted Answer

Er verhindert endlose Rekursion.

Answer

Er garantiert sinnvolle Ergebnisse.

Answer

Er vereinfacht die Implementierung.

Answer

Er ist nur für Funktionen mit mehreren Parametern erforderlich.

Question 5

Welcher Suchalgorithmus ist in einer aufsteigend sortierten Liste von n Elementen am effizientesten, um ein bestimmtes Element zu finden?

Accepted Answer

Binäre Suche (schlechteste Fallkomplexität: O(log n))

Answer

Sequentielle Suche (schlechteste Fallkomplexität: O(n))

Answer

Tiefensuche (schlechteste Fallkomplexität: O(n), wenn die Liste als Baum oder Graph betrachtet wird)

Answer

Breitensuche (schlechteste Fallkomplexität: O(n), wenn die Liste als Baum oder Graph betrachtet wird)

Question 6

Welche Aussage über binäre Suchbäume ist falsch?

Accepted Answer

Binäre Suchbäume sind immer perfekt ausbalanciert.

Answer

Jeder Knoten speichert einen Schlüssel und kann zusätzliche Daten enthalten.

Answer

Interne Knoten haben höchstens zwei Kinder.

Answer

Die linke Teilstruktur eines Knotens enthält Schlüssel, die kleiner sind als der Schlüssel des Knotens.

Question 7

Welcher Sortieralgorithmus hat eine durchschnittliche Laufzeit von O(n log n)?

Accepted Answer

Heap-Sort

Accepted Answer

Quick-Sort

Answer

Bubble-Sort

Answer

Insertion-Sort

Question 8

Welche Datenstruktur reiht Elemente nach dem Prinzip "First-In-First-Out" (FIFO) aneinander?

Accepted Answer

Warteschlange

Answer

Array

Answer

Baum

Answer

Hash-Tabelle

Question 9

Welche Aussage über binäre Suchbäume (BSTs) trifft zu?

Accepted Answer

Die linke Teilstruktur eines Knotens enthält immer kleinere Schlüssel als der Knoten selbst.

Accepted Answer

BSTs können verwendet werden, um Mengen von Elementen zu speichern, die sortiert sind.

Answer

BSTs können doppelte Elemente enthalten.

Answer

Die Suchkomplexität in einem BST ist O(n), da es sich um eine lineare Datenstruktur handelt.

Question 10

Welche Eigenschaft beschreibt die Größe eines Arrays am besten?

Accepted Answer

Arrays haben eine feste Größe.

Answer

Arrays können ihre Größe während der Laufzeit dynamisch ändern.

Answer

Arrays können Elemente verschiedener Datentypen speichern.

Answer

Arrays sind ungeordnete Datenstrukturen.

Question 11

Welche Datenstruktur ist eine lineare Abfolge von Elementen, die durch Zeiger miteinander verbunden sind?

Accepted Answer

Liste

Answer

Array

Answer

Warteschlange

Answer

Graph

Question 12

Welcher Suchalgorithmus hat die schlechteste Zeitkomplexität für eine ungeordnete Liste?

Accepted Answer

Lineare Suche

Answer

Binäre Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 13

Wie wird eine verkettete Liste üblicherweise implementiert?

Accepted Answer

Als Reihe von Knoten, die durch Zeiger verbunden sind

Answer

Als Array mit fester Größe

Answer

Als Reihe von Binärbäumen

Answer

Als Hash-Tabelle zum Speichern von Elementen

Question 14

Welche Datenstruktur erlaubt das effiziente Löschen eines Elements an einer beliebigen Stelle?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Stapel

Answer

Warteschlange

Question 15

Welche Datenstruktur ist optimal für die Implementierung einer Warteschlange, bei der Elemente in der Reihenfolge ihres Eingangs verarbeitet werden?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Binärer Suchbaum

Answer

Hash-Tabelle

Question 16

Welche der folgenden Aussagen beschreibt korrekt die Eigenschaften binärer Suchbäume?

Accepted Answer

Sie sind immer sortiert, mit kleineren Werten links und größeren Werten rechts.

Accepted Answer

Sie ermöglichen effiziente Suchen durch Vergleich mit dem aktuellen Knoten.

Answer

Sie sind immer ausgeglichen mit einer logarithmischen Höhe.

Answer

Sie können nur ganze Zahlen speichern.

Question 17

Wie lange dauert die Einfügeoperation einer doppelt verketteten Liste, wenn der Einfügepunkt bekannt ist?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 18

Welche Eigenschaft ist charakteristisch für eine doppelt verkettete Liste?

Accepted Answer

Jeder Knoten zeigt auf den vorherigen und den nächsten Knoten.

Answer

Jeder Knoten zeigt nur auf den nächsten Knoten.

Answer

Jeder Knoten zeigt nur auf den vorherigen Knoten.

Question 19

Welches der folgenden ist KEIN abstrakter Datentyp (ADT)?

Accepted Answer

Integer

Answer

Stapel

Question 20

Welches Sortierverfahren vergleicht und tauscht wiederholt benachbarte Elemente, bis die gesamte Liste sortiert ist?

Accepted Answer

Bubble Sort

Answer

Heapsort

Answer

Quicksort

Answer

Mergesort

Question 21

Welche Kollisionsbehandlungsmethode in Hash-Tabellen hasht den Schlüssel erneut und fügt den Wert in einen anderen Bucket ein?

Accepted Answer

Double Hashing

Answer

Verkettung

Answer

Offene Adressierung

Answer

Lineares Sondieren

Question 22

Was ist das zentrale Prinzip eines abstrakten Datentyps (ADT)?

Accepted Answer

Ein ADT definiert eine abstrakte Schnittstelle für das Verhalten einer Datenstruktur, ohne ihre Implementierung festzulegen.

Answer

Ein ADT ist eine konkrete Implementierung einer Datenstruktur in einer bestimmten Programmiersprache.

Answer

Ein ADT ist eine Sammlung von Elementen mit einer bestimmten logischen Struktur.

Answer

Ein ADT ist ein Algorithmus, der Daten in einer bestimmten Reihenfolge verarbeitet.

Question 23

Wie werden Elemente in einer Warteschlange verarbeitet?

Accepted Answer

Nach dem Prinzip "First-In-First-Out" (FIFO)

Answer

Zufällig

Answer

Nach dem Prinzip "Last-In-First-Out" (LIFO)

Answer

Nach ihrer Wichtigkeit

Question 24

Welche Aussage beschreibt die Hauptaufgabe eines Primärschlüssels in einer relationalen Datenbank?

Accepted Answer

Er identifiziert jede Zeile in einer Tabelle eindeutig und sichert so die Datenintegrität.

Answer

Er legt den Datentyp der in einer Tabellenzeile gespeicherten Daten fest.

Answer

Er enthält den Namen der Tabelle.

Question 25

Warum ist die binäre Suche im Vergleich zur linearen Suche in einem sortierten Array so effizient?

Accepted Answer

Sie verringert die Anzahl der Vergleiche bei jedem Schritt deutlich.

Answer

Sie funktioniert auch in unsortierten Arrays.

Answer

Sie ist immer schneller als die lineare Suche.

Answer

Sie kann nicht verwendet werden, um den Index eines Elements zu finden.

Question 26

Welche Operation auf einem Array hat die höchste Zeitkomplexität?

Accepted Answer

Sortieren des Arrays

Answer

Zugriff auf ein Element an einem bestimmten Index

Answer

Hinzufügen eines neuen Elements am Ende des Arrays

Question 27

Welche Technik ermöglicht die effiziente Umwandlung von rekursiven Aufrufen in Schleifen?

Accepted Answer

Tail-Call-Optimierung

Answer

Iteration

Answer

Dynamische Programmierung

Question 28

Welche Aussage beschreibt Hashtabellen korrekt?

Accepted Answer

Sie ermöglichen die schnelle Suche und den Abruf von Elementen anhand eines Hash-Werts.

Answer

Sie sind immer sortiert, was die Suche beschleunigt.

Answer

Sie benötigen immer eine zusätzliche Suchstruktur, um Elemente zu finden.

Answer

Sie eignen sich nur für die Speicherung numerischer Daten.

Question 29

Welche Datenstruktur eignet sich am besten, um die Kanten eines Graphen zu repräsentieren?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Hashtabelle

Answer

Baumstruktur

Question 30

Welche Aussage beschreibt die lineare Suche am besten?

Accepted Answer

Sequenzielle Suche in einer unsortierten Liste nach einem Wert

Answer

Teilungs- und Eroberungsalgorithmus in einer sortierten Liste

Answer

Immer effizienter als die binäre Suche

Answer

Suche in einer unsortierten Liste vom letzten zum ersten Element

Question 31

Welche Eigenschaft ist ein wesentlicher Vorteil von verketteten Listen?

Accepted Answer

Dynamisches Hinzufügen und Entfernen von Elementen ohne Größenänderung des zugrunde liegenden Arrays

Answer

Konstantzeit-Einfügungen und -Löschungen

Answer

Garantierte Speicherung von Elementen in Einfügereihenfolge

Question 32

Welche lineare Datenstruktur funktioniert nach dem Last-In-First-Out (LIFO)-Prinzip?

Accepted Answer

Stapel

Answer

Array

Answer

Warteschlange

Answer

Liste

Question 33

Welche Datenstruktur ist optimal für die Verwaltung einer Sammlung von Elementen, die in beliebiger Reihenfolge abgerufen werden können?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Stapel

Answer

Warteschlange

Question 34

Welche Operation fügt ein Element am Ende einer verketteten Liste **effizient** hinzu?

Accepted Answer

push_back

Answer

push_front

Answer

insert_at

Answer

add

Question 35

Welche Aussage trifft **nicht** auf binäre Suchbäume zu?

Accepted Answer

Es können mehrere Knoten mit gleichem Wert existieren.

Answer

Jeder Knoten hat maximal zwei Kindknoten.

Answer

Der Wert eines Knotens ist stets größer als der Wert seines linken Kindknotens.

Question 36

Welche Operation an einem Stapel hat **keine** konstante Laufzeit?

Accepted Answer

Element suchen

Answer

Element hinzufügen

Answer

Element entfernen

Answer

Oberstes Element abfragen

Question 37

Welche Datenstruktur eignet sich für die Umsetzung des Last-In-First-Out (LIFO)-Prinzips?

Accepted Answer

Stapel

Answer

Array

Answer

Liste

Answer

Warteschlange

Question 38

Wie funktioniert eine Warteschlange?

Accepted Answer

Elemente werden hinten hinzugefügt und vorne entnommen.

Answer

Elemente werden vorne hinzugefügt und hinten entnommen.

Answer

Elemente werden zufällig entnommen.

Answer

Elemente werden nach Priorität entnommen.

Question 39

Welche der folgenden Eigenschaften ist ein grundlegendes Merkmal eines Algorithmus?

Accepted Answer

Eine eindeutige Abfolge von Anweisungen

Answer

Eine zufällige Sammlung von Befehlen

Answer

Eine Garantie für eine Lösung für jede mögliche Eingabe

Question 40

Welche Aussage zur Implementierung verketteter Listen trifft zu?

Accepted Answer

Doppelt verkettete Listen können in beide Richtungen durchlaufen werden.

Answer

Verkettete Listen benötigen immer mehr Speicher als Arrays.

Answer

Einfach verkettete Listen bieten konstante Zugriffszeit auf alle Elemente.

Question 41

Welche der folgenden Aussagen beschreibt die bewährte Vorgehensweise bei der Implementierung abstrakter Datentypen (ADTs)?

Accepted Answer

ADTs sollten eine minimale Schnittstelle mit notwendigen Operationen für den zugrunde liegenden Datentyp bieten.

Answer

ADTs sollten ohne Wrapper-Klassen implementiert werden, um Implementierungsdetails offenzulegen.

Answer

ADTs sollten ausschließlich polymorph sein, um Kompatibilität zu gewährleisten.

Answer

ADTs sollten vorrangig auf Effizienz ausgerichtet sein, auch wenn dies die Verständlichkeit beeinträchtigt.

Question 42

Welche Eigenschaft ist charakteristisch für eine Stack-Datenstruktur?

Accepted Answer

Elemente können nur am Ende eingefügt und entfernt werden.

Answer

Elemente können an beliebigen Positionen eingefügt werden.

Answer

Elemente werden in zufälliger Reihenfolge abgerufen.

Question 43

Welche Bedeutung haben verschiedene Kollisionsbehandlungsmethoden bei der Implementierung von Hash-Tabellen? Erläutern Sie deren Vor- und Nachteile.

Accepted Answer

Die Wahl der Kollisionsbehandlungsmethode hängt von den spezifischen Anforderungen der Anwendung ab.

Answer

Kollisionsbehandlungsmethoden sind für Hash-Tabellen nicht notwendig.

Answer

Verkettung ist die einzige wirksame Kollisionsbehandlungsmethode für Hash-Tabellen.

Answer

Kollisionsbehandlungsmethoden haben keinen Einfluss auf die Effizienz von Hash-Tabellen.

Question 44

Was ist das Prinzip der Rekursion? Nennen Sie ein Beispiel für einen rekursiven Algorithmus in der Datenverarbeitung.

Accepted Answer

Rekursive Algorithmen rufen sich selbst auf, um ein Problem in kleinere Teilprobleme zu zerlegen.

Answer

Rekursive Algorithmen sind immer effizienter als iterative Algorithmen.

Answer

Rekursive Algorithmen können nur für einfache Probleme verwendet werden.

Answer

Rekursive Algorithmen sind aufgrund ihrer Komplexität schwer zu verstehen und umzusetzen.

Question 45

Frage: Was ist asymptotische Zeitkomplexität und warum ist sie wichtig für die Bewertung der Effizienz von Algorithmen?

Accepted Answer

Die asymptotische Zeitkomplexität eines Algorithmus wird als Funktion der Eingabedaten beschrieben, wobei geringe Einflüsse vernachlässigt werden.

Answer

Die asymptotische Zeitkomplexität eines Algorithmus beschreibt seine Laufzeit für kleine Eingaben.

Answer

Die asymptotische Zeitkomplexität eines Algorithmus bestimmt seinen Speicherbedarf.

Answer

Die asymptotische Zeitkomplexität eines Algorithmus ist für praktische Anwendungen nicht relevant.

Question 46

Frage: Analysieren Sie die Zeit- und Raumkomplexität des Quick-Sort-Algorithmus. Vergleichen Sie ihn mit Merge-Sort und Bubble-Sort.

Accepted Answer

Quick-Sort: Best Case: O(n log n), Worst Case: O(n²); Merge-Sort: O(n log n); Bubble-Sort: O(n²)

Answer

Quick-Sort: O(n); Merge-Sort: O(n log n); Bubble-Sort: O(n²)

Answer

Quick-Sort: O(n log n); Heap-Sort: O(n log n); Bubble-Sort: O(n)

Answer

Alle genannten Algorithmen haben eine Zeitkomplexität von O(n²).

Question 47

Was ist das Konzept der **amortisierten Analyse** und warum ist sie für die Leistungsbewertung von Algorithmen, die sequentielle Datenstrukturen verwenden, nützlich?

Accepted Answer

Die amortisierte Analyse verteilt die Kosten von Operationen über die gesamte Laufzeit eines Algorithmus.

Answer

Die amortisierte Analyse bestimmt die durchschnittliche Laufzeit eines Algorithmus.

Answer

Die amortisierte Analyse gilt nur für rekursive Algorithmen.

Question 48

Welche Datenstruktur eignet sich am besten für eine Warteschlange, die Elemente in der Reihenfolge ihres Eingangs verarbeitet (FIFO)?

Accepted Answer

Verkettete Liste

Answer

Binärer Suchbaum

Answer

Hashtabelle

Answer

Array

Question 49

Welche Herausforderungen und Grenzen treten bei der Verarbeitung großer Datenmengen auf und welche Lösungsansätze gibt es?

Accepted Answer

Skalierbarkeit, Datenkomplexität, Speicherbedarf, Verarbeitungsgeschwindigkeit

Answer

Einschränkungen relationaler Datenbanken, Cloud-Computing-Abhängigkeit, hohe Kosten

Answer

Keine Herausforderungen bei der Verarbeitung großer Datenmengen

Answer

Beschränkung auf bestimmte Programmiersprachen

Question 50

Welche Implementierungsmethode wird für binäre Suchbäume verwendet und welche Vor- und Nachteile hat sie?

Accepted Answer

Zeiger

Answer

Arrays

Answer

Verkettete Listen

Answer

Hash-Tabellen

Question 51

Welche Technik kann die Effizienz rekursiver Algorithmen verbessern? Erläutern Sie kurz ihre Funktionsweise.

Accepted Answer

Tail Call Optimierung

Answer

Schleifen statt Rekursion

Answer

Speicheroptimierung

Answer

Datenkomprimierung

Question 52

Welche Komplexität hat ein Algorithmus, der ein Element in einer unsortierten Liste sucht?

Accepted Answer

Lineare Zeit (O(n))

Answer

Konstante Zeit (O(1))

Answer

Logarithmische Zeit (O(log n))

Answer

Quadratische Zeit (O(n^2))

Question 53

Welche Eigenschaft verketteter Listen ermöglicht das effiziente Löschen von Elementen an beliebigen Positionen?

Accepted Answer

Direkter Zugriff auf Elemente durch Zeiger

Answer

Kenntnis der Listengröße

Answer

Zusammenhängende Speicherung von Elementen

Answer

Lineare Anordnung von Elementen

Question 54

Welche Aussage zur Implementierung von Bäumen in Java ist zutreffend?

Accepted Answer

Java bietet spezielle Klassen für die Implementierung verschiedener Baumtypen, wie z. B. binäre Bäume und AVL-Bäume.

Answer

Bäume können in Java nur als binäre Suchbäume implementiert werden.

Answer

Bäume in Java sind immer perfekt ausbalanciert.

Answer

Bäume können in Java nicht als generische Datenstrukturen implementiert werden.

Question 55

Welche Faktoren müssen bei der Auswahl einer geeigneten Datenstruktur für die Implementierung einer Prioritätswarteschlange berücksichtigt werden?

Accepted Answer

Größe der zu verwaltenden Daten

Accepted Answer

Häufigkeit der Einfüge- und Extraktionsvorgänge

Accepted Answer

Benötigte Sortierreihenfolge der Daten

Answer

Verwendete Programmiersprache

Question 56

Welche Vor- und Nachteile haben die folgenden Hash-Funktionen: lineares Hashing, Divisionsmethode und Multiplikationsmethode?

Accepted Answer

Lineares Hashing: einfach zu implementieren, aber anfällig für Kollisionen

Accepted Answer

Divisionsmethode: schnell und einfach zu implementieren, aber kann zu ungleichmäßiger Verteilung führen

Accepted Answer

Multiplikationsmethode: gute Verteilung, aber komplexere Implementierung

Answer

Alle Hash-Funktionen sind gleichwertig und haben keine Vor- oder Nachteile.

Question 57

Welche Aussage über die Konnektivität eines Graphen trifft zu?

Accepted Answer

Ein zusammenhängender Graph hat keine isolierten Knoten.

Accepted Answer

Ein Graph mit einer Euler-Schleife ist immer zusammenhängend.

Answer

Ein Graph mit ungerader Knotenzahl ist immer unzusammenhängend.

Answer

Ein Graph mit einer geraden Anzahl ungerader Knoten ist immer zweifach zusammenhängend.

Question 58

Welche Datenstruktur eignet sich am besten für eine Warteschlange, in der Elemente basierend auf ihrer Priorität verarbeitet werden?

Accepted Answer

Prioritätswarteschlange

Answer

FIFO-Warteschlange (First-In-First-Out)

Answer

Stack (Last-In-First-Out)

Answer

Hash-Tabelle

Question 59

Welche der folgenden Aussagen über Arrays trifft zu?

Accepted Answer

Ein Array ist eine linear angeordnete Datenstruktur mit fester Länge, in der alle Elemente den gleichen Datentyp aufweisen. Der Zugriff auf Elemente erfolgt über ihren Index.

Answer

Der Zugriff auf Elemente in einem Array erfolgt über einen Hash-Wert.

Answer

Arrays können Elemente verschiedener Datentypen enthalten.

Question 60

Welche Operation hat in einer verketteten Liste die schlechteste Zeitkomplexität im Durchschnitt?

Accepted Answer

Zufälliges Einfügen

Answer

Sequenzielles Löschen am Anfang

Answer

Sequenzielles Einfügen am Ende

Question 61

Was ist das wesentliche Unterscheidungsmerkmal zwischen einem Stack und einer Queue?

Accepted Answer

Bei einem Stack erfolgt das Einfügen und Löschen von Elementen am selben Ende (LIFO), während bei einer Queue dies an entgegengesetzten Enden geschieht (FIFO).

Answer

Stacks sind lineare Datenstrukturen, während Queues zirkuläre Datenstrukturen sind.

Question 62

Welcher Sortieralgorithmus weist die beste Zeitkomplexität im durchschnittlichen Fall auf?

Accepted Answer

Quicksort

Answer

Insertionsort

Answer

Bubblesort

Question 63

Welche Art von Funktion ruft sich selbst auf?

Accepted Answer

Rekursive Funktion

Answer

Iterative Funktion

Answer

Anonyme Funktion

Question 64

Welcher Suchalgorithmus ist am effizientesten für die Suche nach einem Element in einer sortierten Liste?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hash-Suche