D'où vient le mot « algorithme » ?
Réponse : Du mathématicien al-Khwarizmi
Le mot vient de la latinisation du nom du mathématicien al-Khwarizmi, auteur au IXe siècle de traités sur le calcul.
Questions et réponses : Algorithmique & Structures de données
Révisez le thème Algorithmique & Structures de données : voici une sélection de questions de tous niveaux, avec la réponse et une explication. Pour vous tester sans voir les réponses, jouez aux quiz.
Jouer aux quiz Algorithmique & Structures de donnéesFacile
Dans un programme, que désigne une variable ?
Réponse : Un emplacement mémoire nommé dont la valeur peut changer
Une variable est un emplacement mémoire identifié par un nom, dont la valeur peut être lue et modifiée pendant l'exécution.
Quelle structure permet d'exécuter un bloc d'instructions seulement si une condition est vraie ?
Réponse : L'instruction si (if)
L'instruction si (if) évalue une condition et n'exécute le bloc associé que lorsqu'elle est vraie.
Que se passe-t-il avec une boucle tant que dont la condition reste toujours vraie ?
Réponse : Elle ne s'arrête pas sans interruption forcée
Une boucle tant que s'exécute tant que sa condition est vraie : si rien ne la rend fausse, la boucle tourne sans fin.
Qu'est-ce que le pseudo-code ?
Réponse : Une description d'algorithme en langage proche du français, indépendante d'un langage
Le pseudo-code décrit un algorithme dans une langue proche du français, sans dépendre d'un langage de programmation précis.
Dans le tri à bulles, que fait-on à chaque passage sur le tableau ?
Réponse : On compare deux voisins et on les échange s'ils sont mal ordonnés
À chaque passage, les voisins mal ordonnés sont échangés, ce qui fait remonter le plus grand élément restant vers la fin.
Dans une recherche séquentielle sur un tableau non trié de 100 éléments, combien de comparaisons faut-il au maximum ?
Réponse : 100
Dans le pire cas, il faut parcourir tout le tableau : la recherche séquentielle compare l'élément cherché à chaque case, soit 100 comparaisons.
Dans une pile (LIFO), quel élément est retiré en premier ?
Réponse : Le dernier élément ajouté
Une pile fonctionne comme une pile d'assiettes : on retire toujours l'élément qui se trouve au-dessus.
Moyen
Dans une liste chaînée, qu'est-ce qui relie deux éléments successifs ?
Réponse : Une référence (un pointeur) vers l'élément suivant
Chaque élément contient une référence, ou pointeur, vers le suivant, ce qui évite d'avoir un bloc mémoire continu.
Quelle est la complexité de l'accès au i-ème élément d'un tableau, par accès direct ?
Réponse : O(1)
Dans un tableau, l'adresse de l'élément i se calcule directement, quelle que soit la taille du tableau : c'est un accès en temps constant.
Dans un arbre binaire de recherche, où se trouvent les valeurs plus petites que celle d'un nœud ?
Réponse : Dans le sous-arbre gauche
Dans un arbre binaire de recherche, les valeurs inférieures sont dans le sous-arbre gauche et les valeurs supérieures dans le sous-arbre droit.
Dans un tas-min (min-heap), que contient la racine ?
Réponse : Le plus petit élément de l'ensemble
Dans un tas-min, chaque parent est plus petit que ses enfants, donc la racine porte la plus petite valeur.
À quoi sert la fonction de hachage dans une table de hachage ?
Réponse : À calculer, à partir de la clé, la position où ranger la valeur
La fonction de hachage transforme une clé en un indice, qui indique l'emplacement où ranger ou retrouver la valeur.
Quelle structure de données utilise le parcours en largeur (BFS) d'un graphe ?
Réponse : Une file
Le parcours en largeur visite les sommets niveau par niveau, en gérant les sommets à traiter dans l'ordre de leur arrivée.
Quelle est la complexité dans le pire cas du tri fusion ?
Réponse : O(n log n)
Le tri fusion divise le tableau en moitiés puis fusionne les parties : il y a un nombre de niveaux logarithmique, et chaque niveau coûte n.
Quand le tri rapide (quicksort) atteint-il sa complexité du pire cas, en O(n²) ?
Réponse : Quand chaque pivot ne sépare qu'un seul élément d'un côté
Si chaque pivot ne sépare qu'un seul élément d'un côté, il faut environ n partitions successives : c'est le cas d'un pivot naïf sur un tableau trié.
Difficile
Quelle est la complexité en mémoire auxiliaire d'un tri fusion classique sur n éléments ?
Réponse : O(n)
Le tri fusion classique copie les données dans un tableau temporaire lors de la fusion, ce qui demande un espace proportionnel à n.
Quel est le principal prérequis d'un tri par comptage ?
Réponse : Les valeurs doivent être des entiers dans un intervalle connu et de taille raisonnable
Le tri par comptage compte les occurrences de chaque valeur entière : il lui faut donc des clés entières dans un intervalle connu.
Dans l'algorithme de Dijkstra, quelle condition doivent respecter les poids des arêtes ?
Réponse : Les poids doivent être positifs ou nuls
Dijkstra fixe les distances dans l'ordre croissant, ce qui n'est juste que si aucun poids n'est négatif.
Sur quelles propriétés repose principalement la programmation dynamique ?
Réponse : Des sous-problèmes qui se chevauchent et une sous-structure optimale
Elle résout un problème à partir de sous-problèmes qui se répètent, en mémorisant leurs résultats pour ne pas les recalculer.
Donald Knuth est l'auteur de quelle œuvre de référence sur l'algorithmique ?
Réponse : « The Art of Computer Programming »
Donald Knuth a écrit « The Art of Computer Programming », dont le premier volume paraît en 1968.
Dans un arbre AVL, quelle propriété est maintenue pour chaque nœud ?
Réponse : Les hauteurs des deux sous-arbres diffèrent d'au plus 1
Un arbre AVL est un arbre binaire de recherche qui rééquilibre ses sous-arbres pour que leurs hauteurs diffèrent au plus d'une unité.
Dans un arbre rouge-noir, que dit la règle sur les nœuds rouges ?
Réponse : Les enfants d'un nœud rouge sont obligatoirement noirs
Dans un arbre rouge-noir, deux nœuds rouges ne peuvent pas se suivre : les enfants d'un nœud rouge sont noirs.
Quel est le rôle de la fonction heuristique dans l'algorithme A* ?
Réponse : Estimer le coût restant jusqu'à l'objectif pour guider la recherche
A* classe les sommets selon le coût déjà parcouru plus une estimation du coût restant, ce qui oriente la recherche vers l'objectif.
Thèmes proches
Jouer aux quiz Algorithmique & Structures de données