Les listes chaînées et les arbres binaires de recherche sont deux exemples de structures de données chaînées, dans lesquelles chaque nœud de la structure de données est connecté à d'autres nœuds. Étant donné une liste chaînée des nombres un à sept, organisée par ordre croissant, dessinez deux exemples différents d'arbres binaires de recherche représentant les mêmes nombres.

Étant donné l'arbre binaire de recherche suivant, dessinez la liste chaînée correspondante triée par ordre croissant contenant les mêmes nombres.

Nous avons défini la saisie semi-automatique comme un problème qui prend en entrée une chaîne de caractères qui pourrait représenter le début d'un mot, et produit en sortie une liste de mots qui correspondent à l'entrée. Décrivez deux autres modèles de problème pour la saisie semi-automatique et définissez les ramifications de ces modèles.

Comparez et opposez les modèles de problème de saisie semi-automatique. Quels sont les compromis de chaque modèle de problème ?

Considérez le problème d'organiser les icônes du bureau dans une disposition en grille de manière à ce qu'elles se remplissent colonne par colonne, en commençant par le côté gauche de l'écran. Supposons que nous ayons une liste d'icônes de bureau par ordre alphabétique et que le placement d'une icône dans une position de grille est une opération à temps constant. Quel est l'ordre de grandeur Big O d'un algorithme qui prend chaque icône dans l'ordre donné et place chaque icône dans la prochaine position de grille disponible par rapport à N, le nombre d'icônes de bureau ?

Supposons que nous ayons une liste d'icônes de bureau par ordre alphabétique, mais que le placement d'une icône dans une position de grille est une opération à temps linéaire par rapport au nombre d'icônes. (Peut-être qu'une recherche séquentielle est nécessaire pour vérifier que l'icône n'a pas déjà été placée sur le bureau.) Quel est l'ordre de grandeur Big O de cet algorithme d'arrangement d'icônes par rapport à N, le nombre d'icônes de bureau ?

Pourquoi l'ordonnancement d'intervalles glouton, qui sélectionne la tâche la moins chère et la moins chronophage, ne parvient-il pas à maximiser le nombre de tâches terminées ?

Quelle est une règle simple pour l'ordonnancement d'intervalles glouton qui maximisera le nombre de tâches terminées ?

Le temps d'exécution de la plupart des opérations de file de priorité à tas binaire est en O(log N) par rapport à N, la taille de la file de priorité. Le facteur logarithmique est dû à la hauteur de la structure de données du tas binaire. Mais trouver un élément dans un tas binaire nécessite généralement une recherche séquentielle. Comment pouvons-nous appliquer le patron de conception d'algorithme de hachage pour trouver un élément dans un tas en temps constant ?

Le temps d'exécution du parcours en largeur est en O(|V| + |E|) car chaque sommet atteignable et chaque arête sont traités un par un pendant le parcours du graphe par niveaux. Pourquoi le temps d'exécution de l'algorithme de Prim est-il en O(|E| log |V| + |V| log |V|) ? Expliquez en termes de temps nécessaire pour traiter chaque sommet ou arête dans le graphe.