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

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALe plus court chemin vers tous les autres sommets
2. BLa liste de ses sommets voisins
3. CUne ligne de V valeurs booléennes
4. DLe nombre total d'arêtes du graphe

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

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

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ADans un ordre aléatoire
2. BÉgales à la valeur du nœud
3. CSupérieures à la valeur du nœud
4. DInférieures à la valeur du nœud

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. A2i + 1 et 2i + 2
2. Bi/2 et i/2 + 1
3. C2i et 2i + 1
4. Di + 1 et i + 2

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

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

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

1. A14
2. B24
3. C10
4. D11

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

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

Que fait un arbre splay (splay tree) après chaque accès ?

1. AIl recolorie les nœuds du chemin de recherche
2. BIl fait remonter le nœud accédé jusqu'à la racine par des rotations
3. CIl reconstruit tout l'arbre sous forme équilibrée
4. DIl déplace le nœud accédé vers une feuille