Exercices d'entraînement

On souhaite implémenter une pile à l'aide d'une liste chaînée. La classe Maillon est définie ainsi : ```python class Maillon: def __init__(self, valeur, suivant=None): self.valeur = valeur self.suivant = suivant ``` 1. Écrire une classe Pile avec les méthodes : - est_vide() : renvoie True si la pile est vide - empiler(x) : ajoute x au sommet de la pile - depiler() : retire et renvoie l'élément au sommet - sommet() : renvoie l'élément au sommet sans le retirer 2. Quelle est la complexité de chaque opération ?

On représente un graphe non orienté par un dictionnaire d'adjacence : ```python graphe = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } ``` 1. Écrire une fonction parcours_largeur(graphe, depart) qui renvoie la liste des sommets visités en parcours en largeur (BFS) depuis le sommet depart. 2. Modifier la fonction pour qu'elle renvoie également les distances de chaque sommet par rapport au départ. 3. Quelle est la complexité de l'algorithme ?

Soit le schéma relationnel suivant : - LIVRE(isbn, titre, annee_publication, editeur_id) - AUTEUR(id_auteur, nom, prenom, nationalite) - ECRIRE(isbn, id_auteur) - EDITEUR(id_editeur, nom_editeur, ville) Écrire les requêtes SQL pour : 1. Afficher les titres des livres publiés après 2020. 2. Afficher le nom et prénom des auteurs français, triés par nom. 3. Afficher le titre des livres et le nom de leur éditeur. 4. Compter le nombre de livres par éditeur, n'afficher que ceux ayant plus de 5 livres. 5. Afficher les auteurs ayant écrit plus de 3 livres.

Le problème des tours de Hanoï consiste à déplacer n disques de la tour A vers la tour C en utilisant une tour B auxiliaire, avec les règles suivantes : - On ne peut déplacer qu'un disque à la fois - Un disque ne peut être posé que sur un disque plus grand 1. Écrire une fonction récursive hanoi(n, source, auxiliaire, destination) qui affiche les mouvements à effectuer. 2. Combien de mouvements sont nécessaires pour n disques ? 3. Prouver que la complexité est en O(2^n).

1. Convertir le nombre décimal 45 en binaire. 2. Convertir le nombre binaire 10110011 en décimal. 3. Sur 8 bits en complément à deux : a) Représenter -42 b) Quel entier représente 11010110 ? 4. Expliquer pourquoi sur n bits en complément à deux, on peut représenter les entiers de -2^(n-1) à 2^(n-1) - 1.

On définit un arbre binaire par la classe : ```python class Noeud: def __init__(self, valeur, gauche=None, droite=None): self.valeur = valeur self.gauche = gauche self.droite = droite ``` 1. Écrire une fonction recherche(arbre, x) qui renvoie True si x est dans l'ABR, False sinon. 2. Écrire une fonction inserer(arbre, x) qui insère x dans l'ABR et renvoie la racine. 3. Écrire une fonction infixe(arbre) qui renvoie la liste des valeurs en parcours infixe. 4. Que remarque-t-on sur le résultat du parcours infixe d'un ABR ?