Université d’Ottawa University of Ottawa
Faculté de génie Faculty of Engineering
École de science informatique School of Electrical Engineering
et de génie électrique and Computer Science
Introduction à l’informatique II (ITI1521)
E XAMEN FINAL
Instructeurs: Guy-Vincent Jourdan et Marcel Turcotte
Avril 2019, durée: 3 heures
Identification
Nom de famille : Prénom(s) :
# Étudiant : # Siège : Signature :
Instructions Barème
1. Examen à livres fermés. Question Maximum Résultat
2. L’utilisation de calculatrices, d’appareils électroniques ou 1 15
tout autre dispositif de communication est interdit.
2 15
(a) Tout appareil doit être éteint et rangé.
3 15
(b) Toute personne qui refuse de se conformer à ces
règles pourrait être accusée de fraude scolaire. 4 15
3. Répondez sur ce questionnaire. Total 60
(a) Utilisez le verso des pages si nécessaire.
(b) Aucune page supplémentaire n’est permise.
4. Écrivez vos commentaires et hypothèses afin d’obtenir des
points partiels.
5. Écrivez lisiblement, puisque votre note en dépend.
6. Ne retirez pas l’agrafe du livret d’examen.
7. Attendez l’annonce de début de l’examen.
Tous droits réservés. Il est interdit de reproduire ou de transmettre le contenu du présent document, sous quelque forme ou par
quelque moyen que ce soit, enregistrement sur support magnétique, reproduction électronique, mécanique, photographique, ou
autre, ou de l’emmagasiner dans un système de recouvrement, sans l’autorisation écrite préalable des instructeurs.
Avril 2019 ITI 1521 Page 2 de 20
Question 1 (15 points)
Implémentez la méthode d’instance merge pour la classe LinkedList qui a les caractéristiques suivantes.
• La liste commence toujours par un noeud factice, qui sert de marqueur pour le début de la liste. Le
noeud factice n’est jamais utilisé pour enregistrer des données. La liste vide est constituée du noeud
factice seulement ;
• Dans l’implémentation pour cette question, les noeuds de la liste sont doublement chaînés ;
• Dans cette implémentation, la liste est circulaire, c’est-à-dire que la référence next du dernier noeud de
la liste pointe vers le noeud factice, la référence prev du noeud factice pointe vers le dernier noeud de
la liste. Dans la liste vide, le noeud factice est le premier et le dernier noeud de la liste, ses références
prev et next pointent vers le noeud lui-même ;
• Le dernier noeud est facilement accessible, parce que c’est toujours le noeud précédent le noeud factice,
l’en-tête de la liste n’a pas de pointeur vers le dernier élément.
La méthode merge ajoute tous les éléments de la liste désignée par le paramètre other à cette liste. Après un
appel à la méthode merge, la liste a désigné le paramètre other est vide.
• Cette question évalue votre compréhension des structures chaînées. Pour cette raison, vous ne pou-
vez pas utiliser les méthodes de la classe LinkedList. En particulier, vous ne pouvez pas utiliser les
méthodes add() ou remove().
• La méthode ne lance jamais d’exception.
public class Test {
public static void main(String[] args) {
LinkedList<String> firstList, secondList;
firstList = new LinkedList<String>();
secondList = new LinkedList<String>();
firstList.addLast("alpha");
firstList.addLast("bravo");
firstList.addLast("charlie");
firstList.addLast("delta");
secondList.addLast("echo");
secondList.addLast("foxtrot");
System.out.println(firstList);
System.out.println(secondList);
firstList.merge(secondList);
System.out.println(firstList);
System.out.println(secondList);
}
}
L’exécution du programme ci-dessus produit ceci sur la console.
[alpha, bravo, charlie, delta]
[echo, foxtrot]
[alpha, bravo, charlie, delta, echo, foxtrot]
[]
Avril 2019 ITI 1521 Page 3 de 20
Complétez l’implémentation de la méthode merge.
public class LinkedList<E> implements List<E> {
private static class Node<T> {
private T value;
private Node<T> prev;
private Node<T> next;
private Node(T value, Node<T> prev, Node<T> next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
private final Node<E> head;
private int size;
public LinkedList() {
head = new Node<E>(null, null, null);
head.next = head.prev = head;
size = 0;
}
public void merge(LinkedList<E> other) {
if ( && ) {
Node<E> thisLast, otherFirst, otherLast;
thisLast = ;
otherFirst = ;
otherLast = ;
= thisLast;
= otherFirst;
= otherLast;
otherLast.next = ;
other.head.next = ;
= ;
= ;
= ;
}
}
Avril 2019 ITI 1521 Page 4 de 20
Question 2 (15 points)
Complétez l’implémentation de la méthode findAndReplace pour la classe LinkedList de la page suivante.
La méthode remplace toutes les occurrences de l’élément spécifié par le paramètre target par la valeur du
paramètre replacement. La méthode retourne aussi le nombre total d’éléments remplacés.
Il s’agit d’une méthode récursive. Veuillez noter que la liste est simplement chaînée et qu’il n’y a pas de
noeud factice. Pour vous aider à bien comprendre les attentes, voici un programme test.
LinkedList<String> list;
list = new LinkedList<String>();
System.out.println(list);
System.out.println(list.findAndReplace("I", "she"));
System.out.println(list);
list.addLast("I");
list.addLast("said");
list.addLast("she");
list.addLast("said");
list.addLast("she");
list.addLast("said");
list.addLast("I");
list.addLast("said");
System.out.println(list);
System.out.println(list.findAndReplace("I", "she"));
System.out.println(list);
System.out.println(list.findAndReplace("I", "she"));
System.out.println(list);
L’exécution du programme ci-dessous produira le résultat suivant sur la sortie.
[]
0
[]
[I, said, she, said, she, said, I, said]
2
[she, said, she, said, she, said, she, said]
0
[she, said, she, said, she, said, she, said]
Avril 2019 ITI 1521 Page 5 de 20
Complétez l’implémentation de la méthode findAndReplace.
public class LinkedList<E> implements List<E> {
private static class Node<T> {
private T value;
private Node<T> next;
private Node(T value, Node<T> next) {
this.value = value;
this.next = next;
}
}
private Node<E> head;
private int size;
public int findAndReplace(E target, E replacement) {
if ( ) {
return findAndReplace( , target, replacement);
}
private findAndReplace( , E target, E replacement) {
int number;
if ( ) { // Cas de base
} else { // Cas général
= findAndReplace( , target, replacement);
if ( ) {
return ;
}
}
Avril 2019 ITI 1521 Page 6 de 20
Question 3 (15 points)
Pour cette question, notre but est de fournir cinq (5) méthodes pour l’implémentation d’une liste à l’aide
d’un tableau circulaire et dynamique. Voici les variables d’instance de cette classe :
• array est une variable référence désignant le tableau contenant les éléments de la liste ;
• size est la taille logique (actuelle) de la liste ;
• first est l’index du premier élément de la liste dans le tableau désigné par la variable d’instance array ;
• last est l’index du dernier élément de la liste dans le tableau désigné par la variable d’instance array ;
• capacity est la capacité (taille physique) du tableau.
Par convention, lorsque la liste est vide, les variables first et last ont toutes les deux la valeur zéro. Nous
avons deux constructeurs pour notre classe : le premier, sans paramètre, crée un tableau de la capacité par
défaut, tandis que le second utilise la valeur de son paramètre comme taille initiale du tableau. La taille doit
être d’au moins un (1). Voici une implémentation partielle pour notre classe :
public class CircularDynamicArrayList<E> {
private E[] array;
private int size;
private int first, last;
private int capacity = 100;
@SuppressWarnings("unchecked")
public CircularDynamicArrayList() {
array = (E[]) new Object[capacity];
first = last = 0;
size = 0;
}
@SuppressWarnings("unchecked")
public CircularDynamicArrayList(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("Minimum capacity is 1");
}
this.capacity = capacity;
array = (E[]) new Object[capacity];
first = last = 0;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
// Les autres méthodes seraient ici
}
Avril 2019 ITI 1521 Page 7 de 20
Question 3.1 ensureSpace
La première méthode que nous voulons écrire est ensureSpace. Cette méthode permet de s’assurer que la
liste pourra accueillir un nouvel élément. Si nécessaire, la méthode double la taille du tableau. Complétez le
code source de l’implémentation ci-dessous.
public class CircularDynamicArrayList<E> {
// (...)
private void ensureSpace() {
if ( ) {
newArray =
for (int i = ; i < ; i++) {
newArray[ ] =
first =
last =
capacity =
array =
}
}
}
Avril 2019 ITI 1521 Page 8 de 20
Question 3.2 addFirst
La méthode addFirst ajoute un nouvel élément à la liste à la première position. Tous les autres éléments sont
conservés. Nous devons nous assurer de traiter les conditions qui ne sont pas valides. Vous pouvez utiliser les
méthodes de la classe écrites jusqu’à présent dans cette nouvelle méthode.
public class CircularDynamicArrayList<E> {
// (...)
public void addFirst(E newElement) {
if ( ) {
throw
if (isEmpty()) {
} else {
first =
array[ ] =
size =
}
}
Avril 2019 ITI 1521 Page 9 de 20
Question 3.3 removeFirst
La méthode removeFirst supprime et retourne l’élément à la première position. Tous les autres éléments sont
conservés. Nous devons nous assurer de traiter les conditions qui ne sont pas valides. Vous pouvez utiliser les
méthodes de cette classe écrites jusqu’à présent dans cette nouvelle méthode.
public class CircularDynamicArrayList<E> {
// (...)
public E removeFirst() {
if ( ) {
throw
E resultat =
array[ ] =
size =
if (size == 0) {
} else {
return
}
}
Avril 2019 ITI 1521 Page 10 de 20
Question 3.4 add
La méthode add ajoute un nouvel élément à la liste à la position spécifiée. Les index débutent avec la valeur
zéro (0). Tous les autres éléments sont conservés. Nous devons nous assurer de traiter les conditions qui ne
sont pas valides. Vous pouvez utiliser les méthodes de la classe écrites jusqu’à présent dans cette nouvelle
méthode.
public class CircularDynamicArrayList<E> {
// (...)
public void add(E newElement, int index) {
if ( ) {
throw
if ( ) {
throw
if (isEmpty()) {
addFirst(newElement);
} else {
int currentIndexLocation =
int i =
while (i != ) {
array[ ] =
i =
}
}
}
Avril 2019 ITI 1521 Page 11 de 20
Question 3.5 remove
Enfin, la méthode remove supprime l’élément à l’index spécifié dans la liste, et le renvoie. Tous les autres
éléments sont conservés. Nous devons nous assurer de traiter les conditions qui ne sont pas valides. Vous
pouvez utiliser les méthodes de la classe écrites jusqu’à présent dans cette nouvelle méthode.
public class CircularDynamicArrayList<E> {
// (...)
public E remove(int index) {
if( ) {
throw
if( ) {
throw
E resultat;
if (size == 1) {
} else {
int currentIndexLocation =
resultat =
int i =
while (i != ) {
array[ ] =
i =
}
}
Avril 2019 ITI 1521 Page 12 de 20
Question 4 (15 points)
Dans cette question, nous utilisons des listes et des arbres binaires de recherche ensemble. Plus précisé-
ment, nous allons travailler avec l’interface List suivante :
public interface List<E> {
// Retourne la taille actuelle (logique) de la liste
int getSize();
// Renvoie true si et seulement si la liste est vide
boolean isEmpty();
// Ajoute un élément comme premier élément de la liste
void addFirst(E elem);
// Ajoute l’élément elem comme dernier élément de la liste
void addLast(E elem);
// Ajoute un élément à l’index «index» dans la liste
void add(int index,E elem);
// Renvoie la référence du premier élément de la liste
E getFirst();
// Renvoie la référence du dernier élément de la liste
E getLast();
// Retourne la référence de l’élément à l’index «index» dans la liste
E get(int index);
// Supprime et renvoie la référence du premier élément de la liste
E removeFirst();
// Supprime et renvoie la référence du dernier élément de la liste
E removeLast();
// Supprime la référence de l’élément à l’index «index» dans la liste
E remove(int index);
}
Dans ce qui suit, nous avons accès à deux implémentations de l’interface List. Nous ne précisons pas
encore laquelle utiliser. Nous avons aussi une classe BinarySearchTree. Certaines parties de son implémen-
tation sont présentées ci-dessous.
Avril 2019 ITI 1521 Page 13 de 20
Question 4.1 buildSortedList
Notre premier but est d’ajouter une méthode buildSortedList à la classe BinarySearchTree. Cette méthode
reçoit en paramètre la référence d’une liste vide (objet dont la classe réaliste l’interface List), et elle remplit
cette liste avec tous les éléments actuellement dans l’arbre binaire de recherche, en ordre croissant.
Par exemple, le code test suivant :
public static void testBuildSortedList(List<String> list) {
BinarySearchTree<String> tree;
tree = new BinarySearchTree<String>();
tree.add("F"); tree.add("A"); tree.add("C");
tree.add("X"); tree.add("M"); tree.add("N");
tree.add("O"); tree.add("B"); tree.add("L");
System.out.println(list);
tree.buildSortedList(list);
System.out.println(list);
produit la sortie suivante :
[]
[A, B, C, F, L, M, N, O, X]
Si l’arbre est actuellement vide, les listes restent inchangées. Par exemple, le code test suivant :
public static void testBuildSortedList2(List<String> list) {
BinarySearchTree<String> tree;
tree = new BinarySearchTree<String>();
System.out.println(list);
tree.buildSortedList(list);
System.out.println(list);
produit la sortie suivante :
[]
[]
Avril 2019 ITI 1521 Page 14 de 20
Une déclaration partielle et incomplète de la classe BinarySearchTree est fournie ci-dessous :
public class BinarySearchTree <E extends Comparable<E>> {
private static class Node<T> {
private T value;
private Node<T> left;
private Node<T> right;
private Node(T value) {
this.value = value;
left = null;
right = null;
}
}
private Node<E> root;
private int size;
public BinarySearchTree() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean contains(E obj) {
// Caché pour sauver de l’espace
}
public boolean add(E obj) {
// Caché pour sauver de l’espace
}
public String toString() {
// Caché pour sauver de l’espace
}
// Les autres méthodes apparaitraient ici
}
Avril 2019 ITI 1521 Page 15 de 20
Dans l’espace ci-dessous, fournissez le code de la méthode buildSortedList. Comme vous pouvez le voir,
la méthode utilise une méthode privée, suggérant une implémentation récursive.
public class BinarySearchTree <E extends Comparable<E>> {
// Beaucoup de code caché
public void buildSortedList(List<E> list) {
if (list == null) {
throw new NullPointerException("List must not be null");
}
if (list.getSize() != 0) {
throw new IllegalArgumentException("List must be empty");
}
private void buildSortedList( List<E> list, Node<E> current) {
}
Avril 2019 ITI 1521 Page 16 de 20
Question 4.2 Construire un arbre balancé
Nous utilisons maintenant la liste triée pour construire un nouvel arbre binaire de recherche. Dans cette
section, nous devons ajouter un nouveau constructeur à la classe BinarySearchTree. Ce constructeur reçoit
comme paramètre la référence à une liste (objet dont la classe réalise l’interface List), qui est censée être
triée. Le but du constructeur est de créer un nouvel arbre binaire de recherche contenant tous les éléments de
la liste. L’arbre résultant devrait être aussi équilibré que possible.
Par exemple, supposons que list désigne une liste avec les éléments suivants : [1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144, 233, 377]. Cette liste contient les 13 premiers nombres de Fibonnacci consécutifs et triés.
L’extrait de code suivant :
System.out.println(list);
BinarySearchTree<Integer> tree;
tree = new BinarySearchTree<Integer>(list);
produit la sortie suivante :
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
null
377
null
233
null
144
null
89
null
55
null
34
null
21
null
13
null
8
null
5
null
3
null
2
null
1
null
Autrement dit, il construit l’arbre suivant :
21
3 89
1 8 34 233
2 5 13 55 144 377
Avril 2019 ITI 1521 Page 17 de 20
Dans l’espace ci-dessous, donnez votre implémentation du nouveau constructeur. Là encore, la méthode
utilise une méthode privée.
public class BinarySearchTree <E extends Comparable<E>> {
// Beaucoup de code caché
public BinarySearchTree(List<E> list) {
if(list == null || list.getSize() == 0) {
return;
}
root =
private Node<E> buildBalanced(int from, int to, List<E> list) {
}
Avril 2019 ITI 1521 Page 18 de 20
Question 4.3 Implémentation efficace
Le but ultime de nos deux méthodes est de pouvoir créer un arbre binaire de recherche équilibré (balancé) à
partir d’un arbre binaire de recherche existant et possiblement déséquilibré, en utilisant des énoncés similaires
à ceux qui sont présentés ci-dessous :
public BinarySearchTree<E> createBalanced(BinarySearchTree<E> unbalanced) {
List<E> list;
list = ... // Initialisation
unbalanced.buildSortedList(list);
BinarySearchTree<E> balanced;
balanced = new BinarySearchTree<E>(list);
return balanced;
}
Il faut donc que ce code soit aussi efficace que possible 1 , ce qui signifie que notre méthode buildSorted-
List et notre nouveau constructeur pour l’arbre binaire de recherche doivent être efficaces.
Pour l’implémentation de notre liste, nous avons deux choix : notre premier choix est une liste circulaire
doublement chaînée avec un noeud factice. Cette implémentation a un seul constructeur, sans paramètre :
public class DoublyLinkedListDummyNode<E> implements List<E> {
public DoublyLinkedListDummyNode() {
// Code source
}
// Encore du code source
}
Notre deuxième choix est une implémentation de liste à l’aide d’un tableau dynamique et circulaire simi-
laire à celle de la Question 3. Dans cette implémentation, la taille du tableau est doublée lorsqu’un élément
est ajouté à un tableau rempli. Cette implémentation a deux constructeurs : un constructeur sans paramètre,
et un autre qui reçoit une valeur de type int en paramètre d’entrée. Avec le premier constructeur, une valeur
par défaut est utilisée pour la taille initiale du tableau. Avec le second constructeur, la valeur du paramètre
d’entrée est utilisé comme taille initiale du tableau :
public class CircularDynamicArrayList<E> implements List<E> {
public CircularDynamicArrayList() {
// Utilise une valeur par défaut pour la taille initiale du tableau
}
public CircularDynamicArrayList(int initialSize) {
// Utilise initialSize pour la taille initiale du tableau
}
// Encore du code
}
1
Spécifiquement, il doit être linéaire en fonction de la taille de l’arbre binaire de recherche déséquilibré.
Avril 2019 ITI 1521 Page 19 de 20
Vous devez décider quelle implémentation utiliser dans la méthode createBalanced afin d’avoir une im-
plémentation rapide. Ajoutez votre initialisation de la variable list dans le code ci-dessous :
public BinarySearchTree<E> createBalanced(BinarySearchTree<E> unbalanced) {
List<E> list;
list =
unbalanced.buildSortedList(list);
BinarySearchTree<E> balanced;
balanced = new BinarySearchTree<E>(list);
return balanced;
}
Avril 2019 ITI 1521 Papier brouillon
