Welke soorten datastructuren zijn er?
- Lineair
- (Niet-)geïndiceerd - Niet-lineair
- Set, struct/record, object, netwerk (graaf), boom - Abstract
- Stack, dict, (priority) queue
Wat zijn kenmerken van een array?
= Een rij gegevens die achter elkaar in het geheugen worden opgeslagen
- Aantal elementen ligt vast
- Alle gegevens zijn van hetzelfde type
- Index => direct toegang tot bepaald gegeven
Wat zijn kenmerken van een list?
= Een rij gegevens die in een bepaalde volgorde worden opgeslagen, waarvan de waar en hoe het in het geheugen wordt opgeslagen niet relevant is.
- Aantal elementen ligt NIET vast.
- Gegevens hoeven niet altijd van hetzelfde type te zijn.
- Indexgebruik zoals bij array.
Wat zijn kenmerken van een tuple?
= Een rij gegevens die in een bepaalde volgorde worden opgeslagen, waarvan de waar en hoe het in het geheugen wordt opgeslagen niet relevant is.
- Aantal elementen ligt vast.
- Gegevens hoeven niet altijd van hetzelfde type te zijn.
- In python: gegevens IN een tuple zijn immutable.
- Indexgebruik zoals bij array en list.
Wat zijn kenmerken van een file?
= Een rij bits die onder een bepaalde naam is opgeslagen op extern geheugen.
- Software moet weten hoe de bits in groepen verdeeld zijn en wat ze betekenen (bestandsformaat).
- Tekstfile = opgedeeld in porties bits van vaste grootte waarbij elke portie een bepaald karakter voorstelt (ASCII).
- Toegang is direct of sequentieel, afhankelijk van het opslagmedium en formaat van de file.
Wat zijn kenmerken van een linked list?
= De implementatie van een samenhangende, gerichte, lineaire graaf.
- Knopen zijn geïmplementeerd als objecten waarvan een van de velden verwijst naar een object van hetzelfde type.
- Pointer = Verwijzing = Geheugenadres van volgende knoop
- Sequentiële toegang
Wat zijn kenmerken van een set?
= Verzameling
- Volgorde irrelevant
- Indexgebruik niet zinvol
- Geen duplicaten
Wat zijn kenmerken van een dictionary?
= “Woordenboek”: een rij van gegevensparen
- Eerste element is uniek en wordt gebruik als index.
- Volgorde van de paren is irrelevant.
Wat zijn kenmerken van een struct en object?
Struct
- Bestaat uit een aantal vaste onderdelen van verschillend type
- Volgorde is irrelevant bij deze onderdelen
- Onderdeel is te bereiken via een eigen naam (identifier), meestal voorafgegaan door de naam van de struct.
Object
- Bevat methodes
Wat zijn kenmerken van het netwerk en de boom?
= Implementaties van grafen en bomen
- Knopen bevatten 1 of meer verwijzingen naar andere knopen.
- Binaire boom: 2 extra velden per knoop (“LEFT” en “RIGHT”).
- Als het vooraf onduidelijk is hoeveel verwijzingen in een knoop zitten ==> List van verwijzingen als veld van de knoop
Wat is kenmerkend voor alle ADT’s?
- Hoe het gegeven precies is opgeslagen is irrelevant.
- Alleen wat je ermee kunt doen is relevant
Wat zijn kenmerken van een stack?
- Gegevens individueel toevoegen of verwijderen.
- Niet bedoeld om te zoeken.
- LIFO (Last in, First out)
Wat zijn kenmerken van een queue?
- Gegevens individueel toevoegen of verwijderen.
- Niet bedoeld om te zoeken.
- FIFO (First in, First out)
- Deque = double-ended queue.
Wat zijn kenmerken van een priority heap?
- Gegevens individueel toevoegen of verwijderen.
- Niet bedoeld om te zoeken.
- Kunt alleen gegevens met de hoogste prioriteit verwijderen.
Wat is het verschil tussen een binaire boom, een geordende binaire boom, een binaire heap en een binaire zoekboom?
Binaire boom: boom met maximaal 2 kinderen per knooppunt. Elke andere boom hier is een soort binaire boom.
Geordende binaire boom: boom waarvan de elementen een bepaalde volgorde aanhouden.
Binaire zoekboom: alle knooppunten links zijn kleiner, alle knooppunten rechts groter.
Binaire heap: Complete binaire boom, waarbij elk knooppunt kleiner is dan of gelijk is aan zijn ouder.
Wat is het verschil tussen directe en sequentiële toegang?
Bij directe toegang hoef je niet eerst de voorafgaande gegevens te lezen voordat je het relevante gegeven kunt lezen.
Bij sequentiële toegang moet je alle voorafgaande gegevens lezen voordat je het relevante gegeven kunt lezen.
