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

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. ALa suppression de l'élément de tête
2. BLa lecture du premier élément
3. CL'insertion en tête
4. DL'accès à l'élément d'indice i

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre d'arêtes du plus long chemin de la racine à une feuille
2. BLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
3. CLe nombre d'enfants de la racine
4. DLe nombre de feuilles de l'arbre

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl stocke des paires clé–valeur
2. BIl stocke des éléments dans l'ordre trié
3. CIl ne permet l'accès qu'à une seule extrémité
4. DIl stocke des éléments sans doublons

Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?

1. AAu nœud le plus à gauche de son sous-arbre droit
2. BÀ son parent, toujours
3. CAu nœud le plus à droite de son sous-arbre gauche
4. DÀ son enfant droit, toujours

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A10
2. B24
3. C11
4. D14

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. A1
2. B√n
3. Cn (il devient une liste chaînée)
4. Dlog₂ n

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

1. AUne matrice d'adjacence indiquant quels sommets ont déjà été retirés
2. BUn tas max ordonné par degré sortant
3. CUne pile de toutes les arêtes visitées
4. DUne file (ou toute collection) des sommets de degré entrant 0

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

1. ACela rend la table triée
2. BVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés
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