《华北电力大学2020年硕士生入学考试初试科目考试大纲.docx》由会员分享，可在线阅读，更多相关《华北电力大学2020年硕士生入学考试初试科目考试大纲.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、华北电力大学2020年硕士生入学考试初试科目考试大纲科目代码：842科目名称：数据结构与操作系统本门课程由数据结构和操作系统两门课程组成，两门课程各 占75分，具体要求如下：第一局部：数据结构一、考试的总体要求掌握数据结构中常用的逻辑结构、存储结构和基本操作，灵活 运用所学的数据结构解决实际问题；掌握典型的查找和排序算法, 并能够针对不同特征的数据集进行有效应用；能够分析算法的时 间复杂度，设计具有较高时空性能的算法。二、考试的内容1、基本概念和术语2、线性表线性表的定义；线性表的逻辑结构；线性表的存储结构（顺序 存储、链式存储）；不同存储方式下操作的实现；线性表的应用。3、栈与队列栈：栈的定
2、义；栈的逻辑结构；栈的存储结构（顺序存储，链 式存储）；不同存储方式下操作的实现；栈的应用。队列：队列的定义；队列的逻辑结构；队列的存储结构（顺序, 链式）；不同存储方式下操作的实现；队列的应用。4、树和二叉树二叉树：二叉树的概念；二叉树的基本性质；二叉树的逻辑结 构；二叉树的存储结构（顺序、链式）；各存储结构上的操作实现； 线索二叉树；二叉树的应用。树和森林：树（森林）的基本概念；树（森林）的逻辑结构；树 （森林）的存储结构（双亲表示法，孩子链表表示法，孩子兄弟链表 表示法）；树（森林）的基本操作实现；树（森林）与二叉树之间的相 互转换；树（森林）的应用。哈夫曼树（最优二叉树）：哈夫曼树的定
3、义、哈夫曼树的存储与应 用。5、图图的定义与基本术语；图的逻辑结构；图的存储结构；不同存储 结构上的基本操作实现；图的应用。6、查找基本概念与术语；静态查找（顺序查找、折半查找、分块查找）; 动态查找（二叉排序树、二叉平衡树和B-树的查找、插入和删除）; 哈希查找（哈希表的概念、常用的哈希函数、解决冲突的方法）；查 找性能分析；查找的应用。7、排序插入类排序（直接插入排序、折半插入排序、希尔排序）、交换类 排序（冒泡排序、快速排序）、选择类排序（简单项选择择排序、堆排序）、 归并类排序（二路归并排序）、基数排序；各种排序方法的稳定性和 时间性能分析；排序的应用。8.综合应用：根据实际问题，设计
4、有效的数据结构和算法， 并进行时间复杂度分析。三、考试的题型选择题、填空题、判断题、简答题、综合应用题、算法设计 题四、参考书目1.林碧英，石敏，焦润海.新编数据结构与算法教程.清华 大学出版社.第二局部：操作系统一、考试的总体要求要求考生熟练掌握计算机操作系统中的基本概念、基本原理; 从资源管理角度掌握计算机操作系统的主要功能及设计思想；了 解和掌握现代计算机系统对其各种软硬资源的管理方法及实现技 术；了解当代计算机操作系统的新技术与开展趋势。二、考试的内容.操作系统概述：包括操作系统的定义；操作系统的开展过程；操作系统的分类; 操作系统的特征和服务；操作系统的功能；常用操作系统的结构特 点
5、。1 .进程管理：包括进程的基本概念；进程控制（进程的状态机转换）；进程同 步；经典的进程同步互斥问题；进程通信；线程的定义及实现。2 .处理机调度与死锁：包括处理机调度的基本概念；调度方式及算法；死锁的基本概 念；死锁产生的原因；死锁的处理策略。3 .存储器管理：包括程序的装入和链接；连续分配存储管理方式；覆盖与交换; 分页存储管理方式；分段存储管理方式。虚拟存储器的基本概念； 请求分页存储管理方式；页面置换算法；请求分段存储管理方式。4 .设备管理：包括I/O系统的组成；I/O控制方式；I/O软件层次结构；设 备独立性；缓冲管理；假脱机技术（SPOOLing技术）；设备分配; 设备处理（驱动）。5 .磁盘管理：包括磁盘调度；磁盘空闲存储空间的管理；磁盘容错技术；磁 盘阵列。6 .文件管理：包括文件和文件系统；文件逻辑结构；外存分配方法（文件物 理结构）；目录管理；文件保护。三、考试的题型单项选择题、填空题、综合应用题。四、参考书目1.邹鹏，操作系统原理与实践，北京：高等教育出版社，2008.2-汤小丹等，计算机操作系统，第四版.西安：西安电子科技 大学出版社，2014.