Discussion :

[sarusman]

bonsoir la communauté,
Après un test de qcm passé, voici quelques questions qui m'ont donné du fil à retordre et j'aimerai que vous m'éclairer là dessus:

1. convertir l'expression ((A + B) * C -(D-E) ^ (F + G)) à la notation de préfixe équivalent.
a) -^/-*+ABC-DE+FG
b) AB+C*DE--FG+^
c) ^-*+ABC-DE+FG
d) ^-+*ABC-DE+FG

2. Quelle structure de données est utilisée pour effectuer la récursion?
a) Liste chainée
b) tableau
c) Pile (Stack)
d) String
e) Char

3. Laquelle des structures de données suivante est de type linéaire?
a) String
b) Liste
c) Pile
d) aucune bonne réponse
4. Lequel des algorithmes de tri suivant est de type diviser pour régner?
a) tri à bulles,
b) le tri par insertion,
c) tri rapide,

5. Les listes chainées sont meilleures ...
a) pour les collections relativement permanentes de données ,
b) pour les structures dont la taille et les données sont en constante évolution,
c) le a) et le b)
d) aucune bonne réponse

6: Laquelle des structures de données suivantes est de type non linéaire?
a) String
b) Listes
c) Pile
d) aucune bonne réponse

NB: la question suivante est à réponse ouverte

7. Quelle est la struture de données qui permet les suppressions aux deux extrémités de la liste mais l'insertion à une seule extrémité?


pour mes réponses voilà mes choix

1. b

2. a

3. b

4. c (normalement c'est le tri par fusion mais je ne sais pas pourquoi ce choix n' a pas été mis)

5. b

6. a

7.Aucune idée

cordialement

[Sve@r]

Bonjour

1 => je ne vois pas trop lequel convient mais le b ne convient pas. Le b c'est la notation postfixe (désolé). Me semble que c'est le 1c...
2c => hé oui, la récursion implique un empilement des valeurs qu'on met en attente et un empilement se fait dans une pile...
3 => je ne vois pas trop ce qu'ils entendent par "linéaire". Si c'est des données contigües, alors c'est 3a (une string est un tableau de caractères et un tableau est toujours contigu en mémoire)
4c => C'est vrai que le tri fusion est une division du travail mais le tri rapide part d'un pivot d'où on place à gauche toutes les valeurs inférieures et à droites les valeurs supérieures. Puis on réapplique le même algo sur la partie gauche puis la partie droite. Il s'agit donc bien là aussi d'une division du travail...
5b je suis d'accord
6 => même problématique que 3 mais inversée...
7 => là non plus je ne vois pas...

Bon courage

[foetus]

Si c'est des données contigües, alors c'est 3a (une string est un tableau de caractères et un tableau est toujours contigu en mémoire)

Je sais c'est du C , mais on peut faire un tableau dynamique (une liste chaînée de chunk par exemple): donc contigu en mémoire, cela dépend de l'implémentation de ton tableau.

C'est comme la réponse 2: tableau, string utilisent une structure de données. char est un type de base et faire une pile de récursion avec une liste chaînée au lieu d'une pile - stack (<- d'ailleurs tu l'implémentes comment), c'est toi qui voit

Sinon pour le 7b, je pense à une liste [doublement] chaînée cyclique ("last->Next = first"), et soit il y a une contrainte soit une débilité de marketeux (*)

* -> du style: tu peux supprimer le dernier et le premier maillon, mais l'insertion se fera toujours entre les 2 (donc 1 seule possibilité)

[ternel]

Pour la 7, c'est débile, si on connait une extrémité qu'on peut changer, on peut le faire en ajout comme en suppression.

[foetus]

Pour la 7, c'est débile, si on connait une extrémité qu'on peut changer, on peut le faire en ajout comme en suppression.

Bon non justement c'est "la feinte du loup gris"

Si tu as une structure cyclique avec 2 pointeurs last et first, alors:

1. Pour la suppression, tu peux choisir de supprimer l'un ou l'autre.
2. Mais pour l'insertion, que ce soit une insertion à la fin ou au début, le nœud sera toujours ajouter au milieu des 2 nœuds. Et alors ce nœud devient le dernier? le premier?. Donc quelle que soit la façon dont tu gères tes pointeurs, il sera toujours "ajouté à la fin"

[sarusman]

Merci pour toutes vos interventions pertinentes;
j'aimerai exposer sur certaines questions ma façon de raisonner et à vous de me guider:

=>pour la question 6, mon choix est porté sur le a) car dans certains tutos on dit les listes linéaires chainées et comme une pile est un cas particulier de listes alors je ne pouvais que prendre les String qui sont des tableaux de caractères et à ce que je sache les tableaux sont des types structurés

=> Et c'est pour cette même raison (liste linéaire chainée) qu'à la question 3 j'ai choisi le b) (et dans ce cas, je devrai aussi prendre le c) car les piles sont un cas particulier des listes chainées), c'est pertubant!!!

=> Pour la question 2 je ne sais quoi dire? et j'aimerai savoir pourquoi à la question 1 ce n'est pas le d) puisqu'elle peut aussi être une notation préfixée

=> Pour le 7, c'est liste doublement chainée cyclique ou quoi?

Merci encore ...

[foetus]

Ouais, après recherche sur Internet, on parle de structure linéaire, et de données contiguës en mémoire

Une structure linéaire, c'est une structure dans laquelle chaque élément à un successeur (sauf le dernier) et que l'on parcourt sans redondance (donc un unique successeur)

Donc dans ce cas: une liste chaînée, une pile (LIFO), une file (FIFO) sont des structure linéaires.
De même, les tableaux statiques et les char sont des types de base en C.

Maintenant: Les tableaux et les chaînes de caractères: types de base? structures linéaires?

Et pour finir: pour moi un type structuré (puisque tu en parles), c'est un type fait avec un struct.
Donc tous les types qui ont pour 1 élément, plusieurs données (la valeur + un pointeur par exemple) sont des types structurés


Sur ce, je vais prendre un cachet d'aspirine ... voire même 2


Et pour la réponse 7, MOI, je mets une pièce sur liste [doublement <- éventuellement] chaînée cyclique

[Sve@r]

...et faire une pile de récursion avec une liste chaînée au lieu d'une pile - stack (<- d'ailleurs tu l'implémentes comment), c'est toi qui voit

On n'est pas obligé d'utiliser des listes chainées pour implémenter une pile. On peut très bien l'implémenter via malloc/realloc.
On alloue N et on insère n (<= N) éléments. Et dès que n atteint N, on réalloue N de plus. Et au pop on supprime l'élément [n] et on décrémente n...

Pour moi la récursion utilise donc une pile. Le fait que tu implémentes ta pile par une liste chainée ça c'est de ton implémentation...

[Invité]

Pour la réponse 7, mon professeur d'algorithmie nous scanderait haut et fort : " Il s'agit d'une liste chainée ".

Pour la simple et bonne raison qu'à partir d'une liste chainée, il en revient à nous et à nous seul de définir la manière dont l'ajout et l'insertion se font. Pile, File, tout ce genre de chose sont des conventions et l'on peut tout aussi bien définir une pile contenant un pointeur sur le dernier de ces éléments et pour une raison X ou Y dépiler le dernier plutôt que le premier élément. ( c'est crade, je l'accorde, mais dans les faits rien ne l'empêche en C ).

[gangsoleil]

Pour la réponse 7, mon professeur d'algorithmie nous scanderait haut et fort : " Il s'agit d'une liste chainée ".

Pour la simple et bonne raison qu'à partir d'une liste chainée, il en revient à nous et à nous seul de définir la manière dont l'ajout et l'insertion se font.

Oui, mais pour autant tu ne peux pas dire que la liste chaînée limite l'insertion à une extrémité. Et si tu as une liste circulaire, il n'y a pas d'extrémité du tout


Soit dit en passant, si on veut être extrèmement rigoureux, on pourrait dire qu'aucune de ces questions ne concerne le langage C.

[Vincent PETIT]

Pour la réponse 7, je pense à une pile.

- On insert toujours l'élément en haut de la pile.
- Lorsqu'on dépile, on retire le premier élément (destruction) et on remonte toute la pile de 1 niveau (d'où la déstruction du dernier élément) du moins c'est ainsi que fonctionne une pile matérielle.

Logiciellement parlant c'est un vulgaire tableau qui aurai un ressort tout en bas et des que tu retires le premier élément tout remonte. Pour moi au vu de cette image ça m'a l'air de coller avec la question 7.

Me goure je ?

[Invité]

Pour la réponse 7, je pense à une pile.

- On insert toujours l'élément en haut de la pile.
- Lorsqu'on dépile, on retire le premier élément (destruction) et on remonte toute la pile de 1 niveau (d'où la déstruction du dernier élément) du moins c'est ainsi que fonctionne une pile matérielle.

Logiciellement parlant c'est un vulgaire tableau qui aurai un ressort tout en bas et des que tu retires le premier élément tout remonte. Pour moi au vu de cette image ça m'a l'air de coller avec la question 7.

Me goure je ?

Si l'on prends une pile dans sa définition logique strict, oui.

Une pile doit normalement suivre le principe LIFO ( Last in, First out ) : Le dernier arrivé est le premier à partir. De ce fait, on insère et on retire toujours en tête de pile...

7. Quelle est la struture de données qui permet les suppressions aux deux extrémités de la liste mais l'insertion à une seule extrémité?

Ne respecte donc pas la logique d'une pile.

Ce qui t'induit en erreur je pense n'est non pas la logique derrière la pile, mais son implémentation logicielle qui diffère d'une pile matériel.
Si l'on implémente une pile avec un tableau, on va plutôt jouer avec un indice de "tête". Chaque fois que l'on empile un élément, on incrémente l'indice de tête et on place l'élément. Quand on dépile un élément, on prends l'élément disponible à l'indice de la tête et par la suite on décrémente cet indice. De ce fait, on se retrouve avec une implémentation plus performante que si l'on remontait en permanence tout les éléments après dépilation (et on ne retrouve plus cette notion de "on enlève à chaque extrémité").

On pourrait également implémenter cette pile avec une liste chaîné, dont on aurait indiqué que le mode d'ajout et de suppression ne se fait que sur le premier élément de la liste. Pareillement, on ne se retrouve plus avec une notion de "on enlève à chaque extrémité".

Si l'on reste dans un niveau strictement logique, on ne peut donc pas dire que cela soit une pile.

[Vincent PETIT]

Ok, merci pour l'explication.
Donc si j'ai bien compris dans une pile logicielle on vient finalement insérer un élément en écrasant l'éléments précédemment sortie (en jouant avec les index) mais sans remonter la pile ?

[foetus]

Si je ne me trompe pas, toi tu décris une pile en utilisant un tableau dont le haut de la pile est le premier élément: donc oui lorsque tu dépiles, il faut que tu déplaces tous tes éléments de -1 [tu les remontes]

Or archMqx. lui parle de 2 autres implémentations.
Soit avec un tableau, mais dont le haut de la pile est le dernier élément. Donc tu n'as plus besoin de "faire remonter les éléments". Il y a juste un indice à gérer [et qui peut-être utilisé aussi comme nombre d'éléments dans la pile]

Ou alors si tu veux que le haut de la pile soit le premier élément, tu l'implémentes avec une liste chaînée et donc dans ce cas, ce sera des insertions/ suppressions [seulement] en tête

[Vincent PETIT]

J'ai compris c'est très clair.
Je te remercie.

A+
Vincent