Sujet du bac 2024 de NSI — Polynésie française, jour 2 (général)

24-NSIJ2PO1 Page : 1 / 15 BACCALAURÉAT GÉNÉRAL ÉPREUVE D’ENSEIGNEMENT DE SPÉCIALITÉ SESSION 2024 NUMÉRIQUE ET SCIENCES INFORMATIQUES JOUR 2 Durée de l’épreuve : 3 heures 30 L’usage de la calculatrice n’est pas autorisé. Dès que ce sujet vous est remis, assurez-vous qu’il est complet. Ce sujet comporte 15 pages numérotées de 1 / 15 à 15 / 15. Le sujet est composé de trois exercices indépendants. Le candidat traite les trois exercices. 24-NSIJ2PO1 Page : 2 / 15 EXERCICE 1 (6 points) Cet exercice porte sur les structures de données FILE et PILE, les graphes et les algorithmes de parcours. Partie A Une agence de voyages organise différentes excursions dans une région de France et propose la visite de certaines villes. Ces excursions peuvent être visualisées sur le graphe ci -dessous : les sommets désign ent les villes, les arêtes représentent les routes pouvant être empruntées pour relier deux villes et les poids des arêtes représentent des distances, exprimées en kilomètre. Figure 1. Graphe pondéré 1. Déterminer le plus court chemin allant du sommet Mp au sommet Nc et préciser la longueur, en kilomètres, de ce chemin. Aucune justification n’est attendue. On souhaite toujours se rendre du sommet Mp au sommet Nc mais en visitant le minimum de villes. 2. Déterminer les deux chemins possibles. 24-NSIJ2PO1 Page : 3 / 15 Partie B L’agence souhaite proposer un itinéraire permettant de visiter toutes les villes. On appelle G le graphe non pondéré ci-dessous. Figure 2. Graphe non pondéré On choisit d’implémenter un graphe par listes d’adjacence, à l’aide d’un dictionnaire, en langage Python, dont : • les clés sont les sommets du graphe ; • la valeur associée à une clé est la liste des voisins de ce sommet clé. Les sommets sont de type str. 3. Donner l’implémentation, en langage Python, du graphe de la figure 2. Le dictionnaire obtenu sera stocké da ns une variable nommée G. Afin …