1. Describa brevemente las características de la estructura de almacenamiento secuencial y la estructura de almacenamiento en cadena.
Respuesta: La ventaja de la estructura de almacenamiento secuencial es que no es necesario agregar espacio de puntero adicional para expresar la relación lógica entre elementos; puede acceder aleatoriamente a cualquier elemento de la tabla; La desventaja es que el espacio debe asignarse con anticipación y es difícil expandir la capacidad de la tabla; las operaciones de inserción y eliminación requieren mover muchos nodos, lo cual es muy ineficiente.
La ventaja de la estructura de almacenamiento en cadena es que el almacenamiento de nodos utiliza almacenamiento dinámico y la capacidad de la tabla es fácil de expandir, la inserción y eliminación son muy convenientes y no es necesario mover el nodo; , solo es necesario modificar el puntero en el nodo. La desventaja es que cada nodo requiere un espacio de puntero, que es menor que la densidad de almacenamiento de la estructura de almacenamiento secuencial que solo se puede encontrar en orden;
2. ¿Por qué deberíamos introducir el nodo principal en la lista enlazada?
Respuesta: Al insertar y eliminar una lista vinculada, debe determinar si la operación está al principio de la lista vinculada. Si se inserta un nuevo nodo antes del primer nodo y se elimina el primer nodo, el valor principal del primer puntero cambiará. De lo contrario, el valor de cabeza no cambiará. Agregar un nodo principal delante de la lista vinculada (usando solo el campo de puntero para apuntar al nodo principal de la lista vinculada) evita el juicio de las dos situaciones, lo que simplifica el diseño del programa y hace que la estructura del programa sea más clara.
2. Describa brevemente cómo determinar el árbol binario a través de los órdenes transversales de preorden, orden medio y postorden del árbol binario.
Respuesta: Entre las tres secuencias transversales, la secuencia de preorden, la secuencia intermedia, la secuencia intermedia y la secuencia de postorden pueden determinar de forma única un árbol binario, porque la secuencia de preorden o la secuencia de postorden pueden determinar el nodo raíz. del árbol binario. La secuencia intermedia determina los subárboles izquierdo y derecho de la raíz. La secuencia de preorden y la secuencia de postorden no pueden determinar de forma única un árbol binario, pero tenga en cuenta que la secuencia de preorden y la secuencia de postorden del árbol pueden determinar de forma única el árbol, porque la secuencia de postorden del árbol es la secuencia de orden del árbol binario.
4. Mejora en el peor de los casos de la clasificación rápida
Respuesta: cuando la secuencia a ordenar es una secuencia ordenada, la eficiencia de la clasificación rápida es muy baja y se convierte en clasificación de burbujas. Para evitar esto, seleccione el primer elemento de la secuencia como elemento pivote (o elemento de referencia) y el primer elemento, el elemento del medio y el elemento del medio del último elemento de la secuencia como elemento de referencia (simplemente use el elemento del medio como referencia), lo que puede mejorar en gran medida el rendimiento de la clasificación rápida. Por ejemplo:
8, 0, 4, 9, 6, 3, 5, 2, 7, 1
Tome el elemento medio grande 6 como punto de referencia, el elemento de referencia y el último elemento El intercambio es el siguiente:
8, 0, 4, 9, 1, 3, 5, 2, 7, 6
↑ ↑
J internacional
Comparo los contenidos de I y J, si los contenidos de I son menores que la línea base, entonces avanzo, en caso contrario me detengo y comienzo la comparación de J: Si los contenidos de J son mayores que la línea de base, luego J avanza; de lo contrario, J se detiene y el contenido de I se intercambia con el contenido de J, repita el proceso anterior hasta que J < I ltSPAN gt verifique, intercambie la línea de base y mi contenido, complete en un segmento. , de la siguiente manera:
8, 0, 4, 9, 1, 3, 5, 2, 7, 6
2, 0, 4, 9, 1, 3, 5 , 8, 7, 6
2, 0, 4, 5, 1, 3, 9, 8, 7, 6
2, 0, 4, 5, 1, 3 , 6, 8, 7, 9
5. Describa brevemente la idea básica del método de programación dinámica.
Respuesta: Para ahorrar el tiempo de buscar repetidamente el mismo subproblema, se introduce una tabla (matriz) Las soluciones a nuevos subproblemas se almacenan en la tabla independientemente de si son útiles para la solución final. . Cuando nos encontremos con el mismo subproblema en el futuro, no volveremos a encontrar el subproblema, sino que obtendremos directamente la solución al subproblema de la tabla. Ésta es la idea básica adoptada por el método de programación dinámica.
(4) Preguntas de opción múltiple
1. La cola circular utiliza la matriz A[0...m-1] para almacenar los valores de sus elementos. Suponiendo que su puntero principal y su puntero final son el puntero frontal y el puntero posterior respectivamente, el número de elementos en la cola actual es.
A.(back-front m) m B.read-front 1
c .read front-1 D.read front
Respuesta de referencia a
2. En términos generales, el proceso de ejecución del algoritmo recursivo se puede dividir en dos etapas: (1) y (2).
(1) A. Intento b. Recursión c. Enumeración d. Análisis
(2) A. Regresión b. >nRespuestas de referencia (1) B (2) B
3. Supongamos que la longitud de la tabla hash es m = 11 y la función hash H (clave) = clave11. Hay cuatro nodos en la tabla: addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7 y las direcciones restantes están vacías. Si la segunda sonda y el hash chocan, la dirección del nodo con la clave 49 es.
A.8 B.3 C.5 D.9
Respuesta de referencia d
4. Todos los no terminales (excepto la raíz) en la M -order B-tree El número de palabras clave del nodo debe ser mayor o igual que.
A.-1 b . 1 c .-1d .
Respuesta de referencia c
5. 46, 79, 56, 38, 40, 84), entonces se obtiene el resultado de la primera división basado en el primer registro.
38, 40, 46, 56, 79, 84
40, 38, 46, 56, 79, 84
Respuesta de referencia c
6. Si un problema se puede resolver mediante recursividad y algoritmo recursivo, entonces el algoritmo (1) se utiliza a menudo debido a (2).
(1) A. Recurre primero, luego recurre b. Recurre primero, luego recurre c.
(2) A. La recursividad es más eficiente que la recursividad b. La recursividad es adecuada para la descomposición de problemas.
C. La recursividad es más eficiente que la recursividad. d. La recursividad es adecuada para la descomposición de problemas.
nRespuestas de referencia (1)D (2)A
7. Numere los nodos de un árbol binario completo con 100 nodos de arriba a abajo y de izquierda a derecha. El número del nodo raíz es 1 y el número del nodo secundario izquierdo del nodo número 49 es.
A.99 BC
Respuesta de referencia b
8. El problema que el árbol binario no puede resolver de manera efectiva después de que se le solicite es.
A. Busque el sucesor del predecesor en el árbol binario de pistas anterior b. Encuentre el sucesor intermedio en el árbol binario de pistas intermedias.
C. Encuentre el orden en el árbol binario de pistas de orden inverso, d.
Consulte la respuesta d
9. La condición para juzgar que un nodo P en el árbol binario de pistas tiene un hijo izquierdo es (1). Si el árbol binario convertido del bosque no está vacío, la forma del árbol binario es (2).
(1)A.P! = nulo B . P- gt;Niños. =null C.P->ltag=0 D.P->ltag=1
(2) A. Un árbol binario con un nodo raíz pero sin subárbol derecho b. Un árbol binario con un nodo raíz pero sin subárbol izquierdo.
C. El nodo raíz puede tener un subárbol izquierdo y un subárbol derecho. Un árbol binario con un solo hijo por nodo.
nRespuestas de referencia (1)C (2)C
10. En el encabezado de una lista enlazada individualmente, si desea insertar un nodo señalado por el puntero Q después del nodo señalado. por el puntero P, implementar_ _ _ _.
A.p->; siguiente = q-gt; siguiente; q->; siguiente = p;
C.p->; siguiente = q- gt; siguiente; p->; siguiente = q;
D.q->; siguiente = p-gt; next = q;
Respuesta de referencia d
11 Supongamos que se organiza la matriz bidimensional a[0...m-1][0...n-1]. en la columna prioridad El orden se almacena en el área de almacenamiento con la primera dirección loc(a[0][0] Cada elemento ocupa d unidades, luego A [I] [
A.loc(a). [0][ 0]) (j×n I)×d b . loc(a[0][0]) (j×m I)×d
c . 0]) ( (j-1)×n I-1)×d . loc(a[0][0]) ((j-1)×m I-1)×d
Referencia. respuesta b
12. Si la secuencia de entrada de una pila es 1, 2, 3, 4, y cada elemento debe entrar y salir de la pila una vez, entonces es imposible obtener la salida de la pila. secuencia _ _ _ _.
A 4, 3, 2, 1 B 4, 2, 1, 3 C 1, 3, 2, 4 D 3, 4, 2, 1
Respuesta de referencia b
13. Al ordenar rápidamente n elementos, la peor complejidad del tiempo es.
A.O(log2n)B . O(n)C . O(nlog2n)D .
Respuesta de referencia d
14. En el algoritmo de clasificación interno de "Comparación", si se clasifican 6 elementos, el peor número de comparaciones requeridas es al menos.
a . 10 b . 11 C . 21d 36
Respuesta de referencia a
IV. árbol Los métodos transversales de preorden, inorden y postorden son los más adecuados para ser implementados por (1).
En un árbol de búsqueda, la suma de las longitudes de las rutas desde el nodo raíz hasta todos los demás nodos se llama (2), y el árbol que minimiza la suma de las longitudes de las rutas se llama (3). Definitivamente es ④.
Entre las diversas afirmaciones sobre los árboles, sólo (5) es correcta.
(1) A. Programa recursivo b. Programa iterativo c. Operación de cola d. Operación de pila
(2) A. Longitud de la ruta interna c. .Suma de profundidad
(3) a.b.Árbol b.b árbol c.Árbol completo d.Árbol de subprocesos
(4)a.b.-árbol b.Árbol equilibradoc.Árbol desequilibrado d. /p>
(5) A. Un árbol binario con n nodos, almacenado en forma de punteros, con al menos n 1 punteros.
En un árbol B de orden B-m, el número de consecuentes de cada nodo no hoja es ≥
En un árbol B de orden C.M, hay k nodos consecutivos que debe contener k -1 valor clave.
D. Un árbol equilibrado debe estar rollizo.
nRespuestas de referencia (1) A (2) B (3) C (4) B (5) C.
2. Un árbol binario de búsqueda cuyos nodos A, B, C, D, E, F se almacenan en un área continua en orden y la dirección inicial es n (suponiendo que las direcciones están numeradas en bytes). orden), cada nodo ocupa 4 bytes: los primeros dos bytes almacenan el valor del nodo y los dos últimos bytes se colocan secuencialmente con el puntero izquierdo y el puntero derecho. Si el nodo raíz del árbol binario de búsqueda es E, entonces un posible recorrido de preorden es (1) y el recorrido de nivel correspondiente es (2). En las dos situaciones transversales anteriores, la dirección de almacenamiento del puntero izquierdo Lc del nodo C es (3) y el contenido de Lc es (4). El contenido del puntero derecho Ra del nodo A es (5).
(1)A . EFA CDB C . eab CFD .
(2)A . BDF
(3)a n 9 b . 16
(5)a . n 4 b . n 8 c . A(5)B A(3)B(4)A(5)B.
3. Para un conjunto determinado de palabras clave (12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18), cada algoritmo obtiene los resultados después de la primera clasificación. según el siguiente algoritmo: Clasificación Hill. La clasificación rápida (seleccionando el primer registro como elemento de referencia) obtiene (2), la base (base 10) obtiene (3), la clasificación por fusión bidireccional obtiene (4) y la clasificación en montón obtiene (5).
(1)A.2, 4, 6, 8, 10, 12, 16, 18, 20, 28, 30
C.12, 210, 20, 618, 416, 30, 8, 28
(2)A.10,6,18,8,4,2,12,20,16,30,28 B.6,2,10,4, 8, 12, 28, 30, 20, 16, 18
C.2, 4, 6, 8, 10, 12, 16, 18, 20, 28, 30
(3)A.10, 6, 18, 8, 4, 2, 12, 20, 16, 30, 28 b 12, 10, 20, 6, 18, 4, 16, 30, 8, 28
C.2, 4, 6, 8, 10, 12, 16, 18, 20, 28, 30
(4)A.2, 12, 16, 8, 28, 30 , 4, 6, 10, 18, 20
C.12, 216, 8, 28, 30, 4, 6, 10, 28, 18
(5)A. 30, 28, 20, 12, 18, 16, 4, 10, 2, 6, 8 B.20, 30, 28, 12, 18, 4, 16, 10, 2, 8, 6
20, 8, 30, 18
nRespuestas de referencia (1) C (2) B (3) D (4) B (5) C.
4. En todos los métodos de clasificación, el número de comparaciones de palabras clave no tiene nada que ver con el orden de clasificación inicial de los registros (1).
El método de sacar en orden los elementos de la secuencia desordenada, compararlos con los elementos de la secuencia ordenada (vacíos al principio) y colocarlos en la posición correcta de la secuencia ordenada se llama (2). Hay 1000 elementos desordenados. Espero seleccionar los 10 elementos más grandes lo más rápido posible. Es mejor elegir el método de clasificación (3).
(1) A. Clasificación por colinas b. Clasificación por burbujas c. Clasificación por inserción d. Clasificación por selección
(2) A. Clasificación por colinas b. Clasificación por selección
(3) A. Clasificación por burbujas b. Clasificación rápida c. Clasificación por base d.
5. Cuando la tabla lineal (25, 84, 21, 47, 15, 27, 68, 35, 20) se ordena según un determinado método de clasificación, el orden de los elementos cambia de la siguiente manera:
①25, 84, 21, 47, 15, 27, 68, 35, 20 ②20, 15, 21, 25, 47, 27, 68, 35, 84
③15, 20 , 21, 25, 35, 27, 47, 68, 84 ④15, 20, 21, 25, 27, 35, 47, 68, 84
El método de clasificación utilizado es (1). La clasificación inestable en (2) a continuación es (2).
Referencia de clasificación externa (3).
(1) A. Clasificación por selección b. Clasificación por colinas c. Clasificación por fusión d. Clasificación por inserción directa b. Combinar clasificación
(3) A. Utilice las instrucciones de la máquina para ordenar directamente los datos que se ordenarán en el disco duro.
b. Ordenar los datos que se ordenarán a través de otras máquinas de gran capacidad.
c.Transfiera los datos que se ordenarán en la memoria externa a la memoria interna a la vez y guárdelos en la memoria externa después de ordenarlos.
d. Los datos a ordenar en la memoria externa son mayores que el espacio permitido de la memoria y la clasificación se logra mediante múltiples intercambios internos y externos.
nRespuestas de referencia (1) D (2) C (3)D
6. En la clasificación interna, generalmente es necesario escanear los datos ordenados varias veces. Varios métodos de clasificación tienen diferentes procesos de implementación de clasificación y complejidad de tiempo. Cuando una secuencia entera dada (541, 132, 984, 746, 518, 181, 946, 314, 205, 827) se ordena de pequeña a grande,
Supongamos que la secuencia ordenada tiene n elementos, burbuja La complejidad temporal de la clasificación y la clasificación por selección simple es (3); la complejidad temporal de la clasificación rápida es (4);
(1)
A (181, 132, 314, 205, 541, 518, 946, 827, 746, 984) y (5465438)
B (132, 541, 746, 518, 181, 946, 314, 205, 827, 984) y (5465438)
C. 946, 984, 541, 827) y (65438)
D (541, 132, 984, 746, 827, 181, 946, 314, 205, 518) y (65438)
(2)A.(181,132,314,205,541,518,946,827,746,984)
B.(541,132,827,746,518,181, 946, 314, 205)
C.(205,132,314,181 ,518,746,946,984,541,827)
D .(541, 132, 984, 746, 827, 181, 946, 314, 205, 518)
(3)A . O(nlog2n)B . (N2)
(4)A . O(nlog2n)B . O(N2 log2n)C . B (2 )C (3)D (4)A
7. Determine el orden de las palabras clave de los nodos (F, B, J, G, E, A, I, D, C, H). , Según el orden alfabético del diccionario, utilizando diferentes métodos, el resultado final es el mismo. Pero los resultados intermedios son diferentes.
El resultado del primer escaneo de clasificación de shell (paso 5) debe ser (1).
La función de la primera burbuja en la clasificación de burbujas (un gran número se hunde) es (2).
El primer resultado del escaneo de la clasificación rápida es (3)
El primer final de la clasificación por combinación bidireccional es (4).
Si el árbol binario completo correspondiente se construye usando secuencias jerárquicas y el montón se construye usando el método de filtrado, el primer montón es (5).
(1)A.(B,F,G,J,A,D,I,E,H,C)
B.(B,F,G,J ,A,E,D,I,C,H)
C.(A,B,D,C,E,F,I,J,G,H)
D.(C,B,D,A,E,F,I,G,J,H)
(2)A.(A,B,D,C,F,E,I, J, H, G)
B.(A, B, D, C, E, F, I, H, G, J)
C.(B, F, G, E, A, I, D, C, H, J)
D.(B, F, G, J, A, E, D, I, C, H)
(3)A.(C,B,D,A,F,E,I,J,G,H)
B.(C,B,D,A,E,F ,I,G,J,H)
C.(B,A,D,E,F,G,I,J,H,C)
D.(B ,C,D,A,E,F,I,J,G,H)
(4)A.(B,F,G,J,A,E,D,I,C, H)
B.(B,A,D,E,F,G,I,J,H,C)
C.(A,B,D,C, E, F, I, J, G, H)
D.(A, B, D, C, F, E, J, I, H, G)
( 5)
nRespuestas de referencia (1) C (2) C (3) B (4) A (5) B.
8. Árbol binario (1).
En un árbol binario completo, si un nodo no tiene (2), entonces debe ser un nodo hoja. Cada árbol se puede transformar de forma única en su árbol binario correspondiente. En el árbol binario transformado del árbol, el subárbol izquierdo del nodo N es (3) correspondiente al nodo del árbol original, y el subárbol derecho de N es (4) correspondiente al nodo del árbol original. La longitud de búsqueda promedio de un árbol de clasificación binario es (5).
(1) A. es un árbol especial b. no es una forma especial de árbol.
c es el nombre colectivo de dos árboles. d es una estructura de árbol con solo dos nodos raíz.
(2) A. Subárbol izquierdo b. Subárbol derecho c. Subárbol izquierdo o ningún subárbol derecho d.
(3) ~ (4) A. Most El subárbol izquierdo b. . El subárbol más a la derecha c . El hermano derecho más cercano d . El hermano izquierdo más cercano
⑤A . >
nRespuestas de referencia (1) B (2) A (3) A (4) C (5) C.
9. La idea básica del almacenamiento de hash es determinar (2) en función de (1), y el conflicto (colisión) se refiere a (3). _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Cuanto mayor sea el problema, las dos formas principales de abordar los conflictos son (5).
(1) ~ (2) A. Dirección de almacenamiento b. Número de serie del elemento c. Número de elementos Valor clave
(3) A. Los números de serie de los dos. los elementos son iguales b. Los valores clave de los dos elementos son diferentes, pero el atributo nonce es el mismo.
C. Diferentes valores clave corresponden a la misma dirección de almacenamiento d.
(4) A. Atributos sin código b. Longitud promedio de recuperación c. Factor de carga d. Espacio de tabla hash
(5) A. Método de exploración lineal y método de función hash doble. b. Método de área de desbordamiento y método de área sin desbordamiento
C. Método de división y método de plegado d. Método de dirección abierta
nRespuesta de referencia (1) D (2) A. (3)C(4)C(5)D A(3)C(4)C(5)D.
10. Supongamos que los subíndices de fila de la matriz bidimensional F son de 1 a 5 y los subíndices de columna son de 0 a 8. Cada elemento de datos de F ocupa 4 bytes. En el caso del almacenamiento de filas, se sabe que la dirección del primer byte del elemento de datos F[2,2] es 1044, por lo que las direcciones del primer byte de F[3,4] y F[4,3] Son (1) y (2) respectivamente, mientras que el primer byte del primer elemento de datos de la matriz y el último byte de la matriz.
Para una matriz bidimensional general G, cuando (5), la dirección de G[I, J] almacenada en filas es la misma que la dirección de G[J, I] almacenada en columnas.
(1)a .1088b .1084c 1120d . 3)a .1004 b .1044 c .1187
④a . igual que el número de filas.
El límite superior de la columna de b.g es el mismo que el límite superior de la fila de g.
El límite superior de la columna de c.g es el mismo que el límite inferior de la fila de g.
Los límites superior e inferior de las columnas de d.g son los mismos que los límites superior e inferior de las filas de g.
nRespuestas de referencia (1)A (2)C (3)C (4)B (5)D
11. Una tabla almacenada en un orden determinado, con 90.000. elementos, se han ordenado en orden ascendente de palabras clave. Ahora supongamos que la probabilidad de buscar cada elemento es la misma y que las palabras clave para cada elemento son diferentes.
Cuando se utiliza el método de búsqueda secuencial, el número promedio de comparaciones es aproximadamente (1) y el número máximo de comparaciones es (2).
Ahora los 90.000 elementos se dividen en varios grupos según el orden de disposición, de modo que cada grupo tenga g elementos (el último grupo puede ser menor que g). Al realizar la búsqueda, comience desde el primer grupo, busque el grupo donde se encuentra el elemento a buscar comparando la palabra clave del último elemento de cada grupo y luego utilice el método de búsqueda secuencial para encontrar el elemento a buscar. En este método de búsqueda, G que minimiza el número promedio total de comparaciones es (3) y el número promedio de comparaciones en este momento es (4). Cuando el valor de g es mayor o igual a 90000, la velocidad de búsqueda de este método es cercana a (5).
(1)~(2)a. 25.000 B. 30.000 c. 45.000 D. 90.000
(3)~(4)a 100 b. 400
(5) A. Clasificación rápida b. Búsqueda de Fibonacci c. Dicotomía d. Búsqueda secuencial
n Respuesta de referencia (1) C (2 )D(3)C(4 )C(5)D D(3)C(4)C(5)D.
12. La lista de adyacencia del gráfico no dirigido conocido se muestra en la Figura 2-35:
El gráfico no dirigido correspondiente a esta lista de adyacencia es (1). El primer recorrido en profundidad de este gráfico a partir de f es (2). Un recorrido en amplitud a partir de f es (3). El árbol de expansión en profundidad que comienza desde f es (4). El árbol de expansión en anchura que comienza en f es (5).
(1)
(2)a .F . I . p>
(3)a . G . I . buen ejemplo
(4)
(5)
nRespuesta de referencia (1)C(2)B(3)B(4 )A(5) B(3)B(4)A(5)B.
13. La Figura 2-36 es la lista de adyacencia del gráfico dirigido ponderado G. La secuencia de nodos obtenida al atravesar el gráfico G desde el nodo V1 es (1); G es (2); una secuencia topológica de G es (3); el camino más corto desde el nodo V1 al nodo V8 es (4);
(1)A V1, V2, V3, V4, V5, V6, V7, V8 B. V1, V2, V3, V8, V4, V5, V6, V7
C.V1, V2, V3, V8, V4, V5, V7, V6 D. V1, V2, V3, V8, V5, V7, V4, V6
(2)A. , V3, V4, V5, V6, V7, V8 B. V1, V2, V4, V6, V5, V3, V7, V8
C.V1, V2, V4, V6, V3, V5, V7, V8
(3)A V1, V2, V3, V4, V5, V6, V7, V8 B. V1, V2, V4, V6, V5, V3, V7, V8
C.V1, V2, V4, V6, V3, V5, V7, V8
(4)~(5)A.( V1, V2, V4, V5, V3, V8) B. (V1, V6, V5, V3, V8)
C (V1, V6, V7, V8) D. (V1, V2, V5, V7, V8)
nRespuestas de referencia (1) D (2) C (3) B (4) D (5) B.
Cosas como esta, esto es solo una parte, todas han sido enviadas a tu buzón.