Klausurfragen

Question 1

Welche Datenstruktur benutzt ihre CPU ausschliesslich

Answer 1

Stack

Question 2

Unterschied Dynamische, Statische Menge

Answer 2

Statische Menge:

Definition: Unveränderliche Sammlung von Elementen.
Eigenschaften: Feste Größe, keine Änderung der Elemente möglich.
Beispiele: Feste Arrays.

Dynamische Menge:
Definition: Veränderbare Sammlung von Elementen.
Eigenschaften: Variable Größe, Elemente können hinzugefügt oder entfernt werden.
Beispiele: Listen (z.B. ArrayList in Java, List in Python).

Question 3

Warum Stack

Answer 3

• Computer verfolgt LIFO-Strategie beim Berechnen
• Schnelligkeit

Question 4

Wie können so viele Threads parallel laufen

Answer 4

Scheduler, Jeder Thread hat
seinen eigenen Stack

Question 5

Sie möchten durch Insert-Sort ein aufsteigend sortiertes Feld aufsteigend sortieren. Geht das Schneller

Answer 5

Ja

Question 6

Zwei Kriterien zur Bestimmung von Sortieralgorithmen

Answer 6

• Speicherplatz
• Laufzeit

Question 7

Weiteres Kriterium zur Bestimmung von Sortieralgorithmen

Answer 7

Stabilität

Question 8

Welcher Sortieralgorithmus sortiert nicht selber

Answer 8

RadixSort: Sortierung nach Stellen

Question 9

Die Breitensuche Erreicht auf jeden Fall alle Knoten ?

Answer 9

Nein

Wo steht das im Code ? : Codezeile 0 = Expliziter Startknoten (s)

Question 10

Breitensuche schneller als Tiefensuche

Answer 10

Shortest Path: BFS
Worst Time: O(V+E)
Ergebnis näher an der Wurzel: BFS schneller
Ergebnis tiefer im Graph: DFS schneller

Question 11

Was sind die Eigeenschaften die einen systematische
Graphendurchsuchungsalgorithmus vollständig machen

Answer 11

• Alle Knoten Werden untersucht
• Nicht Lost in Zyklus
• Nicht Lost in Tiefenpfaden

Question 12

Wann werden gpopte Elemente gelöscht

Answer 12

Wenn neue Elemente über Push() eingefügt werden (überschrieben werden)

Question 13

Wie viele Elemente können auf einem Stack oder in einer Queue gespeichert werden ?

Answer 13

-> Stack = N-Elemente
-> Queue = N-1 Elemente

Question 14

Warum benutzen wir Hashfunktionen bei Rabin Karp

Answer 14

Damit die Zahlen nicht so groß werden & Speicherplatz gespart wird. Laufzeitverlust durch Divisionsmethode, Doppelungen ohne Hash möglich

Question 15

Wie viele Aktzeptierte Zustände hat ein NEA beim String matching

Answer 15

genau einen

Question 16

Wie ist die Basis des Hornerschemas bei ASCII

Answer 16

128 Bit

Question 17

Welcher String-Matching Algorithmus hat die längste Vorbereitungszeit

Answer 17

NEA/DEA Endlicher Automat

Question 18

Was sind abstrakte Datenstrukturen

Answer 18

Abstrakte Datenstrukturen (ADS) sind konzeptionelle Modelle zur Organisation und Verwaltung von Daten, unabhängig von ihrer konkreten Implementierung. Sie definieren Operationen und Regeln für den Umgang mit den Daten. Beispiele für ADS sind:

Listen (Lists): Geordnete Sammlung von Elementen, z.B. Arrays, verkettete Listen.
Stapel (Stacks): LIFO-Prinzip (Last In, First Out), z.B. Push, Pop.
Warteschlangen (Queues): FIFO-Prinzip (First In, First Out), z.B. Enqueue, Dequeue.
Bäume (Trees): Hierarchische Struktur aus Knoten, z.B. Binärbaum.
Graphen (Graphs): Knoten und Kanten, die Beziehungen darstellen, z.B. gerichtet oder ungerichtet.
Hashtabellen (Hash Tables): Schlüssel-Wert-Paare mit schneller Zugriffsmöglichkeit.
Mengen (Sets): Ungeordnete Sammlung eindeutiger Elemente.

 Ein ADT bestehen aus Objekten und darauf definieren Funktionen.
 Realisierung ist vor dem Nutzer (Client) verborgen

Beispiele
 Stapel (Stack)
 Warteschlangen (Queue)

Beispiele Python
 set (Repräsentation von Mengen)
 list (Repräsentation von Listen)
 class (zur Erstellung neuer Klassen/ADTs)