Article sur la structure de données (1)
1. Questions à choix multiples (2 points par question, 20 points au total)
1. Les caractéristiques communes des piles et des files d’attente sont ( ).
A. N’autoriser l’insertion et la suppression d’éléments qu’au point d’extrémité
B. Tous premier entrant, dernier sorti
C. Tout est premier entré, premier sorti
D. Il n’y a pas de terrain d’entente
2. La file d’attente stockée de manière liée est insérée lors de l’opération d’insertion ( ).
A. Seul le pointeur de tête est modifié B. Les pointeurs de tête et de queue doivent être modifiés
C. Modifier uniquement le pointeur de queue D. Les pointeurs de tête et de queue peuvent devoir être modifiés
3. Laquelle des structures de données suivantes est une structure non linéaire ? ( )
A. File B. Pile C. Table linéaire D. Arbre binaire
4. S’il existe un tableau bidimensionnel A[m][n], en supposant que A[0][0] est stocké à 644 (10), et A[2][2] est stocké à 676 (10), chaque élément occupe un espace, où est stocké A[3][3][3](10) ? La note de bas de page (10) indique qu’elle est exprimée en décimale.
A.688 B.678 C.692 D.696
5. Les arbres sont mieux utilisés pour représenter ( ).
A. Éléments de données ordonnés B. Éléments de données non ordonnés
C. Données avec des relations hiérarchiques ramifiées entre les éléments D. Données sans connexion entre les éléments
6. Le nombre maximal de nœuds dans la k-ième couche de l’arbre binaire est ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. S’il existe une table ordonnée de 18 éléments stockée dans un tableau unidimensionnel A[19], le premier élément est placé dans A[1], et qu’une recherche binaire est effectuée, alors le sous-indice de la séquence de comparaison pour trouver A[3] est ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Trier rapidement les fichiers de n enregistrements, et l’espace de stockage auxiliaire requis est à peu près le même
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Pour les tables linéaires (7, 34, 55, 25, 64, 46, 20, 10) pour le stockage par hachage, si H(K)=K %9 est sélectionné comme fonction de hachage, il y a ( ) des éléments avec une adresse de hachage de 1.
A.1 B.2 C.3 D.4
10. Un graphe non orienté avec 6 nœuds, et le graphe doit avoir au moins ( ) arêtes pour garantir un graphe connexe.
A.5 B.6 C.7 D.8
2. Remplir les blancs (1 point par blanc, 26 points au total)
1. La qualité de l’algorithme est généralement évaluée sous quatre angles : _________, _________, _________ et _________.
2. La complexité temporelle d’un algorithme est (n3+n2log2n+14n)/n2, et son ordre de grandeur est exprimé en ________.
3. En supposant que la table généralisée d’un arbre soit représentée par A(C,D(E,F,G),H(I,J)), alors le nombre de nœuds contenus dans l’arbre est __________, la profondeur de l’arbre est ___________, et le degré de l’arbre est _________.
4. La valeur de la formule du suffixe 9 2 3 +- 10 2 / - est __________. La formule du suffixe correspondant à la formule du milieu (3+4X)-2Y/3 est _______________________________.
5. Si un arbre binaire est stocké avec une liste chaînée, chaque nœud possède deux pointeurs vers l’enfant gauche et l’enfant droit en plus du champ de données. Dans cette structure de stockage, l’arbre binaire avec n nœuds possède un total de ________ champs pointeurs, dont ________ champs pointeurs stockent des adresses et ________________ pointeurs sont des pointeurs vides.
6. Pour un graphe orienté et un graphe non orienté avec n sommets et arêtes en E-bar, il y a respectivement _______ et ________ nœuds d’arêtes dans sa table d’adjacence correspondante.
7. Le réseau AOV est un graphe ___________________.
8. Dans un graphe complet non orienté avec n sommets, il y a ________ arêtes, et dans un graphe complet orienté avec n sommets, il y a ________ arêtes.
9. En supposant qu’une table linéaire soit (12,23,74,55,63,40), si les éléments du même reste deviennent une sous-table selon la condition de Key % 4, les quatre sous-tables obtenues sont ____________________________, ___________________, _______________________ et __________________________.
10. Lors de l’insertion d’éléments dans un arbre B_, si le nœud racine de l’arbre est finalement scindé, la hauteur du nouvel arbre est ___________ de celle de l’arbre d’origine.
11. Dans le processus de tri du tas, la complexité temporelle du tamisage de n’importe quel nœud de branche est ________, et la complexité temporelle de l’ensemble du processus de tri du tas est ________.
12. Dans le tri rapide, le tri par tas et le tri par fusion, _________ tri est stable.
Article sur la structure de données (2)
1. Questions à choix multiples (24 points)
1. La description suivante des tables linéaires est incorrecte ().
(A) Les tables linéaires sont stockées séquentiellement et doivent occuper un espace de stockage contigu
(B) Les tables linéaires sont chaînées et n’occupent pas un espace de stockage continu
(C) Les tables linéaires sont implémentées avec un stockage en chaîne pour faciliter les opérations d’insertion et de suppression
(d) Les tables linéaires sont implémentées avec un stockage séquentiel pour faciliter les opérations d’insertion et de suppression
2. Supposons que le nombre total de nœuds feuilles dans l’arbre de Huffman soit m, et si une liste binaire chaînée est utilisée comme structure de stockage, il y a un total de ( ) champs pointeurs vides dans l’arbre de Huffman.
(A) 2m-1 (B)2m (C)2m + 1 (D)4m
3. Si les pointeurs tête et queue de la file de boucle séquentielle Q[0 :M-1] sont respectivement F et R, le pointeur tête F pointe toujours vers la position précédente de l’élément tête, et le pointeur de queue R pointe toujours vers la position actuelle de l’élément de queue, alors le nombre d’éléments dans la file de boucle est ( ).
(A) R-F (B) F-R (C) (R-F+M) %M (D) (F-R+M) %M
4. Si la suite de parcours d’ordre intermédiaire d’un arbre binaire est ABCD et que la suite de parcours de séquence précédente est CABD, alors la suite obtenue en parcourant l’arbre binaire dans l’ordre suivant est ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Supposons qu’il y ait n sommets dans un graphe complètement non orienté, alors il y a ( ) des arêtes dans le graphe complètement non orienté.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Supposons qu’il y ait 2000 nœuds dans un arbre binaire, alors la hauteur minimale de cet arbre est ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Supposons qu’il y ait n sommets dans un graphe orienté, alors il y a ( ) des nœuds d’en-tête dans la table d’adjacence correspondant au graphe orienté.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Définir un ensemble de séquences initiales de mots-clés d’enregistrement (5, 2, 6, 3, 8), et le résultat d’un tri rapide basé sur le premier mot-clé d’enregistrement 5 est ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Remplir les blancs (24 points)
1. Pour appliquer efficacement la technologie de recherche HASH, deux problèmes doivent être résolus sont ____________________ et __________________________.
2. La fonction du segment de programme suivant réalise les données x dans la pile, et nécessite que la bonne instruction soit remplie dans le soulignement.
typedefstruct {int s[100] ; Int top ; } pile carré ;
Push du vide (sqstack&stack,int x)
{
if (stack.top==m-1) printf(« overflow ») ;
sinon {____________________ ; _________________; }
}
3. La séquence obtenue en parcourant l’arbre binaire de tri dans l’ordre intermédiaire est une ___________ séquence (remplie dans un ordre ou un non).
4. La pire complexité temporelle du tri rapide est ___________, et la complexité temporelle moyenne est __________.
5. Si le nombre de nœuds de degré 0 dans un arbre binaire est N0 et que le nombre de nœuds de degré 1 est N1, alors le nombre de nœuds de degré 2 dans l’arbre binaire est _________ ; Si une liste binaire chaînée est utilisée comme structure de stockage de l’arbre binaire, il y a _______ champs pointeurs vides dans l’arbre binaire.
6. Supposons que le nombre de sommets et d’arêtes dans un certain graphe non orienté soit n et e, respectivement, et que la somme des degrés de tous les sommets soit d, alors e = _______.
7. Si la séquence initiale de mots-clés de l’enregistrement est (55, 63, 44, 38, 75, 80, 31, 56), alors le tas initial établi par la méthode de sélection est ___________________________.
8. On sait que la structure de stockage de table d’adjacence d’un graphe orienté est la suivante : À partir du sommet 1, la séquence de sortie de la traversée DFS est :
, la suite de sortie de la traversée BFS est
Document sur la structure des données (3)
1. Questions à choix multiples (1 point par question, 20 points au total)
1. Si la forme binaire d’une structure de données s’exprime comme A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, alors la structure de données A est ( ).
(A) Structure linéaire (B) Structure en arbre (C) Structure physique (D) Structure graphique
2. Le complexe temporel du programme suivant est ()
pour (i=1,s=0 ; i<=n ; i++) {t=1 ;for(j=1 ;j<=i ; j++) t=t*j ; s=s+t ; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Définir la variable pointeur p pour pointer vers le nœud A dans une seule liste chaînée, si vous supprimez le nœud A dans une seule liste chaînée, vous devez changer la séquence d’opérations du pointeur vers ().
(A) q=p->suivant ; p->data=q->data ; p->suivant=q->suivant ; libre(q) ;
(B) q=p->suivant ; q->data=p->data ; p->suivant=q->suivant ; libre(q) ;
(C) q=p->suivant ; p->suivant=q->suivant ; libre(q) ;
(D) q=p->suivant ; p->data=q->data ; libre(q) ;
4. S’il y a n mots-clés d’enregistrement à trier, ( ) des unités auxiliaires d’enregistrement sont requises dans le tri du tas.
(A) 1 (B) n (C) nlog2n (D) n2
5. Si les mots-clés initials de l’enregistrement sont (20, 15, 14, 18, 21, 36, 40, 10), alors le résultat après la fin d’un tri rapide enregistré avec 20 comme référence est ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. Supposons qu’il y ait n nœuds dans l’arbre de tri binaire, alors la longueur moyenne de recherche dans l’arbre de tri binaire est ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Supposons qu’il y ait n arêtes de sommets e dans le graphe non orienté G, alors le nombre de nœuds d’en-tête et de nœuds de table dans la table d’adjacence correspondante est ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Supposons qu’il y ait n sommets dans un graphe de connexion forte, alors il y a au moins ( ) d’arêtes dans le graphe de connexion forte.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Il y a 5000 mots-clés d’enregistrement à trier, si vous devez utiliser la méthode la plus rapide pour sélectionner les 10 mots-clés les plus petits d’enregistrement, vous pouvez utiliser la méthode suivante ( ) pour atteindre cet objectif.
(A) Tri rapide (B) Tri tas (C) Tri par fusion (D) Tri insertion
10. Les quatre types suivants de ( ) ont la plus grande complexité spatiale.
(A) Tri par insertion (B) Tri par bulles (C) Tri par tas (D) Tri par fusion
2. Remplir les blancs (1 point par blanc, 20 points au total)
1. La structure physique des données inclut principalement deux situations : _____________ et ______________.
2. S’il y a 500 nœuds dans un arbre binaire complet, la profondeur de l’arbre binaire est __________ ; Si vous utilisez une liste binaire chaînée comme structure de stockage pour l’arbre entièrement binaire, il y a ___________ champs pointeurs vides.
3. Si la séquence d’entrée est 1, 2, 3, alors ___________ séquences de sortie différentes peuvent être obtenues après l’action de la pile.
4. Si la matrice d’adjacence A[n][n] est utilisée comme structure de stockage pour le graphe G, alors la somme de tous les éléments de la ligne i dans la matrice d’adjacence est égale à la ________ du sommet i, et la somme de tous les éléments de la colonne i est égale à la ________ du sommet i.
5. S’il y a n nœuds dans l’arbre de Huffman, il y a ________ nœuds de degré 1 dans l’arbre de Huffman.
6. S’il existe n sommets e dans le graphe directionnel G avec des arêtes directionnelles, et que la somme de tous les sommets entrant dans les degrés est d, alors la relation entre e et d est _________.
7. __________ parcourant les nœuds de l’arbre de tri binaire peut obtenir une séquence incrémentale de mots-clés (rempli, milieu ou postérieur).
8. S’il y a 100 éléments dans la table de recherche, si vous utilisez la méthode de recherche dichotomique pour trouver l’élément de données X, vous devez le comparer jusqu’à ________ fois pour déterminer si l’élément de données X est dans la table de recherche.
9. Qu’il s’agisse d’une pile avec une structure de stockage séquentielle ou d’une pile avec une structure de stockage en chaîne, la complexité temporelle des opérations d’entrée et de sortie de la pile est ____________.
10. Un arbre binaire complet avec n nœuds, si numérotés de haut en bas et de gauche à droite à partir de 1, le nœud parent du i-ème nœud est numéroté ____________, et le nombre du nœud enfant de droite est ___________.
11. Si l’ensemble initial de mots-clés enregistrés est (72, 73, 71, 23, 94, 16, 5), alors le résultat d’un tri rapide basé sur le mot-clé enregistré 72 est ___________________________.
12. S’il existe un ensemble d’arêtes dirigées dans le graphe directionnel G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, alors une suite topologique du graphe est ____________________.
13. L’algorithme suivant implémente le mot-clé avec la valeur x dans la liste de hachages séquentielle, veuillez remplir la bonne instruction dans le soulignement.
struct record{int key ; dans d’autres ; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j ; j=i=k % p ;
tandis que (Hashtable[J].key !=K&&Hashtable[J].flag !=0){J=(____) %M ; si (i==j) return(-1) ; }
si (_______________________ ) retourner (j) ; sinon retour(-1) ;
}
14. L’algorithme suivant implémente la valeur clé k dans l’arbre de tri binaire, veuillez remplir la bonne instruction dans le soulignement.
typedefstruct node{int key ; nœud de struct *lchild ; nœud de struct *rchild ; }bitree ;
bitree *bstsearch(bitree *t, int k)
{
si (t==0) retour(0) ; sinon tandis que (t !=0)
if (t->clé==k)_____________ ; sinon si (t->clé>k) t=t->lchild ; else_____________ ;
}
Épreuve de test de structure des données (1) Référez-vous à la réponse
1. Questions à choix multiples (2 points par question, 20 points au total)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Remplir les blancs (1 point par blanc, 26 points au total)
1. Correction, lisibilité, solidité et haute efficacité
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5,2n n-1 n+1
6.e 2e
7. Directionnel et non-circuit
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Ajouter 1
11.O(log2n) O(nlog2n)
12. Consolidation
Les réponses aux autres questions du test sont disponibles :
Touristes, si vous voulez voir le contenu caché de ce post, s’il vous plaît Répondre
|
Publié sur 25/11/2014 12:46:30
|
|
|
Publié sur 30/12/2014 00:10:55