Week 3 Flashcards
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.
