Examen final "Estructura de datos" (A)
1 Preguntas de opción múltiple (cada pregunta vale 2 puntos, ***24 puntos)
1. . Los objetos reconocidos, almacenados y procesados por las computadoras se denominan colectivamente (A)
Datos B. Elemento de datos
Estructura de datos D. Tipo de datos
.2. Tanto las pilas como las colas son (A)
A. Estructura lineal que limita los lugares de acceso B. Estructura lineal de almacenamiento secuencial
C. Estructura lineal de la cadena de almacenamiento D. Estructura no lineal que limita los lugares de acceso
3. En comparación con la pila secuencial, las ventajas obvias de la pila en cadena son (D)
A. La operación de inserción es más conveniente B. La operación de eliminación es más conveniente.
C. no ocurrirá Caso D. No ocurrirá desbordamiento
4. Las cadenas que utilizan dos estructuras de almacenamiento diferentes pueden denominarse (B) respectivamente
A. Cadena principal y subcadena B. Cadena secuencial y cadena de cadena
C. . Cadenas variables y cadenas constantes
5. La dirección de almacenamiento del primer elemento de un vector es 100 y la longitud de cada elemento es 2. Entonces la dirección del quinto elemento es: B
A 110 B .108
<. p> C. 100 D. 1206． La cadena es una tabla lineal especial, su particularidad se refleja en: B
A. Puede almacenar B en secuencia. El elemento de datos es un carácter.
C. Los elementos de datos pueden tener varios caracteres
7. Supongamos que solo hay nodos con grado 0 y grado 2 en un árbol binario con altura h, entonces el número de nodos contenidos en dicho árbol binario es al menos: C
A. 1
C. 2h 1 D. h 1
Red de desarrollo de software www.mscto.com
8. Las estrategias transversales básicas de los árboles se pueden dividir en recorrido de raíz primero y recorrido posterior a la raíz; las estrategias transversales básicas de árboles binarios se pueden dividir en recorrido de preorden, recorrido de orden y recorrido de postorden. Aquí, llamamos al árbol binario convertido del árbol el árbol binario correspondiente a este árbol.
¿Cuál de las siguientes conclusiones es correcta? A
A. La secuencia transversal previa a la raíz de un árbol es la misma que la secuencia transversal previa al orden de su árbol binario correspondiente
B. un árbol es la misma que la secuencia transversal posterior al orden de su árbol binario correspondiente. Igual
C. La secuencia transversal de la raíz del árbol es la misma que la secuencia transversal en orden del árbol binario correspondiente.
D. Ninguna de las anteriores es correcta
9. ¿Cuál es el número máximo de aristas que tiene un grafo no dirigido con n vértices? C
A.n B .n(n-1)
C n(n-1)/2 D. 2n
10. En una gráfica, ¿cuántas veces es igual la suma de los grados de todos los vértices al número de todas las aristas C
A. D.4
p>
11． Al insertar un nuevo nodo en un árbol ordenado binario, si no hay ningún nodo en el árbol con la misma clave que el nodo que se va a insertar y la clave del nuevo nodo es menor que la clave del nodo raíz, entonces el nuevo el nodo El punto se convertirá en (A)
A. El nodo hoja del subárbol izquierdo B. Nodo de rama del subárbol izquierdo
C. El nodo hoja del subárbol derecho D. Nodo de rama del subárbol derecho
Red de desarrollo de software www.mscto.com
12. Para la función hash H(key)=key13, las palabras clave llamadas sinónimos son (D)
A.35 y 41 B.23 y 39
C.15 y 44 D. 25 y 51
2. Se sabe que los resultados del recorrido de preorden de un determinado árbol binario son A, B, D, E, G, C, F, H, I, J, entre otros. cual recorrido en orden Los resultados son D, B, G, E, A, H, F, I, J, C. Dibuje la estructura específica de la bifurcación. (Tenga cuidado de escribir los pasos específicos) (10 puntos)
Para conocer el principio, consulte la página 128 del libro de texto.
3 Hay una imagen de la siguiente manera. la profundidad primero y el ancho primero a partir del vértice c0. El resultado del recorrido. (10 puntos)
Profundidad primero; C0-C1-C3-C4-C5-C2
Anchura primero: C0-C1-C2-C3-C4-C5
4. Como se muestra en la figura siguiente, el árbol de expansión mínimo se obtiene según el algoritmo de Kruskal. Se requieren pasos completos. (10 puntos)
Consulte la página 250 del libro de texto para conocer el principio
5. Dada la tabla lineal (12, 23, 45, 66, 76, 88, 93, 103, 166), intente escribir el proceso de realizar una búsqueda binaria en los valores clave 12, 93 y 166. Y escribe el algoritmo de búsqueda binaria. (20 puntos)
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
Proceso:
medio=(0 8)/2=4
alto=3, bajo=0 medio=1
alto=0, bajo=0 medio=0 (encontrar 12)
alto=8, bajo=5, medio=6 (93 encontrados)
alto=8, bajo=7, medio=7
alto=8 low=8 mid=8
Algoritmo: consulte la página 84 del libro de texto
6. Sepa que la estructura de nodos de una lista enlazada individualmente es
Datos a continuación.
El siguiente algoritmo realiza una clasificación de selección simple en la lista enlazada individualmente L con el nodo principal, de modo que los elementos en L estén ordenados de valor pequeño a grande.
Complete el contenido apropiado en los espacios en blanco para que sea un algoritmo completo.
(Se puede utilizar texto para describir la idea básica y el proceso de ejecución del algoritmo, 10 puntos)
void SelectSort(LinkedList L)
{
LinkedList p , q, min;
Tipo de datos rcd;
p= (1)
while(p!=NULL) {
min=p ;
q=p-gt; siguiente;
while(q!=NULL){
si( (2) )min=q ;
p>
q=q-gt; siguiente
}
si( (3) ){
rcd=p-gt;
p-gt; datos=min-gt;
min-gt;
( 4) ;
}
}
Esta pregunta no se puede responder. oye oye. . . .
7. ¿Qué propiedades básicas debe tener un algoritmo completo? Explique brevemente el significado de cada propiedad respectivamente. (5 puntos)
Entrada:
Cuatro propiedades básicas: 1. Entrada: Hay cero o más cantidades proporcionadas externamente como entradas al algoritmo
2: Salida: El algoritmo produce al menos una cantidad como salida
3.: Determinista: Cada instrucción que compone el algoritmo es clara e inequívoca.
4.: Finitud: El número de ejecuciones de cada instrucción del algoritmo es limitado, y el tiempo para ejecutar cada instrucción también lo es
8. ¿Qué es el "falso desbordamiento"? de la cola? ¿Cómo solucionarlo? (5 puntos)
El fenómeno del falso desbordamiento de la cola es que en la cola secuencial implementada por la matriz de índice, el puntero de cola de la cola ha alcanzado el límite superior de la tabla inferior de la matriz y Se produce un desbordamiento, pero todavía hay algo de espacio inactivo antes del puntero principal de la cola. Una solución es utilizar tecnología de cola circular para conectar el final del espacio de la matriz.
9. Explicar y comparar las distintas estructuras físicas de los archivos. (6 puntos)