Tiempo: agosto de 2006 - 65438+6 meses Lectura: 447
Estructura de datos y sistema operativo - Graduado de 2007 de la Universidad de Fudan Esquema del examen de ingreso
La Universidad de Fudan reclutará estudiantes de posgrado en 2007.
Esquema del examen del curso profesional de estructura de datos y sistemas operativos
Parte 1 Estructura de datos
Preguntas de prueba: preguntas de respuesta corta, preguntas de programación
Bibliografía: "Estructura de datos" (descrita utilizando el método C++ orientado a objetos) Yin Renkun, Tsinghua University Press.
Puntuación total: 100 puntos
Requisitos básicos para el examen
Los candidatos deben comprender sistemáticamente los conceptos y teorías básicos de las estructuras de datos y dominar las características. y características de diversas estructuras de datos. El método básico enfatiza que los candidatos deben tener la capacidad de aplicar de manera integral el conocimiento que han aprendido para analizar y resolver problemas.
Requisitos para los lenguajes de programación
Todos los algoritmos en las pruebas de estructuras de datos deben describirse en lenguaje C o C++.
1. Matriz
Contenido del examen
Datos; coincidencia de cadenas.
Requisitos del examen
1. Comprender la estructura de almacenamiento de las matrices y dominar la relación correspondiente entre los elementos de la matriz y las unidades de almacenamiento en el caso del almacenamiento secuencial.
2.Comprender la estructura y características de las listas de secuencias, y dominar los algoritmos de implementación de operaciones básicas sobre listas de secuencias.
3. Dominar los algoritmos básicos de comparación de cadenas (incluido el algoritmo KMP).
4. Tener capacidad para utilizar estructuras matrices para la resolución de problemas prácticos.
Segundo, lista enlazada
Contenido del examen
Lista enlazada individualmente; lista enlazada circularmente dispersa;
Requisitos del examen
1. Comprender la estructura de almacenamiento y las características de las listas enlazadas simples, listas enlazadas dobles y listas enlazadas circulares, y dominar los algoritmos de implementación de sus operaciones básicas.
2. Comprender la estructura de almacenamiento y las características de las matrices dispersas y dominar los algoritmos de implementación de las operaciones básicas de las matrices dispersas.
3. Tener la capacidad de utilizar estructuras de listas enlazadas para resolver problemas prácticos (como operaciones polinómicas implementadas mediante listas enlazadas).
En tercer lugar, apilar y poner en cola
Contenido del examen
Apilar;
Requisitos del examen
1. Comprender la definición y características estructurales de la pila, dominar su método de almacenamiento (almacenamiento secuencial y almacenamiento vinculado) y el algoritmo de implementación de operaciones básicas.
2. Comprender la estructura y características de la cola, dominar su método de almacenamiento (almacenamiento secuencial y almacenamiento vinculado) y el algoritmo de implementación de operaciones básicas.
3. La capacidad de utilizar estructuras de cola y pila para resolver problemas prácticos (como cálculos de expresiones, colas de prioridad).
Cuarto, recursividad
Contenido del examen
Recursividad.
Requisitos del examen
1. Comprender los conceptos básicos y los principios de implementación de la recursividad y dominar el método de uso de la recursividad para describir problemas y escribir algoritmos.
2. Domina las soluciones recursivas a problemas como la Torre de Hanoi y el Laberinto.
3. Utilice la pila para dominar soluciones no recursivas a problemas recursivos.
Verbo (abreviatura de verbo) árboles y bosques
Contenido de la prueba
Árbol, árbol binario, bosque, montón.
Requisitos del examen
1. Comprender la estructura de los árboles y dominar los conceptos principales de los árboles.
2. Comprender las estructuras de varios árboles binarios, dominar sus características y tener la capacidad de utilizar árboles binarios para resolver problemas prácticos.
3. Domine los principios y propiedades de los tres métodos transversales de los árboles binarios, aplique métodos transversales de árboles binarios para resolver problemas como el número y el recuento de nodos de hojas en árboles binarios y domine lo no recursivo. método de implementación de recorrido.
4. Dominar la estructura y operaciones básicas de los árboles binarios de pistas.
5. Comprender los principios del montón y dominar los métodos de implementación de las operaciones básicas.
6. Comprender la definición y estructura de almacenamiento de árboles y bosques, y dominar la implementación de métodos como el recorrido de árboles y bosques.
7. Comprender los principios básicos de la codificación Huffman y dominar el método de generación de codificación Huffman basada en árboles de Huffman.
Colección y búsqueda de verbos intransitivos
Contenido del examen
Ensamblaje; estructura de búsqueda estática; mejor árbol de búsqueda binaria;
Requisitos del examen
1. Comprender los conceptos básicos de las colecciones y dominar varios métodos de almacenamiento de las colecciones.
2. Dominar el algoritmo de generación de clases de equivalencia.
3. Dominar los métodos de búsqueda como la búsqueda por pliegues y Fibonacci en listas ordenadas.
4. Comprenda la definición y las características del árbol AVL y domine el principio de implementación de la operación de ajuste del árbol AVL.
5. Dominar los principios de construcción y algoritmos relacionados de árboles binarios óptimos.
Siete. Números
Contenido del examen
Gráfico; gráfico mínimo; red activa;
Requisitos del examen
1. Comprender varios conceptos básicos relacionados con los gráficos y dominar varios métodos de almacenamiento de gráficos.
2. Dominar los dos métodos de búsqueda de gráficos y el método de generación de componentes conectados.
3. Domina dos métodos para generar árboles de expansión mínima.
4. Domina varios métodos para encontrar el camino más corto.
5. Dominar las características de las dos estructuras de red de uso de vértices para representar actividades y uso de aristas para representar actividades, así como los algoritmos de implementación de operaciones relacionadas.
8. Clasificación
Contenido del examen
Clasificación por inserción; clasificación por selección; clasificación por base;
Requisitos del examen
Comprender la implementación de varios métodos de clasificación, dominar la complejidad del tiempo y las características de varios algoritmos de clasificación y poder comparar horizontalmente.
Nueve. Estructura de índice y hash
Contenido del examen
Estructura de índice estática;
Requisitos del examen
1. Comprender la estructura y las características de la estructura de índice lineal, la lista invertida y el árbol de búsqueda estático.
2. Comprender la estructura del árbol B y dominar los algoritmos de implementación de diversas operaciones.
3. Comprender los principios de implementación del hash y dominar los algoritmos de implementación de diversas operaciones.
La segunda parte del sistema operativo
El contenido del examen incluye los principios de diseño y los métodos de implementación de los cuatro componentes básicos de proceso, gestión de almacenamiento, entrada y salida y sistema de archivos. El contenido también cubre los conocimientos básicos de los sistemas operativos distribuidos, los sistemas de clúster y la seguridad del sistema operativo.
Los candidatos deben comprender y dominar sistemáticamente los conceptos básicos, las funciones principales, los componentes principales y los diferentes métodos de implementación de cada componente principal del sistema operativo para dominar el diseño del sistema operativo desde la perspectiva de los recursos; Gestión y la interfaz entre programas de aplicación y sistemas de hardware. Ideas básicas, dominar la tecnología de gestión de diversos recursos blandos y duros en los sistemas informáticos modernos. Se requiere que los candidatos tengan la capacidad de aplicar de manera integral los conocimientos adquiridos para analizar y resolver problemas.
Preguntas tipo test: preguntas para rellenar espacios en blanco y preguntas de opción múltiple, preguntas de resolución de problemas y de cálculo.
Bibliografía: William Stalling S. Sistemas operativos: aspectos internos y principios de diseño. Cuarta edición, Prentice Hall 2001.
Puntuación total: 50 puntos
Detalles del contenido y requisitos del examen
1. Descripción general del sistema operativo
Contenido del examen
.1. La estructura básica de la computadora, la estructura interna del procesador, memoria caché;
2. El concepto, evolución, características, clasificación, entorno operativo y funciones del sistema operativo.
3. Estructura jerárquica de la memoria
Requisitos del examen
1. Revisar los principios básicos de las computadoras y comprender los recursos de software y hardware que rigen el sistema operativo;
2. Comprender los conceptos clave del sistema operativo y comprender las características y funciones del sistema operativo en su conjunto;
3. Realizar un estudio de caso sobre la estructura jerárquica de la memoria. .
4. Establecer los conceptos funcionales de gestión de recursos e interfaz de programas de aplicación del sistema operativo.
Segundo, proceso
Contenido del examen
Proceso, descripción del proceso y transición del estado del proceso
Requisitos del examen
Captar las características esenciales del proceso, aclarar las características dinámicas del proceso, estar familiarizado con las razones de las transiciones entre estados del proceso y establecer los procesos como los conceptos básicos de las unidades de asignación de recursos y las entidades operativas.
Hilos, multiprocesamiento simétrico SMP y microkernel
Contenido del examen
1. El concepto de hilo define la necesidad y posibilidad del hilo;
2. Características funcionales e implementación de subprocesos;
3. Arquitectura SMP multiprocesamiento simétrico:
4. Arquitectura del sistema operativo (microkernel y kernel monolítico) y su análisis de rendimiento.
Requisitos del examen
1. Comprender la necesidad y posibilidad de introducir subprocesos como entidades de ejecución básicas
2. Dominar los diversos métodos de implementación y características de los subprocesos;
3. Familiarizado con la arquitectura SMP y la arquitectura del sistema operativo (microkernel y kernel monolítico).
Cuarto, Concurrencia
Contenido del examen
1. Concurrencia y conceptos relacionados, como secciones críticas, exclusión mutua, semáforos y canalizaciones.
2. Diversos algoritmos para la exclusión mutua, sincronización y comunicación de procesos;
3. El concepto, causas y condiciones del punto muerto.
4. Algoritmos de prevención, evitación y detección de interbloqueos.
Requisitos del examen
1. Puede utilizar semáforos, canalizaciones y otras tecnologías para resolver el problema de los pasos del contrato mutuamente excluyentes.
2. punto muerto y punto muerto Condiciones necesarias y suficientes para los bloqueos;
3. Dominar los algoritmos de prevención, evitación y detección de puntos muertos;
4.
Gestión de memoria del verbo (abreviatura de verbo)
Contenido del examen
1. Gestión, sobrescritura e intercambio del almacenamiento de particiones;
2. Gestión de páginas y gestión de segmentos;
3. Métodos de gestión y tecnologías de implementación de almacenamiento de segmentos y páginas;
4. Los principios de la memoria virtual y los algoritmos y estructuras de datos relacionados.
Requisitos del examen
1. Comprender las funciones de gestión del almacenamiento y su soporte para la multiprogramación.
2. Dominar los métodos de gestión del almacenamiento de segmentos y páginas. y tecnología de implementación;
3. Centrarse en dominar los principios de la memoria virtual y los algoritmos y estructuras de datos relacionados.
6. Programación de un solo procesador
Contenido del examen
1. Tres tipos de programación de procesadores;
2 Programación de procesos Varios. Algoritmos y sus características.
Requisitos del examen
1. Comprender los tres tipos de programación: de largo plazo, de mediano alcance y de corto plazo.
2. Varios algoritmos de programación de procesos y su entorno aplicable.
7. Programación multiprocesador y programación en tiempo real
Contenido del examen
1. El impacto de los multiprocesadores en la programación de procesos
2. Algoritmos de programación de procesos y subprocesos en entornos multiprocesador:
3. Características de los procesos en tiempo real;
4. Métodos de programación de plazos y tarifas monótonas.
Requisitos del examen
1. Comprender el concepto de granularidad de programación;
2. Estar familiarizado con los algoritmos de programación de procesos y subprocesos en entornos multiprocesador. p>
3. Comprender la naturaleza de los procesos en tiempo real y dominar los métodos de programación de plazos y programación de tarifas monótonas.
8. Gestión de dispositivos y programación de discos
Contenido del examen
1. Organización de las funciones de entrada y salida en el sistema operativo;
2. Manejo de interrupciones;
3. Controladores de dispositivos, interfaces de software independientes del dispositivo y tecnología de almacenamiento en búfer;
5. ;
6. Matriz de discos.
Requisitos del examen
1. Comprender la organización de los dispositivos de entrada y salida y las funciones de entrada y salida en el sistema operativo.
2. controladores y equipos Interfaz de software independiente y tecnología de cola.
3. Concéntrese en dominar diversas estrategias de almacenamiento en búfer y algoritmos de programación de discos utilizados para mejorar el rendimiento.
4. confiabilidad en varias configuraciones de matrices de discos.
9. Sistema de archivos
Contenido del examen
1. Características del sistema de archivos y organización de archivos;
2. ;
3. Las propiedades básicas de los directorios y sus métodos de implementación;
4. Gestión del espacio en disco.
Requisitos del examen
1. Comprender las características del sistema de archivos y la organización de los archivos
2.
3. Comprender las propiedades básicas de archivos y directorios y sus métodos de implementación;
4. Centrarse en la gestión del espacio en disco, el rendimiento y la confiabilidad de los sistemas de archivos y los mecanismos de seguridad y protección de sistemas de archivos.
X. Sistema informático distribuido
Contenido del examen
1. Características y tipos de procesamiento distribuido;
2. Arquitectura de muchas capas. tecnología de middleware;
3. Sistema de clúster;
4. Problemas de diseño del sistema operativo relacionados con la gestión de procesos distribuidos.
Requisitos del examen
1. Comprender las características y tipos de procesamiento distribuido.
2. Dominar los conceptos básicos de arquitectura multicapa, tecnología de middleware y clúster. sistemas y características;
3. Centrarse en el estudio de la migración de procesos, la identificación de estados globales distribuidos, la exclusión mutua distribuida y la prevención de puntos muertos.
XI. Sistema informático de confianza
Contenido del examen
1. Problemas de seguridad que enfrentan los sistemas informáticos y sus mecanismos de respuesta:
2.
Requisitos del examen
1. Comprender los problemas de seguridad que enfrentan los sistemas informáticos y sus mecanismos de respuesta;
2. Dominar un método integral de diseño de seguridad informática. Sistema confiable.
¿Cómo te va últimamente? Vale la pena tu referencia