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

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

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

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

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

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre d'enfants de la racine
2. BLe nombre de feuilles de l'arbre
3. CLe nombre d'arêtes du plus long chemin de la racine à une feuille
4. DLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

1. AChaque ligne contient exactement un 1
2. BElle est toujours triangulaire supérieure
3. CElle est symétrique par rapport à la diagonale principale
4. DSa diagonale principale contient toujours des 1

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALe tri de nombres
2. BLes recherches par préfixe, comme l'autocomplétion
3. CLe stockage de matrices
4. DLa recherche des plus courts chemins

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 + 1 et i + 2
3. Ci/2 et i/2 + 1
4. D2i et 2i + 1

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

1. APar niveaux seul
2. BPréfixe et postfixe
3. CPréfixe seul
4. DPréfixe et infixe

Pourquoi ne peut-on pas simplement supprimer des éléments d'un filtre de Bloom standard en remettant leurs bits à zéro ?

1. ALes bits d'un filtre de Bloom ne peuvent pas être modifiés après sa création
2. BLa suppression porterait le taux de faux positifs à 100%
3. CLes filtres de Bloom stockent les éléments complets, qui sont introuvables une fois hachés
4. DCes bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs