Terminale NSI
Plus proche ancêtre communs
1. Compléter le tableau ci-dessous, en mettant en dessous de chaque noeud de l'arbre, son père.
noeud |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
père |
None |
0 |
1 |
1 |
0 |
4 |
4 |
4 |
7 |
7 |
2. En déduire le tableau suivant, donnant, pour chaque noeud de l'arbre, la liste de ses ancêtres:
noeud |
ancêtres |
0 |
0 |
1 |
0, 1 |
2 |
0,1,2 |
3 |
0, 1, 3 |
4 |
0, 4 |
5 |
0, 4, 5 |
6 |
0, 4, 6 |
7 |
0, 4, 7 |
8 |
0, 4, 7, 8 |
9 |
0, 4, 7, 9 |
3. Compléter le tableau suivant, dans lequel on placera à l'intersection de la ligne i
et de la colonne j
, le plus proche ancêtre commun à i
et j
dans l'arbre précédent:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
1 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
0 |
0 |
0 |
0 |
4 |
5 |
4 |
4 |
4 |
4 |
6 |
0 |
0 |
0 |
0 |
4 |
4 |
6 |
4 |
4 |
4 |
7 |
0 |
0 |
0 |
0 |
4 |
4 |
6 |
7 |
7 |
7 |
8 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
7 |
8 |
7 |
9 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
7 |
7 |
9 |
4. Compléter le script Python ci-dessous, pour que la variable a
ait pour valeur l'arbre de la page précédente:
a = { 0: [1, 4],
1: [2, 3],
2: [],
3: [],
4: [5,6,7],
5: [],
6: [],
7:[8,9],
8: [],
9: [] }