Werkblad Algoritmen & complexiteit met antwoorden

Welke ontwerpstrategie gebruikt mergesort?

1. AGulzige keuze (greedy)
2. BBrute kracht
3. CVerdeel en heers
4. DDynamisch programmeren

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

Wat is de worst-case tijdcomplexiteit van mergesort?

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

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

1. AZe loopt in O(1) tijd
2. BDe compiler maakt er altijd een lus van die veilig eindigt
3. CZe geeft automatisch 0 terug
4. DZe blijft zichzelf aanroepen totdat de call stack overloopt

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

1. AEen array waarvan alle elementen verschillend zijn
2. BEen array die al gesorteerd is
3. CEen array van lengte 2
4. DEen array in willekeurige volgorde

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, de ondergrens is dus fout
2. BNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
3. CJa, maar alleen voor arrays korter dan 100
4. DNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is

Voor welke variant van het knapzakprobleem geeft de gulzige regel "neem items in volgorde van waarde per gewicht" altijd een optimaal antwoord?

1. ADe fractionele knapzak, waarbij items mogen worden opgesplitst
2. BDe 0/1-knapzak, waarbij items altijd in hun geheel moeten worden genomen
3. CBeide varianten
4. DGeen van beide varianten