Final Exam

Question 1

Qu’est-ce qu’une “skip list” ?

Answer 1

une liste chaînée qui permet une recherche plus rapide dans une séquence triée

Question 2

Une “skip list” est similaire à laquelle des structures de données suivantes ?
A) Pile
B) Tas (heap)
C) Arbre binaire de recherche
D) Arbre binaire de recherche balancé

Answer 2

D) Arbre binaire de recherche balancé

Question 3

Quelle est l’amélioration de la complexité en temps pour une “skip list” par rapport à une liste chaînée, en insertion et en suppression pour une liste contenant n éléments ?

A) O(n) à O(log n)
B) O(n) à O(1)
C) Aucune
D) O(n) à O(n2)

Answer 3

A) O(n) à O(log n)

Question 4

À quelle structure de données une “skip list” est-elle similaire en termes de complexité en
temps dans le pire et le meilleur des cas ?

Answer 4

arbre binaire de recherche balancé

Question 5

Le nombre total de nœuds d’une “skip list” est déterminé de manière :

Answer 5

A) probabiliste

B) aléatoire

Question 6

Les affirmations ci-dessous sont-elles vraies ?
Dans un ensemble d’éléments triés, une “skip list” peut implémenter les opérations ci-dessous :
i. étant donné un élément, trouver le plus proche élément dans l’ensemble dans O(log n).
ii.trouver le nombre d’éléments de l’ensemble dans un intervalle donné dans O(log n)

Answer 6

OUI

Question 7

Comment maintenir la propriétés sur plusieurs niveaux d’une “skip list” lorsque des
insertions et des suppressions sont effectuées ?

Answer 7

concevoir chaque niveau avec des probabilités variées

Question 8

Est-ce qu’une “skip list” est comme un arbre balancé ?

Answer 8

OUI

Question 9

Une “skip list” permet d’implémenter l’application maxima-set ?

Answer 9

OUI

Question 10

Qu’est-ce qu’une table de hachage ?

Answer 10

une structure qui associe des clés à des valeurs

Question 11

Comment on appelle lorsque plusieurs éléments sont en compétition pour la même entrée
dans la table de hachage ?

Answer 11

collision

Question 12

Qu’est-ce que l’adressage direct ?

Answer 12

une adresse distincte pour chaque clé possible

Question 13

Quelle est la complexité de l’adressage direct ?

Answer 13

O(1)

Question 14

Qu’est-ce qu’une fonction de hachage ?

Answer 14

une fonction qui calcule la position d’une clé dans la table

Question 15

Quelles peuvent être les techniques pour éviter les collisions ?

Answer 15

A) faire apparaître la fonction de hachage de manière aléatoire
B) utiliser la méthode de chaînage externe
C) utiliser un hachage uniforme

Question 16

Qu’est-ce que le facteur de charge ?

Answer 16

la moyenne des longueurs de chaînage

Question 17

Qu’est-ce que le hachage simple uniforme ?

Answer 17

Toutes les clés possèdent la même probabilité de hacher dans n’importe quelle entrée de la table

Question 18

Dans le hachage uniforme simple, quelle est la complexité de la recherche ?

Answer 18

O(1)

Question 19

Dans le hachage par chaînage séparé, quelle structure de données est la plus efficace?

Answer 19

liste doublement chaînée

Question 20

Arbre binaire de recherche

Vrai ou faux : l’enfant de gauche est toujours inférieur à son parent

Answer 20

Vrai

Question 21

Arbre binaire de recherche

Vrai ou faux : l’enfant à droite est toujours plus grand que son parent

Question 22

Arbre binaire de recherche

Vrai ou faux : ) les sous-arbres gauche et droit doivent également être des arbres binaires de recherche

Answer 22

Vrai