Ch25 – Algorithmique appliquée – QCM

Question 1

Quelle est la complexité de la recherche séquentielle dans un tableau de \(n\) éléments (pire cas) ?

\(O(1)\) \(O(n)\) \(O(\log n)\) \(O(n^2)\)

Question 2

Quelle condition est indispensable pour appliquer une recherche dichotomique ?

le tableau doit contenir des entiers le tableau doit être de taille paire le tableau doit être trié le tableau ne doit pas contenir de doublons

Question 3

La recherche dichotomique dans un tableau trié de \(n\) éléments a une complexité de :

\(O(\log_2 n)\) \(O(n)\) \(O(n \log n)\) \(O(1)\)

Question 4

On applique une passe de tri à bulles sur \([5, 3, 1, 4, 2]\). Quel est le résultat après la première passe complète ?

\([1, 2, 3, 4, 5]\) \([3, 5, 1, 4, 2]\) \([1, 3, 4, 2, 5]\) \([3, 1, 4, 2, 5]\)

Question 5

Quelle est la complexité moyenne du tri rapide (quicksort) ?

\(O(n^2)\) \(O(n \log n)\) \(O(n)\) \(O(\log n)\)

Question 6

Une structure de données LIFO (dernier entré, premier sorti) est :

une file une liste chaînée une pile un tableau trié

Question 7

On empile successivement \(10\), \(20\), \(30\) dans une pile, puis on effectue un pop(). Quelle valeur est retournée ?

\(30\) \(10\) \(20\) la pile est vidée entièrement

Question 8

Tout algorithme récursif doit obligatoirement comporter :

une boucle while au moins deux appels récursifs un tableau trié au moins un cas de base (condition d'arrêt)

Question 9

Pour résoudre les tours de Hanoï avec \(n\) disques, le nombre de déplacements nécessaires est :

\(n!\) \(2^n - 1\) \(n^2\) \(2n\)

Question 10

Pour la liste triée \([2, 4, 6, 8]\) (\(n=4\), nombre pair), comment calcule-t-on la médiane ?

l'élément central, soit \(6\) le premier élément, soit \(2\) la moyenne des deux éléments centraux : \((4+6)/2 = 5\) la moyenne de tous les éléments : \(5\)

Question 11

Quelle relation d'ordre croissant des complexités est correcte (de la plus rapide à la plus lente) ?

\(O(1) \lt O(\log n) \lt O(n) \lt O(n\log n) \lt O(n^2) \lt O(2^n)\) \(O(1) \lt O(n) \lt O(\log n) \lt O(n^2) \lt O(n\log n) \lt O(2^n)\) \(O(2^n) \lt O(n^2) \lt O(n\log n) \lt O(n) \lt O(\log n) \lt O(1)\) \(O(\log n) \lt O(1) \lt O(n) \lt O(n^2) \lt O(n\log n) \lt O(2^n)\)

Question 12

Pour gérer efficacement une file (FIFO) en Python, quelle structure faut-il préférer ?

list avec list.pop(0) un dictionnaire un tableau trié collections.deque avec popleft()