2019年计算机专业基础综合科目考试大纲

2019年《计算机专业基础综合》科目考试大纲一、考查目标计算机应用技术专业（专业硕士）入学考试计算机专业基础科目考试内容包括《算法与数据结构》和《操作系统》两门计算机学科基础课程，要求考生系统掌握相关学科的基本知识、基础理论和基本方法，并能运用相关理论和方法分析、解决实际问题，提高利用计算机解决实际问题的实践技能。二、考试形式与试卷结构（一）试卷成绩及考试时间本试卷满分为150分，考试时间为180分钟。（二）答题方式答题方式为闭卷、笔试。（三）试卷内容结构各部分内容所占分值为：算法与数据结构约80分操作系统约70分（四）试卷题型结构填空题：10小题，每小题1分，共10分选择题：20小题，每小题1分，共20分应用题：8小题，每小题15分，共120分三、考查范围算法与数据结构（一）、考查目标1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解，具备采用C或C++或JAVA语言设计与实现算法的能力。（二）、考查内容一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.广度优先搜索（四）图的基本应用1.最小（代价）生成树2.最短路径3.拓扑排序4.关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树及其基本操作、B+树的基本概念（五）散列（Hash）表及其查找（六）查找算法的分析及应用六、内部排序（一）排序的基本概念（二）插入排序1.直接插入排序2.折半插入排序（三）起泡排序（bubblesort）（四）简单选择排序（五）希尔排序（shellsort）（六）快速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用操作系统（一）、考查目标1.了解操作系统在计算机系统中的作用、地位、发展和特点2.理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题。（二）、考查内容一、操作系统概述（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类（三）操作系统的运行环境二、进程管理（一）进程与线程1.进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统；消息传递系统；管道通信。6.线程概念与多线程模型（二）处理机调度1.调度的基本概念2.调度时机、切换与过程3.调度的基本准则4.调度方式5.典型调度算法：先来先服务调度算法；短作业（短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。（三）进程同步1.进程同步的基本概念2.实现临界区互斥的基本方法软件实现方法；硬件实现方法。3.信号量4.管程5.经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题。（四）死锁1.死锁的概念2.死锁处理策略3.死锁预防4.死锁避免系统安全状态：银行家算法。5.死锁检测和解除三、内存管理（一）内存管理基础1.内存管理概念：程序装入与链接；逻辑地址与物理地址空间；内存保护。2.交换与覆盖3.连续分配管理方式4.非连续分配管理方式分页管理方式；分段管理方式；段页式管理方式。（二）虚拟内存管理1.虚拟内存基本概念2.请求分页管理方式3.页面置换算法：最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）。4.页面分配策略5.抖动抖动现象；工作集。6.请求分段管理方式7.请求段页式管理方式四、文件管理（一）文件系统基础1.文件概念2.文件的逻辑结构：顺序文件；索引文件；索引顺序文件。3.目录结构：文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。4.文件共享5.文件保护：访问类型；访问控制。（二）文件系统实现1.文件系统层次结构2.目录实现3.文件实现（三）磁盘组织与管理1.磁盘的结构2.磁盘调度算法3.磁盘的管理五、输入输出（I/O）管理（一）I/O管理概述1.I/O设备2.I/O管理目标3.I/O管理功能4.I/O应用接口5.I/O控制方式（二）I/O核心子系统1.I/O调度概念2.高速缓存与缓冲区3.设备分配与回收4.假脱机技术（SPOOLing）5.出错处理主要参考书：1.数据结构(C语言版)，严蔚敏，李冬梅，吴伟民，人民邮电出版社2.计算机操作系统(第三版)，汤小丹，梁红兵，哲凤屏，汤子瀛，西安电子科技大学出版社