1. Preguntas de verdadero o falso
(
) 1. Una tabla lineal adopta una estructura de almacenamiento secuencial, la longitud del elemento es 4 y la primera dirección. es 100, entonces el subíndice La dirección de almacenamiento del elemento 12 (13) es 148.
Correcto. La dirección del elemento 0 es 100, luego la dirección del elemento i-ésimo es 100 4*i, y al sustituir 12 se obtiene 148.
(
) 2. El acceso aleatorio no es posible en ningún tipo de lista enlazada lineal.
Error. Por ejemplo, siempre que conozca la primera dirección de la tabla de secuencia y el número de unidades de almacenamiento ocupadas por cada elemento de datos, puede encontrar la dirección de almacenamiento del i-ésimo elemento de datos. Esta también es la característica de la tabla de secuencia. teniendo acceso aleatorio según el número de serie del elemento de datos.
(
) 3. Una pila secuencial es una pila que especifica el orden en el que los elementos se insertan en la pila.
Error. Según la estructura de almacenamiento, la pila se divide en pila secuencial y pila en cadena. La estructura de almacenamiento secuencial de la pila se denomina pila secuencial. Es una tabla secuencial con operaciones limitadas, pero no especifica el orden de los elementos. son empujados hacia la pila.
(
) 4. Cada elemento de la lista circular tiene un sucesor.
Correcto. Tenga en cuenta que puede haber un error administrativo aquí, debería escribirse como "lista circular enlazada" en lugar de "lista circular".
(
) 5. Elimine un nodo en un árbol binario y luego insértelo nuevamente, y definitivamente obtendrá el árbol de clasificación binario original.
Error.
2. Completa los espacios en blanco.
6. La complejidad temporal del siguiente programa es___________.
para
(int
i=1;
ilt;=m;
i )
para
(int
j=1;
jlt;=n;
j
)
S =i
Regla 1: bucle for: El tiempo de ejecución de un bucle for es como máximo el tiempo de ejecución de las declaraciones (incluidas las pruebas) dentro del for loop multiplicado por El número de iteraciones.
Regla 2: Bucles anidados: Analiza estos bucles de adentro hacia afuera. El tiempo total de ejecución de una declaración dentro de un conjunto de bucles anidados es el producto del tiempo de ejecución de la declaración multiplicado por el tamaño de todos los bucles del conjunto.
Para el bucle for anidado aquí, de acuerdo con las reglas anteriores, la complejidad del tiempo es O (m*n).
7. Insertar un elemento en la posición i-ésima (1≤i≤n 1) de una lista de secuencia de longitud n. El número de movimientos del elemento es ____________.
Del elemento i-ésimo (original) al elemento n-ésimo, cada elemento se desplaza hacia atrás un bit, lo que toma n 1-i veces.
8. Inserte un nuevo nodo en una lista enlazada individualmente ordenada con n nodos y mantenga la lista enlazada individualmente insertada todavía en orden, entonces la complejidad temporal de esta operación es del orden de ______.
Encuentre la posición del nodo, O (n); inserte la operación en una lista enlazada individualmente, O (n); la complejidad del tiempo total es O (n n) = O (n).
9. Si s[1]~s[n] se utiliza como el mismo espacio de almacenamiento de dos pilas secuenciales, y las partes superiores de las pilas izquierda y derecha son t1 y t2 respectivamente, entonces determine un cierto La condición para saber si se puede insertar un nuevo elemento en la pila es _______________.
Cuando se utilizan dos pilas en el programa al mismo tiempo, la parte inferior de las dos pilas se puede establecer en ambos extremos del espacio vectorial, de modo que las dos pilas puedan extenderse hacia el medio. Cuando hay más elementos en una pila que la mitad del espacio vectorial, siempre que no haya muchos elementos en la otra pila, el primero puede ocupar parte del espacio de almacenamiento del segundo.
La condición aquí para determinar si se puede insertar un nuevo elemento en una pila es amp;t1!=amp;t2
10. el primero y el segundo, el número de nodos de los tres árboles es n1, n2 y n3 respectivamente. Después de convertir el bosque en un árbol binario, hay ____________ nodos en el subárbol izquierdo del nodo raíz.
El método específico para convertir un bosque en un árbol binario es: ①
Convertir cada árbol del bosque en un árbol binario ②
Porque el convertido; árbol binario Los subárboles derechos de los nodos raíz están todos vacíos, por lo que los nodos raíz de cada árbol binario pueden considerarse hermanos y conectarse entre sí de izquierda a derecha para formar un árbol binario.
Personalmente, creo que puedes completar 3 respuestas aquí, n1-1 o n2-1 o n3-1.
11. En la matriz de adyacencia de un gráfico dirigido ponderado, el número de elementos distintos de cero en la i-ésima fila es igual a _______________.
Cuando el nodo Vi es adyacente a un nodo Vj, entonces A(i, j) toma un valor distinto de cero.
12. Entre varios métodos de búsqueda, el método de búsqueda cuya longitud de búsqueda promedio no tiene nada que ver con el número de nodos n es _____________.
Búsqueda hash.