Numérique et sciences informatiques · 1ere

Algorithmique avancée : structures de données et complexité

Ce que tu dois retenir

Chapitre 1 — Les structures de données : organiser l'information

L'accès à un élément d'un tableau par son indice est direct et rapide.

Chapitre 2 — Piles et files : ranger pour mieux traiter

La pile mémorise l'ordre inverse des actions ; la file conserve l'ordre d'arrivée.

Chapitre 3 — Dictionnaires et ensembles : accès par clé

Avec une clé, l'accès à une valeur est direct, comme chercher un mot dans un dictionnaire papier grâce à l'ordre alphabétique.

Chapitre 4 — Complexité : mesurer l'efficacité d'un algorithme

La complexité permet de comparer des algorithmes indépendamment de la machine utilisée.

Teste-toi

1. Quelle structure de données fonctionne selon le principe LIFO ?

AA. Une pile
BB. Une file
CC. Un tableau
DD. Un dictionnaire
Voir la réponse

Réponse : A — A. Une pile

LIFO = Last In, First Out : le dernier élément ajouté est le premier retiré, c'est la pile.

2. Dans un tableau Python de n éléments, quel est l'indice du dernier élément ?

AA. n
BB. n-1
CC. 1
DD. n+1
Voir la réponse

Réponse : B — B. n-1

Les indices commencent à 0, donc le dernier élément est à l'indice n-1.

3. Quelle est la complexité d'une recherche séquentielle dans un tableau de taille n ?

AA. O(1)
BB. O(log n)
CC. O(n)
DD. O(n²)
Voir la réponse

Réponse : C — C. O(n)

On peut devoir parcourir tous les éléments du tableau, donc le nombre d'opérations est proportionnel à n.

4. Un dictionnaire associe :

AA. des indices numériques à des valeurs
BB. des clés uniques à des valeurs
CC. des éléments ordonnés sans doublon
DD. des valeurs uniquement entières
Voir la réponse

Réponse : B — B. des clés uniques à des valeurs

Un dictionnaire est une collection de couples clé-valeur où chaque clé est unique.

5. Laquelle de ces opérations est typique d'une file ?

AA. Empiler
BB. Dépiler
CC. Défiler
DD. Insérer au milieu
Voir la réponse

Réponse : C — C. Défiler

Une file utilise les opérations enfiler et défiler ; empiler/dépiler sont pour une pile.

6. Un algorithme de tri par insertion a une complexité en :

AA. O(n)
BB. O(log n)
CC. O(n log n)
DD. O(n²)
Voir la réponse

Réponse : D — D. O(n²)

Le tri par insertion compare chaque élément à presque tous les précédents, ce qui donne un ordre quadratique O(n²).

7. Pourquoi la recherche dichotomique est-elle plus efficace que la recherche séquentielle sur un tableau trié ?

AA. Elle utilise moins de mémoire
BB. Elle divise l'espace de recherche par deux à chaque étape
CC. Elle fonctionne sur tous les tableaux
DD. Elle trie le tableau
Voir la réponse

Réponse : B — B. Elle divise l'espace de recherche par deux à chaque étape

La dichotomie réduit de moitié la zone à explorer à chaque comparaison, d'où une complexité O(log n).

8. Quel type de structure est un ensemble (set) en Python ?

AA. Une collection ordonnée avec doublons
BB. Une collection non ordonnée d'éléments uniques
CC. Une pile LIFO
DD. Une file FIFO
Voir la réponse

Réponse : B — B. Une collection non ordonnée d'éléments uniques

Un ensemble stocke des éléments uniques, sans ordre garanti et sans doublon.

Retour au cours ruedusavoir.com · Apprendre, c'est avancer.