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 ...

[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.