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

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ASa position dans la liste d'adjacence
2. BLa longueur du plus long chemin partant de lui
3. CLe nombre d'arêtes qui lui sont reliées
4. DLe nombre de sommets du graphe

Qu'est-ce qu'un graphe orienté ?

1. AUn graphe qui n'a pas de cycle
2. BUn graphe dont toutes les arêtes ont un poids
3. CUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
4. DUn graphe dont les arêtes ont une direction d'un sommet vers un autre

Dans une table de hachage, qu'est-ce qu'une collision ?

1. ADeux clés différentes sont associées au même indice
2. BUne clé ne peut pas du tout être hachée
3. CLa table manque de mémoire
4. DDeux clés égales sont stockées deux fois

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. AChaque nœud est colorié en rouge ou en noir
2. BLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
3. CLes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
4. DToutes les feuilles sont exactement à la même profondeur

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne matrice d'adjacence
2. BUn unique tableau trié de sommets
3. CUne liste d'adjacence
4. DUn tas binaire d'arêtes

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

1. AO(V²)
2. BO(V)
3. CO(E log V)
4. DO(V + E)

Dans une table de hachage à adressage ouvert, pourquoi la suppression se fait-elle souvent avec un marqueur « pierre tombale » (tombstone) ?

1. AVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés
2. BCela rend la table triée
3. CLes clés supprimées doivent être conservées pour toujours pour des raisons de sécurité, si bien que les emplacements ne peuvent jamais être réutilisés
4. DLes pierres tombales accélèrent le hachage