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

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
2. BUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
3. CUn tableau statique ne peut stocker que des nombres
4. DUn tableau statique offre un accès par indice plus lent

Une table de hachage stocke les données sous forme de :

1. AArbre à clés ordonnées
2. BChaîne de longueur fixe
3. CPaires clé–valeur localisées par une fonction de hachage
4. DListe triée uniquement

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud ayant exactement un enfant
2. BLe nœud de plus grande valeur
3. CUn nœud sans enfant
4. DUn nœud sans parent

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice ⌊i / 2⌋ + 1
2. BÀ l'indice ⌊(i − 1) / 2⌋
3. CÀ l'indice i − 1
4. DÀ l'indice 2i + 1

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

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

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

1. AO(log n)
2. BO(n log n)
3. CO(1)
4. DO(n)

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. AAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
2. BCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
3. CStocker chaque nœud visité dans un ensemble haché
4. DTrier la liste et chercher des doublons

Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?

1. APréfixe et infixe
2. BPréfixe et postfixe
3. CPréfixe seul
4. DPar niveaux seul