Considérez l'arbre de jeu suivant:

Supposons qu'une opération magique a réordonné, sans qu'on le sache, les noeuds afin de maximiser le nombre de coupures alpha-beta. Dans ce contexte, quel coup devrait être exploré en premier entre A,B,C et D?

Indiquez aussi les noeuds min (Ax,Bx,Cx et Dx) qui seront explorés, toujours en considérant un ordre parfait.

Considérer le heap suivant:

                                                      38

                                 /                                               \

                      37                                                                35

           /                            \                                         /                      \

        34                              36                                 25                           32

     /            \                     /          \                     /           \                  /        \

   33             30              14             17            24              23            26           22 

  /    \            /    \         /    \          /    \          /    \            /    \        /    \         /    \

31   27       28    29    13   11       16  15       20  12        21    18   10   19

Supposez que vous supprimez la racine du Max-Heap ci-haut. Cochez les valeurs des noeuds impliquées dans une ou plusieurs comparaisons.

Un Max-Heap peut être converti en un Min-Heap dans un temps :

Considérez l'arbre de jeu suivant:

Supposons qu'une opération magique a réordonné, sans qu'on le sache, les noeuds afin de maximiser le nombre de coupures alpha-beta. Dans ce contexte, quel coup devrait être exploré en premier entre A,B,C et D?

Indiquez aussi les noeuds min (Ax,Bx,Cx et Dx) qui seront explorés, toujours en considérant un ordre parfait.

Le tableau [A,B,C,D,E,F,G,H,I,J] représente un min-heap contenant 10 entiers distincts. Où peut se trouver le troisième plus petit élément?  

Choisissez toutes les positions possibles.

Quel est le nombre minimum de noeuds dans un arbre binaire complet de hauteur h?

Considérer le heap suivant:

                      32

                  /         \

                22         14

           /       \        /      \

        20        8    12        6

     /    \

  16      1

Ajouter successivement les éléments 3, 17 et 35.  Donner votre réponse en présentant le heap sous la forme d'un tableau (utiliser la virgule comme séparateur, ex: 1,2,3,4,5,6,7).

Si vous savez que les éléments d'une liste sont presque triés, quel type de tri parmi les tris suivants allez-vous utiliser?

Trouver l'ordre asymptotique de l'équation de récurrence suivante:

Un programmeur décide de modifier le tri rapide de la manière suivante. Au lieu de prendre un seul pivot à chaque niveau de récursivité qui divise le tableau en deux parties, une partie dont les valeurs des éléments sont plus petites que le pivot et une autre plus grandes que le pivot, il prend deux pivots p₁ et p₂ où p₁ < p₂. 

Ainsi le tableau sera divisé en trois parties: une partie dont les valeurs des éléments sont plus petites que p_1, une autre partie où les valeurs des éléments sont entre p₁ et p₂ et, finalement une partie où les valeurs des éléments sont plus grandes que p₂.

Quel serait l'ordre de ce nouvel algorithme dans le meilleur des cas?