Werkblad Datastructuren met antwoorden

Wat is een gewogen graaf?

1. AEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
2. BEen graaf die op schijf is opgeslagen
3. CEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
4. DEen graaf met meer kanten dan knopen

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AInvoegen aan de kop
2. BHet kopelement verwijderen
3. CHet element op index i benaderen
4. DHet eerste element lezen

Wat doet een hashfunctie in een hashtabel?

1. AVersleutelt de waarden in de tabel
2. BSorteert de sleutels in de tabel
3. CBeeldt een sleutel af op een index in de tabel
4. DTelt hoeveel sleutels er zijn opgeslagen

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

1. AOp index 2i + 1
2. BOp index ⌊i / 2⌋ + 1
3. COp index ⌊(i − 1) / 2⌋
4. DOp index i − 1

Hoe wordt een nieuw element in een binaire heap ingevoegd?

1. APlaats het in de wortel en laat het omlaag zakken (sift down)
2. BVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
3. CBouw de hele heap opnieuw op
4. DPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

1. AO(V + E)
2. BO(V²)
3. CO(E)
4. DO(log V)

Wat is de looptijd van breadth-first search op een graaf met V knopen die als adjacency matrix is opgeslagen?

1. AO(V + E)
2. BO(V)
3. CO(E log V)
4. DO(V²)

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

1. AO(1 + α), waarbij α = n / m
2. BO(n)
3. CO(m)
4. DO(log n)