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.
Teste tes connaissances avec un QCM de 46 questions sur Listes, piles, files et arbres.
1. Quel type d’adressage permet d’accéder au contenu d’une variable en utilisant le nom de cette variable ?
2. Dans un programme C, qu’est-ce qu’un pointeur contient précisément ?
Révisez le cours complet dans la fiche de révision de Listes, piles, files et arbres.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards