Skip to content

Séquence 4

L'objectif de la séquence est de travailler sur la construction de types abstraits, parmi lesquels les structures linéaires (liste, pile, file) On poura lire le chapitre 10 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

On considère une pile Pmunie de ses opérateurs empileret dépiler. On effectue successivement les opérations suivantes:

empiler(P,a)
empiler(P,b)
dépiler(P)
empiler(P,c)
dépiler(P)
dépiler(P)
L'ordre dans lequel les éléments sont enlevés de la piles est : 1. a,c,b 2. b,c,a 3. a,b,c 4. b,a,c

réponses (éléments)

réponse correcte 2. b,c,a

- état de la pile ||
empiler(P,a)
- état de la pile |a|
empiler(P,b)
- état de la pile |ab|
dépiler(P)
- état de la pile |a| b est extrait
empiler(P,c)
- état de la pile |ac|
dépiler(P)
- état de la pile |a| c est extrait
dépiler(P)
-état de la pile || a est extrait

Question 2

Pour vérifier qu'une expression est bien parenthésée avec des parenthèses ( et ), quelles affirmations sont vraies ? 1. Il suffit de vérifier que le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes 2. On utilise 2 compteurs, l'un comptant le nombre de parenthèses ouvrantes, l'autre les fermantes et s'assurer que le premier compteur est toujours plus grand que le second lors du parcours séquentiel de l'expression. 3. L'expression contient maintenant en plus des parenthèses, des crochets [et ]. Pour vérifier que l'expression est bien parenthésée il suffit de rajouter 2 autres compteurs associés aux [et ] et appliquer la même méthode que pour les parenthèses.

réponses (éléments)

  1. Faux : l'expression )(est mal parenthésée et les compteurs ont la même valeur
  2. Faux : en effet il faut qu'à la fin du parcours de l'expression les 2 compeurs aient la même valeur
  3. Faux : même si on a égalité des compteurs en fin de parcours de l'expression, l'expression ({)}sera considérée bien parenthésée alors qu'elle ne l'est pas

Question 3

Dans un arbre binaire de hauteur \(h\) ayant \(n\) noeuds, on prend pour convention que la hauteur de la racine de l'arbre est \(0\),

  1. Quel est le nombre minimal de noeuds possibles à la hauteur \(k\) avec \(0 \leq k \leq h\) ? \(1\), \(k\), \(2k\) \(2^k\), \(2^h\)
  2. Le nombre de noeuds à la hauteur \(h\) est plus petit/égal/plus grand que le nombre de noeuds à la hauteur \(h-1\) ou bien toues les solutions sont possibles ?
  3. Parmi ces inégalités lesquelles sont vérifiées \(n \leq 2^h\), \(n \geq h+1\), \(h \geq \log_2 n-1\)

réponses (éléments)

  1. \(1\) il existe un noeud de l'arbre à la hauteur \(h\) donc un chemin de la racine à ce noeud, donc au moins un noeud à la hauteur \(k\). Un arbre dégénéré (fil de hauteur \(h\)) a un seul noeud à la hauteur \(k\) cqfd.
  2. Toutes les solutions sont possibles (faire des dessins)
  3. \(n \leq 2^h\) : Faux cette inégalité n'est pas forcemment vérifiée, un arbre complet de hauteur \(h\) a \(2^{h+1}-1\) noeuds ce qui est plus grand que \(2^h\) sauf si \(h=0\). \(n \geq h+1\) Vrai, en effet il existe une feuille à hauteur \(h\) donc un chemin de la racine à cette feuille, ce chemin de longueur \(h\) compte \(h+1\) noeuds. \(h \geq \log_2 n-1\) Vrai un arbre de hauteur \(h\) contient au maximum \(2^{h+1}-1\) sommets.

Question 4

On considère l'arbre de 9 noeuds étiquetés, de racine le noeud 1

noeud étiquette fils gauche fils droit
1 E 2 7
2 B 8 /
3 J / /
4 T / /
5 Z / 4
6 F / /
7 R 5 3
8 K 6 9
9 G / /

Parmis ces parcours de l'arbre

[F,G,T,K,Z,J,B,R,E]

[E,B,K,F,G,R,Z,T,J]

[F,G,K,B,T,Z,J,R,E]

[K,F,G,Z,T,R,J,E,B]

[E,R,J,Z,T,B,K,G,F]

[E,B,R,K,Z,J,F,G,T]

[F,K,G,B,E,Z,T,R,J]

donner le parcours correspondant à (s'il existe dans la liste)

  1. un parcours en largeur d'abord
  2. un parcours en profondeur d'abord préfixé
  3. un parcours en profondeur d'abord infixé
  4. un parcours en profondeur d'abord post-fixé

réponses (éléments)

  1. [E,B,R,K,Z,J,F,G,T] parcours en largeur d'abord
  2. [E,B,K,F,G,R,Z,TJ] parcours en profondeur d'abord préfixé
  3. [F,K,G,B,E,Z,T,R,J] parcours en profondeur d'abord infixé
  4. [F,G,K,B,T,Z,J,R,E] parcours en profondeur d'abord post-fixé