En 2002, la Universidad de Ciencia y Tecnología de Beijing realizó el examen de ingreso para estudiantes de maestría.
Sujeto de prueba: estructura de datos
Especialidades aplicables: tecnología de aplicaciones informáticas, software informático e ingeniería de sistemas teóricos, estructura de sistemas informáticos
Nota: todos los candidatos deben hacer 1 - Hay 7 preguntas y los candidatos individuales deben responder las preguntas 1, 2, 3, 5, 6, 8 y 9. Asegúrese de escribir sus respuestas a todas las preguntas en su hoja de respuestas.
1. (20 puntos) Responda las siguientes preguntas:
1. ¿Cuáles son los métodos comunes para mapear (o representar) estructuras lógicas de datos en la memoria de una computadora?
2. Describa brevemente el significado de certeza del algoritmo.
3. ¿Cuáles son las características de la estructura lineal y la estructura de árbol?
4. Supongamos que el campo de datos del nodo en la lista enlazada individualmente son datos, el campo del puntero es el siguiente y el puntero p es la dirección del nodo en la tabla. Escriba una declaración de descripción en lenguaje C para insertar un nodo S antes del nodo P.
5. Describa brevemente dos ejemplos del uso de pilas y colas en el diseño de su algoritmo.
6. Suponga que el número de nodos de hoja de un árbol ternario es n0, y el número de nodos con grados 2 y 3 son n2 y n3 respectivamente. .
7. ¿Cuáles son los dos algoritmos típicos para construir árboles de expansión mínima de redes conectadas no dirigidas?
8. En presencia de n (n >: =0), cuando se busca en un árbol B de orden M usando palabras clave, ¿cuántos nodos están involucrados en la ruta de búsqueda?
9. Indique tres métodos de clasificación interna estables y tres inestables.
10.¿Qué orden de índice de tres niveles se utiliza para recuperar archivos ISAM? ¿De qué tres partes consta un archivo VSAM?
2. (10 puntos) Algoritmo Completa los espacios en blanco:
El algoritmo para encontrar la longitud de ruta ponderada (WPL) del árbol de Huffman es el siguiente, donde ht es el puntero. al nodo raíz y S es la pila de trabajo, Clearstack(S), Push(S, P), Pos(S) y Emptystack(S) son funciones para la pila vacía, el puntero P para entrar, salir y juzgar la pila vacía respectivamente. Complete los espacios subrayados en el algoritmo para completar su funcionalidad.
Tres. (10 puntos)
Asumimos que el salario total ST de los empleados de una determinada unidad se compone de tres elementos: "salario", "deducción" y "pago real". Los elementos salariales incluyen el "salario básico". " y "asignación" ", "Bono", la deducción incluye los gastos de "agua", "electricidad" y "gas".
1. Utilice la tabla de salarios ST descrita en forma de tabla generalizada y utilice las funciones GetHead(ST) y GetTail(ST) para extraer los elementos de bonificación en la tabla.
2. Utilice el lenguaje C para describir la estructura de elementos en la tabla generalizada y dibujar la estructura de almacenamiento de la tabla de salarios.
Cuatro. (10 puntos para los candidatos)
Establezca el árbol binario BT de la siguiente manera:
1. Dibuje la estructura de almacenamiento de "secuencia" y "lista enlazada binaria" de este árbol binario BT;
2. Utilice los métodos de "orden previo", "orden medio" y "orden posterior" para escribir la secuencia de resultados obtenidos al atravesar el árbol binario BT y dibuje el árbol binario de pistas de orden posterior de BT.
V. (15 puntos)
Supongamos que la matriz de adyacencia A de la red no dirigida G es la siguiente:
1. matriz A La estructura lógica de la red G (los vértices en G están representados por v1 ~ v8);
2 De acuerdo con los métodos de búsqueda "primero en profundidad" y "primero en amplitud", escriba el resultado. de atravesar la red G a partir del vértice v1 La secuencia de vértices
3 A partir del vértice v1, dibuje el árbol de expansión mínimo de la red G de acuerdo con el algoritmo de Prim para encontrar el árbol de expansión mínimo.
VI. (15 puntos)
Supongamos que el conjunto de registros clave es k = {26, 36, 41, 44, 15, 68, 12, 6, 51, 25}.
1. Construya un árbol de Huffman con K como conjunto de pesos; tome los valores en k a su vez para construir un árbol de clasificación binario.
2. tabla hash Para m = 16, el método para seleccionar la función hash es H (clave) = clave13, y el método para manejar conflictos es "exploración secundaria y luego hash". Tome los valores en k uno por uno y construya una estructura de tabla hash que cumpla con las condiciones dadas;
3 Tome la primera palabra clave (26) en K como punto de apoyo y utilice la "clasificación rápida". método para Cuando se ordena K, el resultado se escribe al final de la primera clasificación y K se ajusta al montón con el valor máximo del elemento superior.
7. (20 puntos por esta pregunta)
Diseño de algoritmo:
1. Sea L el puntero del primer nodo de la circular unidireccional. lista enlazada (sin nodo principal), los números de nodo son 1, 2,...,n, y el número en la lista enlazada es K (1
2. El gráfico dirigido G con n vértices tiene se ha almacenado en la estructura de la lista de adyacencia. El puntero de la tabla de vértices es G, y la penetración de cada vértice en el gráfico se ha registrado en el campo de identificación del vértice (es decir, G->datos[i]. id=el primero I ( 1
ocho, (10 puntos por este cuestionario)
Supongamos que el bosque F = {T1, T2, T3} de la siguiente manera:
Si este bosque F se almacena usando "representación del hermano del niño", dibuje su estructura de almacenamiento;
2 Utilice los métodos "preorder" e "inorder" para escribir la secuencia de resultados obtenida al atravesar el bosque F.
9. (20 puntos por este cuestionario)
Diseño de algoritmo:
1. Suponga que los punteros principales de dos listas enlazadas individualmente con nodos principales son A y B respectivamente. Los campos de datos de los nodos en la lista vinculada son datos (establecidos en un número entero), el campo de puntero es el siguiente. Escriba el algoritmo para fusionar la tabla A y la tabla B en una única lista vinculada L en forma de lenguaje C. función: Unión (A, B, L) (Nota: si la tabla A y hay nodos con el mismo valor de datos en la tabla B, solo se conserva uno de ellos);
2. El conjunto de palabras clave k = {k1, k2,..., kn} se ha almacenado en la matriz de enteros En A[n], utilice la forma de función del lenguaje C para escribir un algoritmo para ajustar la matriz A[n] en una montón raíz pequeño: crear montón (A [n]) (Nota: si el valor en k satisface ki
Lo siento, realmente no puedo encontrarlo