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

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

1. ADequeue (défiler)
2. BEnqueue (enfiler)
3. CPush (empiler)
4. DInsert (insérer)

Que fait une fonction de hachage dans une table de hachage ?

1. AElle compte le nombre de clés stockées
2. BElle associe une clé à un indice de la table
3. CElle chiffre les valeurs de la table
4. DElle trie les clés de la table

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. AEnqueue (enfiler)
2. BPush (empiler)
3. CPeek (consulter)
4. DPop (dépiler)

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

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

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

1. ALes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
2. BToutes les clés d'un tas sont égales
3. CC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
4. DLes tas ne contiennent jamais plus de 100 éléments

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUn arbre binaire de recherche
2. BUne table de hachage
3. CUne file
4. DUne pile

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

1. AChaque nœud stocke une seule clé
2. BToutes les feuilles sont à la même profondeur
3. CLes clés ne sont stockées que dans la racine
4. DChaque nœud a exactement deux enfants

Quelle propriété un arbre rouge-noir doit-il respecter ?

1. AChaque nœud doit être rouge
2. BLa racine doit être rouge
3. CTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
4. DTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs