Fragen zur Praktischen Informatik

 Praktische Informatik

WAHR

FALSCH

Lineare Suche ist in jedem Fall schlechter als binäre Suche

x

Die Zeiteffizienz der linearen Suche ist O(n)

x

Interpolationssuche arbeitet dann besonders günstig, wenn die Schlüsselwege sehr ungleichmäßig verteilt sind

x

Vollständig ausgeglichene Bäume haben immer (2^h-1)/(k-1) Knoten, wobei H die Höhe und k die Anzahl der Söhne je innerem Knoten ist

x

Vollständig ausgeglichene Bäume haben immer (k^h-1)/(k-1) Knoten, wobei H die Höhe und k die Anzahl der Söhne je innerem Knoten ist

x

Jeder Knoten eines k-beschränkten Baumes muss k Kinder haben

x

Jeder Knoten eines k-beschränkten Baumes darf nicht mehr als k Kinder haben

x

Ein ungerichteter Graph ist immer zusammenhängend

x

Ein Graph heißt stark zusammenhängend, wenn ein beliebiger Knoten entfernt weden kann, ohne dass der restliche Graph in unzusammenhängende Komponenten zerfällt

x

Jeder azyklische Graph ist ein Baum

x

Jeder azyklische Baum ist ein Graph

x

Jeder Baum ist ein Graph

x

Jeder Baum ist ein azyklischer Graph

x

Ein Graph mit 1000 Knoten und 15000 Kanten wird als lichter Graph bezeichnet

x

Ein Graph mit 1000 Knoten und 7000 Kanten wird als dünnbesetzter Graph bezeichnet

x

Für dichte Graphen ist die Darstellung als Adjazenzmatrix nicht eeignet

x

Die Wurzel eines ungerichteten Graphen ist immer ein Schnittpunkt des Graphen, wenn diese Wurzel mehr als eine Kante besitzt

x

Eine Wurzel im Tiefensuchwald eines ungerichteten Graphen ist immer ein Schnittpunkt des Graphen, wenn diese Wurzel im Tiefensuchwald mehr als eine Kante besitzt

x

Wird ein Schnittpunkt aus einem zusammenhängenden Graphen entfernt, so zerfällt dieser in zwei unabhängige Teilgraphen

x

Als Suchverfahren in Graphen ist Tiefensuche effizienter als Breitensuche

x

Der Aufwand der Tiefensuche in Graphen ist linear in der Anzahl der Knoten des Graphen

x

Der Aufwand von Tiefensuche auf einer Adjazenzmatrix ist unabhängig von der Zahl der Kanten im Graph

x

Die topologische Ordnung eines gerichteten Graphen ist die Ordnung, in der die Knoten bei einer Breitensuche erreicht werden

x

Die topologische Ordnung eines gerichteten Graphen ist die Ordnung, in der die Knoten bei einer Tiefensuche erreicht werden

x

Die Topologische Ordnung eines gerichteten Graphen ist eine Besuchsordnung, die in gerichteten azyklischen Graphen garantiert, dass ein Knotenerst nach all seinen Vorgängerknoten besucht wird

x

Die iterative Tiefensuche verwendet als Datenstruktur einen Stack

x

Der Tiefensuchwald für einen stark zusammenhängenden gerichteten Graphen besteht aus genau einem Baum

x

Der Tiefensuchwald für einen zusammenhängenden gerichteten Graphen besteht aus genau einem Baum

x

Ein TSB für einen ungerichteten Graphen beinhaltet alle Kanten des Graphen außer einigen Kanten, die Knoten mit Vorgängern im TSB verbinden

x

Ein TSB für einen ungerichteten, zusammenhängenden Graphen beinhaltet alle Kanten des Graphen außer einigen Kanten, die Knoten mit Vorgängern im TSB verbinden

x

Im Breitensuchwald sind alle Kanten des Originalgraphen vorhanden, außer einigen Kanten, die Wurzeln disjunkter Teilbäume des Waldes miteinander verbinden

x

Der Algorithmus von Dijkstra baut den minimalen Spannbaum des Graphen auf

x

Der minimale Spannbaum ist ein Spannbaum, der jeden Knoten mit der Wurzel auf dem kürzesten möglichen Weg verbindet

x

Der minimale Spannbaum eines gewichteten Graphen ist jener Tiefensuchbaum (TSB), für den jeder Knoten des Graphen von der Wurzel aus über einen Pfad mit minimalem Gesamtgewicht seiner Kanten erreicht wird

x

Jeder binäre Suchbaum ist 2-gleichverzweigt

x

Der Binärbaum ist laut Definiton kein Baum , weil er leer sein darf ?

x

In einem 2-gleichverzweigten Baum sind mindestens die Hälfte der Knoten Blätter des Baums

x

Ein Binärbaum der Höhe h hat maximal 2^h Knoten

x

Die Inorder-Traversierung eines binären Suchbaums besucht die Kanten des Baumes in sortierte Reihenfolge

x

Für einen gegebenen ausgeglichenen binären Suchbaum mit N Knoten erfordert die Suche im schlechtesten Fall O(N) Vergleiche

x

Für einen gegebenen binären Suchbaum mit N Knoten erfordert die Suche durchschnittlich O(log N) Vergleiche

x

Die Suche in einem vorgegebenen binären Suchbaum benötigt im durchschnittlichen Fall O(log n)

x

Es gibt AVL-Bäume, die nicht vollständig ausgeglichen sind

x

Es gibt vollständig ausgeglichene Bäume, die nicht die AVL-Eigenschaft besitzen

x

Ein AVL-Baum ist ein binärer Suchbaum, der in jedem Knoten ausgeglichen ist?

x

Nach dem Einfügen in einen AVL-Baum ändert sich immer die Balance aller Knoten

x

Es ist maximal 1 Ausgleichsoperation notwendig, um einen Baum, der vor einer Einfügeoperation die AVL-Eigenschaft besitzt, nach dieser Operation wieder in einen AVL-Baum zu überführen

x

Für einen gegebenen AVL-Suchbaum mit N Knoten erfordert die Suche im schlechtesten Fall O(logn) Vergleiche

x

Beim Einfügen in einen B-Baum muss höchstens ein Knoten aufgespalten werden

x

Die Ordnung m eines B-Baums

Bei internem Hashing ist ein Belegungsfaktor > 1 möglich

x

Löschen ist bei internem Hashing sehr ineffizient im Vergleich zu externem Hashing

x

Hashverfahren haben im schlimmsten Fall eine Komplexität von O(n)

x

Bei Hashverfahren ist die konstante Komplexität O(1)

x

Bei Hashverfahren ist die konstante Komplexität am besten

x

Bei perfektem Hashing treten keine Kollisionen auf, solange unterschiedliche Schlüssel eingetragen werden sollen

x

Beim perfekten Hashing gibt es keine voneinander verschiedenen Schlüssel, die denselben Hashwert haben

x

Bei einem Hashverfahren mit interner Konfliktauflösung durch quadratische Sondierung in einer Tabelle primärer Länge kann sein, dass ein Eintrag nicht erfolgen kann, obwohl Tabelleneinträge frei sind

x

Bei einem Hashverfahren mit interner Konfliktauflösung durch quadratische Sondierung kann es vorkommen, dass ein Eintrag nicht erfolgen kann, obwohl Tabelleneinträge frei sind

x

Bei einem Hashverfahren mit interner Konfliktauflösung durch lineare Sondierung mit primärer Schrittweise in einer Tabelle primärer Länge (ungleich der Schrittweise) kann ein Eintrag immer erfolgen, solangeTabelleneinträge frei sind

x

Bei einem Hashverfahren mit interner Konfliktauflösung durch lineare Sondierung in einer Tabelle kann ein Neueintrag nur dann nicht erfolgen, wenn alle Tabelleneinträge belegt sind

?

Mit quadratischem Sondieren werden immer alle Einträge einer Hashtabelle ausgenutzt

x

Wenn eine Datenmenge unbekannter Größen zu sortieren ist, die erst während der Programmausführung aufgebaut wird, ist eine Darstellung in verzeigerten Datenstrukturen unumgänglich

x

Es gibt Sortierverfahren, die weniger Schritte brauchen, als Elemente zu sortieren sind, um eine vollständig sortierte Reihenfolge der Elemente zu garantieren

x

Wenn eine Datenfolge bekannter Größe zu sortieren ist, ist eine Darstellung in Arrayform einer Listendarstellung, z.B. aus Gründen der Speichereffizienz, vorzuziehen

?

Ein Sortierverfahren heißt ordnungsverträglich, wenn es um so effizienter ist, je weniger Fehlstände die Elemente der zu sortierenden Reihe aufweisen

x

Ein Sortierverfahren heißt ordnungsverträglich, wenn die anfänglich existierende Ordnung von Elementen mit gleichem Suchschlüssel zueinander durch das Sortieren nicht verändert wird

x

Ein Sortierverfahren heißt ordnungsverträglich, wenn die Reihenfolge der Elemente mit gleichem Schlüssel beim Sortieren nicht verändert wird

x

Ein Sortierverfahren wird als stabil bezeichnet, wenn es für vorsortierte Folgen schneller arbeitet, wenn es also eine eventuelle Vorsortiertheit der Folge ausnutzt

x

Ein Sortierverfahren heißt stabil, wenn es für die anfänglich existierende Ordnung von Elementen mit gleichem Suchschlüssel zueinander durch das Sortieren nicht verändert wird

x

Es gibt ein Sortierverfahren, dass weniger Schritte für eine vollständig sortierte Folge benötigt als die Anzahl der Folgenelemente

x

Es existiert allgemein ein Sortierverfahren mit binärem Aufwand ( O(log n) )

x

Ordnungsverträgliche Sortierverfahren sind immer auch stabil

x

Ordnungsverträgliche Sortierverfahren sind immer stabil da die Reihenfolge gleicher Elemente nicht verändert wird

x

Sind die Elemente einer zu sortierenden Folge sehr umfangreich, so bietet es sich an, die Technik der Schlüssel-Verweis-Tabelle anzuwenden

x

Direktes Aussuchen ist ein stabiles Sortierverfahren

x

Bubblesort ist ein stabiles Sortierverfahren

x

Bei Wahl des Pivot-Elementes mittels der 3-Median-Strategie hat Quicksort im schlechtesten Fall die Komplexität O(nlogn)

x

Quicksort ist ein instabiles Sortierverfahren

x

Quicksort ist grundsätzlich ein effizienteres Sortierverfahren als Direktes Einfügen

x

Quicksort arbeitet im schlechtesten Fall mit Aufwand O(NlogN)

x

Heapsort ist grundsätzlich ein effizienteres Sortierverfahren als Direktes Einfügen

x

Heapsort ist ein stabiles Sortierverfahren

x

Heapsort arbeitet auch im schlechtesten Fall mit Aufwand O(nlogn)

x

Der terminierende Algorithmus hat einen eindeutig vorgeschriebenen Ablauf

x

Ein Record ist ein homogenes kartesisches Produkt und dient generell der Darstellung homogener Information

x

Die Syntax einer Programmiersprache legt die Bedeutung der Programme fest

x

Ein Vorteil der dynamischen Variablen ist es, dass Programme mit dynamischen Variablen im Allgemeinen sehr gut verständlich und daher einfach wartbar sind

Die Verifikation eines Programms besteht aus dem Nachweis, dass Spezifikation und Beschreibung des Programmes verträglicher sind

Beim Bubblesort werden Inversionen am Anfang schneller behoben als am Ende der Folge

x

Grössere Elemente wandern durch eine vorsortierte Reihe beim Bubblesort hindurch und ordnen sich hinten im Array an

x

Die Inversion sind beim Bubblesort asymmetrisch verteilt

x

Das direkte Einfügen ist nicht stabil

x

In einem Kantenzug kommen die selben Kanten mehrfach vor

x

Kein Knoten in einem Weg mehrfach vor

x

der Eulersche Zyklus ist ein geschlossener Kantenzug

x

Ein Hamiltonischer Zyklus muss nicht alle Kanten besuchen

x

Der Hamiltonische Zyklus hat die Länge (V), V ist die Menge aller Kanten

x

Alle Blätter haben bei einem vollständig ausgeglichenem Baum den Level der Höhe des Baumes

x

Ein vollständig ausgeglichener Baum hat nur Blätter mit dem Level der Höhe des Baumes oder einen um 1 verminderten Level

x

Ein Heap ist ein Binärbaum in dem jeder Knoten einen grösseren Wert hat als seine Kinder.

x

Ein Heap ist ein Suchbaum, weil er die Suchbaumeigenschaft hat

x

Zwischen Baumknoten, Randknoten und unsichtbaren Knoten muss nur bei der Tiefensuche unterschieden werden.

x

Baumknoten sind die bereits besuchten Knoten

x

Randknoten sind Nachbarn von Baumknoten, die besucht wurden

x

Unsichtbare Knoten sind die noch nicht angetroffenen Knoten

x

Ein lichter (dünn besetzter) Graph hat relativ wenig Kanten: Zahl der Kanten < Zahl der Knoten * log (Zahl der Knoten)

x

Ein dichter Graph ist vollständig

x

Ein dichter Graph ist fast vollständig

x

Ein vollständiger Graph ab 5 Knoten ist nicht mehr kreuzungsfrei zu zeichen

x

In der Adjazenzliste stehen alle Knoten eines Graphes

x

Die Adjazenzliste enthält alle mit dem Knoten verbundenen Kanten. Pro Knoten eine Liste

x