Structures de données partie 1

Question 1

quelles sont les opérations générales pour la Structures de données (7)

Answer 1

• initialisation;
• recherche par adresse;
• recherche par contenu;
• insertion;
• échange;
• suppression;
• tri (ou liste), ordonné par contenu.

Question 2

quelles sont les opérations spécifiques pour la Structures de données (7)

Answer 2

• premier ou dernier élément;
• élément précédent ou suivant;
• etc.

Question 3

Définir les piles et ses deux opérations spécifiques

Answer 3

Liste linéaire particulière qui ne peut accéder qu’au dernier élément
inséré.
– Push: insérer un nouvel élément au sommet de la pile;
– Pop: retirer l’élément inséré en dernier du sommet de la pile.

Question 4

Comment peut s’implémenté des piles?

Answer 4

– tableaux plus une variable auxiliaire SP ;
• indice de l’élément inséré en dernier ;
– listes chaînées (tête = élément inséré en dernier)

Question 5

Avantages et desavantages de l’Implémentation d’une pile par un tableau?

Answer 5

Désavantage: limité par la taille.
–Avantage: accès direct à un élément au sommet (par la
variable sp)

Question 6

Quels sont les avantages desavantages et la caractéristique de l’Implémentation d’une pile par une liste chaînée?

Answer 6

– Lien vers le sommet. Ce lien change à chaque
ajout = dernier élément inséré.
– Avantage: Espace utilisé au besoin.
– Désavantage: Le système doit allouer et
désallouer la mémoire.

Question 7

Définir les files et ses deux opérations spécifiques?

Answer 7

Liste linéaire particulière qui ne peut ajouter qu’en queue et
consulter et supprimer qu’en tête.
Deux opérations spécifiques:
– Enqueue: insérer un nouvel élément à la fin de la file;
– Dequeue: retirer le premier élément de la file (donc
celui qui a été inséré en premier).

Question 8

Critères de Implémentation d’une file par une liste chaînée?

Answer 8

– Deux pointeurs
• Lien vers le sommet = élément inséré en 1er
• plus lien vers la queue (élément inséré en dernier).
– Ces liens changent à chaque opération
– Plus simple que pour une réalisation avec un tableau.

Question 9

Compare file, pile et Queue de priorité!

Answer 9

Pile :Dernier entré, premier sorti
File: Premier entré, premier sorti
Queue de priorité :Le « meilleur » en premier sorti

Question 10

Racine

Answer 10

Le seul nœud qui n’a pas de parent

Question 11

Enfant

Answer 11

Un nœud directement connecté à un autre nœud lorsqu’on

s’éloigne de la racine

Question 12

Frères

Answer 12

Un ensemble de nœuds ayant le même parent

Question 13

Descendant

Answer 13

Un nœud atteignable par une suite d’accès parent-enfant

Question 14

Ancêtre

Answer 14

Un nœud atteignable par une suite d’accès enfant-parent

Question 15

Feuille

Answer 15

Un nœud sans enfant

Question 16

Branche

Answer 16

Connexion entre deux nœuds

Question 17

Chemin

Answer 17

Une séquence de branches qui connectent un nœud à un

descendant

Question 18

Hauteur d’un nœud

Answer 18

Le nombre de branches dans le chemin le plus long entre le

nœud et une feuille

Question 19

Hauteur de l’arbre

Answer 19

Hauteur du nœud racine

Question 20

Profondeur d’un nœud

Answer 20

Le nombre de branches entre le nœud et la racine

Question 21

Niveau

Answer 21

Le niveau d’un nœud est défini comme 1+ la profondeur du

noeud

Question 22

Quelles sont les propriétés du « Max-Heap »

Answer 22

Propriétés:
• Arbre binaire presque complet.
• La valeur d’un nœud est supérieure à la valeur de tous ses nœuds
enfants.
• Les nœuds sont sauvegardés dans un tableau.

Question 23

Combien y a-t-il d’opérateur et decrit les!

Answer 23

5
Insert() Insert un nouvel élément dans la queue
Max() Retourne le meilleur élément
DeleteMax() Enlève le meilleur élément de la queue
Update() Met à jour une valeur (suppose que la nouvelle
valeur a une priorité plus élevée)
Size() Nombre d’éléments dans la queue

Question 24

Qu’est que la racine de l’arbre

Answer 24

L’élément avec la plus grande priorité

Question 25

Quel est le principe de l’extraction de la racine?

Answer 25

– Place le dernier élément du « heap » à la racine.
– Rétablir la propriété du « heap ».
avec downheap
– Utilise DownHeap() pour rétablir la propriété du « heap ».

Question 26

décrit Fonction DownHeap

Answer 26

DownHeap(H,i)

1. g = Gauche(i)
2. d = Droite(i)
3. si g ≤ size[H] et H[g] > H[i]
4. plusGrand = g
5. sinon
6. plusGrand = i
7. si d ≤ size[H] et H[d] > H[plusGrand]
8. plusGrand = d
9. si plusGrand ≠ i
10. H[i] ↔ H[plusGrand]
11. DownHeap(H,plusGrand)

Question 27

Principe de l’insertion et son analyse asymptotique

Answer 27

Principe:
– Ajoute l’élément à la fin du tableau
– Déplace l’élément vers la racine de façon à maintenir la propriété du
« heap ».
Analyse Asymptotique:
• Même principe que l’extraction
• O(lg N)

Question 28

Comment faire pour trier un tableau de n éléments?La première étape consiste à créer un « heap » à partir du tableau
Quel est le principe du heap?

Answer 28

Visite chacun des éléments du heap en commençant
par les feuilles et on applique la fonction DownHeap()

dia 29 a 32

Question 29

fonction BuildHeap, Pourquoi la fonction se comporte de manière linéaire?

Answer 29

• L’opération de base de la fonction est l’échange des valeurs
• Dans le pire cas, combien d’échanges sont effectués par nœuds?
• Dans l’analyse précédente, on suppose que tous les nœuds sont déplacés log n fois
• Est-ce vraiment le cas?

Question 30

Principe de HeapSort et ses étapes

Answer 30

Le heap est déjà partiellement ordonné, nous allons donc utiliser cette propriété.

Étape 1: Échanger la racine avec le dernier élément du tableau
Étape 2: Réduire la taille du heap de 1
Étape 3: Appliquer la fonction DownHeap() sur la racine
Répéter jusqu’à ce que le heap soit vide

ex dia 37 a 46

Question 31

But, l’optimisation et l’utilité de introsort

Answer 31

But:
Être aussi rapide que le tri rapide en pratique mais
être en Θ “ log “ .

Optimisation du tri rapide:
• Applique le tri rapide normal
• Utilise le heapsort si la hauteur de la récursion
dépasse 2 log(n)
• Utilise le tri par insertion pour n=16

Utilisation:
• C++ STL
• MS .NET Framework

Question 32

Considérez un max-heap contenant n nombres.
Étant donné un nombre k et un nombre x, écrire un
algorithme qui détermine si la kième plus grande clé
du heap est plus grand que x.
L’algorithme doit-être en O(k) et peut utiliser O(k)
d’espace mémoire.
2

Answer 32

Sais-tu la réponse pck pas moi!!!