Top 100 des questions et réponses d'entrevue sur les structures de données

30 octobre 2021

Ces questions et réponses d'entrevue de structure de données guident le développement d'une carrière dans l'apprentissage automatique. Un examen de poste d'expert en apprentissage automatique, d'analyste de données et de scientifique de données sera plus facile pour ceux qui passeront par les questions et les réponses d'un entretien sur la structure des données.

Table des matières

1. Que sont les structures de données ?

  • Méthodes et techniques utilisées pour maintenir les données de manière organisée.
  • Définissez la dépendance et les relations des données.

2. Quelle est la différence entre une structure de fichiers et une structure de données ?

Vous trouverez ci-dessous la différence entre la structure de fichier et la structure de données :



Structure du fichierStructure de données
Données stockées sur disqueDonnées stockées à la fois sur RAM et sur disque
Politiques de stockage de fichiers standardPolitiques de stockage personnalisées
Faible compatibilité avec les applications externesHaute compatibilité avec les applications externes

3. Qu'est-ce qu'une liste chaînée ?

  • La structure de données de la liste chaînée se compose d'entités individuelles appelées nœuds.
  • Les nœuds ont la capacité de se connecter à d'autres nœuds et de créer une chaîne.
  • La structure de la chaîne continue se forme pour devenir une liste chaînée de données.

4. Où les structures de données sont-elles principalement utilisées ?

  • Calcul numérique
  • Système opérateur conception
  • Intelligence artificielle
  • Conception du compilateur
  • Gestion de la base de données
  • Traitement graphique
  • Analyse lexicale
  • Statistiques

5. Quels sont les types de recherche utilisés dans Data Structure ?

  • La recherche linéaire implique une itération sur une unité de données pour effectuer l'opération requise.
  • Recherche binaire : est plus efficace dans la mesure où il peut diviser l'unité de données en morceaux, puis effectuer une opération de recherche.

6. Comment fonctionne la recherche binaire ?

  • La recherche binaire ne fonctionne que sur les données ordonnées (triées).
  • Pour commencer, l'élément du milieu du tableau est trouvé et la recherche commence à partir de là.
  • Le tableau est recherché en deux parties en fonction de la valeur de recherche supérieure ou inférieure à l'élément du milieu.
  • Il est essentiel de connaître l'ordre de l'arrangement pour aider à rechercher la valeur en conséquence.

7. Comment accède-t-on aux éléments individuels d'un tableau ?

  • Chacune des valeurs d'un tableau reçoit une position d'index allant de 0 à n-1, où 'n' est le nombre d'éléments du tableau.
  • Les éléments individuels sont accessibles en utilisant l'élément index pour les opérations.
  • Les tableaux multidimensionnels auront plus d'une dimension avec laquelle travailler.

8. Qu'est-ce qu'une file d'attente dans les structures de données ?

  • Une structure de données de file d'attente est largement utilisée pour désigner l'accès ordonné et la manipulation d'un élément.
  • Le fonctionnement de cette structure de données est le même qu'une file d'attente littérale dans le monde réel.
  • Les éléments sont ajoutés les uns après les autres et sont traités sur le front-end.

9. Qu'est-ce qu'un arbre binaire ?

  • Un arbre binaire, comme son nom l'indique, est une structure de données arborescente à deux nœuds, qui sont les nœuds situés à gauche et à droite du nœud racine.
  • En usage, un arbre binaire est considéré comme une liste chaînée étendue.
  • La structure de données du tas est un arbre binaire équilibré spécial où la clé du nœud racine est comparée à ses enfants et organisée en conséquence.
  • Si dans l'ordre le parcours d'un arbre binaire est trié, alors l'arbre binaire est BST.
Voir également Top 100 des questions et réponses d'entrevue JavaScript

10. Quelle est la signification de la pile ?

  • Une pile est une autre structure de données largement utilisée qui offre aux utilisateurs la possibilité de travailler avec des données à un seul point.
  • Comme son nom l'indique, cela peut correspondre au fonctionnement d'une pile de cartes.

11. Quel est le fonctionnement de LIFO ?

  • LIFO est l'ordre d'accès Dernier entré, Premier sorti.
  • Cela correspond à la façon dont les données peuvent être travaillées et modifiées.
  • L'entité de données qui est stockée ou poussée en dernier est la première à être travaillée à tout moment.
  • S'il est nécessaire d'accéder au tout premier élément stocké, vous devez d'abord récupérer toutes les données entrées après l'élément.

12. Que sont les tableaux multidimensionnels ?

  • Les tableaux multidimensionnels sont des tableaux qui s'étendent sur plusieurs dimensions.
  • Il y aura plus d'une variable d'index pour chaque point de stockage.
  • Il est utile lors du stockage de données qui ne peuvent pas être représentées à l'aide d'une indexation unidimensionnelle.

13. Les listes chaînées sont-elles des structures de données linéaires ou non linéaires ?

  • Les listes liées sont considérées comme le meilleur des deux mondes ici.
  • En fonction de l'utilisation, s'il s'agit d'une politique de stockage, elle peut être considérée comme une structure de données non linéaire.
  • Alors que si une personne l'envisage sur la base de stratégies de récupération, cela peut être considéré comme une structure de données linéaire.

14. Qu'est-ce qu'un arbre de recherche binaire ?

Un arbre de recherche binaire se compose de deux nœuds principaux à partir du nœud racine.

  • Les valeurs des nœuds dans le sous-arbre de gauche sont inférieures en nombre à la valeur du nœud racine, et les valeurs des nœuds à droite du nœud racine sont en conséquence plus élevées que la racine.
  • De plus, individuellement, ces deux sous-arbres gauche et droit sont leurs arbres de recherche binaires à tout moment.

15. Quelle est la signification de FIFO ?

  • FIFO, également connu sous le nom de First in, First out, est un moyen de représenter une opération de données sur des facteurs tels que la manière dont les données sont accessibles et dans quel ordre.
  • Ici, les données qui sont placées en premier dans la liste seront la première entité à sortir de la structure de données ordonnée.

16. Quelle est la différence entre void et null dans Data structure ?

  • Void est un identifiant de type de données dans les structures de données, tandis que null est considéré comme une valeur sans présence physique.
  • Lorsque le vide est utilisé, cela indique qu'il n'y a pas de taille lors de l'initialisation de la structure de données.

17. Qu'est-ce que la gestion dynamique de la mémoire ?

  • La gestion dynamique de la mémoire est une technique dans laquelle les unités de stockage sont allouées en fonction des besoins en continu.
  • En utilisant des allocations de mémoire dynamiques, les structures de données individuelles peuvent être stockées séparément ou combinées pour former des entités appelées composites.
  • Ces composites peuvent être travaillés si nécessaire.

18. Que sont les opérations push et pop dans Data Structure ?

  • L'opération push indique que les utilisateurs ajoutent des données dans la structure.
  • L'opération Pop indique que les données sont extraites ou supprimées de la structure.
  • Habituellement, l'élément le plus haut est pris en compte lors de l'exécution d'opérations push et pop.

19. Comment une variable est-elle stockée en mémoire lors de l'utilisation de structures de données ?

  • Une variable est stockée en fonction de la quantité de mémoire nécessaire.
  • Tout d'abord, la quantité de mémoire requise est attribuée, puis elle est stockée en fonction de la structure de données utilisée.
  • L'utilisation de concepts tels que l'allocation dynamique garantit une efficacité élevée et que les unités de stockage peuvent être fournies en fonction des besoins en temps réel.

20. Qu'est-ce que le tri par fusion ?

  • Le tri par fusion est une méthode de tri basée sur la technique de division pour mieux régner.
  • Ici, les entités de données adjacentes les unes aux autres sont d'abord fusionnées et triées à chaque itération pour créer des listes triées.
  • Ces petites listes triées sont combinées à la fin pour former la liste complètement triée.

21. Pourquoi le tas devrait-il être utilisé sur une pile ?

  • La structure de données en tas est plus efficace à utiliser que la pile.
  • Parce que le allocation de mémoire dans une tête est dynamique et peut être alloué et supprimé selon les besoins.
  • La structure de la mémoire et le temps d'accès d'une pile sont relativement lents.

22. Quelle est la signification de l'abstraction de données ?

  • L'abstraction de données est l'un des outils les plus utilisés dans les structures de données.
  • L'objectif est de décomposer des entités complexes en problèmes plus petits et de les résoudre en utilisant les concepts de structures de données.
  • Cela offre aux utilisateurs l'avantage de se concentrer sur les opérations et de ne pas s'inquiéter de la manière dont les données sont stockées ou représentées dans la mémoire.

23. Quelle est la signification d'une expression postfixée dans les structures de données ?

  • Les expressions suffixées sont utilisées dans un scénario où chaque opérateur est précédé de ses opérandes.
  • Élimine le besoin de parenthèses ou de sous-expressions lorsqu'il s'agit du concept de priorité des opérateurs.

24. Quel est le fonctionnement d'un tri par sélection ?

  • Le travail est simple où la plus petite entité est d'abord découverte et l'index de celle-ci est mis à zéro, triant ainsi de manière permanente cela dans la première étape.
  • Les étapes restantes consistent à parcourir d'autres éléments et à ajouter l'index suivant en conséquence. Ceci est fait jusqu'à ce que tous les éléments soient triés.

25. Que sont les nombres signés dans la structure de données ?

  • Les nombres signés sont les unités qui ont un bit de données au début du nombre qui indique si le nombre est positif ou négatif.
  • Les nombres signés ont une plage de -128 à +127.

Top 100 des questions et réponses des entretiens sur les structures de données

26. Quel est le minimum de nœuds que les arbres binaires peuvent avoir ?

  • Les arbres binaires peuvent avoir zéro nœud ou un minimum de 1 ou 2 également.
  • Il peut être égal à zéro dans les cas où tous les nœuds ont une valeur NULL.

27. Quelles structures de données utilisent des pointeurs ?

Les pointeurs sont utilisés dans une variété de structures de données. Ils sont principalement utilisés dans les structures de données suivantes :

  • Arbres binaires
  • Listes liées
  • Files d'attente
  • Piles

28. A quoi servent les Structures de Données dynamiques ?

La structure de données dynamique offre aux utilisateurs une grande flexibilité en termes de fourniture de techniques de stockage et de manipulation de données.

Il est utilisé pour changer pendant le fonctionnement de l'algorithme ou l'exécution du programme.

29. Qu'est-ce qu'une file d'attente prioritaire ?

Une file d'attente prioritaire est un type de données abstrait qui ressemble à une file d'attente normale mais dont la priorité est attribuée aux éléments.

  • Les éléments de priorité supérieure sont traités avant les éléments de priorité inférieure.
  • Un minimum de deux files d'attente est nécessaire dans ce cas, une pour les données et l'autre pour stocker la priorité.

30. Les pointeurs allouent de la mémoire pour le stockage des données. Vrai ou faux?

Faux, les opérations de pointeur telles que la déclaration n'alloueront aucune mémoire pour le stockage des données. Mais, la mémoire est allouée pour la variable vers laquelle pointe le pointeur. Le traitement de la mémoire ne commence que lorsque le programme commence son exécution.

31. Quel est le sens de deque ?

Un deque est une file d'attente à double extrémité.

  • Cela signifie que des éléments peuvent être ajoutés ou supprimés de n'importe laquelle des deux extrémités. Il peut être utilisé à la fois comme file d'attente normale et comme pile.
  • Il fonctionne mieux que les listes liées et les piles en général.

32. Différencier la structure de données linéaire et non linéaire ?

Vous trouverez ci-dessous les différences entre la structure de données linéaire et les structures de données non linéaires :

Voir également Top 100 des questions et réponses d'entrevue Ansible
Structures de données linéairesStructures de données non linéaires
Dans la structure de données Linears, les éléments de données sont stockés les uns à côté des autresLes éléments de données peuvent être séparés par d'autres entités en mémoire
Exemples de structure de données linéaire : tableaux, listes chaînées, piles et files d'attenteExemples de structures de données non linéaires : arbres et graphiques

33. Quelle est la signification d'un arbre AVL ?

Un arbre AVL est un type d'arbre de recherche binaire où l'arbre n'est que légèrement équilibré. L'équilibre est l'unité de comparaison entre les hauteurs des sous-arbres à partir du nœud principal (racine). Tous les arbres vérifient la hauteur des sous-arbres gauche et droit et s'assurent que la différence n'est pas supérieure à 1.

34. Comment fonctionne l'algorithme de Huffman ?

L'algorithme de Huffman utilise un tableau contenant la fréquence d'occurrence de chaque entité de données de la liste.

  • Ceci est utilisé pour créer des arbres binaires étendus, qui sont connus pour avoir des poids minimums pour les longueurs de chemin.
  • Ceci considère chacun des poids correspondants.

35. Que sont les algorithmes récursifs ?

Les algorithmes récursifs sont des algorithmes qui résolvent un problème en le décomposant en sous-problèmes plus simples, puis en les résolvant de manière itérative.

La sortie d'une opération de récursivité est généralement l'entrée directe de l'opération d'itération suivante, et ce processus se poursuit.

36. Comment fonctionne le tri à bulles ?

Appliqué aux tableaux où les éléments adjacents les uns aux autres sont comparés et les valeurs sont échangées en fonction de l'ordre d'arrangement.

C'est ce qu'on appelle le tri à bulles en raison du concept d'échange d'éléments comme une bulle flottant au sommet de l'eau et des entités plus grandes coulant vers le bas.

37. Quel est l'algorithme de tri le plus rapide disponible ?

Parmi les nombreux types d'algorithmes tels que le tri à bulles, le tri rapide, le tri par fusion, etc., il n'est pas juste de placer une méthode sur le podium en termes de performances.

Cela varie considérablement en fonction des données, de la réaction après que l'algorithme a traité les données et de la manière dont elles sont triées.

La notion de complexité temporelle est considérée ici.

38. Quelle est la forme postfixée de (X+Y)*(Z-C) ?

La forme postfixée de l'expression donnée est XY+ZC-*

39. Où sont utilisées les structures de données arborescentes ?

Une structure de données arborescente est utilisée dans une variété d'applications. Voici quelques-uns d'entre eux :

  • Gestion des expressions arithmétiques
  • Création de table de symboles
  • Analyse lexicale
  • Modélisation hiérarchique des données

40. Quelles sont les structures de données utilisées dans les graphiques ?

Pour implémenter des graphes, deux structures de données de graphe jouent un rôle clé. Ils sont:

  • Matrice d'adjacence : utilisée pour la représentation séquentielle des données
  • Liste de contiguïté : utilisée pour représenter les données liées

41. Quelles sont les structures de données utilisées dans les algorithmes DFS et BFS ?

  • Dans la recherche en profondeur d'abord (DFS), la structure de données de la pile est utilisée.
  • Dans le cas de la technique de recherche en largeur d'abord (BFS), des files d'attente sont utilisées.

42. Quelles sont les complexités temporelles de la recherche linéaire et de la recherche binaire ?

La recherche binaire est plus efficace car elle nécessite moins de comparaisons pour rechercher un élément dans un tableau.

  • La complexité temporelle de la recherche linéaire est O(n)
  • La complexité temporelle est O(log n) pour la recherche binaire.

43. Où sont utilisées les structures de données multi-liées ?

Les structures de données multi-liées sont utilisées dans de nombreux domaines. Voici les deux cas d'utilisation les plus importants des structures de données multi-liées :

  • Génération de matrices creuses
  • Création d'index pour les entités de données

44. Quelle est la méthode utilisée pour parcourir l'ordre dans les arbres ?

Le parcours dans l'ordre fonctionne de la manière suivante :

  • L'arbre est traversé par le sous-arbre de gauche.
  • Le nœud racine est visité après la visite de gauche.
  • Ensuite, le sous-arbre de droite est parcouru.

45. Quel est le fonctionnement du parcours post-ordre dans les arbres ?

La traversée post-ordre fonctionne de la manière suivante :

  • Tout d'abord, le sous-arbre de gauche est traversé.
  • Le sous-arbre de droite est parcouru ensuite.
  • Le nœud racine est visité après la visite du sous-arbre droit.

46. ​​Quels sont les inconvénients de la mise en œuvre de files d'attente à l'aide de baies ?

  • Dimensionnement du tableau : la file d'attente doit être constamment étendue pour faire place à davantage d'éléments à implémenter. Il ne sera pas toujours possible d'étendre la taille du tableau car il y aura un écart dans la création de la taille de tableau correcte.
  • Vidages mémoire : la mémoire utilisée pour stocker les éléments de la file d'attente ne peut pas être réutilisée pour stocker la file d'attente. Cela est dû au fonctionnement des files d'attente où l'insertion se produit uniquement au niveau du nœud principal.

47. Comment insérer des éléments dans la file d'attente circulaire ?

Il existe deux cas dans lesquels les éléments peuvent être placés dans une file d'attente circulaire. Ils sont les suivants :

  • Lorsque front != 0 et rear = max -1. Cela rend possible car la file d'attente ne sera pas pleine, et de nouveaux éléments peuvent être insérés ici.
  • Quand arrière != max -1. Cela garantit que l'arrière est incrémenté jusqu'à la taille d'allocation maximale et que les valeurs peuvent être insérées facilement à l'extrémité arrière de la file d'attente.

48. A quoi servent les pointeurs vides ?

Les pointeurs vides sont utilisés en raison de leur capacité à stocker n'importe quel pointeur pointant vers une grande variété de données.

Il est utilisé pour implémenter des listes chaînées hétérogènes dans de nombreux langages de programmation. Un espace mémoire supplémentaire pour un pointeur est requis avec chaque élément de la liste chaînée.

49. Quelle est la signification de la condition de débordement de pile ?

Le débordement de pile est le terme donné lorsque la pile est pleine et qu'un élément ne peut plus être inséré dans la pile. Le débordement de pile se produit lorsque top = Maxsize-1

50. Avez-vous obtenu une sorte de certification pour améliorer votre processus d'apprentissage et de mise en œuvre ?

  • Avancements de carrière
  • Forte aspiration
  • Apprenant efficace

Énumérez les certifications, si vous en avez, et parlez-en brièvement, en expliquant tout ce que vous avez appris du programme et en quoi cela vous a été utile jusqu'à présent.

Top 100 des questions et réponses des entretiens sur les structures de données

51. Expliquer les types de structures de données.

types de structures de données

52. Quels sont les avantages de la structure des données ?

avantages de la structure des données

53. Énumérez les opérations que vous pouvez effectuer sur la structure des données.

opérations que vous pouvez effectuer sur la structure de données

54. Comment les nombres signés et non signés affectent-ils la mémoire ?

En signé le premier bit est utilisé pour indiquer si le nombre est positif ou négatif. Le non signé reconnu a tous les bits disponibles pour ce nombre.

Exemple : le nombre 8 bits non signé a une plage de 0 à 255, tandis que le nombre signé 8 bits a une plage de -128 à +127.

55. Quelle est la différence entre l'allocation de mémoire statique et dynamique ?

Allocation statiqueAllocation dynamique
Exécuté au moment de la compilationExécuté au moment de l'exécution
Affecté à la pileAffecté au tas
La taille doit être connue au moment de la compilationLa taille peut être inconnue au moment de la compilation
Affectation FILOPas d'affectation particulière
Exécution plus rapideExécution plus lente

56. Expliquez le rôle de malloc(), calloc(), realloc() et free().

Malloc() : utilisé pour l'allocation dynamique de mémoire. Syntaxe : int * p = (int *) malloc(sizeof(int))

Calloc() : utilisé pour l'allocation de mémoire dynamique contiguë. Syntaxe : p = (castType*)calloc(n, taille);

Realloc() : utilisé pour redimensionner la mémoire allouée sans perdre les anciennes données. Syntaxe : void * realloc(void * p.size_t newsize);

Free() : permet de libérer le bloc mémoire qui a été alloué dynamiquement. Syntaxe : libre(p);

57. Faites la différence entre la structure des fichiers et le stockage.

Vous trouverez ci-dessous les différences entre la structure des fichiers et le stockage :

Structure de stockageStructure du fichier
Représentation de la structure de données dans la mémoire du système informatique.Représentation des données en mémoire secondaire ou auxiliaire
Exemple : mémoire allouée ou variable ou constanteExemple : Enregistrer un fichier sur un disque dur

58. Expliquez la récursivité.

C'est un processus dans lequel une fonction s'appelle directement ou indirectement est appelée récursivité et la fonction correspondante est appelée fonction récursive. C'est une structure de données récursive ayant un pointeur vers son élément supérieur.

59. Faites la différence entre la récursivité et l'itération.

RécursivitéItération
La fonction s'appelle elle-mêmeUn ensemble d'instructions exécutées à plusieurs reprises
Se termine lorsque le cas de base est reconnuTerminer lorsque la condition de boucle échoue
Utilisé lorsque la complexité temporelle n'est pas un problèmeUtilisé lorsque la complexité temporelle doit être équilibrée par rapport à une taille de code étendue
Taille de code plus petiteGrande taille de code

60. Toutes les instructions de déclaration conduisent-elles à une réservation de mémoire fixe ?

La plupart des déclarations le font, à l'exception des pointeurs. La déclaration de point n'alloue pas de mémoire pour les données, mais l'adresse de la variable pointeur. L'allocation de mémoire réelle pour les données intervient pendant l'exécution.

Voir également Top 100 des questions et réponses d'entrevue Ansible

61. Qu'est-ce qu'un tableau ?

C'est une structure de données qui contient un groupe d'éléments. Un tableau est composé de plusieurs variables du même type. Il peut contenir des types primitifs et des références d'objet. La taille du tableau est toujours fixe.

62. Comment créer un tableau ?

Les tableaux peuvent être déclarés comme la façon dont une variable est déclarée.

  • Déclaration : int myArray[ ] ; OU int[ ] monTableau ;
  • Allocation de mémoire : int myArray[ ] ; OU int[ ] monTableau ;

63. Expliquez les types d'une liste chaînée ?

  • Liste chaînée simple : chaque nœud stocke l'adresse du nœud suivant. Par exemple : 1->2->3->4->NULL
  • Liste doublement chaînée : Deux références sont associées à chaque nœud. Par exemple : NUL<-123->NUL
  • Liste chaînée circulaire : tous les nœuds sont connectés pour former un cercle. Il n'y a pas de NULL à la fin, par exemple, 1->2->3->1

64. Quelle est la différence entre tableau et liste chaînée ?

DéployerListe liée
Taille fixeTaille dynamique
L'insertion, la suppression d'éléments est difficileL'insertion, la suppression des éléments est facile
Accès aléatoire autoriséL'accès aléatoire n'est pas autorisé
Meilleure localité du cacheMauvaise localité de cache
Risque de perte de mémoirePas de perte de mémoire

65. Quelles sont les applications des listes doublement liées ?

  • Navigation vers l'arrière et vers l'avant des pages Web.
  • Visionneuse d'images
  • Lecteur de musique
  • Jeu de cartes dans un jeu

66. Comment recherchez-vous une clé cible dans une liste chaînée ?

  • Commencez par l'élément le plus à gauche de arr[ ] et comparez un par un x avec chaque élément de arr[ ]
  • Si x correspond à un élément, renvoie l'index.
  • Si x ne correspond à aucun des éléments, renvoie -1

67. Énumérez quelques applications de la file d'attente circulaire.

  • Le fonctionnement des feux de circulation est le meilleur exemple pour les files d'attente circulaires. Les couleurs du feu de signalisation suivent un motif circulaire.
  • Dans les algorithmes de remplacement de page, une liste circulaire de pages est maintenue et lorsqu'une page doit être remplacée, la page en tête de la file d'attente sera choisie.

68. Expliquez certaines applications de la pile ?

  1. Gestion des expressions
  • Conversion d'infixe en suffixe ou d'infixe en préfixe.
  • Évaluation du suffixe ou du préfixe.
  1. Procédure de retour en arrière
  2. Appel de fonction et processus de retour

69. Quelle structure de données est utilisée pour effectuer la récursivité ?

La structure de données de la pile est utilisée dans la récursivité en raison de sa nature dernier entré, premier sorti.

70. Qu'est-ce que le débordement de pile ?

C'est une condition lorsque le tableau est vide et que l'utilisateur demande une opération de suppression.

71. Énumérez quelques applications de la structure de données de file d'attente.

  • Utilisé dans l'imprimante, le disque, le processeur.
  • Utilisé dans le transfert asynchrone de données.
  • Utilisé comme tampons dans le lecteur multimédia MP3, lecteur CD.
  • Utilisé pour maintenir la liste de lecture dans les lecteurs multimédias.
  • Utilisé dans le système d'exploitation pour gérer les interruptions.

72. Quelle structure de données est utilisée pour implémenter le cache LRU ?

Deux structures de données sont utilisées pour implémenter un cache LRU

  • File d'attente
  • Hacher

73. Mentionnez différents types d'arbres binaires.

  • Arbre binaire complet
  • Arbre binaire complet
  • Arbre incliné
  • Arbre incliné à gauche
  • Arbre incliné à droite

74. Donnez un algorithme de base pour rechercher un arbre de recherche binaire.

|__+_|

75. Quelles sont les différences entre l'arbre B et l'arbre B+ ?

Arbre BArbre B+
Les clés de recherche ne peuvent pas être stockées à plusieurs reprisesDes clés de recherche redondantes peuvent être présentes
Les données peuvent être stockées dans des nœuds feuilles et des nœuds internesLes données ne peuvent être stockées que sur les nœuds feuilles
La suppression des nœuds internes est complexeLa suppression ne sera jamais un processus complexe
Les nœuds feuilles ne peuvent pas être liés ensembleLes nœuds feuilles sont reliés entre eux pour rendre les opérations de recherche plus efficaces

Top 100 des questions et réponses des entretiens sur les structures de données

76. Quelles sont les différentes opérations appliquées sur les arbres AVL ?

  • Rotation gauche-gauche (LL)
  • Rotation gauche-droite (LR)
  • Rotation droite-droite (RR)
  • Rotation droite-gauche (RL)

77. Quel est le degré d'un nœud ?

Il peut être défini comme le nombre d'enfants d'un nœud.

  • Noeud 1 degré = 2
  • Nœud 2 degré = 2
  • Nœud 5 degré = 3

78. Quel est le degré d'un arbre ?

C'est le degré maximum d'un nœud dans un arbre

  • Noeud 1 degré = 2
  • Nœud 2 degré = 2
  • Nœud 5 degré = 3

Degré d'arbre = 3

79. Expliquer les arbres couvrants.

C'est un sous-ensemble du graphe G, qui a tous les sommets couverts avec un nombre minimum possible d'arêtes.

80. Qu'est-ce qu'un arbre couvrant minimum ?

Un arbre couvrant minimum est un arbre couvrant pondéré où le coût est minimum parmi tous les arbres couvrants.

81. Définir la structure des données du graphique

La structure de données du graphe est une structure de données non linéaire composée d'ensembles finis de nœuds (ou sommets) et d'un ensemble d'arêtes les reliant.

82. Faites la différence entre cycle, chemin et circuit.

Chemin : C'est une séquence de sommets adjacents reliés par les arêtes.

Cycle : C'est un chemin fermé où aucun sommet du chemin ne peut être visité deux fois.

Circuit : C'est un chemin fermé où n'importe quel sommet peut être répété.

83. Comment fonctionne la traversée en profondeur d'abord ?

Ici, le graphique est parcouru dans un mouvement de profondeur. Pile à retenir pour obtenir le sommet suivant.

84. Comment fonctionne le parcours en largeur d'abord ?

Ici, le graphe est parcouru dans un mouvement de largeur et utilise une file d'attente pour se souvenir d'obtenir le sommet suivant.

85. Expliquez l'algorithme de Dijkstra

Cet algorithme est utilisé pour calculer le chemin le plus court entre un nœud de votre choix et tous les autres nœuds d'un graphe.

86. Quelles sont les différentes approches pour développer des algorithmes ?

  • Cupide
  • Diviser et conquérir
  • Programmation dynamique

87. Expliquez une approche gourmande.

C'est une approche utilisée pour construire une solution pièce par pièce, en choisissant toujours la pièce suivante qui offre l'avantage le plus évident et le plus immédiat.

Exemples:

  • Algorithme de Dijkstra
  • Algorithme de Prim

88. Expliquez l'approche diviser pour mieux régner.

En utilisant cette approche, le problème est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment.

Exemples:

  • Recherche binaire
  • Tri par fusion

89. Expliquer la programmation dynamique.

La programmation dynamique est utilisée pour trouver la solution la plus optimisée en éliminant les appels récursifs standards.

Exemples:

  • Trouver la série de Fibonacci
  • Problème de sac à dos

90. Qu'est-ce qu'une recherche de Fibonacci ?

C'est un algorithme de recherche qui s'applique à un tableau trié. Ici, le nombre suivant est la somme des deux nombres précédents.

Exemples:

  • 0,1,1,2,3,5,8,13,21,34,55….

91. Qu'est-ce qu'une technique de recherche par interpolation ?

La recherche par interpolation est une variante améliorée de la recherche binaire.

  • Commencez à rechercher des données à partir du milieu de la liste.
  • S'il s'agit d'une correspondance, renvoie l'index de l'élément et quitte.
  • Si ce n'est pas une correspondance, sondez la position.
  • Divisez la liste à l'aide d'une formule de sondage et trouvez le nouveau milieu.
  • Si les données sont supérieures au milieu, recherchez dans une sous-liste supérieure.
  • Si les données sont plus petites que le milieu, recherchez dans la sous-liste inférieure.

92. Expliquez le fonctionnement du tri rapide.

Il s'agit d'un algorithme basé sur l'approche diviser pour mieux régner dans laquelle le tableau est divisé en sous-tableaux et ces sous-tableaux sont appelés de manière récursive pour trier les éléments.

  • Complexité temporelle : D(nlogn)

93. Quelle est la pire complexité temporelle de Quicksort ?

D(n^2)

  • Un tableau est déjà trié dans le même ordre
  • Le tableau est déjà trié dans l'ordre inverse
  • Tous les éléments sont identiques

94. Qu'est-ce qu'un tri Radix ?

C'est une technique qui trie les éléments en regroupant d'abord les chiffres individuels de la même valeur de position. Ensuite, triez les éléments.

95. Quels sont les inconvénients du tri Radix ?

  • Moins souple
  • La constante pour le tri Radix est supérieure
  • Consomme plus d'espace

96. Quelles sont certaines applications de la structure de données ?

Connaître les différents types de structures de données disponibles aide le programmeur à choisir la structure de données qui convient le mieux pour résoudre efficacement un problème. Certaines des applications en temps réel de la structure de données sont :

  • Pour représenter un réseau téléphonique de région urbaine
  • Pour implémenter la fonctionnalité de retour dans le navigateur Web Internet
  • Pour stocker des données à croissance dynamique auxquelles on accède très fréquemment, sur la base d'une clé-valeur
  • Pour implémenter la fonction d'annulation dans un éditeur de texte
  • Pour stocker les informations sur les répertoires et les fichiers dans un système

97. Mentionner les applications de la deque.

  • Vérificateur palindrome
  • Un algorithme de planification de travail volé

98. Quels sont les avantages d'une liste chaînée par rapport à un tableau ?

Considérons un scénario dans lequel nous devons stocker une grande quantité de données dans un tableau. Mais la mémoire pour stocker ces données n'est pas disponible de manière contiguë. Dans ce cas, nous ne pouvons pas utiliser de tableaux. Par conséquent, nous optons pour une liste chaînée. Étant donné que chaque nœud est connecté à l'aide d'un lien, il n'est pas nécessaire que la mémoire soit contiguë.

99. Écrivez la syntaxe en C pour créer un nœud dans la liste chaînée simple.

|__+_|

100. Quelle est l'utilité d'une liste à double lien par rapport à celle d'une liste à simple lien ?

Dans une liste à liens simples, nous n'avons que des liens vers l'avant. Par conséquent, nous ne pouvons pas parcourir la liste chaînée en arrière. Pour surmonter cela, nous optons pour une liste doublement liée.

Dans une liste à double liaison, chaque nœud a trois champs tels que précédent, données et champ suivant, et a deux liens tels qu'un lien avant et un lien arrière.

Le champ précédent du premier nœud et le champ d'adresse du dernier nœud sont NULL. Le champ précédent du deuxième nœud contient l'adresse du premier nœud et ainsi de suite.

Aussi, l'accès aux éléments peut être fait plus efficacement dans le cas d'une liste doublement chaînée.

Cette liste des 100 principales questions d'entretien sur la structure de données couvre la majeure partie des questions d'entretien sur la structure de données les plus fréquemment posées.