2023 Metropole Juin Jour 2

(3 points) Cet exercice porte sur les protocoles réseau. ARPANET, partie ouest représentée sur la figure 1, est le premier réseau à transfert de paquets de données conçu aux États-Unis. En 1971, ce réseau contenait 23 nœuds dont 8 dans la partie ouest : Figure 1. ARPANET en 1971, partie ouest. SRI : Stanford Research Institute AMES : Ames Research (NASA) UCSB : Université de Santa Barbara UCLA : Université de Los Angeles STANFORD : Université, Silicon Valley RAND : Research And Development SDC : System Development Corporation (Santa Monica) UTAH : Université de Salt Lake City On schématise ce réseau par un ensemble de routeurs (appelés A, B, C, D, E, F, G et H) chacun associé directement à un réseau du même nom : Figure 2. Schématisation du réseau. On s’intéresse au protocole RIP, qui minimise le nombre de sauts entre routeurs. Si on l’applique au nœud A de la figure 2, on obtient la table de coûts suivante : Nœud A Destination Coût B 1 C 2 D 1 E 2 F 1 G 1 H 2 23-NSIJ2ME1 Page : 3/10

(3 points) Cet exercice porte sur les bases de données et le langage SQL. On considère une gestion simplifiée des voyages dans l’espace. La base de données utilisée est constituée de quatre relations nommées Astronaute, Fusee, Equipe et Vol. Voici le contenu des tables Astronaute, Fusee, Equipe et Vol. Les clés primaires sont soulignées et les clefs étrangères sont précédées d’un # : Astronaute id_astronaute nom prenom nationalite nb_vols 1 'PESQUET' 'Thomas' 'français' 2 2 'AMSTRONG' 'Neil' 'américain' 8 3 'MAURER' 'Mathias' 'allemand' 1 4 'MCARTHUR' 'Megan' 'américain' 5 Fusee id_fusee modele constructeur nb_places 1 'Falcon 9' 'SpaceX' 6 2 'Starship' 'SpaceX' 100 3 'Soyouz' 'TsSKB Progress' 2 4 'SLS' 'Boeing' 6 Equipe Vol id_vol #id_astronaute id_vol #id_fusee Date 1 1 1 1 '12/09/2022' 1 2 2 4 '25/10/2022' 1 3 3 3 '18/11/2022' 2 1 4 2 '23/12/2022' 2 3 3 1 3 2 3 4 4 2 4 4 On pourra utiliser les mots clés suivants : COUNT, FROM, INSERT, INTO, JOIN, ON, ORDER BY, SELECT, VALUES, WHERE. • Le mot clé COUNT permet de récupérer le nombre d’enregistrements issu de la requête. Par exemple, la requête suivante renvoie la valeur 4. SELECT COUNT (*) FROM Astronaute; 23-NSIJ2ME1 Page : 5/10 • Le mot clé ORDER BY permet de trier les éléments par ordre alphabétique. Par exemple, la requête suivante : renvoie la table

(6 points) Cet exercice porte sur les arbres binaires, les files et la programmation orientée objet. Cet exercice comporte deux parties indépendantes. PARTIE 1 Une entreprise stocke les identifiants de ses clients dans un arbre binaire de recherche. On rappelle qu’un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellement un sous-arbre droit. La taille d’un arbre est le nombre de nœuds qu’il contient. Sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles. On convient que la hauteur d’un arbre ne contenant qu’un nœud vaut 1 et celle de l’arbre vide vaut 0. Dans cet arbre binaire de recherche, chaque nœud contient une valeur, ici une chaine de caractères, qui est, avec l’ordre lexicographique (celui du dictionnaire) : ̶ strictement supérieure à toutes les valeurs des nœuds du sous-arbre gauche ; ̶ strictement inférieure à toutes les valeurs des nœuds du sous-arbre droit. Ainsi les valeurs de cet arbre sont toutes distinctes. On considère l’arbre binaire de recherche suivant : Figure 1. Arbre binaire de recherche.