W3 - Node Based Datastructures

Question 1

Wat is een ADT?

Answer 1

Abstract DataType
- Hoe = irrelevant
- Wat = relevant
- Verschillende implementaties mogelijk

Question 2

Wat zijn 4 belangrijke operaties (bij ADTs)?

Answer 2

1. Reading
2. Searching
3. Insertion
4. Deletion

Question 3

Waarbij is lezen sneller? Array of Linked List?

Answer 3

Array O(1), Linked List O(N)

Question 4

Waarbij is zoeken sneller? Array of Linked List?

Answer 4

Array O(N), Linked List O(N)

Question 5

Waarbij is Insertion sneller? Array of Linked List?

Answer 5

Begin: Array O(N), Linked List O(1)
Eind: Array O(1), Linked List O(N)

Question 6

Waarbij is Deletion sneller? Array of Linked List?

Answer 6

Begin: Array O(N), Linked List O(1)
Eind: Array O(1), Linked List O(N)

Question 7

Wanneer is een Linked List beter dan een Array?

Answer 7

Als je in 1 lijst veel moet verwijderen.
Array verschuift na elke Deletion de overige elementen.
Linked List gaat direct verder.

Question 8

Waarom is een Binaire boom in Worst Case O(N) bij Search, Insert en Delete?

Answer 8

Als het een ongebalanceerde binaire boom is, waarbij alle waarden alleen naar links óf alleen naar rechts gaat.

Bijv. [1,2,3,4,5,6] zou een boom zijn met alleen rechterkinderen.

Question 9

Zorg dat je de pointer notatie kent met pijltjes, .next, .data, etc.

Answer 9

-