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

Un graphe est constitué de :

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

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
2. BDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
3. CDes données et uniquement un pointeur vers le nœud suivant
4. DDeux copies des données et un pointeur

Que fait l'opération peek (ou top) sur une pile ?

1. AElle renvoie l'élément du sommet sans le retirer
2. BElle retire tous les éléments de la pile
3. CElle renvoie l'élément du fond de la pile
4. DElle retire l'élément du sommet et le renvoie

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. An (il devient une liste chaînée)
2. B1
3. Clog₂ n
4. D√n

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

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

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AL'ordre par niveaux
2. BL'ordre d'insertion
3. CToujours l'ordre décroissant
4. DL'ordre croissant

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

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

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

1. APréfixe seul
2. BPar niveaux seul
3. CPréfixe et postfixe
4. DPréfixe et infixe