Herhaling: Eindexamen datastructuren

Wat is een array?

Een array is een gestructureerde verzameling van elementen van dezelfde datatypes, toegankelijk via indexen.

Wat is een linked list?

Een linked list is een datastructuur bestaande uit knopen, waarbij elke knoop een verwijzing naar de volgende knoop bevat.

Wat is een stack?

Een stack is een datastructuur die principes van LIFO (Last In, First Out) volgt.

Wat is een queue?

Een queue is een datastructuur die FIFO (First In, First Out) principes volgt.

Wat is een hash table?

Een hash table is een datastructuur die key-value paren opslaat en met behulp van een hashfunctie toegang biedt.

Vul in: In een stack kun je alleen ________ en ________ uitvoeren.

push en pop.

Wat is het doel van een binary tree?

Een binary tree is een datastructuur die elke knoop maximaal twee kinderen geeft en het zoeken efficiënt maakt.

Vergelijk een array met een linked list.

Een array heeft vaste grootte met directe toegang, terwijl een linked list dynamisch is en sequentiële toegang vereist.

Wat is de tijdcomplexiteit van het toevoegen aan een linked list?

Toevoegen aan het begin van een linked list is O(1), maar aan het einde is O(n) bij gebrek aan een tail pointer.

Wat is een graaf?

Een graaf is een verzameling knopen (vertices) en verbindingen (edges) tussen deze knopen.

Wat is een bipartiete graaf?

Een bipartiete graaf is een graaf waarvan de knopen in twee groepen kunnen worden verdeeld zonder dat knopen binnen dezelfde groep verbonden zijn.

Wat is een AVL-boom?

Een AVL-boom is een zelfbalancerende binaire zoekboom die de hoogteverschillen tussen subbomen beperkt.

Wat is het doel van een priority queue?

Een priority queue is een datastructuur die elementen op basis van hun prioriteit verwerkt, niet op volgorde van binnenkomst.

Wat betekent O(n) in algoritmes?

O(n) betekent dat de tijdcomplexiteit van het algoritme lineair is ten opzichte van de grootte van de invoer.

Wat is een set?

Een set is een verzameling van unieke elementen zonder specifieke volgorde.

Wat is de functie van een zoekalgoritme?

Een zoekalgoritme zoekt naar specifieke waarden binnen een datastructuur.

Wat is een diepte-eerst zoekalgoritme?

Diepte-eerst zoeken (DFS) verkent een tak van de boom of graaf volledig voordat het terugkijkt.

Wat is een breedte-eerst zoekalgoritme?

Breedte-eerst zoeken (BFS) verkent alle buren van een knoop voordat het dieper gaat.

Wat is een Dijkstra-algoritme?

Dijkstra's algoritme vindt de kortste paden in een gewogen graaf met niet-negatieve gewichten.

Wat is de complexiteit van het Dijkstra-algoritme?

De tijdcomplexiteit van Dijkstra's algoritme is O(V^2) met een array en O(E + V log V) met een priority queue.

Wat is recursie?

Recursie is een programmeertechniek waarbij een functie zichzelf oproept om problemen op te lossen.

Vul in: De worst-case tijdcomplexiteit van een binaire zoekopdracht is ________.

O(log n).

Wat is een trie?

Een trie is een speciaal soort boom die wordt gebruikt om een dynamische set of associatieve array op te slaan, vaak voor woorden.

Wat zijn ordeningsalgoritmes?

Ordeningsalgoritmes zijn methodes voor het rangschikken van een lijst of array in een bepaalde volgorde.

Wat is het verschil tussen quicksort en mergesort?

Quicksort gebruikt een divide-and-conquer aanpak en is vaak sneller, terwijl mergesort stabiel is maar meer geheugen vereist.

Wat is een combinatorische datastructuur?

Combinatorische datastructuren zijn structuren zoals sets en permutaties die combinaties van objecten onderzoeken.