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

《云南大学831数据结构与操作系统考试大纲》详述了计算机科学专业核心课程的数据结构与操作系统的考查目标、考试形式、内容结构和考查范围。这份大纲旨在评估学生对这两门关键课程的理解程度，以及他们将理论应用于实践的能力。 数据结构部分主要涵盖以下几个方面： 1. 基本概念和技术：要求学生掌握数据结构的基础知识，包括算法的基本概念、特性和效率度量。 2. 线性表：讲解顺序存储和链式存储，比较它们的优缺点，并要求能进行相应操作。 3. 栈和队列：讨论不同类型的栈和队列，以及它们在插入和删除操作中的特性，还包括栈与递归的关系。 4. 串：涉及朴素的模式匹配算法。 5. 数组：讲解数组的定义和存储，以及特殊矩阵的压缩存储。 6. 树和二叉树：深入研究二叉树的性质、遍历方法、线索二叉树以及哈夫曼树。 7. 图：介绍图的存储形式，遍历算法，最小生成树的构造方法，有向无环图的拓扑排序和关键路径，最短路径问题的求解。 8. 查找：涉及各种查找算法，如顺序查找、折半查找、索引顺序表、二叉排序树、平衡二叉树和哈希表。 9. 排序：涵盖多种排序算法，包括稳定性、性能特点等。 操作系统部分则包括： 1. 概述：解释操作系统的角色、发展历史、分类和运行环境。 2. 用户界面：涉及作业管理和命令控制界面接口，以及系统调用。 3. 处理机管理：重点关注进程管理，包括进程状态转换、调度算法（如FCFS、SJF、PR、HRN、MLFQ等）和进程同步与互斥。 4. 存储管理：涉及虚拟存储、地址变换、内存分配和回收，以及页式、段式和段页式存储管理，重点讨论了页面置换算法。 5. 文件管理：包括文件系统的基本概念，文件存储和访问控制，以及磁盘调度算法。 6. 设备管理：讲解设备管理的功能，数据传输控制方式，中断技术和缓冲技术，以及设备分配与回收。 考试形式为闭卷笔试，试卷总分为150分，考试时间为180分钟，包括选择题、简答题、综合题和程序设计题，各部分分数占比为数据结构75分，操作系统75分。考生需具备扎实的理论基础和程序设计能力，能够灵活运用所学知识解决实际问题。