Preguntas del examen de estructura de datos para el Examen Nacional de Autoestudio de Educación Superior en junio de 2013.

De las cuatro opciones enumeradas en cada subpregunta, solo una cumple con los requisitos de la pregunta. Complete su código entre paréntesis después de la pregunta. No importa si elige más de una.

En la estructura de datos, la estructura lógica de los datos se puede dividir en ()

a Estructura interna y estructura externa b Estructura lineal y estructura no lineal

c Estructura cerrada y estructura no compacta D Estructura dinámica y estructura estática

En una lista lineal con una lista enlazada individualmente como estructura de almacenamiento, la relación lógica entre elementos de datos está representada por ()

a data La dirección adyacente del elemento representa la representación del número de secuencia del elemento de datos b en la tabla.

El puntero al elemento siguiente representa la representación del valor del elemento de datos D.

Supongamos que P apunta a un nodo S en la lista enlazada individualmente, apuntando al nodo a insertar, entonces la función del siguiente segmento del programa es ()

s gtnext = p gtnext; p gtnext = s;

t = p gt data; p gtdata = s gt data = t

Intercambia los campos de datos del nodo A *py; nodo s.

Insertar un elemento antes del elemento del nodo señalado por p.

Insertar un elemento después del elemento del nodo señalado por p.

d inserta el nodo *s antes del nodo *p.

Las pilas y las colas son ambas ()

Estructura lineal de ubicación de acceso restringido, estructura lineal de almacenamiento secuencial

Estructura lineal de almacenamiento en cadena C y D no restringido -estructura lineal de ubicación de acceso

Si la matriz s[n] es el * * * espacio de almacenamiento de dos pilas S y S, y solo cuando s[n] está lleno, cada pila no se puede insertar la pila, entonces la mejor solución para asignar espacio para estas dos pilas es que los valores iniciales de los punteros superiores de S y S sean () respectivamente.

a y n B y n/

c y nd y n

Después de ejecutar el siguiente segmento del programa, el valor de la cadena X es ()

s =『abcdefgh』; t =『xyzw』;

substr(X S strlen(T));

substr (Y S columna central(T));

strcat(X Y);

a[cdefgh]B[cdxyzw]

c[cdefxy]D[cdefef]

Multidimensional Las matrices tienen dos métodos de almacenamiento, prioridad de fila y prioridad de columna, porque ()

Los elementos de la matriz A están en una relación fila-columna y los elementos de la matriz B deben organizarse en orden de izquierda a derecha.

Existe una relación secuencial entre los elementos de la matriz C. La matriz d es una estructura multidimensional y la memoria es una estructura unidimensional.

De la tabla generalizada LS =( (p q) r s), la operación para descomponer el átomo q es ().

a cola (cabeza (LS)) B cabeza (cola (cabeza (LS)))

c cabeza (cola (LS)) D cola (cola (cabeza (LS) ) )

En un árbol binario estricto con n nodos de hoja, el número total de nodos es ()

Un sustantivo y un sustantivo

China Daily

Una arista de un gráfico dirigido se llama ()

A v i es adyacente a v j, B v j es adyacente a v i

C v i y v j son adyacentes, y D v i y v j no son adyacentes.

En un gráfico conectado ponderado G, el borde con el peso más pequeño debe incluirse en () de G.

En el árbol de expansión mínima. , b es la generación de profundidad primero. Árbol

c árbol de expansión de ancho primero y D bosque de expansión de profundidad primero

Al insertar un nuevo nodo en un árbol ordenado binario, si lo hay. No hay ningún nodo en el árbol con la misma clave que el nodo a insertar, y la clave del nuevo nodo es menor que la clave del nodo raíz, el nuevo nodo se convertirá en ().

Nodo hoja del subárbol izquierdo Nodo rama del subárbol izquierdo

C Nodo hoja del subárbol derecho D Nodo rama del subárbol derecho

Clasificación de colinas The la secuencia de incremento debe ser ()

a aumenta b aleatoriamente

c disminuye y d no disminuye.

Si durante el proceso de clasificación, cada vez que un registro a ordenar se agrega a la posición apropiada en la subtabla previamente ordenada según el tamaño de la clave, se llama al método de clasificación ().

Ordenación por inserción b Ordenación por fusión

c Ordenación por burbuja d Ordenación en montón

El archivo que establece el área de desbordamiento es ()

a Índice Archivo no secuencial B Archivo ISAM

Archivo VSAM d archivo de secuencia

Rellene los espacios en blanco (esta gran pregunta* *Pequeña pregunta* *Puntos extra por cada pequeña pregunta)

Complete la respuesta correcta en el espacio en blanco de cada pregunta corta. No importa si la completó incorrectamente o no.

La complejidad temporal del siguiente segmento del programa es_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

product=;

for( I = n; i gt; i)

for(j = I; j ltn; j)

Producto* = j;

17. El puntero P apunta a un nodo en la lista enlazada individualmente, entonces la función P->next = p-gt;next-gt;next es _ _ _ _ _ _ _ _ _ _ _. Wainwit.

65438

19. Si el puntero en el nodo de la cadena de cadena ocupa 4 bytes y cada carácter ocupa 1 byte, entonces la densidad de almacenamiento de la cadena de cadena con un tamaño de nodo de 2 sí_ _ _ _ _ _ _ _ _ _ _ _ _ _.

20. La tabla generalizada que se muestra a la derecha es _ _ _ _ _ _ _ _ _ _ _ _ _ _.

21. Si un árbol tridente completo contiene 121 nodos, entonces

La profundidad de este árbol es _ _ _ _ _ _ _ _ _ _ _.

22. Si el grafo dirigido está representado por una matriz de adyacencia, la matriz de adyacencia

El número de elementos distintos de cero en la fila I es el _ _ _ _ _ _ _ _ del vértice v. _ _ _ _ _.

23. Si solo desea encontrar los 8 elementos más pequeños entre los 4800 elementos mediante 8 clasificaciones y desea comparar la menor cantidad de palabras clave posible durante el proceso de clasificación, entonces debe elegir _ _ _ _ _ _ _ _ _ _ _ _ _ _ _Ordenar por.

24. Para encontrar una palabra clave en un árbol B de tercer orden (árbol 2-3) que contiene 20 palabras clave, necesita acceder a la memoria externa como máximo _ _ _ _ _ _ _ veces.

25. Las dos operaciones principales sobre archivos son _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _.

3. Resuelve el problema (este gran problema consta de *** 4 preguntas pequeñas, cada pregunta pequeña vale 5 puntos, *** 20 puntos)

26. Si la pila La secuencia de S1 es 1^2^3^4 (cada número tiene 13 elementos), es imposible obtener una secuencia de pila de 3142. Pero se puede lograr agregando la pila S2. Por ejemplo, como lo muestran las flechas en la figura siguiente, al pasar secuencialmente las pilas S1 y S2, puede obtener la secuencia 3 1 4 2.

Si se usan H1 y H2 para representar las operaciones de inserción de S1 y S2 respectivamente, y P1 y P2 se usan para representar las operaciones de extracción de las dos pilas, los pasos de operación para obtener 3 1 4 2 son de la siguiente manera

H1, H1, H1, P1, H2, P2, P1, H2, P1, H2, P2, H1, P1, H2, P2, P2

Siga las ejemplo anterior y escriba Dos pilas, siga los pasos para pasar de 1^2^3^4 a 4^1^3^2.

27. Los árboles conocidos se muestran a la derecha.

(1) Escribe la secuencia del árbol;

(2) Dibuja el árbol binario transformado a partir de este árbol.

28. Construya una tabla hash con una longitud de 7 para la palabra clave (17, 33, 31, 40, 48), suponiendo que la función hash es h (clave) = clave7 y abra el método de direccionamiento para resolver La secuencia de detección de conflictos es

hi =(h(key) I(key 5 1)) 7 0≤I≤6

(1) Dibuje la tabla hash construida <; /p>

(2) Encuentre la duración promedio de la búsqueda cuando la búsqueda tiene éxito con la misma probabilidad.

29. Se sabe que los elementos en R [1...8] son ​​(12, 5, 9, 20, 6, 31, 24, 27) en orden. Lo que está escrito es que la función Merge(R, low, mid, high se llama 5 veces en el proceso de clasificación de fusión bidireccional de arriba hacia abajo de R según el algoritmo MergeSortDC.

void MergeSortDC (int R[], int bajo, int medio, int alto)

{

int medio

if (bajo lt alto)p = " " gt lt/ alto)>

{

medio = (bajo alto)/2

MergeSortDC (R, bajo, medio

); MergeSortDC (R, medio 1, alto)

Fusionar (R, bajo, medio, alto

}

} // MergeSortDC

( 1) Valor del parámetro para la primera llamada;

(2) Valor del parámetro para la segunda llamada;

(3) Valor del parámetro para la tercera llamada;

(4) Valores de parámetros para la cuarta convocatoria;

(5) Valores de parámetros para la quinta convocatoria;

4 Preguntas de lectura de algoritmos (este. pregunta importante *** 4 preguntas, cada pregunta tiene 5 puntos, *** 20 puntos)

30. , y tiene dos incrementos La tabla de secuencia (no hay elementos de datos con el mismo valor en la tabla) realiza las siguientes operaciones: insertar todos los nodos que existen en la tabla Lb pero no en la tabla La en La, donde La y. Lb son los punteros principales de las dos listas enlazadas respectivamente. Complete los espacios en blanco con el contenido apropiado para que sea un algoritmo completo.

Unión no válida (lista enlazada La, lista enlazada Lb)

{

//La función de este algoritmo es combinar los elementos que existen en la Lb tabla pero no existen en la tabla La. Todos los nodos se insertan en la tabla La.

LinkList pre = La, q;

Lista enlazada pa = La-gt siguiente

Lista enlazada pb = Lb -gt;

next;

gratis(libra);

mientras (pa amp amppd)

{

si (pa- gt; datos datos )

{ pre = papa = pa- gt; next;}

else if(pa- gt; data gtpb -> data)

{

(1);

pre = pb

Pb = p B- gt;

(2);

}

Otros

{

q = pbPb = p B- gt; siguiente;

}

}

SI (cliente potencial)

(3);

}

(1)

(2)

(3)