Diskrete Mathematik: Grundlagen und Anwendungen in der Informatik

Question 1

Welche Aussage zur Mengenlehre ist richtig?

Accepted Answer

Die leere Menge ist eine Teilmenge jeder Menge.

Accepted Answer

Die Potenzmenge einer Menge ist die Menge aller Teilmengen dieser Menge.

Answer

Die Vereinigung zweier Mengen ist immer eine Teilmenge ihres Durchschnitts.

Answer

Eine Menge kann sich selbst als Element enthalten.

Question 2

Welche Aussage trifft NICHT auf einen ungerichteten Graphen zu?

Accepted Answer

Jeder Kreis im Graphen muss eine gerade Anzahl von Kanten haben.

Answer

Jeder Knoten hat einen Grad, der der Anzahl der ihn verbindenden Kanten entspricht.

Answer

Jeder Graph kann durch eine Adjazenzmatrix dargestellt werden.

Answer

Ein vollständiger Graph mit n Knoten hat n(n-1)/2 Kanten.

Question 3

Welche Eigenschaft beschreibt die Transitivität einer Relation?

Accepted Answer

Wenn (a, b) und (b, c) zur Relation gehören, dann gehört auch (a, c) zur Relation.

Answer

Wenn (a, b) zur Relation gehört, dann gehört auch (b, a) zur Relation.

Answer

Wenn (a, a) zur Relation gehört, dann ist die Relation transitiv.

Answer

Wenn (a, b) und (b, a) zur Relation gehören, dann gehört auch (a, a) zur Relation.

Question 4

Welche Aussage trifft **immer** auf endliche Graphen zu?

Accepted Answer

Die Anzahl der Kanten ist kleiner oder gleich der Anzahl der Ecken.

Answer

Die Anzahl der Ecken ist mindestens doppelt so groß wie die Anzahl der Kanten.

Answer

Der Graph ist immer zusammenhängend.

Answer

Der Graph hat immer einen Eulerkreis.

Question 5

Welche Aussage trifft **nicht** auf die Diskrete Mathematik zu?

Accepted Answer

Sie beinhaltet die Berechnung von Integralen und Ableitungen.

Answer

Sie untersucht endliche oder abzählbare Mengen.

Answer

Sie nutzt diskrete Strukturen wie Graphen und Logik.

Answer

Sie hat Anwendungen in der Informatik und anderen Gebieten.

Question 6

Welche Eigenschaften treffen auf Funktionen f: A → B zu?

Accepted Answer

Das Urbild eines Elements aus B kann leer sein.

Accepted Answer

Das Bild eines Elements aus A ist eindeutig.

Accepted Answer

Eine Funktion ist surjektiv, wenn ihr Bild gleich B ist.

Answer

Die Umkehrfunktion einer injektiven Funktion ist immer surjektiv.

Question 7

Eine Menge A enthält n Elemente. Wie viele Teilmengen hat die Menge A?

Accepted Answer

2^n

Answer

n

Answer

n^2

Answer

n!

Question 8

Welche Aussage über Relationen ist richtig?

Accepted Answer

Eine Relation ist eine Teilmenge des kartesischen Produkts zweier Mengen.

Answer

Eine Relation ist immer reflexiv.

Answer

Eine Relation ist immer antisymmetrisch.

Answer

Eine Relation ist immer transitiv.

Question 9

Welche Eigenschaft trifft **nicht** auf eine Relation zu?

Accepted Answer

Asymmetrie: Wenn Element a zu Element b in Relation steht, so steht Element b **nicht** zu Element a in Relation.

Answer

Reflexivität: Jedes Element steht in Relation zu sich selbst.

Answer

Transitivität: Wenn Element a zu Element b und Element b zu Element c in Relation steht, so steht auch Element a zu Element c in Relation.

Answer

Symmetrie: Wenn Element a zu Element b in Relation steht, so steht auch Element b zu Element a in Relation.

Question 10

Die Goldbachsche Vermutung besagt, dass jede gerade Zahl ab 4:

Accepted Answer

als Summe zweier Primzahlen dargestellt werden kann.

Answer

als Summe von zwei ungeraden Zahlen dargestellt werden kann.

Answer

größer als 1 ist.

Answer

durch 3 teilbar ist.

Question 11

Welche Menge ergibt sich aus der Differenzmenge von A = {1, 2, 3} und B = {2, 4, 6}?

Accepted Answer

{1, 3}

Answer

{2, 4, 6}

Answer

{1, 2, 4, 6}

Answer

{3}

Question 12

Welche Eigenschaft ist charakteristisch für einen vollständigen Graphen?

Accepted Answer

Jeder Knoten ist mit allen anderen Knoten verbunden.

Answer

Der Graph ist zusammenhängend, aber nicht vollständig.

Answer

Die Anzahl der Kanten ist kleiner als die Anzahl der Knoten.

Question 13

Welche Aussage beschreibt das Gesetz der ausgeschlossenen Mitte?

Accepted Answer

Entweder ist es Montag oder nicht.

Answer

Alle Katzen sind grün.

Answer

Wenn es regnet, wird die Straße nass.

Question 14

Welche der folgenden Eigenschaften trifft auf die Vereinigung von Mengen **nicht** zu?

Accepted Answer

Die Vereinigung zweier Mengen ist immer eine Teilmenge der beiden Mengen.

Answer

Die Vereinigung zweier Mengen ist die Menge aller Elemente, die in mindestens einer der beiden Mengen enthalten sind.

Answer

Die Vereinigung zweier Mengen ist kommutativ, d.h. A ∪ B = B ∪ A.

Answer

Die Vereinigung zweier Mengen ist assoziativ, d.h. (A ∪ B) ∪ C = A ∪ (B ∪ C).

Question 15

Was ist die korrekte Definition der reflexiven Hülle einer Relation R?

Accepted Answer

Die Menge aller Paare (a, a) mit a aus der Grundmenge von R

Answer

Die Menge aller Paare (a, b) mit a und b aus der Grundmenge von R und a ≠ b

Answer

Die Menge aller Paare (a, b) mit a und b aus der Grundmenge von R

Answer

Die Menge aller Paare (a, a) mit a aus der Bildmenge von R

Question 16

Welche der folgenden Aussagen trifft auf die leere Menge zu?

Accepted Answer

Sie ist in jeder nicht-leeren Menge enthalten.

Answer

Sie umfasst alle Elemente des Universums.

Answer

Ihre Anzahl ist größer als 1.

Question 17

Welche Aussage beschreibt eine Bijektion?

Accepted Answer

Eine Abbildung, die injektiv und surjektiv ist.

Answer

Eine Abbildung, die nur injektiv ist.

Answer

Eine Abbildung, die nur surjektiv ist.

Answer

Eine Abbildung, die weder injektiv noch surjektiv ist.

Question 18

Was ist eine Tautologie in der Aussagenlogik?

Accepted Answer

Eine Aussage, die für alle möglichen Kombinationen von Wahrheitswerten ihrer Variablen wahr ist.

Answer

Eine Aussage, die für mindestens eine Kombination von Wahrheitswerten ihrer Variablen wahr ist.

Answer

Eine Aussage, die für keine Kombination von Wahrheitswerten ihrer Variablen wahr ist.

Answer

Eine Aussage, deren Wahrheitswert von der jeweiligen Zuweisung von Wahrheitswerten zu ihren Variablen abhängt.

Question 19

Welche Menge ergibt sich aus der symmetrischen Differenz von A = {1, 2, 3} und B = {2, 3, 4}? Die symmetrische Differenz enthält alle Elemente, die nur in einer der beiden Mengen vorkommen.

Accepted Answer

{1, 4}

Answer

{1, 2, 3, 4}

Answer

{2, 3}

Answer

{∅}

Question 20

Welche Aussage ist eine logisch gültige Schlussfolgerung aus den Aussagen "Alle Menschen sind sterblich" und "Sokrates ist ein Mensch"?

Accepted Answer

Sokrates ist sterblich.

Answer

Alle Menschen sind Sokrates.

Answer

Einige Menschen sind unsterblich.

Answer

Sokrates ist unsterblich.

Question 21

Was zeichnet einen bipartiten Graphen aus?

Accepted Answer

Knoten lassen sich in zwei Gruppen aufteilen, wobei Kanten nur zwischen Knoten verschiedener Gruppen verlaufen.

Answer

Kann sowohl gerichtete als auch ungerichtete Kanten haben.

Answer

Jeder Knoten ist mit jedem anderen Knoten verbunden.

Answer

Enthält keine Zyklen.

Question 22

Was ist die grundlegende Definition einer Turingmaschine?

Accepted Answer

Ein abstraktes Computermodell mit unendlichem Band, Schreib-/Lesekopf und endlichen Anweisungen.

Answer

Ein physisches Gerät zur Ausführung beliebiger Berechnungen in begrenzter Zeit.

Answer

Ein Algorithmus, der in einer bestimmten Programmiersprache implementiert ist.

Answer

Eine hypothetische Maschine, die das menschliche Gehirn nachahmt.

Question 23

Was ist die beste Definition einer Relation?

Accepted Answer

Eine Teilmenge des kartesischen Produkts zweier Mengen, die Elemente miteinander verknüpft.

Answer

Eine Eigenschaft, die alle Elemente einer Menge teilen.

Answer

Eine Funktion, die jedem Element einer Menge einen eindeutigen Wert in einer anderen Menge zuordnet.

Answer

Eine Menge, die unter bestimmten Operationen abgeschlossen ist.

Question 24

Welche Probleme werden in der Komplexitätstheorie durch die Klasse P repräsentiert?

Accepted Answer

Mit einer deterministischen Turingmaschine in polynomialer Zeit lösbar

Answer

Mit einer nichtdeterministischen Turingmaschine in linearer Zeit lösbar

Answer

Mit einer deterministischen Turingmaschine in konstanter Zeit lösbar

Answer

Mit einer nichtdeterministischen Turingmaschine in exponentieller Zeit lösbar

Question 25

Welcher Aspekt ist **kein** zentraler Bestandteil der Komplexitätstheorie?

Accepted Answer

Entwicklung effizienter Algorithmen

Answer

Analyse der asymptotischen Komplexität von Algorithmen

Answer

Einteilung von Problemen in Komplexitätsklassen

Answer

Untersuchung der Algorithmuskomplexität für unterschiedliche Eingabedaten

Question 26

Welche Aussage beschreibt eine Bijektion korrekt?

Accepted Answer

(a) Eine Funktion, die injektiv und surjektiv ist.

Answer

(b) Eine Funktion, die injektiv ist.

Answer

(c) Eine Funktion, die surjektiv ist.

Answer

(d) Eine Funktion, die weder injektiv noch surjektiv ist.

Question 27

Eine endliche Menge hat n Elemente. Wie verhält sich die Anzahl der Teilmengen mit ungerader Mächtigkeit zur Gesamtzahl der Teilmengen dieser Menge?

Accepted Answer

Die Anzahl der Teilmengen mit ungerader Mächtigkeit ist halb so groß wie die Gesamtzahl der Teilmengen.

Answer

Die Anzahl der Teilmengen mit ungerader Mächtigkeit ist größer als die Hälfte der Gesamtzahl der Teilmengen.

Answer

Die Anzahl der Teilmengen mit ungerader Mächtigkeit ist kleiner als die Hälfte der Gesamtzahl der Teilmengen.

Question 28

Was ist eine rekursive Sprache? Erkläre, warum rekursive Sprachen in der Berechenbarkeitstheorie wichtig sind.

Accepted Answer

Eine rekursive Sprache wird durch Regeln definiert, die sich selbst wiederholen.

Answer

Eine rekursive Sprache wird durch eine begrenzte Anzahl von Wörtern definiert.

Answer

Eine rekursive Sprache wird durch eine Reihe von Symbolen definiert.

Answer

Eine rekursive Sprache wird durch eine kontextsensitive Grammatik definiert.

Question 29

Wie viele Kanten hat ein vollständiger Graph mit n Knoten?

Accepted Answer

n(n+1)/2

Answer

n

Answer

n-1

Answer

n+1

Question 30

Frage zur Entscheidbarkeitstheorie:

Was ist ein entscheidbarer Satz? Nenne ein Beispiel und erläutere die praktische Bedeutung der Entscheidbarkeit in der Informatik.

Accepted Answer

Ein entscheidbarer Satz ist ein Satz, der durch einen Algorithmus in endlicher Zeit entschieden werden kann.

Answer

Ein entscheidbarer Satz ist ein Satz, der in allen Modellen wahr ist.

Answer

Ein entscheidbarer Satz ist ein Satz, der in allen Interpretationen wahr ist.

Answer

Ein entscheidbarer Satz ist ein Satz, der in höchstens einer Interpretation wahr ist.

Question 31

Kardinalität endlicher Mengen:

Was ist die Kardinalität einer endlichen Menge? Erläutere, wie man die Kardinalität endlicher Mengen mithilfe von Mengenoperationen berechnet.

Accepted Answer

Die Kardinalität einer endlichen Menge ist die Anzahl ihrer Elemente.

Answer

Die Kardinalität einer endlichen Menge ist die Anzahl ihrer Teilmengen.

Answer

Die Kardinalität einer endlichen Menge ist die Summe ihrer Elemente.

Answer

Die Kardinalität einer endlichen Menge ist die Anzahl ihrer Elemente, die größer als 0 sind.

Question 32

Welches ist das Hauptziel der Kryptographie?

Accepted Answer

Informationen vor unbefugtem Zugriff schützen

Answer

Kommunikation zwischen zwei Parteien ohne Zuhörer ermöglichen

Answer

Authentifizierung von Benutzern und Systemen gewährleisten

Answer

Die Leistung von Computersystemen optimieren

Question 33

Erläutern Sie das Konzept einer Turingmaschine. Beschreiben Sie ihre Bestandteile und Funktionsweise anhand eines einfachen Beispiels.

Accepted Answer

Eine Turingmaschine ist ein abstraktes Modell der Berechnung, bestehend aus einem unendlichen Band, einem Lese-/Schreibkopf und einem endlichen Satz von Anweisungen.

Answer

Eine Turingmaschine ist ein physisches Gerät, das zur Ausführung von Programmen dient.

Answer

Eine Turingmaschine ist ein Algorithmus mit einer begrenzten Anzahl von Anweisungen.

Question 34

Erläutern Sie die Konzepte abzählbarer und überabzählbarer Mengen und nennen Sie jeweils ein Beispiel.

Accepted Answer

Abzählbare Mengen: Mengen, deren Elemente sich eins-zu-eins den natürlichen Zahlen zuordnen lassen. Beispiel: Die Menge der natürlichen Zahlen.

Accepted Answer

Überabzählbare Mengen: Mengen, deren Elemente sich nicht eins-zu-eins den natürlichen Zahlen zuordnen lassen. Beispiel: Die Menge der reellen Zahlen.

Answer

Abzählbare Mengen sind endlich oder unendlich. Überabzählbare Mengen sind unendlich.

Answer

Abzählbare Mengen sind endlich. Überabzählbare Mengen sind unendlich.

Question 35

Was ist das modulare Rechnen und wie wird es in der Kryptographie eingesetzt?

Accepted Answer

Das modulare Rechnen berechnet Reste bei der Division durch eine bestimmte Zahl.

Answer

Das modulare Rechnen berechnet Primzahlen.

Answer

Das modulare Rechnen berechnet Logarithmen.

Answer

Das modulare Rechnen berechnet Wahrscheinlichkeiten.

Question 36

Welche Axiome legen die grundlegenden Eigenschaften von Graphen fest? Erläutern Sie ihre Bedeutung für die präzise Definition eines Graphen.

Accepted Answer

Axiom 1: Ein Graph G ist ein Paar (V, E) aus einer nichtleeren Menge V von Knoten und einer Menge E von Kanten.

Accepted Answer

Axiom 2: Jede Kante e in E ist ein Paar (v, w) von Knoten in V.

Accepted Answer

Axiom 3: Die Nachbarschaft eines Knotens v in V ist die Menge aller Kanten, die v enthalten.

Question 37

Definiere den Begriff planarer Graphen und nenne die notwendigen Bedingungen, die erfüllen sein müssen, damit ein Graph planar ist. Führe Beispiele für planare und nicht-planare Graphen an.

Accepted Answer

Ein planarer Graph ist ein Graph, der in einer Ebene gezeichnet werden kann, ohne dass sich Kanten schneiden.

Answer

Ein planarer Graph ist ein Graph, der keine geschlossenen Pfade enthält.

Answer

Ein planarer Graph ist ein Graph, der keine Kreise enthält.

Answer

Ein planarer Graph ist ein Graph, der keine Brücken enthält.

Question 38

Wie trägt die Aussagenlogik zur Analyse und zum Entwurf digitaler Schaltungen bei?

Accepted Answer

Sie bietet eine präzise Sprache zur Beschreibung der Schaltkreisfunktion und ermöglicht eine systematische Analyse und Synthese.

Answer

Sie dient ausschließlich der Fehlerbehebung in digitalen Schaltungen.

Answer

Sie spielt keine wesentliche Rolle im Entwurf digitaler Schaltungen.

Question 39

Welche logische Verknüpfung repräsentiert das exklusive ODER?

Accepted Answer

⊕

Answer

∧

Answer

∨

Answer

→

Question 40

Welche der folgenden Mengen ist eine Äquivalenzrelation?

Accepted Answer

Die Menge aller Beziehungen, die reflexiv, symmetrisch und transitiv sind

Answer

Die Menge aller Teilmengen einer gegebenen Menge

Answer

Die Menge aller geraden Zahlen

Answer

Die Menge aller Mengen, die mehr als 5 Elemente enthalten

Question 41

Wie viele Kanten besitzt ein vollständiger Graph mit n Knoten?

Accepted Answer

n(n-1)/2

Answer

n

Answer

n-1

Answer

n^2

Question 42

Welche der folgenden Aussagen über Permutationen ist falsch?

Accepted Answer

Es gibt gleich viele gerade und ungerade Permutationen von n Elementen.

Answer

Die Anzahl der Permutationen von n Elementen beträgt n!

Answer

Eine Permutation ist eine bijektive Abbildung einer Menge auf sich selbst.

Answer

Eine Permutation kann aus Zyklen bestehen.

Question 43

Welchen Grad hat das Polynom x^3 + 2x^2 - 5x + 1?

Accepted Answer

3

Answer

1

Answer

2

Answer

4

Question 44

Welche der folgenden Funktionen ist eine lineare Abbildung?

Accepted Answer

f(x) = 2x + 1

Answer

f(x) = x^2

Answer

f(x) = sin(x)

Answer

f(x) = e^x

Question 45

Was ist der Algorithmus von Dijkstra?

Accepted Answer

Ein Algorithmus, der den kürzesten Weg in einem gewichteten Graphen berechnet.

Answer

Ein Algorithmus, der ein Array sortiert.

Answer

Ein Algorithmus, der einen Hamiltonschen Zyklus in einem Graphen findet.

Answer

Ein Algorithmus, der die konvexe Hülle einer Menge von Punkten berechnet.

Question 46

Was sind die zentralen Ideen der Berechenbarkeitstheorie und wie beeinflussen sie die Grenzen der Computerberechnung?

Accepted Answer

Sie untersucht, welche Probleme Computer lösen können und welche nicht.

Answer

Sie hat nur theoretische Bedeutung und keine praktischen Auswirkungen.

Answer

Sie gilt nur für Algorithmen mit endlicher Laufzeit.

Question 47

Welche grundlegende Rolle spielt die diskrete Mathematik, insbesondere ihre Konzepte und Techniken, bei der Entwicklung und Analyse von Algorithmen?

Accepted Answer

Sie bietet Werkzeuge zur formalen Beschreibung und Analyse der Algorithmusstruktur, einschließlich ihrer Zeit- und Speicherkomplexität.

Accepted Answer

Sie ermöglicht die Modellierung von Problemen mithilfe diskreter Strukturen wie Graphen oder kombinatorischer Objekte.

Answer

Sie ist auf die Analyse von sequentiellen Algorithmen beschränkt und hat keine Bedeutung für parallele oder verteilte Algorithmen.

Answer

Sie ist rein theoretisch und hat keine praktische Relevanz für die Algorithmik.

Question 48

Welche der folgenden Aussagen über Mengen ist **nicht** korrekt?

Accepted Answer

Die Vereinigungsmenge zweier Mengen ist immer nicht leer.

Answer

Die Differenz zweier Mengen ist die Menge der Elemente, die nur in der ersten Menge enthalten sind.

Answer

Der Durchschnitt zweier Mengen ist eine Teilmenge beider Mengen.

Question 49

Wie viele Teilmengen können aus einer Menge mit n Elementen gebildet werden?

Accepted Answer

2 hoch n

Answer

n!

Answer

n hoch 2

Answer

n

Question 50

Welche der folgenden Aussagen über Boolesche Algebra ist **falsch**?

Accepted Answer

Das Kommutativgesetz gilt für die XOR-Operation.

Answer

Das Assoziativgesetz gilt für die AND-Operation.

Answer

Das Distributivgesetz gilt für die OR-Operation über die AND-Operation.

Answer

Das De-Morgan-Gesetz gilt sowohl für die AND- als auch für die OR-Operation.

Question 51

Welche der folgenden Aussagen über Relationen ist **korrekt**?

Accepted Answer

Eine Relation ist eine Teilmenge des kartesischen Produkts der beteiligten Mengen.

Answer

Eine Relation ist immer reflexiv.

Answer

Eine Relation ist immer symmetrisch.

Question 52

Welcher der folgenden Algorithmen ist für die Suche eines Elements in einer sortierten Liste am effizientesten?

Accepted Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Hash-Suche

Answer

Lineare Suche

Question 53

Welcher der folgenden Begriffe beschreibt eine Sprache, die durch reguläre Ausdrücke erkannt werden kann?

Accepted Answer

Reguläre Sprache

Answer

Rekursiv aufzählbare Sprache

Answer

Turing-vollständige Sprache

Answer

Kontextfreie Sprache

Question 54

Welche der folgenden Aussagen über endliche Automaten ist **nicht** korrekt?

Accepted Answer

Endliche Automaten können alle Sprachen erkennen.

Answer

Endliche Automaten können deterministisch oder nichtdeterministisch sein.

Answer

Endliche Automaten können durch reguläre Ausdrücke beschrieben werden.

Answer

Endliche Automaten haben eine endliche Anzahl von Zuständen.

Question 55

Wie viele Kanten hat ein vollständiger Graph mit n Knoten?

Accepted Answer

n * (n - 1) / 2

Answer

n * n - 1

Answer

n * (n - 2) / 2

Answer

n * (n + 1) / 2

Question 56

Wie viele Permutationen gibt es für eine Menge mit k Elementen?

Accepted Answer

k!

Answer

2^k

Answer

k^(k-1)

Answer

k*(k-1)

Question 57

Wie viele Wege gibt es, um eine Gruppe von n Personen in zwei Teams mit der gleichen Anzahl von Personen aufzuteilen?

Accepted Answer

C(n, n/2)

Answer

P(n, n/2)

Answer

2^n

Question 58

Welcher Graph ist ein bipartiter Graph?

Accepted Answer

Ein Graph, dessen Knotenmenge in zwei disjunkte Teilmengen partitioniert werden kann, sodass jede Kante zwischen Knoten aus verschiedenen Teilmengen verläuft.

Answer

Ein Graph, der keine Kreise enthält.

Question 59

Welche Aussage über die asymptotische Schranke Big-O beschreibt ihr Verhalten am besten?

Accepted Answer

Sie gibt eine obere Schranke für das Wachstumsverhalten einer Funktion an.

Answer

Sie beschreibt genau das Wachstumsverhalten einer Funktion.

Answer

Sie gibt eine untere Schranke für das Wachstumsverhalten einer Funktion an.

Question 60

Welcher der folgenden Graphen ist ein Baum?

Accepted Answer

Ein Graph ohne Zyklen.

Answer

Ein Graph mit genau einer Komponente.

Answer

Ein Graph mit Eulerpfad.

Answer

Ein Graph mit gerader Anzahl von Knoten.

Question 61

Wie viele Möglichkeiten gibt es, 5 Personen in **einer Reihe** zu stellen?

Accepted Answer

120

Answer

60

Answer

24

Answer

360

Question 62

Welcher der folgenden Algorithmen hat eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 63

Welche der folgenden Datenstrukturen ist eine Liste?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Hashtabelle

Answer

Baum

Question 64

Welcher der folgenden Compiler erzeugt Java-Bytecode?

Accepted Answer

javac

Answer

python

Answer

make

Answer

gcc