Fiche d’exercices de Structures de données avec corrigé

Que fait une fonction de hachage dans une table de hachage ?

1. AElle trie les clés de la table
2. BElle associe une clé à un indice de la table
3. CElle chiffre les valeurs de la table
4. DElle compte le nombre de clés stockées

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. APush (empiler)
2. BEnqueue (enfiler)
3. CPop (dépiler)
4. DPeek (consulter)

Un graphe est constitué de :

1. ALignes et colonnes
2. BUniquement des clés et des hachages
3. CUniquement une racine et des feuilles
4. DSommets (nœuds) reliés par des arêtes

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(log n), où n est le nombre de mots
2. BO(L), quel que soit le nombre de mots stockés
3. CO(L × n)
4. DO(n), où n est le nombre de mots

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
2. BOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
3. COn le place à la racine et on le fait descendre
4. DOn reconstruit entièrement le tas

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file de priorité min
2. BUn ensemble sans ordre
3. CUne pile
4. DUne file FIFO

Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :

1. ADes faux négatifs possibles mais aucun faux positif
2. BDes faux positifs possibles mais aucun faux négatif
3. CDes réponses uniquement pour des nombres
4. DDes réponses toujours exactes

La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :

1. AO(n²)
2. BO(n)
3. CExactement O(log n)
4. DO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant