考试科目
820
计算机专业基础
考试形式
笔试（闭卷）
考试时间
180
分钟
考试总分
150 分
本科目包含《数据结构》和《计算机操作系统》两门课程，总分
150 分，两门课程各占
75 分
《数据结构》
一、整体要求
《数据结构》是计算机程序设计的重要理论技术基础，是计算机科学与技术学科的中心课程。要求：
1.理解数据结构的基本观点；  掌握数据的逻辑结构、  储存结构及其差别，  以及各样基本操作的实现。
2.掌握基本的数据办理原理和方法的基础上，可以剖析算法的时间复杂度与空间复杂度。
3. 可以选择适合的数据结构和算法策略进行问题求解，具备采纳    ?C?或 ?C++或 ?JAVA?语言设计与实
现算法的能力。
二、内容
1.数据结构及算法的有关观点和术语（ 1）数据结构及算法的观点；
（ 2）数据的逻辑结构和储存结构；（ 3）算法的定义及特征；
（ 4）算法时间复杂度和空间复杂度的剖析方法。
2．线性表
（1）线性表的定义
（2）线性表的基本操作及在次序储存及链式储存上的实现；
（3）各样变形链表（循环链表、双向链表、带头结点的链表等）的表示和基本操作的实现；
（4）递归过程的特及实现方法；

（ 5）栈和行列的基本观点；栈和行列的次序储存结构、链式储藏结构及其储存特；（
列的应用
（ 7）循环行列的判满、判空方法；
（ 8）特别矩阵的压缩储藏；
3．广义表的基本观点、储存结构和基本操作

6）栈和队

4．树和二叉树
（ 1）树与丛林的基本观点
（ 2）树与丛林的储存结构及遍历
（ 3）二叉树的定义及数据结构与算法考研真题    6 大性质
（ 4）二叉树的次序储藏与链式储藏结构
（ 5）二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现
（ 6）线索二叉树的基本观点与结构方法
（ 7）树与二叉树的应用：二叉排序树；二叉均衡树；哈夫曼树与哈夫曼编码
5．图
（ 1）图的基本观点和术语；
（ 2）图的储存结构：毗邻矩阵、毗邻表、逆毗邻表；
（ 3）遍历算法：深度优先搜寻算法和广度优先搜寻算法；
（ 4）应用：最小生成树；最短路径，拓扑排序和要点路径。
6．查
（ 1）查的基本观点；静态查与动向查；

（2）次序查、折半查、索引查
（3）哈希查
哈希函数的基本结构方法，解决地点矛盾的基本策略；
（4）各样查算法的时间复杂度和空间复杂度。
7．排序
（1）排序的基本观点
（2）插入排序
（3）简单项选择择排序
（4）希尔排序
（5）迅速排序
（6）堆排序
（7）合并排序
（8）基数排序
（9）排序算法的比较。
三、题型及分值比率
1.填空题（ 10 分）
2.单项选择题（ 20 分）
3.简答题（ 30 分）
4.算法题（ 15 分）
此中算法题分为阅读、改正和编写算法三类：
(1)阅读算法：阅读指定算法，回答使用的数据结构、算法实现的功能或履行的结果；
(2)改正算法：阅读指定算法，指出算法的错误并修正；指出算法的不足并改良；按给定功能填写算法空缺部分；
(3)编写算法：依据算法功能要求，选择或许设计适合的数据结构，用程序设计语言编写算法，实
现指定功能。
以上皆可剖析给定或许设计的算法时空复杂度。
操作系统部分
一、整体要求
主要观察学生对操作系统基本观点、原理的理解程度，要点观察操作系统的设计方法与实现技术，同时可以具备运用所学的操作系统原理、方法与技术剖析问题和解决问题的能力。
二、内容及比率
1.操作系统的基本观点
1)批办理与多道程序设计
2)分时系统与及时系统
3)操作系统的基本种类与特
4)并发与并行的观点
5)操作系统的层次结构与功能模块
6)程序的并发履行与次序履行
2.办理机管理
1)进度 :  进度控制块、进度的几种基本状态与状态变换（进度的创立、进度的停止、进度的

2)

堵塞与唤醒、进度的挂起与激活等）
进度的同步与互斥：临界资源、临界区、进度同步与互斥问题、信号量体制以及    P、V 操
作、管程体制。