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

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. APile (stack)
2. BGraphe
3. CEnsemble haché (hash set)
4. DFile (queue)

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds qui ont le même parent
2. BUn nœud et son parent
3. CDes nœuds qui n'ont pas d'enfant
4. DDes nœuds de même profondeur dans des sous-arbres différents

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud a au plus deux enfants
2. BChaque nœud a exactement deux enfants
3. CL'arbre a exactement deux niveaux
4. DChaque nœud stocke un nombre binaire

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

1. A14
2. B10
3. C24
4. D11

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

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

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. AÀ son enfant droit, toujours
2. BÀ son parent, toujours
3. CAu nœud le plus à droite de son sous-arbre gauche
4. DAu nœud le plus à gauche de son sous-arbre droit

En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?

1. AIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
2. BIl stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
3. CIl trie les enfants de chaque nœud par fréquence
4. DIl ne garde que la première lettre de chaque mot

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

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