Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

1. AO(log n)
2. BO(n²)
3. CO(1)
4. DO(n)

Wat vereist binair zoeken van de invoer?

1. ADe array mag alleen positieve getallen bevatten
2. BDe lengte van de array moet een macht van twee zijn
3. CDe array mag niet meer dan 1000 elementen hebben
4. DDe array moet gesorteerd zijn

Welke hiervan groeit het langzaamst als n groot wordt?

1. AO(n log n)
2. BO(log n)
3. CO(n²)
4. DO(n)

Wat is de oplossing van de recurrente betrekking T(n) = T(n − 1) + O(n)?

1. AO(n log n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(n)

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

1. ABellman-Ford is in alle gevallen vereist
2. BHet algoritme van Kruskal
3. CDiepte-eerst zoeken (DFS)
4. DHet algoritme van Dijkstra

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

1. ADe minimaal opspannende boom
2. BEen topologische volgorde in alle grafen
3. CKortste paden in grafen met negatieve kantgewichten
4. DKortste paden in aantal kanten vanaf de startknoop

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

1. AJa, maar alleen voor arrays korter dan 100
2. BNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
3. CJa, de ondergrens is dus fout
4. DNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)