{{tc_info:td_4-2pages.pdf |Le sujet}}

===== Partie A =====

===== Partie  C =====
==== Exercice 8 ====
** Table d'allocation **

On considère un tableau $T$ de taille $n$ dans lequel 
  * $p<n$ cases sont occupées. Chaque donnée $d$ est indexée par l'adresse $i<n$ donnant sa position dans le tableau & on connaît  sa taille $m$ ($d$ occupe $m$ cases consécutives de $T$). 
  * On suppose de plus 
    * que la //table d'allocation// des différentes cases du tableau est codé au format binaire dans un entier $B$ de $n$ bits :
<code>
  B=0010010100100...01
</code>
    * qu'il existe une fonction $f(B,i)$ donnant le i$^{eme}$ bit de $B$ ($f(B,i)$ vaut 1 si la  i$^{eme}$ case de $T$ est occupée, & 0 si elle est libre).

Écrire un algorithme permettant d'insérer une donnée $d$ dans le premier bloc de $m$ cases disponible (pensez à mettre à jour la table d'allocation $B$).

Peut-on faire mieux en appliquant un pré-traitement à $B$~?



[[tc_info:td7-alt|Ancien sujet]]