Les arbres binaires de recherche organisent les éléments par ordre croissant au sein de l'arbre. Cependant, les arbres binaires de recherche peuvent devenir déséquilibrés. Dans le pire des cas, un arbre binaire de recherche peut ressembler exactement à une liste chaînée. Donnez un ordre d'insertion des nombres suivants dans un arbre binaire de recherche de manière à ce que l'arbre résultant ressemble à une liste chaînée : 7, 3, 8, 1, 2, 5, 6, 4.

Considérez ces deux approches différentes pour implémenter le type de données abstrait file de priorité en utilisant une structure de données de liste chaînée : (1) organiser les éléments par ordre décroissant de valeur de priorité, et (2) organiser les éléments de manière arbitraire. Décrivez des algorithmes pour insérer un élément ainsi que pour récupérer et supprimer l'élément de plus haute priorité de ces deux structures de données.

Dans notre définition d'une file de priorité, nous avons mis l'accent sur la récupération et la suppression des éléments de plus haute priorité — une file de priorité maximale. Et si nous voulions plutôt prioriser la récupération et la suppression des éléments de plus basse priorité — une file de priorité minimale ? Décrivez un changement simple que nous pourrions apporter pour qu'une file de priorité maximale fonctionne comme une file de priorité minimale.

Décrivez formellement le modèle de problème pour un système médical d'administration de médicaments en termes de données d'entrée et de données de sortie représentées comme des listes, des ensembles, des cartes, des files de priorité et des graphes.

Décrivez formellement le modèle de problème pour un système de recommandation musicale en termes de données d'entrée et de données de sortie représentées comme des listes, des ensembles, des cartes, des files de priorité et des graphes.

Il peut parfois y avoir des milliers, voire des millions, de résultats correspondant à une requête de recherche Web. Pour rendre cette information plus utile aux humains, nous pourrions vouloir classer les résultats selon un score de pertinence de sorte que les résultats plus pertinents apparaissent avant les moins pertinents. Décrivez comment nous pouvons résoudre ce problème de récupération des N plus grands éléments en utilisant les patrons de conception d'algorithmes suivants : (1) un algorithme de tri, et (2) un type de données abstrait file de priorité.

Quel est l'ordre de grandeur en notation Grand O dans le meilleur et le pire des cas de la recherche séquentielle par rapport à N, la taille de la liste ?

Quel est l'ordre de grandeur en notation Grand O dans le meilleur et le pire des cas de la recherche binaire par rapport à N, la taille de la liste triée ?

Quel est l'ordre de grandeur en notation Grand O dans le pire des cas de la recherche séquentielle suivie de la recherche binaire par rapport à N, la taille de la liste triée ?

Quelles sont les deux sous-listes combinées à l'étape finale du tri fusion sur la liste [9, 8, 2, 5, 4, 1, 3, 6] ?

Si un graphe connexe a des poids d'arêtes uniques, l'algorithme de Kruskal trouvera-t-il le même arbre couvrant minimal que l'algorithme de Prim ? Qu'en est-il d'un graphe connexe avec des poids d'arêtes dupliqués ?

Qu'est-ce qu'un algorithme de réduction pour le problème de la recherche de l'élément médian dans une liste ?

L'algorithme de tri par tas applique une file de priorité de tas binaire ordonnée par l'opération de comparaison pour trier les éléments. Que pouvons-nous dire du premier élément retiré du tas binaire s'il implémente une file de priorité minimale ? Qu'en est-il du dernier élément retiré ? La structure de données du tas binaire est-elle triée ?

Les algorithmes de hachage peuvent fournir une solution à temps constant au problème de recherche sous certaines conditions. Quelles sont les conditions nécessaires pour garantir que le temps d'exécution d'un algorithme de recherche par hachage est constant ?

Pourquoi la recherche en profondeur ne peut-elle pas être directement appliquée pour calculer un arbre des plus courts chemins non pondéré ?