Prueba de estructura de datos (Beijing en el primer semestre de 1998)
1 Preguntas de opción única (elija una respuesta correcta entre las cuatro respuestas alternativas para cada pregunta y complete. el número después de la raíz de la pregunta, cada pregunta vale 2 puntos, ***10 puntos)
1. La secuencia de entrada de una pila es 1, 2, 3, 4, ¿cuál es la siguiente? ¿No puede ser la secuencia de salida de esta pila? ( ) A. 1, 3, 2, 4 B. 2, 3, 4, 1 C. 4, 3, 1, 2 D. 3, 4, 2, 1
2. La siguiente clasificación método ¿En qué método el número de comparaciones no tiene nada que ver con el estado de disposición inicial de los registros? ( ) A. Ordenación por inserción directa B. Ordenación por burbuja C. Ordenación rápida D. Ordenación por selección directa
3. Realice una ordenación por combinación bidireccional en archivos con n registros El costo de tiempo total es A. O. (nlog2n) B. O(n2) C. O(log2n) D. O(n)
4. Si un árbol binario tiene 10 nodos con grado 2, entonces el grado del árbol binario es The el número de nodos de 0 es ( ) A. 9 B. 11 C. 12 D. Inseguro
5. Entre las siguientes descripciones sobre el árbol B y el árbol B, la incorrecta es A. B- árbol Tanto el árbol B como el árbol B son poliárboles equilibrados B. El árbol B y el árbol B son estructuras de índice que se pueden utilizar para archivos C. Tanto el árbol B como el árbol B pueden admitir eficazmente la recuperación secuencial D. Ambos B -tree y B-tree pueden admitir eficazmente la búsqueda aleatoria
2. Preguntas para completar los espacios en blanco (2 puntos por cada espacio en blanco, ***20 puntos)
1. Desde la perspectiva de la estructura lógica, las tablas lineales son típicas y los árboles son típicos.
2. Suponga que la dirección de almacenamiento de la matriz bidimensional A es , almacenada en el orden de la primera columna, y la dirección de almacenamiento del elemento A es .
3. Si todos los nodos de un árbol binario completo con n nodos están numerados del 1 al n en orden jerárquico, entonces cuando i es y menor que n, el hermano derecho del nodo I es el nodo; de lo contrario, El nodo i no tiene ningún hermano adecuado.
4. El algoritmo para encontrar el árbol binario extendido con la longitud de ruta externa ponderada mínima se llama algoritmo. El método para construir un montón en ordenación por montón se llama .
En un árbol B de orden 5.6, cada nodo contiene como máximo códigos clave. Excepto los nodos raíz y hoja, cada nodo contiene al menos códigos clave.
3. Preguntas de respuesta corta (cada pregunta tiene 6 puntos, máximo 18 puntos)
1. Describa brevemente el papel de la función hash en el almacenamiento de hash y dé ejemplos Un ejemplo de una función hash.
2. Describa brevemente los dos métodos básicos para manejar colisiones (conflictos) en el almacenamiento de hash.
3. Describa brevemente la definición de factor de carga. ¿Por qué el factor de carga es un parámetro importante para el almacenamiento de hash?
4. Resuelva las siguientes preguntas (cada pregunta tiene 6 puntos, *** 30 puntos)
1. Suponga que el código clave del archivo a ordenar es (512, 275 , 908, 677, 503, 765, 612, 897, 154, 170) Utilice el primer elemento como elemento divisorio para realizar una clasificación rápida (en orden creciente de valor clave). Proporcione los resultados después de un escaneo.
2. Dibuje el árbol binario correspondiente al árbol siguiente.
3. A partir de un árbol de clasificación binario vacío, inserte los siguientes valores clave en secuencia: 25, 13, 15, 31, 7, 20, 37. Dibuje el resultado una vez completadas todas las inserciones. Árbol de clasificación binaria.
4. Dibuje un árbol de expansión mínimo para el gráfico ponderado a continuación.
5. Para la siguiente matriz dispersa
1) Dibuje su representación de almacenamiento del método triplete. 2) Dibuje su representación de almacenamiento mediante el método fila-columna (método de lista enlazada cruzada).
5. Pregunta de algoritmo (6 puntos) Hay una tabla lineal almacenada en modo de enlace. Cada nodo en la tabla incluye dos punteros. Los nodos se describen en lenguaje PASCAL de la siguiente manera: TYPE pointer= ↑ node = RECORD infdatatype; enlace2: puntero FINAL; donde enlace1 es el puntero al siguiente nodo del nodo, enlace2 es el puntero al nodo anterior del nodo, como se muestra en la figura. Tanto p como q son variables de tipo puntero. Ahora queremos insertar el nuevo nodo señalado por q delante del nodo señalado por p en la tabla (nota: p no se refiere al primer nodo de la lista vinculada). Utilice declaraciones PASCAL para escribir los pasos clave de la inserción. (El departamento requiere escribir un algoritmo completo y solo requiere escribir los pasos clave en unas pocas oraciones). 6. Complete los espacios en blanco y analice el algoritmo (***16 puntos) El siguiente es un algoritmo de clasificación por inserción binaria escrito en Lenguaje PASCAL. Este algoritmo ordena una lista lineal de números enteros en orden ascendente. TIPO de nodo = clave RECORD: entero; infdatatype End; lista = ARRAY [1..max] DEL nodo; PROCEDIMIENTO binariosort (VAR R: lista; n: entero temp: nodo; : entero; COMIENZO entero; COMIENZO entero; bajo alto) DIV 2; SI ② ENTONCES alto:=m-1 ELSE ③ FINAL; ⑤ FIN; FIN; 1. Cambie La información correcta para completar los espacios en el algoritmo se escribe a continuación. (10 puntos) ① ② ③ ④ ⑤
2. Suponga que el número de registros a ordenar n = 7, cuando el orden de clasificación inicial del código de clasificación es (15, 25, 35, 45, 55 , 65, 75) y (75, 65, 55, 45, 35, 25, 15), díganos cuál es el número total de comparaciones realizadas en el código de clasificación durante el proceso de clasificación. (Supongamos que el método de truncamiento decimal se utiliza para la división de enteros para encontrar el término mediano en el algoritmo). (6 puntos)