Free Printable AL Tutorium 4

1.

Welche Datenstruktur ist am besten geeignet?

Uni will Student*in-Objekte verwalten

a)

Hashtabelle

b)

Liste

c)

Array

d)

Aktenordner

2.

Welche Dinge sind beim Hashing involviert?

a)

Key

b)

Array

c)

Universum

d)

Liste

3.

Was beschreibt das Universum U am besten?

a)

Bild(h)

b)

Schlüsselmenge

c)

Urbild(h)

d)

Objektmenge

4.

Was ist für eine Schlüsselfunktion wünschenswert?

a)

Kleines Bild

b)

Injektivität

c)

Surjektivität

d)

Bijektivität

5.

Welche Operationen unterstütz eine Hashtabelle?

a)

get

b)

push

c)

remove

d)

find

6.

Hashfunktionen sind immer

a)

injektiv

b)

nicht injektiv

c)

surjektiv

d)

besser als Arrays

7.

Was gilt für Hashfunktionen?

a)

immer kollisionsfrei

b)

nie kollisionsfrei

c)

invertierbar

d)

ermöglichen schnellen Zugriff

8.

Was sagt die Simple Uniform Hashing Assumption aus?

Tabellengröße m, $i\in\ \left\{0,...,m-1\right\}$

a)

$P\left(h\left(x\right)=h\left(y\right)\right)=m$

b)

$P\left(h\left(x\right)=i\right)=\frac{1}{m}$

c)

$P\left(h\left(x\right)<m\right)=\frac{1}{m}$

d)

$P\left(h\left(x\right)=h\left(y\right)\right)=\frac{1}{m}$

9.

Was gilt für universelle Familien?

a)

Menge an Hashfunktionen

b)

Zufällig gezogene h1, h2 erzeugen immer wenig Kollisionen

c)

Für alle Paare h1,h2 ist die Kollisionswsk. gering

d)

Sind kollisionsfrei

10.

Wie lassen sich kollisionen vermeiden?

a)

Tabellenvergrößerung

b)

Listen einfügen

c)

andere Hashfunktion wählen

d)

garnicht

11.

Hashfunktionen sind im Worst-Case...

a)

immer gut

b)

immer schlecht

c)

besser als Arrays

d)

eine Liste

AL Tutorium 4

Total questions: 11

Worksheet time: 8mins

Similar Resources on Wayground