云南大学831数据结构与操作系统考试大纲 .docx

【云南大学831数据结构与操作系统考试大纲】主要涵盖了数据结构和操作系统两大部分的核心内容。数据结构部分涉及了基本概念、方法和技术，要求考生具备扎实的编程能力，能够运用所学解决实际问题。 在数据结构中，考试将重点考察以下几个方面： 1. 数据结构概述：包括数据结构的基本概念、算法的特性以及效率度量。 2. 线性表：如顺序存储和链式存储，以及栈和队列的实现，包括顺序栈、链栈、循环队列、链队列等。 3. 串：朴素的模式匹配算法和数组存储。 4. 二叉树：包括性质、存储结构（顺序存储和二叉链表）、遍历方法、线索二叉树和哈夫曼树。 5. 树和森林：树的存储表示、转化成二叉树以及遍历。 6. 图：图的概念、存储形式（邻接矩阵和邻接表）、遍历、最小生成树的构造算法（PRIM和KRUSKAL）、拓扑排序、关键路径和最短路径问题（DIJKSTRA和FLOYD算法）。 7. 查找：包括静态查找与动态查找、平均查找长度、各种查找算法（顺序、折半、索引顺序、二叉排序树、平衡二叉树、B树和哈希表）。 8. 排序：插入排序（直接、折半、2路和希尔排序）、冒泡排序、快速排序、选择排序（简单选择、树选择和堆排序）、归并排序和基数排序。 操作系统部分则注重考生对操作系统原理、机制、策略和技术的理解，以及分析和解决问题的能力： 1. 操作系统概述：涵盖操作系统的作用、特征、功能、历史、分类和运行环境。 2. 用户界面：作业概念、命令控制界面接口和系统调用。 3. 处理机管理：进程管理（状态、转换、控制、通信、同步与互斥、死锁处理），处理机调度（调度算法：FCFS、SJF、RR、优先级、HRN、MLFQ等）。 4. 存储管理：虚拟存储、地址变换、内存分配与回收、覆盖与交换、分区存储（基本原理、分配与回收）、页式和段式管理、工作集、局部性原理和抖动问题。 5. 文件管理：文件系统基础、文件结构、存储管理（空间管理、目录管理、存取控制、层次结构）、磁盘调度算法。 6. 设备管理：设备管理目的、功能、数据传输控制方式（直接控制、中断、DMA、通道）、中断技术、缓冲技术和设备分配与回收。 总体来说，该考试大纲要求考生全面掌握数据结构和操作系统的基础理论和实际应用，具备良好的编程能力和问题解决能力。备考时，考生应重点复习上述知识点，通过大量实践题目巩固理论知识，提高实际操作技能。