677 preguntas del examen de ingreso a posgrado
El Laboratorio de Ingeniería de Software es un laboratorio profesional establecido por nuestro departamento para cursos como ingeniería de software, diseño colaborativo de software y gestión de proyectos de software. El laboratorio ofrece Microsoft Project Standard 2007, una herramienta avanzada de gestión de proyectos para ingeniería de software, y SPARX Enterprise Architect 7.5 para Windows. Las herramientas y plataformas proporcionadas por el laboratorio ayudan a los estudiantes a dominar las teorías y métodos de los cursos teóricos, y a familiarizarse y aplicar herramientas avanzadas para la gestión, el trabajo en equipo, el diseño y el modelado de procesos de desarrollo de software. Permita que los estudiantes se adapten rápidamente al entorno de desarrollo y diseño de las empresas de software después de ingresar al lugar de trabajo.
Espero que el examen simulado adjunto pueda ayudarte y ¡te deseo buena suerte en tu examen de secundaria!
Prueba de simulación de estructura de datos
1. Preguntas de opción múltiple (elija una respuesta correcta de las cuatro respuestas alternativas para cada pregunta y complete el número después de la pregunta, 2 puntos). por cada pregunta, ***10 puntos).
1. La secuencia de entrada de una pila es 1, 2, 3, 4. ¿Cuál de las siguientes secuencias 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. ¿Cuál de los siguientes métodos de clasificación no tiene nada que ver con la disposición inicial de los registros? ( )
A. Clasificación por inserción directa
B. Clasificación por burbujas
Clasificación rápida
D. p> p>
3. El costo de tiempo total para fusionar y ordenar N archivos de registros es
A.O(nlog2n)
Oxígeno (nitrógeno)
<. p> C.O(log2n)D.O(n)
4. Si un árbol binario tiene 10 nodos con grado 2, entonces el número de nodos con grado 0 en el árbol binario es () .
A.9
B.11
C.12
D. Inseguro
5. Las siguientes afirmaciones sobre árboles B y árboles B son incorrectas.
Los árboles A.B y B son ambos multiárboles equilibrados.
B.B-tree y B-tree 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. Tanto el árbol B como el árbol B pueden admitir eficazmente la recuperación aleatoria.
2. Complete 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 más típicas y los árboles. son más típicos.
2. La dirección de almacenamiento de la matriz bidimensional A es 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 menor que n, el hermano derecho del nodo I es un nodo; nodo I No hay derecho hermano.
4. El algoritmo que encuentra el árbol binario extendido con la longitud de ruta externa ponderada mínima se llama algoritmo. Se llama al método de construir un montón en ordenación de montón.
En el árbol B de orden 5.6, cada nodo contiene como máximo un código clave. Excepto el nodo raíz y los nodos hoja, cada nodo contiene al menos un código clave.
Tres. Preguntas de respuesta corta (cada pregunta tiene 6 puntos, ***18 puntos)
1. Describa brevemente la función de la función hash en el almacenamiento de hash y dé un ejemplo de 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 almacenado por el método hash?
4. Resuelva los siguientes problemas (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), utilizando el primer elemento como elemento divisor para una clasificación rápida.
Por favor dibuje el árbol binario correspondiente al siguiente árbol.
3. A partir de un árbol de clasificación binario vacío, inserte los siguientes valores de código clave en secuencia: 25, 13, 15, 31, 7, 20, 37. Dibuje el árbol de clasificación binario después de todas las inserciones.
4. Utilice el siguiente dibujo ponderado para dibujar un árbol de expansión mínimo.
5. Para la siguiente matriz dispersa
1) Dibuje su representación de almacenamiento triple.
2) Dibujar su representación de almacenamiento de filas y columnas (método de lista entrecruzada).
5. Problemas de algoritmos (6 puntos)
Hay una tabla lineal almacenada de forma enlazada. Cada nodo en la tabla incluye dos punteros y el nodo se describe con PASCAL de la siguiente manera:
Tipo puntero= ↑nodo;
Nodo=registro
Información : Tipo de datos;
enlace1, enlace2: puntero
Fin;
donde enlace1 es un puntero al siguiente nodo de este nodo, enlace2 es un puntero a el nodo anterior de este nodo El puntero del nodo, como se muestra en la figura.
P y Q son variables de tipo puntero. Ahora el nuevo nodo señalado por Q en la tabla debe insertarse delante del nodo señalado por P (nota: P no se refiere al primer nodo en 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 que los pasos clave se escriban en unas pocas oraciones. )
6. Algoritmo de análisis y llenado de espacios en blanco (***16 puntos)
El siguiente es un algoritmo de clasificación por inserción binaria escrito en lenguaje PASCAL, que utiliza clasificación de enteros. Código para ordenar una tabla lineal en orden ascendente.
Tipo nodo = registro
clave: entero
Información: tipo de datos
Fin
lista; =ARRAY[1..max de nodo];
Procesar clasificación binaria(VAR R: lista; n: entero);
VAR temp: nodo;
bajo, m, alto, I, j: entero
Inicio
Para I: =2 a n DO
Inicio
temp: = R[I];
Baja: = 1; Alta: = I-1;
Cuando ① esté listo
Iniciar
m:=(bajo alto)DIV 2;
Si ②
entonces alto:=m-1
De lo contrario ③
Fin;
FOR j:= i-1 ABAJO A ④ DO
R[j 1]:= R[j];
⑤< / p>
Fin;
Fin;
1. Escriba el contenido correcto que debe completarse en el espacio en blanco del algoritmo a continuación. (10 puntos)
①
②
③
④
⑤
2. Supongamos que el número de registros a ordenar es n=7. Explique cuándo el orden inicial de los códigos de clasificación es (15, 25, 35, 45, 55, 65, 75) y (75, 65, 55, 45, 35, 25, 15) respectivamente. (Supongamos que la división entera del término medio en el algoritmo utiliza truncamiento decimal). (6 puntos)