Suchalgorithmen

Question 1

Arten von Suchalgorithmen

Answer 1

Sequentielle Suche, Binäre Suche

Question 2

Voraussetzungen für Sequentielle Suche

Answer 2

keine

Question 3

Ablauf einer Sequentieller Suche

Answer 3

Vergleich von Suchschlüssel und Feldwert bei Index i

Question 4

Inputparameter einer sequentiellen Suche

Answer 4

Feld und Suchschlüssel

Question 5

Rückgabewert einer erfolgreichen Sequentiellen Suche

Answer 5

Index des ersten Feldwertes, der dem Suchschlüssel entspricht (nicht der Wert selbst)

Question 6

Rückgabewert einer nicht erfolgreichen Sequentiellen Suche

Answer 6

-1 bzw. NO_KEY

Question 7

Laufzeit Sequentielle Suche: im Bestfall

Answer 7

1

Question 8

Laufzeit Sequentielle Suche: im Worst Case

Answer 8

n (Länge des Feldes)

Question 9

Laufzeit Sequentielle Suche: im Durchschnitt (erfolgreiche Suche)

Answer 9

(n+1)/2 (Hälfte der um eins erhöhten Feldlänge)

Question 10

Laufzeit Sequentielle Suche: im Durchschnitt (nicht erfolgreiche Suche)

Answer 10

n (in jedem Fall wird das gesamte Feld geprüft)

Question 11

Voraussetzung Binäre Suche

Answer 11

sortiertes Feld (je nach Code auf- oder absteigend )

Question 12

Inputparameter Binäre Suche

Answer 12

Feld, Suchschlüssel

Question 13

Ablauf Binäre Suche

Answer 13

1. Abgrenzung des Feldes
2. Kontrolle des mittleren Feldelements
3. neues Feld abgrenzen (entweder linkes oder rechtes Teilfeld)
4. Schritte 1 bis 3 wiederholen

Question 14

Abbruchbedingung Sequentiell Suche

Answer 14

Wert gefunden oder letztes Feldelement erreicht

Question 15

Abbruchbedingung Binäre Suche

Answer 15

Wert gefunden oder Untergrenze ist größer als die Obergrenze

Question 16

Welcher Index wird bei der Binären Suche untersucht, wenn das Feld keine genaue Mitte hat und warum?

Answer 16

immer den kleineren der “beiden Mitten” (weil der int-Wert der Mitte Nachkommazahlen fallen lässt)

Question 17

Rückgabewert einer erfolgreichen Binären Suche

Answer 17

Index des ersten Feldwertes, der dem Suchschlüssel entspricht (nicht der Wert selbst)

Question 18

Rückgabewert einer nicht erfolgreichen Binären Suche

Answer 18

-1 bzw. NO_KEY

Question 19

Laufzeit Binäre Suche: im Bestfall

Answer 19

1

Question 20

Laufzeit Binäre Suche: im Worst Case

Answer 20

log2(n)

Question 21

Laufzeit Binäre Suche: im Durchschnitt (erfolgreiche Suche)

Answer 21

log2(n)

Question 22

Laufzeit Binäre Suche: im Durchschnitt (nicht erfolgreiche Suche)

Answer 22

log2(n)