INF3105 / Quiz 1

Automne 2020

Groupe Question Réponse / Explication
20 et 40 Cochez les mots clé C++ Il y avaient plus blocs de choix de réponses pour chaque groupe.

Choix qui étaient des mots clé:
int, new, delete, class, return, char, double, friend, struct, float, public

Choix qui n'étaient pas des mots clé:
iostream, sqrt, function, cos, lambda, string

Note: Plusieurs de ces noms identifient des fonctions ou des classes de la bibliothèque standard C++. Ces mots ne sont toutefois pas des mots clé (mots réservés) du langage C++. C'est d'ailleurs possible de réutiliser ces noms, car leur portée est limitée à l'espace de noms std. Exemple: 
#include ...
// ne pas mettre using namespace std;
int main(){
  char[] string = "bonjour";
  std::string cos = "allo";
  double cout=0;
  int endl = 32;
  std::cout << string << cos << std::cos(cout) << endl << std::endl;
}
20 et 40 Cochez les caractéristiques du langage C++ Il y avait plusieurs blocs de choix de réponses pour chaque groupe.

C++ est un langage fortement typé. On ne peut pas affecter une variable dans une autre si leurs types sont incompatibles, à moins de demander une conversion explicite (cast)
C++ n'est pas un langage à typage dynamique. C'est plutôt un langage à typage statique, c'est-à-dire que le type de toutes les variables doit être connu à la compilation.
C++ n'est pas destiné à être interprété par une machine virtuelle. Il est plutôt compilé directement en code machine natif de l'architecture de l'ordinateur cible.
C++ est un langage orienté objet. On peut créer des classes, faire de l'héritage, du polymorphisme, etc.
C++ est un langage de programmation procédurale. Il est possible de diviser notre code en plusieurs procédures/fonctions.
C++ est un langage de programmation générique grâce au mécanisme de templates qui permet d'écrire du code qui s'applique à des données de type différent.
20 La ligne #include "abcde.h" est _____ Comme toutes les lignes qui commencent par un dièse (#), c'est une directive de précompilation. Celle-ci demande l'inclusion d'un autre fichier source (généralement une entête).
40 Qu'est-ce que le code suivant affiche : 
int i;
cout << i << endl;
 Le code compile et ne fait pas d'erreur à l'exécution. Par contre, puisque la variable n'est pas initialisée, la valeur affichée sera une valeur inconnue, soit l'actuelle valeur en mémoire. Utiliser des variables non initialisées peut mener à des comportements non déterministes (pseudo aléatoire) du programme, le rendant difficile à investiguer.
20 Cochez les énoncés où a sera initialisé. int a = 0;
int a {3};
std::string a;
seront initialisés, tandis que
int a;
int* a;
ne le seront pas.

La chaîne std::string a est initialisée, car elle n'est pas un type primitif. Son constructeur par défaut est donc automatiquement appelé.
40 Quelle est la valeur que le code suivant affiche : 
int x=0;
int z=x++;
int y=++z;
cout << ++x+y+z++;
 int x=0; (x vaut 0)
int z = x++; (x vaut 1, z vaut 0)
int y = ++z; (x vaut 1, y vaut 1, z vaut 1)
cout << ++x+y+z++; (x est augmenté de 1 avant l'affichage. z est augmenté de 1 après l'affichage)
Le code affiche donc 2+1+1 = 4.
20 Quelle est la valeur de x affichée : 
int x=1;
int y=++x;
x=++y;
std::cout << x;
 int x=1; (x vaut 1)
int y = ++x; (x vaut 2, y vaut 2)
x = ++y; (x vaut 3, y vaut 3)
Le code affiche donc 3.
40 Qu'affiche le code suivant : 
for(int i = 0; i < 3; i++)
  cout << i;
for(int i = 0; i < 3; ++i)
  cout << i;
 Puisqu'il n'y a pas d'assignation de la variable i à une autre variable lorsqu'elle est incrémentée, i++ et ++i fera strictement la même chose. Les deux boucles affichent donc 012 et l'affichage final est donc 012012.
20 Cochez le ou les énoncé(s) valide(s) qui alloue(nt) un tableau par allocation automatique (une variante de la question demande plutôt dynamique) int a déclare un int (donc pas un tableau)
int a1, a2 déclare deux int (donc pas un tableau)
int*a déclare un pointeur vers un int (donc pas un tableau)
int a[1:10] est une instruction syntaxiquement invalide
int a[1] alloue un tableau (d'une seule case) par allocation automatique
int* a = new int[3] alloue un tableau (de 3 cases) par allocation dynamique
40 Combien de fois le constructeur de la classe Entier est-t-il appelé dans le programme ci-bas ? 
class Entier{/*...*/};
class Point{
  Entier x, y, z;
};
struct Quadrilatere{
  Point p[4];
};
int main(){
  Point a, b, c, d, e;
  Quadrilatere* tp = new Quadrilatere[3];
  return 0;
}
 Il y a en tout 5 Point (a, b, c, d, e) et 3 Quadrilatère (de chacun 4 Point), donc au total 17 Point. Chaque Point contient trois Entier, il y a donc au total eu 17*3 = 51 Entier, et donc 51 appels au constructeur d'Entier.
20 Combien de fois le constructeur de la classe Entier est-t-il appelé dans le programme ci-bas ? 
class Entier{/*...*/};
class Point{
  Entier x, y;
};
struct Pentagone{
  Point p[5];
};
int main(){
  Point a, b, c, d, e;
  Pentagone* tp = new Pentagone[2];
  return 0;
}
 Il y a en tout 5 Point (a, b, c, d, e) et 2 Pentagone (de chacun 5 Point), donc au total 15 Point. Chaque Point contient deux Entier, il y a donc au total eu 15*2 = 30 Entier, et donc 30 appels au constructeur d'Entier.
40 Lesquels des éléments suivants sont des facteurs secondaires influençant le temps d'exécution d'un programme ? Le système d'exploitation utilisé, la qualité de l'implémentation de l'algorithme testé, le langage de programmation utilisé et la qualité du matériel sont tous des facteurs secondaires.

La taille du problème (ex.: n) est plutôt le facteur primaire.
20 Dans quel ordre les corps des destructeurs sont appelés dans le programme suivant ? 
class A{
 ...
};
class B : public A{ // B hérite de A
 ...
};
class C{
 ...
  B b;
};
int main(){
  C c;
  return 0;
}
 L'ordre de construction en C++ est:
  1. appel du constructeur de la classe parent (si la classe hérite d'une autre classe)
  2. appel du constructeur de chaque attribut de la classe
  3. exécution du corps du constructeur
L'ordre de destruction est l'inverse de l'ordre de construction:
  1. exécution du corps du destructeur
  2. appel du destructeur de chaque attribut de la classe
  3. appel du destructeur de la classe parent (si la classe hérite d'une autre classe)
Ainsi, dans notre exemple, lorsque l'objet c est détruit, le corps du destructeur de C est appelé, suivi du destructeur de B.
La destruction de b commence par exécuter le corps du destructeur de B, puis finalement appel le destructeur de la classe parent A.
L'ordre d'exécution du corps des destructeurs est donc C, B, A.
40 Quelle est la complexité temporelle de ___ dans un tableau ? L'enlèvement d'un élément spécifique dans un tableau est O(n) car (1) il faut itérer sur le tableau pour trouver sa position si on ne la connait pas déjà, et (2) en enlevant l'élément, il faut décaler d'une case vers la gauche tous ceux qui étaient à la droite de l'élément enlevé.

La destruction d'un tableau est O(1) car l'instruction delete prend un temps constant, peu importe la quantité de mémoire libérée. Note: Si le tableau avait contenu des objets plutôt que des int, la complexité aurait été O(n) car le destructeur de chaque objet dans le tableau aurait dû être appelé.

La complexité d'une fonction qui double la valeur de chaque élément dans un tableau est O(n), car il faut itérer une fois sur chaque élément.
20 Quelle est la complexité temporelle de ___ dans un tableau ? L'ajout dans un tableau a une complexité amortie de O(1) (voir explications dans les vidéos du cours)

L'insertion à une position i dans un tableau a une complexité de O(n), car tous les éléments déjà présents à une position supérieure à i doivent être décalés d'une case. Dans le pire cas, il faut donc faire n décalages.

Inverser l'ordre des éléments dans un tableau a une complexité de O(n), car il faut faire n/2 échanges de valeurs dans le tableau, ce qui est dans l'ordre de grandeur O(n).
20 et 40 Quelle est la complexité temporelle d'une fonction int compteCommuns(const Tableau<T>& x, const Tableau<T>& y) qui retourne le nombre d'objets T qui sont à la fois dans x et y. La variable n représente la taille maximale des deux tableaux. Considérez le pire cas d'entrée et la meilleure implémentation possible. Une solution est de trier chacun des tableaux en temps O(n log n), puis d'itérer alternativement sur chacun des tableaux pour compter les éléments en communs en temps O(n). Le temps total est donc l'opération ayant pris le plus de temps, le tri, et donc O(n log n).

Note: Une variante de la question demandait la même chose, mais pour 3 tableaux plutôt que 2. Par le même raisonnement, la complexité reste O(n log n).
20 et 40 Quelle est la complexité temporelle d'une fonction int compteUniques(const Tableau<T>& x, const Tableau<T>& y) qui retourne le nombre d'objets T qui apparaissent dans une seule des deux tableaux x et y. La variable n représente la taille maximale des deux tableaux. Considérez le pire cas d'entrée et la meilleure implémentation possible. Avec une solution presque identique à celle de la question précédente, on peut résoudre le problème en O(n log n).
20 et 40 Cochez les complexités ne pouvant pas être simplifiées Les choix de réponses étaient différents pour chaque étudiant.

O(1), O(n), O(n+m), O(n*m), O(n² + m), O(n + m) et O(n³ + m) ne peuvent pas être simplifié.

O(2) se simplifie à O(1)
O(n+1) se simplifie à O(n)
O(7n) se simplifie à O(n)
O(n² + 2m) se simplifie à O(n² + m)
O(2n² + m) se simplifie à O(n² + m)
O(log(n²)) se simplifie à O(log(n)) (car log(n²) = 2 log(n))
O(n² + n) se simplifie à O(n²)
40 Cochez les énoncés vrais par rapport à la complexité Il est vrai que l'analyse asymptotique a pour résultat un ordre de grandeur et que O(f(n)) est l'ensemble des fonctions qui croissent à une vitesse similaire. Par contre, les énoncés entre guillemets suivants sont faux:
  • "la complexité empirique est plus précise que la complexité asymptotique pour estimer le temps lorsque n est très grand". L'analyse empirique est sensible aux facteurs secondaires, à la possible rareté du pire cas et au très grand nombre (parfois infini) d'entrées possibles. Ce n'est donc pas plus précis.
  • "l'analyse amortie consiste à trouver la complexité d'un programme lorsqu'il est lancé avec la valeur la plus probable".
  • "la complexité asymptotique nécessite de considérer les facteurs secondaires". C'est plutôt l'analyse empirique qui considère les facteurs secondaires.
20 L'analyse empirique a comme caractéristiques: Il est vrai que l'analyse empirique est une méthode généralement simple et que cela nécessite un ensemble d'entrées («tests») de taille variable.

Par contre, cette méthode n'est pas capable de détecter facilement le pire cas et ne nécessite pas un langage de programmation de haut niveau.
20 Codez une fonction template <class T>void garderUniques(Tableau<T>& t) qui retire les doublons dans un tableau t. Notez que l'ordre relatif des objets conservés doit être préservé. Ex.: «5 7 6 6 7 9 3 6» devient «5 7 6 9 3». Une solution simple consiste à imbriquer deux boucles for. La première parcourt le tableau reçu. La deuxième, la boucle interne, vérifie si l'élément a déjà été ajouté au résultat. 
void garderUniques(Tableau<T>& t){
    Tableau<T> c=t; // garder une copie
    t.vider(); // t sert maintenant de résultat
    for(int i=0;i<c.taille();i++){
    	bool deja = false;
    	for(int j=0;j<t.taille();j++)
    	    if(c[i]==t[j])
    	    	deja=true;
    	if(!deja)
    	    t.ajouter(c[i]);
    }
}
La solution ci-dessus est en temps O(n²). Elle n'est pas optimale, car il existe une meilleure solution en temps O(n log n). Pour arriver une telle solution, on peut : copier le tableau, trier la copie et créer un tableau de booléens b de même taille (qu'on initialise avec des 'false'). Ensuite, on crée un nouveau tableau r qui contiendra la solution. On itère sur le tableau initial: pour chaque itération, on fait une recherche dichotomique (O(log n)) de l'élément t[i] dans le tableau trié. Si l'élément n'a pas déjà été ajouté dans r (b[i] est faux), on l'ajoute et on met le booléen à vrai.

void garderUniques(Tableau<T>& t){
    Tableau<T> copie=t, ttrie = t;
    trier(ttrie);
    bool* dejapris = new bool[t.taille];
    for(int=i;i<t.taille();i++)
       dejapris[i] = false;
    t.vider(); // t devient maintenant le résultat
    for(int i=0;i<copie.taille();i++){
       int index = rechecheDichotomique(ttrie, copie[i], 0, t.taille());
       if(!dejapris[index]){
           r.ajouter(copie[i]);
           dejapris[index]=true;
       }
    }
    delete[] dejapris;
}
20 Codez une fonction template <class T> Tableau<T> placerUniquesDebut(const Tableau<T>& t) qui retourne une copie d'un tableau dans laquelle les doublons sont déplacés après la première occurrence de tous les objets. L'ordre relatif des objets doit être préservé. Ex.: «5 7 6 6 7 9 3 6» retourne «5 7 6 9 3 6 7 6». On peut utiliser les mêmes solutions qu'à la question précédente, mais en créant un tableau supplémentaire qui stocke les éléments qui sont en double pour pouvoir les ajouter à la fin. 
// Version Simple O(n²)
void garderUniques(Tableau<T>& t){
    Tableau<T> c=t; // garder une copie
    Tableau<T> f; // pour garder les doublons et les placer à la fin
    t.vider(); // t sert maintenant de résultat
    for(int i=0;i<c.taille();i++){
    	bool deja = false;
    	for(int j=0;j<t.taille();j++)
    	    if(c[i]==t[j])
    	    	deja=true;
    	if(deja)
    	    f.ajouter(c[i]);
    	else
    	    t.ajouter(c[i]);
    }
    for(int i=0;i<f.taille();i++)
    	t.ajouter(f[i]);
}
20 Codez une fonction template <class T> Tableau<T> regrouperIdentiques(const Tableau<T>& t) qui regroupe les objets identiques. L'ordre de la première occurrence des objets doit être préservé. Ex.: «5 7 6 6 7 9 3 6» retourne «5 7 7 6 6 6 9 3». On peut faire comme pour garderUniques, mais plutôt que d'avoir un tableau de booléens, il suffit d'ajouter les doublons à la suite les uns des autres.
40 Codez une fonction template <class T>void separerPairImpair(Tableau<T>& t) qui met tous les nombres pairs au début du tableau, et tous les nombres impairs à la fin. Les nombres pairs et impairs doivent garder leur ordre relatif entres eux. Ex.: «1 4 2 5 6 8 3 7» -> «4 2 6 8 1 5 3 7». Une façon est de créer deux tableaux temporaires. Ensuite, on itère sur le tableau t et on ajoute tous les éléments pairs rencontrés dans un des tableaux, et tous les éléments impairs dans l'autre. Finalement, on vide t et on ajoute un-à-un tous les nombres pairs et tous les nombres impairs.
40 Codez une fonction template <class T> void triAlterne(const Tableau<T>& t) qui tri le tableau de façon alternée (le deuxième élément est plus grand que le premier, le troisième est plus petit que le deuxième, etc. Autrement dit, on veut tab[0] < tab[1] > tab[2] < tab[3] > tab[4] ...). Ex.: «4 2 1 4 6 8» devient «2 4 1 6 4 8». Note: Le résultat n'est pas unique. Indice: trier le tableau et faire des échanges entre deux valeurs pourrait être utile. Une solution est de d'abord trier le tableau, puis d'itérer sur le tableau (boucle for). Il suffit d'échanger les éléments deux-à-deux (en excluant l'élément de départ). Ainsi, on fait des échanges de la forme échange(tab[i], tab[i+1]), ce qui garantit que la croissance des éléments sera alterné. Note: Il existe aussi une solution en O(n) qui ne nécessite pas de tri.
20 Quelle est la complexité des fonctions f1 et f2: 
bool f1(int* tab, int n){
     for(int i=0;i<n;i++)
         if(tab[i]%2 == 0)
             for(int j=i+1;j<n;j++)
                 if(tab[j]==tab[i])
                     return true;
     return false;
}

bool f2(int* tab, int n){
     for(int i=0;i<n;i++)
         for(int j=0;j<n;j++)
             for(int k=0;k<n;k++)
                 if(i!=j && i!=k && j!=k
                    && tab[i]*tab[j]==tab[k])
                     return true;
     return false;
}

int main(int argc, const char** argv){
    int n;
    std::cin >> n;
    int* tab = new int[n];
    for(int i=0;i<n;i++)
        std::cin >> tab[i];
    if(f1(tab, n))
        std::cout << "F1" << std::endl;
    if(f2(tab, n))
        std::cout << "F2" << std::endl;
    return 0;
}
Pour f1, il est possible dans le pire cas que le premier if soit toujours vrai (donc, qu'on exécute la deuxième boucle for à chaque itération de la première boucle for) et que le deuxième if soit toujours faux (donc, que la fonction ne termine pas hâtivement). Le nombre total d'itérations dans ce cas sera n(n-1)/2, ce qui est dans l'ordre de O(n²).

Pour f2, il est possible que le if ne soit jamais vrai, et donc que les trois boucles s'exécutent au complet. Chacune des trois boucles fait n itérations. Le temps d'exécution total est donc dans l'ordre de O(n³).
40 Quelle est la complexité des fonctions f et main: 
bool f(int* tab, int n) {
    if(n > 1)
        return tab[n-1] + f(tab, n/2);
    return tab[0];
}

int main(int argc, const char* argv[]){
    int n;
    std::cin >> n;
    int* tab = new int[n];
    for(int i=0;i<n;i++)
        std::cin >> tab[i];
    if(f(tab, n) > 10)
        std::cout << "f" << std::endl;
    return 0;
}
La fonction f est récursive et divise par 2 la taille considérée à chaque appel récursif. La complexité de f est donc O(log n).

La fonction main lit n nombres sur l'entrée standard, ce qui prend un temps O(n), puis appelle la fonction f. La complexité totale est donc O(n).