Artículo sobre Estructura de Datos (1)
1. Preguntas de opción múltiple (2 puntos por pregunta, 20 puntos en total)
1. Las características comunes de las pilas y colas son ( ).
A. Solo permitir la inserción y eliminación de elementos en el extremo
B. Todos primero en entrar, último en salir
C. Todo es primero en entrar y primero en salir
D. No hay terreno común
2. La cola almacenada de forma enlazada se inserta al realizar la operación de inserción ( ).
A. Solo el puntero de cabeza se modifica B. Los punteros de cabeza y cola deben modificarse
C. Modificar solo el puntero de cola D. Puede que sea necesario modificar los punteros de cabeza y cola
3. ¿Cuál de las siguientes estructuras de datos es una estructura no lineal? ( )
A. Cola B. Pila C. Tabla lineal D. Árbol binario
4. Si existe un arreglo bidimensional A[m][n], asumiendo que A[0][0] se almacena en 644 (10), y A[2][2] en 676 (10), cada elemento ocupa un espacio, ¿dónde se almacena A[3][3][3](10)? La nota al pie (10) indica que se expresa en decimal.
A.688 B.678 C.692 D.696
5. Los árboles se usan mejor para representar ( ).
A. Elementos de datos ordenados B. Elementos de datos no ordenados
C. Datos con relaciones jerárquicas ramificadas entre elementos D. Datos sin conexión entre elementos
6. El número máximo de nodos en la k-ésima capa del árbol binario es ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Si hay una tabla ordenada de 18 elementos almacenada en un array unidimensional A[19], el primer elemento se coloca en A[1], y ahora se realiza una búsqueda binaria, entonces el subíndice de la secuencia de comparación para encontrar A[3] es ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Ordenar rápidamente los archivos de n registros, y el espacio de almacenamiento auxiliar requerido es aproximadamente el mismo
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Para tablas lineales (7, 34, 55, 25, 64, 46, 20, 10) para almacenamiento hash, si H(K)=K %9 se selecciona como función hash, hay elementos ( ) con una dirección hash 1.
A.1 B.2 C.3 D.4
10. Un grafo no dirigido con 6 nodos, y el grafo debe tener al menos ( ) aristas para asegurar un grafo conexo.
A.5 B.6 C.7 D.8
2. Rellenar los huecos (1 punto por espacio, 26 puntos en total)
1. La calidad del algoritmo suele evalúarse desde cuatro aspectos: _________, _________, _________ y _________.
2. La complejidad temporal de un algoritmo es (n3+n2log2n+14n)/n2, y su orden de magnitud se expresa como ________.
3. Suponiendo que la tabla generalizada de un árbol se representa como A(C,D(E,F,G),H(I,J)), entonces el número de nodos contenidos en el árbol es __________, la profundidad del árbol es ___________ y el grado del árbol es _________.
4. El valor de la fórmula del sufijo 9 2 3 +- 10 2 / - es __________. La fórmula del sufijo correspondiente a la fórmula intermedia (3+4X)-2Y/3 es _______________________________.
5. Si un árbol binario se almacena con una lista enlazada, cada nodo tiene dos punteros al hijo izquierdo y al hijo derecho además del campo de datos. En esta estructura de almacenamiento, el árbol binario con n nodos tiene un total de ________ campos puntero, de los cuales ________ campos de puntero almacenan direcciones y ________________ punteros son punteros vacíos.
6. Para un grafo dirigido y un grafo no dirigido con n vértices y aristas de barra E, hay _______ y ________ nodos de aristas en su tabla de adyacencia correspondiente, respectivamente.
7. La red AOV es un grafo ___________________.
8. En un grafo completo no dirigido con n vértices, hay ________ aristas, y en un grafo completo dirigido con n vértices, hay ________ aristas.
9. Suponiendo que una tabla lineal es (12,23,74,55,63,40), si los elementos del mismo resto se convierten en una subtabla según la condición de Key % 4, las cuatro subtablas obtenidas son ____________________________, ___________________, _______________________ y __________________________.
10. En el proceso de insertar elementos en un árbol B_, si el nodo raíz del árbol se divide finalmente, la altura del nuevo árbol es ___________ que la del árbol original.
11. En el proceso de ordenación de heap, la complejidad temporal para tamizar cualquier nodo de rama es ________, y la complejidad temporal de todo el proceso de ordenación de heap es ________.
12. En la clasificación rápida, la ordenación por heap y la ordenación por fusiones, _________ ordenación es estable.
Artículo sobre Estructura de Datos (2)
1. Preguntas de opción múltiple (24 puntos)
1. La siguiente descripción de las tablas lineales es incorrecta ().
(A) Las tablas lineales se almacenan secuencialmente y deben ocupar un espacio de almacenamiento contiguo
(B) Las tablas lineales están encadenadas y no ocupan un espacio de almacenamiento continuo
(C) Las tablas lineales se implementan con almacenamiento encadenado para facilitar las operaciones de inserción y eliminación
(d) Las tablas lineales se implementan con almacenamiento secuencial para facilitar las operaciones de inserción y eliminación
2. Supongamos que el número total de nodos hoja en el árbol de Huffman es m, y si se usa una lista binaria enlazada como estructura de almacenamiento, hay un total de ( ) campos punteros vacíos en el árbol de Huffman.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Si los punteros cabeza y cola de la cola secuencial Q[0:M-1] son F y R respectivamente, el puntero cabeza F siempre apunta a la posición anterior del elemento cabeza, y el puntero de cola R siempre apunta a la posición actual del elemento de cola, entonces el número de elementos en la cola de bucle es ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Si la secuencia de recorrido de orden medio de un árbol binario es ABCD y la secuencia anterior es CABD, entonces la secuencia obtenida al recorrer el árbol binario en el orden siguiente es ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Supongamos que hay n vértices en un grafo completamente no dirigido, entonces hay ( ) aristas en el grafo completamente no dirigido.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Supongamos que hay 2000 nodos en un árbol binario, entonces la altura mínima del árbol binario es ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Supongamos que hay n vértices en un grafo dirigido, entonces hay nodos de cabecera ( ) en la tabla de adyacencia correspondientes al grafo dirigido.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Establecer un conjunto de secuencias iniciales de palabras clave de registro (5, 2, 6, 3, 8), y el resultado de un ordenamiento rápido basado en la primera palabra clave de registro 5 es ( ).
(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. Rellena los huecos (24 puntos)
1. Para aplicar eficazmente la tecnología de búsqueda HASH, dos problemas que deben resolverse son ____________________ y __________________________.
2. La función del siguiente segmento de programa realiza los datos x en la pila y requiere que la sentencia correcta se rellene en el subrayado.
typedefstruct {int s[100]; int top; } sqstack;
Vacío Push(Sqstack&Stack,int X)
{
if (stack.top==m-1) printf("overflow");
si no, {____________________; _________________; }
}
3. La secuencia obtenida al recorrer el árbol binario de ordenación en el orden medio es una secuencia ___________ (rellenada ordenada o no ordenada).
4. La peor complejidad temporal de la ordenación rápida es ___________, y la complejidad media es __________.
5. Si el número de nodos con grado 0 en un árbol binario es N0 y el número de nodo con grado 1 es N1, entonces el número de nodos con grado 2 en el árbol binario es _________; Si se utiliza una lista binaria enlazada como estructura de almacenamiento del árbol binario, _______ hay campos punteros vacíos en el árbol binario.
6. Supongamos que el número de vértices y aristas en un determinado grafo no dirigido es n y e, respectivamente, y la suma de los grados de todos los vértices es d, entonces e = _______.
7. Si la secuencia inicial de palabras clave del registro es (55, 63, 44, 38, 75, 80, 31, 56), entonces el heap inicial establecido por el método de cribado es ___________________________.
8. Se sabe que la estructura de almacenamiento de tabla de adyacencia de un grafo dirigido es la siguiente: Desde el vértice 1, la secuencia de salida del recorrido DFS es:
, la secuencia de salida del recorrido BFS es
Artículo sobre Estructura de Datos (3)
1. Preguntas de opción múltiple (1 punto por pregunta, 20 puntos en total)
1. Si la forma binaria de una estructura de datos se expresa como 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>}, entonces la estructura de datos A es ( ).
(A) Estructura lineal (B) Estructura en árbol (C) Estructura física (D) Estructura gráfica
2. El complejo temporal del siguiente programa es ()
for(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. Configura la variable puntero p para que apunte al nodo A en una única lista enlazada; si eliminas el nodo A en una sola lista enlazada, necesitas cambiar la secuencia de operaciones del puntero a ().
(A) q=p->siguiente; p->data=q->data; p->siguiente=q->siguiente; libre(q);
(B) q=p->siguiente; q->data=p->data; p->siguiente=q->siguiente; libre(q);
(C) q=p->siguiente; p->siguiente=q->siguiente; libre(q);
(D) q=p->siguiente; p->data=q->data; libre(q);
4. Si hay n palabras clave de registro que ordenar, ( ) se requieren unidades auxiliares de registro en la ordenación del montón.
(A) 1 (B) n (C) nlog2n (D) n2
5. Si las palabras clave del registro inicial son (20, 15, 14, 18, 21, 36, 40, 10), entonces el resultado tras el final de un ordenamiento rápido registrado con 20 como referencia es ( ).
(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. Supongamos que hay n nodos en el árbol binario de ordenación, entonces la longitud media de búsqueda en el árbol binario es ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Supongamos que hay n aristas de vértice e en el grafo no dirigido G, entonces el número de nodos de cabecera y nodos de tabla en la tabla de adyacencia correspondiente es ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Supongamos que hay n vértices en un grafo de conexión fuerte, entonces hay al menos ( ) aristas en el grafo de conexión fuerte.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Hay 5000 palabras clave de registro que deben ordenarse; si necesitas usar el método más rápido para seleccionar las 10 palabras clave más pequeñas, puedes usar el siguiente método ( ) para lograr este propósito.
(A) Ordenación rápida (B) Ordenación por heps (C) Ordenación por fusión (D) Ordenación insertada
10. Los siguientes cuatro tipos de ( ) tienen la mayor complejidad espacial.
(A) Clasificación por inserción (B) Clasificación por burbujeo (C) Clasificación por heps (D) Clasificación por fusión
2. Rellenar los espacios en blanco (1 punto por espacio, 20 puntos en total)
1. La estructura física de los datos incluye principalmente dos situaciones: _____________ y ______________.
2. Si hay 500 nodos en un árbol binario completo, la profundidad del árbol binario es __________; Si usas una lista binaria enlazada como estructura de almacenamiento para el árbol totalmente binario, ___________ hay campos puntero vacíos.
3. Si la secuencia de entrada es 1, 2, 3, entonces se pueden obtener ___________ secuencias de salida diferentes tras la acción de la pila.
4. Si la matriz de adyacencia A[n][n] se utiliza como estructura de almacenamiento para el grafo G, entonces la suma de todos los elementos en la fila i de la matriz de adyacencia es igual al ________ del vértice i, y la suma de todos los elementos en la columna i es igual a la ________ del vértice i.
5. Si hay n nodos en el árbol de Huffman, hay ________ nodos con grado de 1 en el árbol de Huffman.
6. Si hay n vértices e en el grafo direccional G con aristas direccionales, y la suma de todos los vértices que entran en grados es d, entonces la relación entre e y d es _________.
7. __________ recorrer los nodos del árbol binario de ordenación puede obtener una secuencia incremental de palabras clave (relleno, medio o posterior).
8. Si hay 100 elementos en la tabla de búsqueda, si usas el método de búsqueda dicotómica para encontrar el elemento de datos X, necesitas compararlo hasta ________ veces para determinar si el elemento X está en la tabla de consulta.
9. Ya sea una pila con una estructura de almacenamiento secuencial o una pila con una estructura de almacenamiento en cadena, la complejidad temporal de las operaciones dentro y fuera de la pila es ____________.
10. Un árbol binario completo con n nodos, si se numera en orden de arriba a abajo y de izquierda a derecha empezando por 1, el nodo padre del nodo i-ésimo se numera ____________, y el número del nodo hijo derecho es ___________.
11. Si el conjunto inicial de palabras clave registradas es (72, 73, 71, 23, 94, 16, 5), entonces el resultado de una ordenación rápida basada en la palabra clave de registro 72 es ___________________________.
12. Si existe un conjunto de aristas dirigidas en el grafo direccional G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, entonces una sucesión topológica del grafo es ____________________.
13. El siguiente algoritmo implementa la palabra clave con valor x en la lista de hashes secuencial, por favor rellene la sentencia correcta en el guion bajo.
struct record{int key; en otros; };
inthashsqsearch(tabla hash de registro struct[ ],int k)
{
inti,j; j=i=k % p;
mientras que (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; si (i==j) retorna(-1); }
si (_______________________ ) retorna (j); si no, return(-1);
}
14. El siguiente algoritmo implementa el valor clave k en el árbol binario de ordenación, por favor rellene la sentencia correcta en el guion bajo.
typedefstruct node{int key; nodo de struct *lchild; nodo de struct *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
si (t==0) retorno(0); si no, mientras (t!=0)
si (t->clave==k)_____________; si no, si (t->clave>k) t=t->lchild; else_____________;
}
Examen de estructura de datos (1) Consulta la respuesta
1. Preguntas tipo test (2 puntos por pregunta, 20 puntos en total)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Rellenar los huecos (1 punto por espacio, 26 puntos en total)
1. Corrección, legibilidad, resistencia y alta eficiencia
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. Direccional y no circuito
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Suma 1
11.O(log2n) O(nlog2n)
12. Consolidación
Las respuestas a otras preguntas del examen pueden verse:
Turistas, si queréis ver el contenido oculto de esta publicación, por favor Respuesta
|
Publicado en 25/11/2014 12:46:30
|
|
|
Publicado en 30/12/2014 0:10:55
|
