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

Où se trouve le plus petit élément d'un tas binaire min ?

1. AÀ la racine
2. BÀ la dernière position du tableau
3. CDans une feuille quelconque, qu'il faut chercher
4. DDans la feuille la plus à gauche

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un seul bloc contigu, les uns à la suite des autres
2. BDe façon dispersée, reliés par des pointeurs
3. CDans un arbre de pages mémoire
4. DÀ des emplacements aléatoires choisis par un hachage

Un graphe est constitué de :

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

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe sondage linéaire (linear probing)
2. BLe double hachage (double hashing)
3. CLe chaînage séparé (separate chaining)
4. DLe sondage quadratique (quadratic probing)

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. ALa file de la mémoire du tas
2. BUn arbre binaire de recherche de cadres
3. CLa pile d'appels
4. DUne table de hachage des fonctions

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. A2i et 2i + 1
2. Bi/2 et i/2 + 1
3. Ci + 1 et i + 2
4. D2i + 1 et 2i + 2

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

1. APour que la table de hachage soit triée
2. BPour supprimer le besoin de redimensionner la table
3. CPour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
4. DPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

1. AUne file FIFO des k dernières valeurs
2. BUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin
3. CUn tableau trié de toutes les n valeurs
4. DUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive