COMMUNITY
Oefentoets · Informatica · vwo 5 Zoeken, sorteren, complexiteit, recursie en datastructuren oefenen
StudyZone
InformaticaVak
12 vragenOmvang
WAT ZIT ERIN
1Lijst [3, 7, 11, 15, 19, 23, 27, 31] (index 0 tot en met 7). Je zoekt 27 met binair zoeken, waarbij het midden ⌊ (begin + einde)/(2) ⌋ is. Hoeveel elementen vergelijk je met 27 voordat je het vindt (de laatste vergelijking telt mee)?
De antwoorden zie je tijdens het oefenen
12 vragen
1
Lijst [3, 7, 11, 15, 19, 23, 27, 31] (index 0 tot en met 7). Je zoekt 27 met binair zoeken, waarbij het midden is. Hoeveel elementen vergelijk je met 27 voordat je het vindt (de laatste vergelijking telt mee)?
3
7
4
1
2
De lijst [5, 2, 4, 1] wordt oplopend gesorteerd met bubble sort. Hoe ziet de lijst eruit na de eerste ronde (van links naar rechts alle naburige paren vergeleken)?
[1, 2, 4, 5]
[2, 4, 1, 5]
[2, 5, 4, 1]
[5, 4, 2, 1]
3
De lijst [7, 3, 9, 1] wordt oplopend gesorteerd met selection sort. Hoe ziet de lijst eruit na de eerste stap?
[1, 7, 3, 9]
[3, 7, 9, 1]
[1, 3, 9, 7]
[7, 3, 1, 9]
4
Een algoritme bevat een for-lus die keer draait, met daarbinnen een tweede for-lus die ook keer draait. Wat is de orde van grootte van het aantal stappen?
O(n)
O(log n)
O(2^n)
O(n²)
5
Een lus voert uit: while n > 1: n = n // 2. De beginwaarde van n is de invoergrootte. Wat is de orde van grootte van het aantal rondes?
O(log n)
O(n)
O(n²)
O(1)
6
Een algoritme heeft orde . Wat gebeurt er ongeveer met de rekentijd als de invoer twee keer zo groot wordt?
2 keer zo lang
4 keer zo lang
8 keer zo lang
Even lang
7
In een gesorteerde lijst van 1 000 000 elementen zoek je met binair zoeken. Hoeveel vergelijkingen heb je ongeveer maximaal nodig?
1.000.000
500.000
20
1.000
8
Gegeven de functie def som(n): return 0 if n == 0 else n + som(n - 1). Wat is som(4)?
4
24
15
10
9
Een recursieve functie heeft geen basisgeval. Wat gebeurt er als je hem aanroept?
De aanroepen stapelen zich op tot het programma met een fout stopt
Hij stopt na een vast aantal aanroepen en geeft nul terug
Hij verandert vanzelf in een lus die netjes eindigt
Hij geeft direct de waarde van de parameter terug
10
Waarom is het probleem van de handelsreiziger met brute force niet op te lossen voor grote aantallen steden?
Computers kunnen geen afstanden tussen steden berekenen
Het aantal routes groeit als en wordt astronomisch groot
Elke stad moet apart in een eigen bestand staan
Het probleem heeft voor veel steden geen enkele oplossing
11
Een lege stack ondergaat: push(1), push(2), push(3), pop(), push(4). Wat staat er daarna in de stack, van onder naar boven?
1, 2, 3, 4
1, 3, 4
2, 3, 4
1, 2, 4
12
Een lege queue ondergaat: enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4). Welk element wordt bij de volgende dequeue() verwijderd?
1
2
3
4
Staat hier iets dat niet klopt of niet hoort? .
