2013 1 Preguntas sobre la estructura de datos del examen de autoestudio nacional de educación superior
La complejidad temporal del siguiente segmento del programa es ()
for(I =; I ltn; i) p = " " gt/n; i) gt;
for(j = 1; j ltm; j )p = " " gt/m; j )>
a[I][j]= 0;
A .(m n 1) C.O(m n) D.O(m*n)
2. En una lista enlazada individualmente, el puntero P apunta al nodo cuyo elemento es X. La declaración para implementar "eliminar" el sucesor de X" es ( ).
p = p- gt; siguiente; b .p->siguiente = p-gt; = p- gt; next - gt; next;
3. En una única lista enlazada circular con un puntero principal y una longitud de tabla mayor que 1, el puntero P apunta a un nodo en la lista enlazada. Si p->next->next=
cabeza, entonces ()
A.p apunta al primer nodo y B.p apunta al nodo de cola.
El sucesor directo de C.*p es el nodo principal D. El sucesor directo de *P es el nodo final.
4. La condición para juzgar "la cola de la cadena del primer nodo está vacía" es ()
A.Q.front==NULL
C.Q.front==Q. trasero D.Q. delantero! =Q.rear
5. Hay dos cadenas T y P. La operación de cadena para encontrar la primera aparición de P en T se llama ().
A.Join B. Buscar subcadena c. Posicionamiento de caracteres d. Posicionamiento de subcadena
6. Tabla generalizada A=(a, (b), (), (c, La longitud de d, e)) es ().
a4 b . 5 c . 6d 7
7.
a3 b . 4 c . 5d . 6
8. Se sabe que la secuencia de preorden del árbol binario es ABDECF, la secuencia del medio es DBEAFC y la secuencia de postorden es. ().
A.DEBCFA D.DEBFCA
9 El grado de un vértice en un gráfico no dirigido se refiere al () del gráfico
A. vértice b El número de caminos. El número de vértices adyacentes al vértice
C. El número de bucles que pasan por el vértice d. El número de vértices conectados al vértice
Dado el siguiente gráfico, comenzando. desde el vértice A La posible secuencia obtenida mediante el recorrido en amplitud es ().
Inglaterra, Francia, Alemania
British Airways
Royal Airways
D.a c d b f e
11. siguiente Entre los métodos de clasificación, el rendimiento de tiempo promedio es O (nlogn) y el mejor rendimiento de espacio es ().
A. Clasificación rápida b. Clasificación en montón c. Clasificación por fusión d. , 23, 40, 16, 35}, donde cada dos palabras clave adyacentes son subsecuencias ordenadas. Combine los resultados de estas subsecuencias. WingwIT.CoM es ().
A.{25, 36, 48, 72, 23, 40, 79, 82, 16, 35}
B.{25, 36, 48, 72, 16, 23, 40, 79, 82, 35}
C.{25, 36, 48, 72, 16, 23, 35, 40, 79, 82}
D.{ 16, 23, 25, 35, 36, 40, 48, 72, 79, 82}
13. Supongamos que la tabla lineal almacenada secuencialmente tiene 123 elementos y está dividida en tres bloques de acuerdo con los requisitos de bloquear la búsqueda. Si la tabla de índice utiliza una búsqueda secuencial para determinar bloques y realiza una búsqueda secuencial en los bloques determinados, entonces, cuando las probabilidades de búsqueda son iguales, la longitud promedio de búsqueda cuando la búsqueda de bloque es exitosa es ().
21
14. Las características de indexación de archivos no secuenciales son ()
A. Hay un problema con el archivo principal y la tabla de índice. b. El archivo principal está en orden y la tabla de índice está desordenada.
C. El archivo principal está en orden y la tabla de índice está en orden. d. El archivo principal está desordenado y la tabla de índice está desordenada.
15. Las principales ventajas de los archivos invertidos son ()
A. Operaciones fáciles de insertar y eliminar b.
c. Conveniente para consultas de varias palabras clave D. Ahorre espacio de almacenamiento.
2. Completa los espacios en blanco (esta gran pregunta tiene 10 subpreguntas, cada subpregunta vale 2 puntos. Si hay dos espacios, cada espacio tiene 1 punto, un total de 20 puntos)
16. La característica de los tipos de datos abstractos es encapsular _ _ _ _ _ _ _ _ y _ _ _ _ _ _ _ de modo que la información real quede oculta.
17. Cuando se elimina un elemento de una lista de secuencia, todos los elementos después del elemento eliminado en la tabla necesitan una posición _ _ _ _ _ _ _ _ _.
18. En la cola, el final que permite operaciones de inserción se llama _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _. _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
19. top1 y top son punteros a los elementos superiores de las dos pilas respectivamente, por lo que la condición de juicio para "pila llena" es _ _ _ _ _ _ _ _ _ _.
20. Supongamos que S1 = "bueno", S2 = "", S3 = "libro", luego S1, S2 y S3 están conectados en secuencia y el resultado es _ _ _ _ _ _ _ _ _.
21. Supongamos que la matriz tridimensional A[10][9][8] se almacena en orden de prioridad de fila. Si cada elemento ocupa 3 unidades de almacenamiento y la primera dirección es 100, entonces el elemento. A[9] La dirección de almacenamiento de [8][7] es _ _ _ _ _ _ _ _.
22. Se sabe que en un árbol con n nodos, solo hay nodos de rama con grado k y nodos de hoja con grado 0, por lo que el número de nodos de hoja contenidos en el árbol es _ _ _ _ _ _ _ _ _.
23. El gráfico que puede completar con éxito la clasificación topológica debe ser _ _ _ _ _ _ _ _ _ _.
24. Si el orden de las claves antes de la clasificación es cercano al orden directo o inverso, entonces es más apropiado elegir entre clasificación en montón y clasificación rápida _ _ _ _ _ _ _ _ _ _ _.
25. Suponga que la longitud de la tabla hash es my la función hash es H (clave). Si se utiliza el método de sonda lineal para resolver conflictos, la secuencia de direcciones de la sonda se expresa en forma de. _ _ _ _ _ _ _ _ _ _.
3. Responda la pregunta (esta gran pregunta tiene 4 preguntas pequeñas, cada pregunta tiene 5 puntos, un total de 20 puntos)
26. mensajes es {a, b, c, d, e, f}, la frecuencia del primer carácter del mensaje es 34, 5, 12, 23, 8, 18. Intente diseñar la codificación Huffman para estos seis caracteres.
Primero dibuje el árbol de Huffman que construyó (lo que requiere que el peso del nodo secundario izquierdo en el árbol sea menor que el peso del nodo secundario derecho) y luego escriba el código correspondiente a cada carácter.
27. Se sabe que un gráfico es como se muestra en la siguiente figura. Sus vértices se almacenan en la tabla de vértices de la lista de adyacencia en el orden de A, B, C, D, E, f. Dibuje la adyacencia de esta tabla de gráficos, de modo que la secuencia de vértices obtenida mediante el recorrido en profundidad según esta lista de adyacencia sea acbefd, y la secuencia de vértices obtenida mediante el recorrido en anchura sea acbdfe.
28. Las tablas ternarias de dos matrices dispersas de 4×5 conocidas son las siguientes:
0 1 4 16 0 1 1 32
1 2 2 18. 1 2 2 - 22
2 3 4 - 25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
p>Por favor dibuje la tabla ternaria de la suma de estas dos matrices dispersas.
29. A partir del árbol vacío, inserte las palabras clave 40, 8, 90, 15, 62, 95, 12, 23, 56, 32 para construir un árbol de clasificación binario.
(1) Dibujar un árbol binario.
(2) Después de eliminar el nodo con un valor de elemento de 90 en el árbol, dibuje un árbol de clasificación binario.
4. Pregunta de lectura del algoritmo (esta gran pregunta tiene 4 preguntas pequeñas, cada pregunta tiene 5 puntos, un total de 20 puntos)
30. Utilizando la misma implementación del espacio vectorial circular, la definición de tipo de la cola 2 es la siguiente:
estructura typedef {
tipo de datos datos[MaxSize];
int front[2 ], length[2];
} Queue2
Para i=0 o 1, front[i] y length[i] son el puntero principal y la longitud del Hago cola respectivamente. Complete el contenido apropiado en el espacio en blanco para implementar la operación de puesta en cola de la I-ésima cola circular.
int EnQueue(Queue2*Q, int i, DataType x)
{//Si la cola I-ésima no se satisface, el elemento X ingresa a la cola y devuelve 1; de lo contrario, devuelve 0.
Si (i lt0 | | i gt1) devuelve 0
Si ((1))
Devuelve 0
q; ->;datos[(2)]= x;
q->;longitud[(3)];
Retorno 1;
}
(1)
(2)
(3)
31. La estructura de almacenamiento de la lista de pistas del árbol binario es la siguiente. como se muestra en la Figura (b), donde P es el puntero al nodo raíz y la Figura (a) es la estructura del nodo. Lea el siguiente algoritmo y responda las preguntas:
(1) Escriba el resultado de ejecutar la llamada a la función f(p);
(2) Describa brevemente la función de la función f.
void f(árbol binario t) {
mientras(t)
{
printf(t- gt; datos);
if(t->;lchild)
t = t- gt;lchild
Otro
t = t- gt; rchild
}
}
(1)
(2)
32. (La función de G, I) es utilizar una estrategia de búsqueda en profundidad para un gráfico dirigido G con una lista de adyacencia como estructura de almacenamiento para encontrar un bucle simple a través del vértice vi. La matriz Cycle_path se utiliza para guardar el ciclo formado durante el proceso de búsqueda. Cycle_path [k] = j (j≥0) significa que el siguiente vértice del v k en el ciclo es v j. Complete el contenido apropiado en el espacio en blanco. espacio para convertirlo en un algoritmo completo.
El primer borde del vértice
La estructura de nodos de la tabla de vértices de la lista de adyacencia conocida es:
El siguiente es el adjvex
edge table La estructura del nodo EdgeNode es:
int Cycle _ path[MaxNum]
int FindCycle(ALGraph*G, int i)
int j;
for(j = 0;j n;j)cycle _ path[j]=-1;
Devolver DFSPath(G, I , I);
}
int DFSPath(álgebra *G, int j, int i)
{
nodo de borde * p;
int ciclo = 0;
for(p = G- gt; adjlist[j]. firstedge Procter & Gamble. amp! ciclo; p = p- gt; siguiente )
{
cycle_path[j]= p- gt; adjvex
if ((1)) ciclo = 1 // Encuentra el circuito.
Otros
if (ruta del bucle [p- gt; adjvex]==-1) loop = (2); p>Regresión (3)
}
(1)
(2)
(3)
33. Lea el algoritmo de función a continuación y responda las preguntas.
(1) Suponga que la matriz de enteros A [1...8] es (3, 8, 9, 1, 7, 4, 2, 6) en secuencia. Cuando la función de ejecución llama a algo (A, 8), ¿cuántas veces se ejecutará el bucle while externo? ¿Cuál es el valor de retorno de la función?
(2) Describe brevemente la función de algo(L, n).
int algo(int L[], intn)
{
int i=0, j, s=1, t = n;
Y (I!=(n 1)/2)
{
int x = L[s];
I = s; j = t;
mientras(iltj)p = " " gt;