2018年408计算机学科专业基础综合

408计算机学科专业基础综合考试大纲I考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

II考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。

要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

III考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。

二、答题方式答题方式为闭卷、笔试。

三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分(40小题，每小题2分)综合应用题70分IV考查内容数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。

2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储三、树与二叉树(一)树的基本概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼(Huffman)树和哈夫曼编码四、图(一)图的基本概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径五、查找(一)查找的基本概念(二)顺序查找法(三)分块查找法(四)折半查找法(五)B树及其基本操作、B+树的基本概念(六)散列(Hash)表(七)字符串模式匹配(八)查找算法的分析及应用六、排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubble sort)(四)简单选择排序(五)希尔排序(shell sort)(六)快速排序(七)堆排序(八)二路归并排序(merge sort)(九)基数排序(十)外部排序(十一)各种内部排序算法的比较(十二)排序算法的应用计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合试题要求。

1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；A. O(log n)B. O(n1/2)C. O(n)D. O(n2)2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3.对n个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有115个结点，则n的值是A. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。

下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同Ⅲ.若v不是T1的叶结点，则T1与T3一定相同A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.下图所示的AOE网表示一项包含8个活动的工程。

活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性 V.数据的初始状态A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B.C. 6D.9.设主串T=“abaabaabcabaabc”，模式串S=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

thread1 和 thread2 实现对全局变量 x 加 1 的机器级代码描述如下。
thread1
mov R1, x inc R1 mov x, R1
//(x) → R1 //(R1) + 1 → R1 //(R1) → x
thread2
mov R2, x inc R2 mov x, R2
//(x) → R2 //(R2) + 1 → R2 //(R2) → x
2018 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题（第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，
只有一个选项最符合试题要求）
1. 若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F()依次执行下述各步操作：
（1）从 S1 中依次弹出两个操作数 a 和 b；
。
A. 2048、1
B. 64、32
C. 32、64
D. 1、2048
18. 按字节编址的计算机中，某 double 型数组 A 的首地址为 2000H，使用变址寻址和循环
结构访问数组 A，保存数组下标的变址寄存器初值为 0，每次循环取一个数组元素，其偏移地
址为变址值乘以 sizeof(double)，取完后变址寄存器内容自动加 1。若某次循环所取元素的地址
（2）从 S2 中弹出一个运算符 op；
（3）执行相应的运算 b op a；
（4）将运算结果压入 S1 中。
假定 S1 中的操作数依次是 5, 8, 3, 2（2 在栈顶），S2 中的运算符依次是*, -, +（+在栈顶）。
调用 3 次 F()后，S1 栈顶保存的值是

408每个科目题型
408全称是“计算机学科专业基础综合”，包含四个科目：计算机组成原理、数据结构、计算机操作系统和计算机网络。

在题型方面，408包括选择题和简答题两个部分。

其中，选择题部分共有
40题，每题2分，共占80分。

选择题的科目分布如下：
1. 数据结构部分：1-10题
2. 计算机组成原理部分：11-22题
3. 操作系统部分：23-32题
4. 计算机网络部分：33-40题
简答题部分共有7题，每题10分，共占70分。

其中，数据结构2题，操
作系统2题，计算机组成原理2题，计算机网络1题。

具体考试内容、题型和分值分布可能根据年份和考试大纲有所变化，建议查看教育部考试中心发布的相关文件或咨询相关机构获取最新信息。

文化艺术出版社
《美学概论》
人民出版社
602 (建筑/城市、景 《中国城市建设史》 中国建筑工业出版社
作者
王向荣
[英]杰弗瑞·杰里柯//苏 珊杰·里柯 译者：刘滨 谊
周维权
董鉴泓，主编 沈玉麟，编 刘敦祯 潘谷西 陈志华 罗小未 高等艺术院校《艺术概 论》出版组 王朝闻主编 董鉴泓，主编
专注清华大学考研辅导
Stuart C.Poole
Linguistics 》
//166.111.107.7 下载）
616 艺术美学
《现代艺术哲学》 四川人民出版社 《美学与艺术欣赏》 高等教育出版社
H.G.布洛克 肖鹰
《新闻学概论》
中国传媒大学出版社，2007
刘建明
《转型中的新闻学》 南方日报出版社，2005
李希光
618 新闻与传播史 论
刘敦祯
《中国建筑史》
中国建筑工业出版社
潘谷西
《外国建筑史》
中国建筑工业出版社
陈志华
《外国近现代建筑史》中国建筑工业出版社
罗小未
603 数学分析
《数学分析新讲》 《数学分析》
北京大学出版社 上海科学技术出版社
张筑生 周民强，方企勤
604 普通物理
《大学物理》(第二版) 清华大学出版社
第一册至四册
张三慧
范钦珊等 刘鸿文
《材料力学》
高等教育出版社
孙训方
834 工程热力学 《工程热力学》
高等教育出版社
曾丹苓
835 理论力学及自 《理论力学》
动控制原理
《自动控制原理》
清华大学出版社 清华大学出版社
李俊峰 吴麒
836 普通物理（力 《大学物理》一、二、 清华大学出版社（第二版）

2018年计算机学科专业基础综合试题参考答案一、单项选择题1．B2．C3．A4．A5．A6．C7．D8．B9．C10．D11．A12．D13．C14．A15．A16．B17．C18．B19．A20．D21．B22．C23．C24．D25．B26．A27．C28．D29．D30．A31．D32．C33．B 34．C 35．D 36．D 37．D 38．C 39．B 40．D二、综合应用题41．解析：1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。

分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。

由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。

当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。

经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1；否则不做操作。

对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。

若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。

int findMissMin(int A[],int n){int i,*B; //标记数组B=(int *)malloc(sizeof(int)*n); //分配空间memset(B,0,sizeof(int)*n); //赋初值为0for(i=0;i<n;i++)if(A[i]>0&&A[i]<=n) //若A[i]的值介于1~n，则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++) //扫描数组B，找到目标值if (B[i]==0) break;return i+1; //返回结果}3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。

中国人民大学408-计算机学科专业基础综合考研参考书目、考研真题、复试分数线408-计算机学科专业基础综合课程介绍过去全国统一命题的考研科目只有政治理论、外国语、数学等公共课,专业课一般由学校自主命题。

2007年研究生考试教育部首次将历史学、教育学和心理学三门学科专业课初试实行全国联考,2008年农学专业课加入联考行列。

在2009年计算机专业课初试也首次实行全国统一命题。

计算机科学与技术学科的初试科目调整为:政治理论、外国语、数学(一)和计算机学科专业基础综合,卷面满分值分别为100分、100分、150分和150分。

计算机学科专业基础综合的考试内容包括:数据结构、计算机组成原理、操作系统和计算机网络,重点考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。

《数据结构》（C语言版）严蔚敏吴伟民编著清华大学出版社《计算机操作系统》汤子瀛等主编西安电子科技大学出版社《计算机网络》谢希仁编著电子工业出版社《计算机组成原理(第2版)》唐朔飞主编高等教育出版社《计算机学科专业基础综合复习指南(2010版)》复旦大学出版社《全国硕士研究生入学统一考试计算机专业基础综合考试大纲解析(2010年版)》高等教育出版社中国人民大学考研复试分数线学术学位：学科门类政治、外语、专一(数学)、专二、总分01哲学50509090330↓02经济学5555909036003法学50↓50↓909035004教育学5050180330↓05文学5555909035006历史学5050180335↑07理学4545909030008工学4545909030009医学5050180↑30012管理学50↓50↓9090350↓13艺术学45459090330专业学位：专业学位政治、外语、专一、专二、总分备注02经济类专业学位(金融、应用统计、税务、国际商务、保险、资产评估)50509090340035101法律(非法学)50509090340↓035102法律(法学)505090903300352社会工作505090903300453汉语国际教育50509090315↓0552新闻与传播55559090355↓0651文物与博物馆4545180↑3200852软件工程454580803000951农村与区域发展505090903001251工商管理100↓50170↓未通过提前面试同教育部A类分数线通过提前面试1252公共管理115↑50180↑1253会计12060225↑全日制120↑50205↑非全日制1255图书情报12055↓195↓1351艺术40↓40↓9090325↑注：1、各学院可根据生源情况上调复试基本要求。

2018年408答案解析一、单项选择题1．B2． C 3． A 4． A 5． A 6． C 7．D8．B 9． C 10． D 11． A 12． D 13． C 14． A 15． A 16．B 17． C 18． B 19． A 20． D 21．B22． C 23．C24．D 25． B 26． A 27． C 28． D 29．D30． A 31． D 32． C 33． B 34． C 35． D 36． D 37．D38． C 39． B 40． D1.【参考答案】B【解析】第一次调用：①从S1中弹出2和3；②从S2中弹出+；③执行3+2=5;④将5压入S1中。

第一次调用结束后S1中剩余5，8，5 (5在栈项)，S2中剩余*，- (-在栈项)。

第二次调用：①从S1中弹出5和8；②从S2中弹出-；③执行8-5=3;④将3压入S1中，第二次调用结束后S1中剩余5，3(3在栈顶)，S2中剩余*。

第三次调用：①从S1中弹出3 和5；②从S2中弹出*: ③执行5×3= 15；④将15压入S1中，第三次调用结束后S1中仅剩余15 (栈项)。

S2为空。

故选B。

2.【参考答案】C【解析】A的操作顺序：①①②②①①③③。

B的操作顺序：②①①①①①③。

D的操作顺序：②②②②②①③③③③③。

对于C：首先输出3，说明1和2必须先依次入栈，而此后2肯定比1先输出，因此无法得到1，2的输出顺序。

3.【参考答案】A【解析】数组N的下标从0开始，第一个元素m1,1对应存入n0，矩阵M的第一行有12个元素，第二行有11个，第三行有10个，第四行有9个，第五行有8个，所以m6,6是第12+11+ 10+9+8+1=51个元素，下标应为50，故选A。

4.【参考答案】A【解析】非叶结点的度均为2，且所有叶结点都位于同一层的完全二叉树就是满二叉树。

对于一棵高度为h的满二叉树(空树h=0)，其最后一层全部是叶结点，数量为2h-1，总结点数为2h-1。

408计算机学科专业基础一、计算机系统的基本组成：计算机是一个系统，系统最基本的单位是处理器。

它包括运算器、控制器、存储器、输入设备和输出设备五大部分。

二、计算机系统硬件的组成及特点：计算机系统是由输入、存储器和输出设备三大部分组成。

1、计算机系统硬件的组成。

计算机系统硬件通常是指微型计算机和外围设备，主要有CPU、主板、内存、硬盘、光驱、显卡等组成。

2、计算机系统硬件的特点。

①计算机的主要部件，是以集成电路芯片为基础，按照计算机的工作原理，利用电子元件把具有各种功能的电路集成在一块芯片上的。

②计算机主要部件必须具有良好的电磁兼容性。

③计算机主要部件都安装在印刷电路板上。

④计算机主要部件之间采用导线连接起来。

⑤计算机主要部件通过数据总线与外围设备进行连接。

1、计算机系统硬件的组成。

计算机系统硬件通常是指微型计算机和外围设备，主要有CPU、主板、内存、硬盘、光驱、显卡等组成。

2、计算机系统硬件的特点。

①计算机的主要部件，是以集成电路芯片为基础，按照计算机的工作原理，利用电子元件把具有各种功能的电路集成在一块芯片上的。

②计算机主要部件必须具有良好的电磁兼容性。

③计算机主要部件都安装在印刷电路板上。

④计算机主要部件之间采用导线连接起来。

⑤计算机主要部件通过数据总线与外围设备进行连接。

3、计算机主要部件的作用。

这些都是从用户的角度去讲的，下面谈谈我们做为学生该如何看待这些问题。

其实有关计算机系统硬件的很多问题，在每年的考试中并不会涉及到。

因此，做为同学而言，只需要了解他们的基本知识就可以了。

因为每年考试所考的都是新知识，老师不会把考试重点放在一些陈旧的知识上，除非老师想考察你已经把书翻烂了，否则是不会出现这种情况的。

也许有人认为学生是不应该关心这些东西的，因为他们还没有分清学习的重点，但我认为应该将主要精力放在新知识的学习上，那么陈旧的知识不去管他们，其实这是一种错误的想法，因为陈旧的知识，对于我们学习新知识是有帮助的，可以让我们少走弯路。

计算机学科专业基础408 -回复
计算机学科专业基础408（简称CS408）是一门计算机科学与技术领域的专业课程。

它通常涵盖了计算机科学的基本概念和原理，包括数据结构、算法分析、计算理论、操作系统、编程语言等方面的知识。

CS408的课程内容可能包括以下主题：
- 数据结构和算法：包括线性结构（如链表、堆栈、队列、串等）、树形结构（如二叉树、堆、哈夫曼树等）、图结构、排序算法、查找算法等。

- 计算理论：包括有限状态机、自动机、正则表达式、上下文无关文法等。

- 操作系统：包括进程管理、内存管理、文件系统、设备管理等。

- 编程语言：主要讲解一种或多种编程语言的语法、特性、程序设计思想等。

- 软件工程：包括需求分析、系统设计、编码、测试、维护等软件开发生命周期的各个阶段。

- 网络与通信：包括计算机网络基础、网络协议、网络安全、分布式系统等。

这门课程的目标是帮助学生建立起计算机科学和技术领域的基础知识和技能，培养学生的分析和解决问题的能力。

掌握
CS408的知识对于计算机科学与技术专业的学生来说是非常重要的，它为他们后续的学习和工作打下了坚实的基础。

考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

II考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。

要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

III考试形式和试卷结构一、试卷满分及考试时间本试卷满分为 150 分，考试时间为 180 分钟。

二、答题方式答题方式为闭卷、笔试。

三、试卷内容结构数据结构 45 分计算机组成原理 45 分操作系统 35 分计算机网络 25 分四、试卷题型结构单项选择题 80 分(40 小题，每小题 2 分 )综合应用题 70 分IV 考查内容数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。

2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C++ 语言设计与实现算法的能力。

一、线性表(一 )线性表的定义和基本操作(二 )线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组(一 )栈和队列的基本概念(二 )栈和队列的顺序存储结构(三 )栈和队列的链式存储结构(四 )栈和队列的应用(五 )特殊矩阵的压缩存储三、树与二叉树(一 )树的基本概念(二 )二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三 )树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四 )树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼 (Huffman) 树和哈夫曼编码四、图(一 )图的基本概念(二 )图的存储及基本操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表(三 )图的遍历1.深度优先搜索2.广度优先搜索(四 )图的基本应用1.最小 (代价 )生成树2.最短路径3.拓扑排序4.关键路径五、查找(一 )查找的基本概念(二 )顺序查找法(三 )分块查找法(四 )折半查找法(五 )B 树及其基本操作、B+ 树的基本概念(六 )散列 (Hash) 表(七 )字符串模式匹配(八 )查找算法的分析及应用六、排序(一 )排序的基本概念(二 )插入排序1.直接插入排序2.折半插入排序(三 )起泡排序 (BubbleSort)(四 )简单选择排序(五 )希尔排序 (ShellSort)(六 )快速排序(七 )堆排序(八 )二路归并排序 (MergeSort)(九 )基数排序(十 )外部排序(十一 )各种排序算法的比较(十二 )排序算法的应用计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

408计算机学科专业基础考试题型与分值
408计算机学科专业基础考试一般包含选择题和论述题两种题型。

其中，选择题包括单选题和多选题，论述题一般为开放性题目，要求考生进行较为详细的阐述。

选择题的每题分值一般为1分，论述题的分值一般为10分。

具体的题型和分值可以根据不同学校或教师的要求而略有不同，但总体来说，选择题占总分的比例较大，一般占60%~70%，
而论述题占30%~40%。

需要注意的是，以上只是一般情况，具体的题型和分值还需参考相关学校或教师的考试要求。