Flashcards: Listes, piles, files et arbres — 91 cartões

Qu'est-ce que l’adressage direct en programmation ?

Accéder au contenu d’une variable par son nom.

Qu'est-ce qu'un pointeur en C ?

Une variable qui contient l’adresse d’une autre variable et est typée.

Que fait l’opérateur & en langage C ?

Il récupère l’adresse d’une variable.

Que permet l’opérateur unaire * en C ?

D’accéder au contenu de la variable pointée.

Qu'est-ce que l’allocation dynamique ?

Réserver la mémoire pendant l’exécution quand la taille n’est pas connue à la compilation.

Que fait la fonction malloc en C ?

Elle réserve un bloc mémoire et renvoie son adresse ou NULL si insuffisant.

Quelle différence y a-t-il entre calloc et realloc ?

Calloc alloue et initialise à zéro, realloc ajuste la taille d’un bloc existant.

Que faut-il faire après une allocation dynamique en C ?

Tester le pointeur contre NULL puis libérer la mémoire avec free.

Quelle relation utilise la recherche ?

Une relation d’équivalence telle que l’égalité.

Quelle relation utilise le tri ?

Une relation d’ordre total telle que l’infériorité ou l’égalité.

Comment fonctionne la recherche séquentielle ?

Elle compare chaque élément avec l’objet recherché et s’arrête si trouvé ou fin.

Comment agit la recherche dichotomique sur une collection triée ?

Elle découpe autour d’un indice médian et cherche dans la moitié inférieure ou supérieure.

Que fait le tri par sélection dans la partie non triée ?

Il cherche le plus petit élément et le permute avec le premier de cette partie.

Comment fonctionne le tri à bulles ?

Il compare des cases contiguës et fait remonter les plus petits éléments vers le début.

Quelle est la complexité en temps du tri par sélection et du tri à bulles ?

Elle est de l’ordre de O(n²) dans le cas étudié.

Qu’est-ce que la récursivité ?

Le mécanisme par lequel une fonction s’appelle elle-même.

Qu'est-ce qu'un fichier en informatique ?

Un ensemble de données stockées sur une mémoire de masse persistante.

Quelle différence principale existe entre un fichier texte et un fichier binaire ?

Le fichier texte est à accès séquentiel, le fichier binaire permet l'accès direct.

Quel est l'ordre général pour manipuler un fichier ?

Ouverture, lecture ou écriture, puis fermeture.

Que fait la fonction fopen en cas d'échec d'ouverture ?

Elle renvoie NULL.

Quel mode d'ouverture permet la lecture seule d'un fichier existant ?

Le mode r.

Que fait la fonction fread ?

Elle lit des éléments binaires dans un tampon.

Que fait la fonction fwrite ?

Elle écrit des éléments binaires depuis un tampon.

Que fait la fonction fseek et que renvoie-t-elle en cas de succès ?

Elle déplace le descripteur et renvoie zéro en cas de réussite.

Quels éléments contient une liste simplement chaînée ?

Une tête, une queue et des maillons avec information et pointeur suivant.

Comment sont alloués les maillons d'une liste chaînée ?

Ils sont alloués dynamiquement et dispersés en mémoire.

Quelle différence d'accès existe entre tableaux et listes chaînées ?

Les tableaux offrent un accès direct, les listes un parcours séquentiel.

Que contient généralement une structure de liste ?

Un pointeur debut, un pointeur fin et un champ taille.

Que fait l'initialisation d'une liste simplement chaînée ?

Elle met debut et fin à NULL et taille à zéro.

Quelles étapes comprend l'insertion d'un maillon ?

Créer, allouer, remplir, mettre à jour pointeurs et incrémenter taille.

Comment se fait l'insertion en tête d'une liste ?

Créer maillon, affecter donnée, pointer suivant vers debut, actualiser debut et fin si vide, incrémenter taille.

Comment se déroule la suppression en tête d'une liste ?

Sauvegarder maillon, avancer debut, décrémenter taille, mettre fin à NULL si vide, récupérer donnée, libérer maillon.

Qu'est-ce qu'une liste doublement chaînée ?

Une liste où chaque maillon pointe vers son successeur et son prédécesseur.

Quels pointeurs contient une liste doublement chaînée ?

Elle contient les pointeurs debut et fin ainsi qu'un champ taille.

Que contient chaque maillon d'une liste doublement chaînée ?

Chaque maillon contient une donnée, un pointeur suivant et un pointeur precedent.

Que fait l'initialisation d'une liste doublement chaînée ?

Elle affecte NULL à debut et fin et zéro à taille après allocation.

Que met à jour une insertion dans une liste doublement chaînée ?

Les pointeurs suivant et precedent du nouveau maillon et des maillons voisins.

Que se passe-t-il lors de la suppression par position dans une liste doublement chaînée ?

Les voisins sont reliés, la donnée récupérée, la mémoire libérée et taille décrémentée.

Comment une liste doublement chaînée permet-elle un affichage direct et inverse ?

Grâce à ses deux pointeurs de liaison, debut vers fin et fin vers debut.

Qu'est-ce qu'une pile en informatique ?

Une pile est une structure linéaire dynamique de type LIFO.

Que fait l'empilement dans une pile ?

Il crée un maillon, place la donnée, le relie à l'ancien début, actualise début et incrémente taille.

Que se passe-t-il lors du dépilement d'une pile non vide ?

Le maillon début est retiré, début avancé, donnée récupérée, maillon libéré et taille décrémentée.

Qu'est-ce qu'une file en informatique ?

Une file est une structure linéaire de type FIFO avec insertion en queue et suppression en tête.

Que fait l'enfilement dans une file ?

Il crée un maillon, l'ajoute en fin, pointe début si vide, puis incrémente taille.

Que fait le défilement dans une file ?

Il retire le maillon début, avance début, récupère la donnée, libère le maillon, décrémente taille et met fin à NULL si vide.

Comment reconnaît-on un mot bien parenthésé avec une pile ?

On empile chaque parenthèse ouvrante et dépile la correspondante à chaque fermante.

Quand accepte-t-on un mot bien parenthésé en utilisant une pile ?

Si la pile n’est jamais vide lors d’une fermeture et est vide à la fin.

Où place-t-on les opérateurs en notation infixée ?

Entre leurs opérandes.

Où place-t-on l’opérateur en notation préfixée ?

Avant ses opérandes.

Où place-t-on l’opérateur en notation postfixée ?

Après ses opérandes.

Comment fonctionne l’évaluation d’une expression postfixée ?

On empile les valeurs, dépile les opérandes pour chaque opérateur, applique l’opération, puis empile le résultat.

Quelle est la valeur finale de l’expression postfixée 6 5 2 3 + 8 * + 3 + * ?

288.

Comment convertit-on une expression infixe en postfixée ?

On envoie les opérandes en sortie, empile les opérateurs selon leur précédence, et dépile ceux de précédence supérieure ou égale avant d’empiler le courant.

Qu'est-ce qu'un arbre binaire ?

Une structure dynamique non linéaire avec au maximum deux fils par nœud.

Quelle caractéristique distingue la racine dans un arbre ?

Elle n'a pas de père.

Qu'est-ce qui caractérise une feuille dans un arbre ?

Elle n'a pas de fils.

Que contient un nœud d'arbre binaire ?

Une information et deux pointeurs vers ses sous-arbres gauche et droit.

Comment se calcule la hauteur d'un arbre binaire non vide ?

1 plus le maximum des hauteurs de ses sous-arbres gauche et droit.

Comment se calcule le nombre de nœuds d'un arbre binaire non vide ?

1 plus la somme des nombres de nœuds de ses deux sous-arbres.

Quelle est la différence principale entre un parcours en profondeur et un parcours en largeur ?

La profondeur explore une branche entièrement avant la suivante, la largeur visite niveau par niveau.

Quelle est la valeur du nombre de nœuds d’un arbre vide ?

Le nombre de nœuds d’un arbre vide vaut 0.

Comment calcule-t-on le nombre de nœuds d’un arbre non vide ?

Il vaut 1 plus la somme des nombres de nœuds de ses sous-arbres gauche et droit.

Quelle est la valeur du nombre de feuilles d’un arbre vide ?

Le nombre de feuilles d’un arbre vide vaut 0.

Combien de feuilles a un arbre dont la racine est une feuille ?

Il a 1 feuille.

Comment calcule-t-on le nombre de feuilles d’un arbre non-feuille ?

Il est égal à la somme des nombres de feuilles de ses deux sous-arbres.

Quelle est la valeur du nombre de nœuds internes d’un arbre vide ?

Le nombre de nœuds internes d’un arbre vide vaut 0.

Quelle est la valeur du nombre de nœuds internes d’un arbre réduit à une feuille ?

Le nombre de nœuds internes d’un arbre réduit à une feuille vaut 0.

Comment calcule-t-on le nombre de nœuds internes d’un arbre non réduit à une feuille ?

Il vaut 1 plus la somme des nombres de nœuds internes de ses sous-arbres.

Dans un parcours préfixe RGD, quel est l'ordre de traitement des nœuds ?

On traite la racine avant le fils gauche puis le fils droit.

Quel ordre suit un parcours infixe GRD dans un arbre binaire ?

On traite le fils gauche, puis la racine, puis le fils droit.

Que fournit un parcours infixe appliqué à un arbre binaire de recherche ?

Il fournit les valeurs dans l’ordre croissant.

Dans un parcours postfixe GDR, quel est l'ordre de traitement des nœuds ?

On traite le fils gauche, puis le fils droit, puis la racine.

Comment la fonction DFS traite-t-elle la racine dans un parcours préfixe ?

Le traitement de la racine est placé avant l’appel gauche.

Où place-t-on le traitement de la racine dans un parcours infixe DFS ?

Entre les appels gauche et droit.

Quand traite-t-on la racine dans un parcours postfixe DFS ?

Après l’appel droit.

Comment est représenté un arbre vide ?

Par le pointeur NULL.

Que fait la création d’un arbre à partir d’un élément et deux sous-arbres ?

Elle alloue un nœud, lui attribue la valeur, place les sous-arbres en fils gauche et droit, puis renvoie un pointeur vers ce nœud.

Que cherche l’insertion simple dans un arbre ?

Un fils vide récursivement.

Que fait l’insertion simple si l’arbre est vide ?

Elle crée un arbre.

Que fait l’insertion simple si un fils est vide ?

Elle y insère le nouvel élément.

Quelle est la règle des valeurs dans un arbre binaire de recherche d’entiers ?

Les valeurs du sous-arbre gauche sont inférieures à la racine, celles du sous-arbre droit sont supérieures ou égales.

Où sont insérées les valeurs égales dans un arbre binaire de recherche ?

À droite.

Comment insère-t-on une valeur dans un arbre binaire de recherche vide ?

On crée un nœud.

Quelle différence de recherche existe entre un arbre quelconque et un arbre binaire de recherche ?

Dans un arbre binaire de recherche, la recherche suit une seule branche grâce à l’ordre des valeurs.

Que renvoie la recherche dans un arbre quelconque si l’arbre est vide ?

Elle renvoie 0.

Que renvoie la recherche dans un arbre quelconque si la racine contient la valeur cherchée ?

Elle renvoie 1.

Comment la recherche se poursuit-elle dans un arbre quelconque si la racine ne contient pas la valeur ?

Elle explore logiquement les sous-arbres gauche et droit.

Dans un arbre binaire de recherche, quel sous-arbre est exploré si la valeur cherchée est plus petite que la racine ?

Le sous-arbre gauche est exploré.

Quelle est la méthode de suppression complète d’un arbre ?

Supprimer récursivement le sous-arbre gauche, puis droit, puis la racine.

À quel type de parcours correspond la suppression complète d’un arbre ?

Elle correspond à un parcours postfixe.

Pourquoi la suppression d’un nœud est-elle limitée à une feuille dans ce cours ?

Parce que supprimer un nœud avec des fils impose de réorganiser ou supprimer ses sous-arbres.