Ce document a été produit par HEVEA.
Votre browser peut avoir a être configuré pour afficher correctement certains symboles.
Reportez-vous à la documentation d'HEVEA.

Licence d'informatique
Module de C/Unix

Examen -- Partie C

Jean-Luc Levaire

Septembre 2000

Les documents de cours et TD sont autorisés.
 
On rendra deux copies séparées pour la partie Unix et pour la partie langage C. La partie C est à rendre sur une copie de couleur blanche.

Ce document est disponible sous forme d'un fichier PostScript compressé.

1  Questions de cours


Question 1   Donner la représentation schématique de i et de p avant exécution de la boucle for. Qu'affiche le programme ? Quel est le contenu du tableau i à la fin du programme ? 

void 
f (int **i) 
{
  *(*i)++ += 1;
}

void 
main(void) 
{
  int i[5] = {0, 2, 4, 6, 8}, *p = i;

  f(&p);
  printf("%d %d\n", i[0], *p);  
}

Question 2   En quoi consiste la compilation séparée ? Quels en sont les avantages ?

Question 3   Que signifient les déclarations suivantes:

2  Manipulation de graphes

Le but de ce problème est d'implémenter des graphes dirigés. On se propose d'utiliser la structure présentée à la Figure 1. Un graphe G est représenté sous la forme d'une structure contenant trois champs: le nombre de noeuds de G, un tableau suivant contenant pour chaque noeud, sa liste de noeuds suivants, et un tableau precedent contenant pour chaque noeud, sa liste de noeuds précédents. Ces deux tableaux, ainsi que les différentes listes de noeuds sont alloués dynamiquement lors de la création du graphe. Enfin les noeuds sont référencés dans les listes par un numéro d'ordre choisi quelconque à la création du graphe.

Figure 1 : Un graphe G et sa représentation interne.


Question 4   Proposer un type Noeud pour représenter un noeud dans une liste, et un type ListeNoeud pour représenter une liste de noeuds. Proposer alors un type Graphe pour représenter un graphe. Proposer enfin un type Bool pour représenter le type booléen.

Question 5   Écrire une fonction 

Bool Coherent(Graphe G) ;
qui teste si la représentation G d'un graphe est cohérente. Une représentation d'un graphe est cohérente, si les listes des suivants et des précédents sont cohérentes.

Question 6   Écrire une fonction 

Bool Transitif(Graphe G) ;
qui teste si la relation associée à un graphe G est transitive [Un noeud a est en relation avec un noeud b si et seulement si il existe une arête entre a et b dans G. Une relation est transitive si a est en relation avec b et b est en relation avec c, alors a est en relation avec c.].

Question 7   On désire représenter un graphe G sous la forme d'une matrice d'adjacence M. M est une matrice carrée d'entiers, et un élément M[i][j] différent de 0 indique qu'il y a une arête du noeud i vers le noeud j. Écrire une fonction 

int *Convert(Graphe G) ;
qui convertit un graphe G en une matrice d'adjacence. La zone contenant cette matrice sera allouée dynamiquement, et la fonction Convert retourne un pointeur sur son début.

Ce document a été traduit de LATEX par HEVEA.