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

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

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

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un arbre de pages mémoire
2. BÀ des emplacements aléatoires choisis par un hachage
3. CDans un seul bloc contigu, les uns à la suite des autres
4. DDe façon dispersée, reliés par des pointeurs

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

1. AL'insertion en tête
2. BL'accès à l'élément d'indice i
3. CLa lecture du premier élément
4. DLa suppression de l'élément de tête

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

1. AO(V²)
2. BO(E)
3. CO(log V)
4. DO(V + E)

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. ALa file de la mémoire du tas
2. BUn arbre binaire de recherche de cadres
3. CLa pile d'appels
4. DUne table de hachage des fonctions

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

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

Combien de temps faut-il pour rechercher une clé quelconque dans un tas binaire min de n éléments ?

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