Hoofdstuk 5

Question 1

Wat is een rechtstreeks adresseerbare tabel?

Answer 1

Een dictionary waarbij de keys eenvoudig om te zetten zijn in de index. (e.g. Frequentietabel waarbij de key=index)

Alle dictionary operaties zijn O(1). (find, add, remove)

Als er duplicaten zijn met dezelfde key, kan er op die index een gelinkte lijst worden opgeslagen.

Question 2

Wat zijn de eigenschappen van een dictionary die zijn sleutels opslaagt in een ongeordende tabel?

Answer 2

Find key = sequentieel = O(n)
Toevoegen = achteraan = O(1)
Verwijderen = Kan door laatste elem vervangen worden = O(1)

Question 3

Wat zijn de eigenschappen van een dictionary die zijn sleutels opslaagt in een geordende tabel?

Answer 3

Zoeken kan binair dus O(lg n)
Toevoegen = O(n)
Verwijderen = O(n)

Question 4

Wat zijn de eigenschappen van een dictionary die zijn sleutels opslaagt in een ongeordende gelinkte lijst

Answer 4

zoeken = lineair = O(n)
verwijderen = O(1)
toevoegen = achteraan = O(1)

Question 5

Wat zijn de eigenschappen van een dictionary die zijn sleutels opslaagt in een geordende gelinkte lijst

Answer 5

zoeken kan niet binair in gelinkte lijst dus nog steeds O (n)

toevoegen = O(n)
verwijderen = O(n)