Questions de colle MP2I — Structures de données

MP2I, année scolaire 2021-2022 — questions de colle (sans corrigé).

Question 1.

1. Rappeler le principe de l'augmentation de taille dans un tableau dynamique et pourquoi cela garantit une insertion en temps constant amorti.
2. On souhaite rajouter une diminution de la taille ayant de bonnes propriétés.
   1. On va réduire la taille de moitié quand le tableau est rempli à moitié suite à une suppression. Que pensez-vous de cette stratégie ?
   2. Pouvez-vous faire mieux ?

Question 2.

1. Rappeler le principe de la suppression d'un maillon dans une liste chaînée et sa complexité.
2. Quitte à changer des valeurs dans les maillons, pourrait-on faire mieux ?

Question 3. Implémentez un morpion \(n\times n\).

Question 4. Déterminer un algorithme efficace pour vérifier si deux mots sont des anagrammes l'un de l'autre.

Question 5. Déterminer efficacement si un mot est un palindrome à l'aide de piles ou de files.

Question 6. Trouver une manière de faire une structure de données permettant d'ajouter et retirer des éléments comme pour une pile mais aussi de permettre d'obtenir efficacement le maximum courant. On considérera une pile d'entiers pour simplifier.

Question 7. On aimerait implémenter une structure de données permettant de tester si elle est vide, d'insérer un élément à la fin et de pouvoir supprimer et renvoyer la valeur du \(i\)-ème élément.

Proposez et discutez plusieurs implémentations.

Question 8. On suppose qu'on reçoit un flux de données et on cherche une structure de données permettant d'obtenir efficacement les \(k\) dernières valeurs reçues.