Datenstrukturen und Algorithmen II: Interaktive Online-Quizze für Studierende

Question 1

Welcher Suchalgorithmus ist für das Auffinden eines Elements in einer sortierten Liste im ungünstigsten Fall am effizientesten?

Accepted Answer

Binäre Suche

Answer

Sequentielle Suche

Answer

Interpolationssuche

Answer

Hashing

Question 2

Welche Datenstruktur ermöglicht den Zugriff auf Elemente in einer bestimmten Reihenfolge mithilfe eines Schlüssels?

Accepted Answer

Hashtabelle

Answer

Array

Answer

Liste

Answer

Graph

Question 3

Welche Datenstruktur eignet sich am besten, um hierarchische Strukturen wie den Organigramm eines Unternehmens darzustellen?

Accepted Answer

Baum

Answer

Array

Answer

Verkettete Liste

Answer

Hashtabelle

Question 4

Welche lineare Datenstruktur folgt dem Prinzip "Last-In-First-Out" (LIFO)?

Accepted Answer

Stack

Answer

Array

Answer

Verkettete Liste

Answer

Binärer Baum

Question 5

Welche Datenstruktur ist durch eine hierarchische Anordnung gekennzeichnet, bei der Elemente in über- und untergeordnete Knoten unterteilt sind?

Accepted Answer

Baum

Answer

Array

Answer

Liste

Answer

Hashtabelle

Question 6

Welche Eigenschaften kennzeichnen binäre Suchbäume?

Accepted Answer

Die Suche nach einem Element hat eine Laufzeitkomplexität von O(log n).

Accepted Answer

Sie sind für die effiziente Speicherung und Verarbeitung sortierter Datenmengen optimiert.

Answer

Sie können leere Teilbäume enthalten.

Answer

Ihre Höhe ist im schlimmsten Fall linear zur Anzahl der gespeicherten Elemente.

Question 7

Welcher Algorithmus hat die höchste Laufzeitkomplexität von O(n!) im ungünstigsten Fall?

Accepted Answer

Fakultätsberechnung (rekursiv)

Answer

Quicksort

Answer

Bubblesort

Answer

Binäre Suche

Question 8

Wie lautet die worst-case Komplexität einer binären Suche in einem sortierten Array mit n Elementen?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 9

Was ist der Hauptzweck der Komplexitätsanalyse von Algorithmen?

Accepted Answer

Untersuchung der Effizienz von Algorithmen in Bezug auf Zeit- und Speicherbedarf

Answer

Bewertung nur sehr komplexer Algorithmen

Answer

Durchführung nur nach Implementierung in einer bestimmten Programmiersprache

Answer

Rein theoretische Überlegung ohne praktischen Nutzen

Question 10

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

Accepted Answer

Baum

Answer

Array

Answer

Liste

Answer

Hashtabelle

Question 11

Welche Datenstruktur ermöglicht das effiziente Hinzufügen und Entfernen von Elementen an beiden Enden und ist eine dynamische, linear geordnete Sammlung?

Accepted Answer

Liste

Answer

Array

Answer

Baum

Answer

Graph

Question 12

Welche Datenstruktur ist ein sortierter Baum mit binärer Suche, bei dem jeder Knoten maximal zwei untergeordnete Knoten haben kann?

Accepted Answer

Binärer Suchbaum (BST)

Answer

Binärbaum

Answer

AVL-Baum

Question 13

Welcher Sortieralgorithmus hat eine worst-case Laufzeit von O(n²), während die anderen eine worst-case Laufzeit von O(n*log(n)) haben?

Accepted Answer

Bubble-Sort

Answer

Heap-Sort

Answer

Merge-Sort

Answer

Quick-Sort

Question 14

Welches ist der primäre Zweck der Worst-Case-Komplexitätsanalyse eines Algorithmus?

Accepted Answer

Eine Obergrenze für die Laufzeit des Algorithmus für alle Eingaben liefern.

Answer

Die kürzeste Laufzeit des Algorithmus für alle Eingaben ermitteln.

Answer

Die durchschnittliche Laufzeit des Algorithmus über alle möglichen Eingaben schätzen.

Question 15

Welche Datenstruktur ist ideal für die hierarchische Organisation von Daten, wobei jedes Element außer dem Stammknoten genau einen übergeordneten Knoten haben kann?

Accepted Answer

Baum

Answer

Array

Answer

Verkettete Liste

Answer

Graph

Question 16

Welche Zeitkomplexität hat die lineare Suche in einem unsortierten Array mit n Elementen?

Accepted Answer

Lineare Zeit (O(n))

Answer

Konstante Zeit (O(1))

Answer

Logarithmische Zeit (O(log n))

Answer

Quadratische Zeit (O(n²))

Question 17

Welche Aussage beschreibt ein grundlegendes Merkmal von Graphen?

Accepted Answer

Ein Graph besteht aus Knoten, die durch Kanten verbunden sind.

Answer

Ein Graph ist immer zusammenhängend.

Answer

Die Kanten eines Graphen haben immer positive Gewichte.

Answer

Ein Baum ist ein ungerichteter Graph.

Question 18

Was ist die beste Definition für Rekursion?

Accepted Answer

Eine Methode, bei der eine Funktion sich selbst aufruft, um ein Problem in kleinere Teile zu zerlegen.

Answer

Eine Methode, die Schleifen verwendet, um ein Problem Schritt für Schritt zu lösen.

Answer

Eine Methode, die nur für Graphprobleme geeignet ist.

Answer

Eine Methode, die immer zu einer Endlosschleife führt.

Question 19

Welche Notation gibt die obere Grenze für die schlechteste Laufzeit eines Algorithmus an?

Accepted Answer

O-Notation

Answer

Ω-Notation

Answer

θ-Notation

Answer

α-Notation

Question 20

Welche der folgenden Aussagen über binäre Suchbäume (BSTs) trifft zu?

Accepted Answer

Die Werte im linken Teilbaum sind immer kleiner als der Wert des aktuellen Knotens.

Accepted Answer

BSTs sind für effiziente Suche und Einfügung optimiert.

Answer

Die Höhe eines BSTs ist immer logarithmisch zur Anzahl der Knoten.

Answer

BSTs sind immer perfekt ausbalanciert.

Question 21

Welcher Traversierungsalgorithmus für binäre Suchbäume erzeugt eine sortierte Liste der Knotenwerte in aufsteigender Reihenfolge?

Accepted Answer

Inorder

Answer

Preorder

Answer

Postorder

Answer

Levelorder

Question 22

Welche Operation ist **nicht** für einen Stack möglich?

Accepted Answer

Element an beliebiger Position abrufen

Answer

Element hinzufügen

Answer

Element entfernen

Answer

Element an der Spitze abrufen

Question 23

Welche lineare Datenstruktur erlaubt den Zugriff auf Elemente nach dem Prinzip "First-In-First-Out" (FIFO)?

Accepted Answer

Warteschlange

Answer

Array

Answer

Verkettete Liste

Answer

Baum

Question 24

Welche maximale Höhe garantiert eine effiziente Suche und Einfügeoperation in einem Binären Suchbaum (BST)?

Accepted Answer

log2(n)

Answer

n

Answer

n^2

Question 25

Welches Sortierverfahren ist besonders effizient für fast vollständig sortierte Listen?

Accepted Answer

Insertionsort

Answer

Quicksort

Answer

Heapsort

Answer

Merge Sort

Question 26

Welche Datenstruktur eignet sich am besten, um die hierarchische Struktur einer Firma zu modellieren, in der Führungskräfte einander unterstellt sind?

Accepted Answer

Baum

Answer

Lineare Liste

Answer

Hashtabelle

Question 27

Welcher der aufgeführten Sortieralgorithmen hat die ungünstigste worst-case-Laufzeitkomplexität?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 28

Welche Datenstruktur ist optimal, um die Anzahl verschiedener Wörter in einem Text zu ermitteln?

Accepted Answer

Hashtabelle

Answer

Array

Answer

Liste

Answer

Baum

Question 29

Welche Aussage beschreibt die Komplexität der binären Suche in einem sortierten Array?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 30

Welche der folgenden Aussagen beschreibt korrekt die Eigenschaft eines binären Suchbaums (BST)?

Accepted Answer

Der linke Teilbaum eines Knotens enthält immer kleinere Werte als der rechte Teilbaum.

Answer

Die Höhe eines BSTs mit n Knoten ist immer kleiner oder gleich n.

Question 31

Welche Aussage zur Effizienz des Sortieralgorithmus Mergesort ist richtig?

Accepted Answer

Mergesort ist ein stabiler Sortieralgorithmus, der die ursprüngliche Reihenfolge gleicher Elemente beibehält.

Answer

Mergesort hat eine worst-case-Komplexität von O(n^2).

Answer

Mergesort ist effizienter als Quicksort für sortierte Daten.

Answer

Mergesort ist ein in-place-Sortieralgorithmus, der keinen zusätzlichen Speicherplatz benötigt.

Question 32

Wie berechnen Sie die Anzahl der internen Knoten (Knoten mit Kindknoten) in einem Binärbaum?

Accepted Answer

Rekursiv den Baum durchlaufen und jeden Knoten zählen, der mindestens ein Kind hat.

Answer

Die Anzahl der Blätter zählen und von der Gesamtzahl der Knoten abziehen.

Answer

Die Höhe des Baums berechnen und von 1 subtrahieren.

Answer

Die Anzahl der Kanten zählen und halbieren.

Question 33

Ein Graph hat **n** Knoten und **m** Kanten. Wie viele Komponenten kann dieser Graph maximal haben?

Accepted Answer

n

Answer

m

Answer

n^2

Answer

m^2

Question 34

Nennen Sie beispielhaft einen Vorteil von Arrays gegenüber verketteten Listen und einen Vorteil von verketteten Listen gegenüber Arrays.

Accepted Answer

Arrays ermöglichen einen schnelleren Zugriff auf Elemente, da sie im Speicher zusammenhängend angeordnet sind.

Accepted Answer

Verkettete Listen sind effizienter beim Einfügen und Löschen von Elementen, da keine Speicherverschiebungen erforderlich sind.

Question 35

Welche Datenstruktur ist für die effiziente Implementierung einer Prioritätswarteschlange am besten geeignet?

Accepted Answer

Heap

Answer

FIFO-Warteschlange

Answer

Hashtabelle

Answer

B-Baum

Question 36

Wie viele Blätter hat ein vollständiger binärer Baum mit der Höhe 'h'?

Accepted Answer

2^h

Answer

2^(h-1)

Answer

h^2

Question 37

Welche Datenstruktur ist optimal für die effiziente Speicherung und den Abruf von Schlüssel-Wert-Paaren?

Accepted Answer

Hashtabelle

Answer

Binärer Suchbaum

Answer

Verkettete Liste

Answer

Array

Question 38

Welche hierarchisch organisierte Datenstruktur ist für die Speicherung geordneter Daten geeignet?

Accepted Answer

Binärer Baum

Answer

Hashtabelle

Answer

Graph

Answer

Array

Question 39

Welche Operation liefert das minimale Element eines binären Suchbaums?

Accepted Answer

Minimum suchen

Answer

Einfügen

Answer

Löschen

Answer

Maximum suchen

Question 40

Welcher Algorithmus eignet sich für die topologische Sortierung eines gerichteten Graphen?

Accepted Answer

Depth-First-Search

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 41

Welche Aufgabe hat eine Hashfunktion in einer Hashtabelle?

Accepted Answer

Berechnung der Adresse eines Elements

Answer

Vergleich von Elementen

Answer

Speicherung von Elementen

Answer

Löschen von Elementen

Question 42

Welche Aussage zur Komplexität von Einfügeoperationen in Hashtabellen ist korrekt?

Accepted Answer

Im Durchschnitt O(1)

Answer

Im schlimmsten Fall O(log n)

Answer

Im Durchschnitt O(n²)

Answer

Im schlimmsten Fall O(n!)

Question 43

Welcher Algorithmus findet die kürzeste Distanz zwischen zwei Knoten in einem gewichteten, ungerichteten Graphen?

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Prim-Algorithmus

Question 44

Welcher Suchalgorithmus hat eine Komplexität von O(log n) für sortierte Listen?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashing

Question 45

Welcher Unterschied besteht zwischen einem binären Suchbaum und einem AVL-Baum?

Accepted Answer

AVL-Bäume sind immer balanciert, binäre Suchbäume können unausgewogen sein.

Answer

Binäre Suchbäume sind immer balanciert, AVL-Bäume können unausgewogen sein.

Answer

AVL-Bäume sind effizienter beim Einfügen, binäre Suchbäume beim Suchen.

Answer

Binäre Suchbäume sind effizienter beim Einfügen, AVL-Bäume beim Suchen.

Question 46

Welche Datenstruktur ist optimal für die Abbildung einer Hierarchie, in der jedes Element außer dem obersten mehrere übergeordnete Elemente haben kann?

Accepted Answer

gerichteter azyklischer Graph

Answer

Heap

Answer

Binärer Suchbaum

Answer

Hashtabelle

Question 47

Welcher der folgenden Vorteile trifft NICHT auf Bäume im Vergleich zu linearen Datenstrukturen zu?

Accepted Answer

Zugriff in konstanter Zeit

Answer

Schnelle Suche

Answer

Effizientes Einfügen und Löschen

Answer

Hierarchische Organisation

Question 48

Welche Datenstruktur nutzt eine Hashfunktion für die effiziente Speicherung und den Abruf von Elementen?

Accepted Answer

Hashtabelle

Answer

Feld

Answer

Liste

Answer

Baum

Question 49

Welche der folgenden Optionen ist KEIN Sortieralgorithmus?

Accepted Answer

Binäre Suche

Answer

QuickSort

Answer

MergeSort

Answer

BubbleSort

Question 50

Welche Datenstruktur wird für die Speicherung einer Menge von Elementen ohne Duplikate verwendet?

Accepted Answer

Menge

Answer

Feld

Answer

Liste

Answer

Hashtabelle

Question 51

Welches der folgenden Kriterien dient NICHT der Bewertung der Effizienz eines Algorithmus?

Accepted Answer

Verlässlichkeit

Answer

Zeitkomplexität

Answer

Raumkomplexität

Answer

Korrektheit

Question 52

Welche Datenstruktur eignet sich am besten für die Organisation hierarchischer Daten?

Accepted Answer

Baum

Answer

Liste

Answer

Graph

Answer

Feld

Question 53

Welcher Suchalgorithmus hat eine Laufzeit von O(n*log(n)) für ein sortiertes Array?

Accepted Answer

Binäre Suche

Answer

Sequentielle Suche

Answer

Hashtabelle

Question 54

Welche der folgenden Eigenschaften trifft auf die Einfügeoperation in einer Hashtabelle am besten zu?

Accepted Answer

Konstante Laufzeitkomplexität von O(1) für das Einfügen

Answer

Immer erforderlich, eine sequentielle Suche zur Bestimmung der Einfügeposition durchzuführen

Answer

Nur in Tabellen mit fester Größe möglich

Answer

Erfordert eine aufwendige Nachsortierung der Tabelle nach jedem Einfügen

Question 55

Welche Komplexität hat das Einfügen in einen AVL-Baum?

Accepted Answer

O(log(n))

Answer

O(1)

Answer

O(n)

Question 56

Beschreiben Sie die Struktur und Funktionsweise einer Skip-Liste.

Accepted Answer

Eine Skip-Liste ist eine mehrstufige, zufällige Datenstruktur, bei der Elemente mit einer Wahrscheinlichkeit von 50 % auf die nächste Ebene abgebildet werden.

Answer

Eine Skip-Liste ist ein balancierter binärer Suchbaum mit zusätzlichen Ebenen.

Answer

Skip-Listen nutzen Hashing, um Konflikte bei der Einfügung zu lösen.

Answer

Die Suchkomplexität in einer Skip-Liste ist linear zur Anzahl der Elemente.

Question 57

Wie funktioniert der Ansatz des dynamischen Programmierens bei der Lösung von Optimierungsproblemen?

Accepted Answer

Aufteilung des Problems in kleinere Teilprobleme und Speicherung der optimalen Lösungen in einer Tabelle

Answer

Durchsuchen aller möglichen Lösungen mit einem Entscheidungsbaum

Answer

Ausprobieren aller Kombinationsmöglichkeiten mit Brute-Force-Methoden

Question 58

Wie beeinflusst die Anzahl der Elemente in einer Hashtabelle die Wahrscheinlichkeit von Kollisionen?

Accepted Answer

Die Wahrscheinlichkeit von Kollisionen nimmt zu, wenn mehr Elemente in der Hashtabelle sind.

Answer

Die Wahrscheinlichkeit von Kollisionen nimmt ab, wenn mehr Elemente in der Hashtabelle sind.

Answer

Die Wahrscheinlichkeit von Kollisionen ist unabhängig von der Anzahl der Elemente in der Hashtabelle.

Answer

Durch die Verwendung einer perfekten Hashfunktion können Kollisionen vollständig vermieden werden.

Question 59

Welche Komplexität hat die Einfügeoperation in einen AVL-Baum im ungünstigsten Fall?

Accepted Answer

O(log(n))

Answer

O(1)

Answer

O(n)

Question 60

In welchen Anwendungsfällen sind Binäre Suchbäume gegenüber Hashtabellen vorzuziehen? Begründen Sie Ihre Antwort.

Accepted Answer

Wenn die Daten sortiert eingefügt und durchsucht werden sollen.

Answer

Wenn die Daten nach mehreren Schlüsseln durchsucht werden sollen.

Answer

Wenn die Daten häufig eingefügt und gelöscht werden sollen.

Answer

Wenn die Daten sehr groß sind.

Question 61

Wie geht man bei der dynamischen Programmierung vor, um komplexe Optimierungsprobleme zu lösen?

Accepted Answer

Das Problem in kleinere Teilprobleme zerlegen, diese rekursiv lösen und die Lösungen zur späteren Wiederverwendung speichern

Answer

Einen gierigen Algorithmus verwenden, um sich schrittweise der optimalen Lösung anzunähern

Answer

Eine Entscheidungsbaumstruktur erstellen, um alle möglichen Lösungen zu berücksichtigen

Answer

Ein neuronales Netzwerk trainieren, um die optimale Lösung zu finden

Question 62

Wie beeinflusst die Höhe eines AVL-Baumes die Laufzeitkomplexität von Einfüge- und Suchoperationen?

Accepted Answer

Die Komplexität steigt logarithmisch mit der Höhe des Baumes.

Answer

Die Komplexität steigt linear mit der Höhe des Baumes.

Answer

Die Komplexität der Einfügeoperation ist unabhängig von der Höhe des Baumes.

Answer

Die Komplexität der Suchoperation ist unabhängig von der Höhe des Baumes.

Question 63

Wie beeinflusst der Ladefaktor die Effizienz einer Hashtabelle? Erläutern Sie die Vor- und Nachteile verschiedener Kollisionsbehandlungsmethoden.

Accepted Answer

Ein hoher Ladefaktor erhöht die Wahrscheinlichkeit von Kollisionen, was die Suche und das Einfügen verlangsamt.

Accepted Answer

Ein niedriger Ladefaktor verringert die Wahrscheinlichkeit von Kollisionen und verbessert so die Effizienz der Hashtabelle.

Answer

Die Kollisionsbehandlungsstrategie hat keinen Einfluss auf die Effizienz der Hashtabelle.

Question 64

Welche Datenstruktur ist eine hierarchische Anordnung von Elementen?

Accepted Answer

Baum

Answer

Hashtabelle

Answer

Stapel

Answer

Liste