2021 Metropole Candidat Libre Sujet 2

(4 points) Cet exercice porte sur les bases de données relationnelles et le langage SQL. L’énoncé de cet exercice utilise les mots du langage SQL suivants : SELECT FROM, WHERE, JOIN ON, INSERT INTO VALUES, UPDATE, SET, DELETE, COUNT, AND,OR. On considère dans cet exercice une gestion simplifiée des emprunts des ouvrages d’un CDI. La base de données utilisée sera constituée de trois relations (ou tables) nommées Eleves, Livres et Emprunts selon le schéma relationnel suivant : Dans ce schéma relationnel, un attribut souligné indique qu’il s’agit d’une clé primaire. Le symbole # devant un attribut indique qu’il s’agit d’une clé étrangère et la flèche associée indique l’attribut référencé. Ainsi, l’attribut idEleve de la relation Emprunts est une clé étrangère qui fait référence à la clé primaire idEleve de la relation Eleves.

(4 points) Cet exercice porte sur la gestion des processus et des ressources par un système d’exploitation.

(4 points) Cet exercice porte sur les arbres binaires de recherche et la programmation orientée objet. 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. Un nœud sans sous-arbre est appelé feuille. 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. Ainsi la hauteur d’un arbre réduit à un nœud, c’est-à-dire la racine, est 1. Dans un arbre binaire de recherche, chaque nœud contient une clé, ici un nombre entier, qui est : • strictement supérieure à toutes les clés des nœuds du sous-arbre gauche ; • strictement inférieure à toutes les clés des nœuds du sous-arbre droit. Ainsi les clés de cet arbre sont toutes distinctes. Un arbre binaire de recherche est dit « bien construit » s’il n’existe pas d’arbre de hauteur inférieure qui pourrait contenir tous ses nœuds. On considère l’arbre binaire de recherche ci-dessous.

(4 points) Cet exercice porte sur la programmation en général et la récursivité en particulier. On s’intéresse dans cet exercice à un algorithme de mélange des éléments d’une liste.

(4 points) Cet exercice porte sur la programmation en général. Étant donné un tableau non vide de nombres entiers relatifs, on appelle sous-séquence une suite non vide d'éléments voisins de ce tableau. On cherche dans cet exercice à déterminer la plus grande somme possible obtenue en additionnant les éléments d'une sous-séquence. Par exemple, pour le tableau ci-dessous, la somme maximale vaut 18. Elle est obtenue en additionnant les éléments de la sous-séquence encadrée en gras ci- dessous (6 ; 8 ; -6 ; 10). -8 -4 6 8 -6 10 -4 -4