Structures de données

Question 1

Défini la notion de structure de données

Answer 1

Une structure de données est un format d’organisation, de gestion et de stockage de données qui permet des accès et des modifications efficaces.

Question 2

Donne des exemples de structure de donnée

Answer 2

Tableaux, classes (la classe Etudiant permet de stocker, accéder et modifier les données d’étudiants : prénom, nom, matricule…)

Question 3

Quelles sont les limitations concernant les tableaux en Java ?

Answer 3

1. Sa taille doit être déterminée à l’avance
2. Il ne s’agrandit pas
3. Il n’est pas un objet

Question 4

Défini l’abstraction d’une structure de donnée…

Answer 4

L’abstraction d’une structure de donnée est typiquement représentée par une interface. Il définit les opérations applicables sur les données.

Question 5

… et son implémentation concrète

Answer 5

L’implémentation concrète est typiquement une classe qui implements l’interface. Il définit comment les données sont organisées et les opérations effectuées.

Question 6

Donne un exemple d’une abstraction d’une structure de donnée + ses opérations

Answer 6

Liste d’éléments :
1. Obtenir la taille (le nombre d’éléments)
2. Obtenir l’élément à la position i
3. Modifier l’élément à la position i
4. Insérer un élément à la position i
5. Insérer un élément au début/à la fin
6. Supprimer l’élément à la position i

Question 7

Vrai ou faux : Une liste est plus flexible qu’un tableau en java

Answer 7

Vrai, pas besoin de fixer la taille d’une liste ou de nombre maximal d’éléments à l’avance.

Question 8

Donne une implémentation possible pour le type de données abstrait List

Answer 8

Utiliser un tableau pour stocker les éléments. En effet, un tableau stocke la séquence d’éléments de manière contiguë en mémoire.

Question 9

Vrai ou faux : L’avantage d’un tableau est la performance pour accéder à un élément

Answer 9

Vrai, le temps de calcul de l’adresse de la case mémoire du ième élément se fait en temps constant, O(1)
adresse = début du tableau + i * taille d’une case

Question 10

Comment ajouter un élément à la fin ?

Answer 10

Une liste permet d’ajouter un élément à la fin via la méthode add, par exemple .add(40)

Puisque les éléments doivent être contigus, la case qui suit le tableau doit être libre, dans quel cas on peut augmenter la taille du tableau sans problème et efficacement (sauf en Java)

Question 11

Que faire (en Java) si la case n’est pas libre ?

Answer 11

Il faut allouer un nouveau tableau, ailleurs dans la mémoire, là où il y a assez de place pour mettre tous les éléments en plus de celui à ajouter

Question 12

Existe-t-il d’autres solutions ?

Answer 12

Oui, les listes chaînées :
1. À chaque élément, on ajoute l’adresse mémoire (la référence) du prochain dans la liste.
2. Une paire (référence, élément) s’appelle noeud (node)

Question 13

Comment obtenir les éléments dans les listes chaînées ?

Answer 13

En parcourant les noeuds

Question 14

Vrai ou faux, un nouveau noeud peut être placé n’importe où en mémoire ?

Answer 14

Vrai

Question 15

Vaut mieux utiliser les listes chainées ou les tableaux dynamiques ?

Answer 15

Ça dépend de l’application. Beaucoup de modifications/accès en début de liste => Liste chainées.
Beaucoup d’accès aux éléments partout dans la liste => Tableau Dynamique

Question 16

Qu’est ce que ArrayList<E> et LinkedList<E> ?</E></E>

Answer 16

Ce sont des types de données prédéfinis dans la libraire java.util.

ArrayList<E> => Implantation d'un tableau dynamique</E>

LinkedList<E> => Implantation d'une liste chaînée</E>

Le <E> indique une classe générique, càd paramétrisée par un type (par exemple, ArrayList<Etudiant>)</Etudiant></E>

Question 17

C’est quoi List<E> ?</E>

Answer 17

Une interface pour liste

Question 18

Qu’est-ce qu’une collection ?

Answer 18

Une collection représente un groupe d’objets, appelés ses éléments

Question 19

Quel est l’avantage d’un double LinkedList ?

Answer 19

Navigation bidirectionnelle : chaque noeud a deux références (adresse). Cela permet donc de savoir où est le précédent et le prochain noeud. De plus, on passe de O(n) => O(1) pour la suppression de la fin.

Question 20

Qu’est-ce qu’une pile (Stack) ?

Answer 20

Une pile (stack) est une collection d’éléments avec les deux opérations :
1. push, entrer un élément
2. pop, sortir le dernier entré des éléments présents

Question 21

Que veux dire LIFO ?

Answer 21

Last In, First Out

Question 22

En plus de push and pop, on peut :

Answer 22

Regarder le dessus de la pile, vérifier si la pile est vide

Question 23

Qu’est-ce qu’une file (queue) ?

Answer 23

Une file d’attente (queue) est une collection d’éléments avec les 2 opérations :
1. enqueue, entrer un élément
2. dequeue, sortir le premier entré des éléments présents

Question 24

Que veut dire FIFO ?

Answer 24

First In First Out

Question 25

Qu’est-ce qu’un arbre (Tree) ?

Answer 25

Un arbre est une structure de données hiérarchique :
1. Le premier noeud est la racine
2. Chaque noeud peut être suivi de 0,1,2,…, N noeuds
3. Chaque noeud réfère à ses enfants et a exactement 1 noeud parent (sauf la racine qui en a pas)
4. Un noeud qui n’a pas d’enfant est appelé une feuille

Question 26

Qu’est-ce qu’un arbre binaire (binary tree) ?

Answer 26

Un arbre binaire est un cas particulier d’un arbre où chaque noeud a au plus deux enfants.

Question 27

Qu’est-ce qu’un map ?

Answer 27

Un map (ou Dictionnaire, ou Tableau associatif) est une structure de données qui permet d’associer des clés et des valeurs de types arbitraires

Question 28

Donne des implémentations concrètes de map

Answer 28

TreeMap<K, V>
HashMap<K, V>

Question 29

À quoi sert l’interface iterator ?

Answer 29

Il est utilisé pour parcourir les éléments des structures de données.

Question 30

L’interface iterator définit les méthodes :

Answer 30

boolean hasNext(): indique s’il y a un autre élément
element next(): retourne le prochain élément

Question 31

À quoi sert les types paramétrés ?

Answer 31

1. Permettent de définir des classes/interfaces avec un ou plusieurs types paramétrés
2. Évitent de réécrire une nouvelle classe pour chaque type qu’on veut manipuler
3. Évitent de rendre tout object et de caster partout