2018年中科院计算机学科综合(专业)863考研真题

2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。

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

请在答题卡上将所选项的字母涂黑。

b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。

}void main(>{ cout<< s(1>。

}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。

5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。

2020年中科院计算机863考研真题回忆（题号和顺序仅供参考）选择题（选择题记住的不多了）1.进程进入临界区时首先要执行什么指令（特权指令、原子指令、向量指令，xx指令）2.对称密码和非对称密码的（不会，具体题也忘啦）3.用户使用操作系统资源时通过什么方法（系统调用）4.三级页表，虚拟地址24位，每级页号占8位，每个页表项4B，页面大小1KB，先一进程大小128KB，问其页表大小为（1KB，2KB，3KB，4KB）5.对称多处理系统能在多个处理器上同时运行线程还是进程6.下列措施是为了实现保密性的是（根目录只有root能访问）7.下列不是死锁预防措施的是（两阶段加锁，重启系统，假脱机，按顺序分配资源）8.RAID6的特征（6块磁盘并行，可以容忍1？2？3？块磁盘损坏）9.第一次打开文件时的操作（把超级快读入内存，把inode读入内存，xxx）10.CPU流水线5阶段时间分别为xxxns，问你时钟频率最高是多少11.采用程序查询方式，每次程序执行需xxx个周期，每秒需执行xxx次，主频给出，求程序查询占用时间比例问答题41.一般的文件系统在磁盘上有哪些组成部分，分别有哪些功能？42.进程共5个页面，工作集大小为4，给出一组页面访问顺序，问分别采用FIFO、LRU、Optimum（最优置换）算法时缺页次数及缺页时替换的分别为哪个页43.给出一个cache-主存地址转换结构图，问你cache的映射方式、总大小、块大小、写回策略等等（主要是看懂图，看出来是四路组相连）44.给了一个局域网拓扑图，主机通过交换机连接了一个www服务器和一个DNS服务器，让你简述访问www服务器主页的过程，用了哪些协议，分别是什么功能45.一个单周期CPU，5个阶段（取指、析址、执行、访存、写回）第一问问你一条指令执行时间，第二问将执行和访存结合成一个阶段（2选1）问你此时指令执行时间，第三问问这。

2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）数据结构部分一、选择题（共10道，一个2分，共20分）1．数据结构的逻辑结构分类是哪两种？2．给定一颗完全二叉树的结点数，求其中的叶节点个数3．一个有n个结点的图构成一个邻接矩阵几乘几的矩阵4～10暂缺二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理）1．给了8个左右的数字的一个集合，比如{75，63，43…}，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。

2．给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。

3．一个指令集合{I1，I2，I3…}，对应给出了每个指令对应的发生概率大小{0.03，0.03，0.15，0.15，0.3，0.4}（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。

求出他们的一个组织，并且求出每个指令的哈夫曼编码。

4．给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。

5．给定了一个树，转化成对应的二叉树，大概有8个点左右。

计算机网络部分一、选择题（共10道，一个1分，共10分）1．IPV4和IPV6的特征对比，选出一个错误的2．TCP拥塞控制中慢开始算法的特征，选出一个错误的3～10暂缺二、填空题（共10道，一个1分，共10分）1．IEEE802.11用的协议是_____2．CDMA2000采用的编码方式是_____3．移动IP的基本工作过程（给了其中3个步骤，填另一个）4．信道划分的三种方式（给了其中2个，填另一个）5～10暂缺三、简答题（共7道，共40分）1．主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题及答案2018 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40 小题，每小题2 分，共80 分。

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

1.若栈S1 中保存整数，栈S2 中保存运算符，函数F()依次执行下述各步操作：（1）从S1 中依次弹出两个操作数 a 和b；（2）从S2 中弹出一个运算符op；（3）执行相应的运算 b op a；（4）将运算结果压人S1 中。

假定S1中的操作数依次是5,8,3,2（2在栈顶），S2中的运算符依次是*,-,+（+在栈顶）。

调用3 次F()后，S1 栈顶保存的值是。

A. -15B. 15C. -20D. 202.现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。

若仅允许下列3 种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。

A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 13.设有一个12×12 的对称矩阵M，将其上三角部分的元素m i, j （1≤i≤j≤12）按行优先存人C 语言的一维数组N 中，元素m6, 6 在N 中的下标是。

A. 50B. 51C. 55D. 664.设一棵非空完全二叉树T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。

若T 有k 个叶结点，则T 的结点总数是。

A. 2k-1B. 2kC. k2D. 2k-15.已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。

A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006.已知二叉排序树如下图所示，元素之间应满足的大小关系是。

2018年华中科技大学834计算机专业基础综合复习八套卷一（版）一．填空题（20分，每题2分）1. 在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动个元素。

2. 栈是的线性表，其运算遵循的原则3. 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是。

4. 己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为。

5. 对矩阵压缩是为了。

6. 在哈希函数H（key）=key%p中，p值最好取。

7. IP地址21.12.240.17的网络类别是类，主机号是。

8. 100BASE-T标准规定的信号是，网络速率是。

9. 信息传输速率的单位是，码元传输速率的单位是。

10. 在TCP/IP网络中，TCP协议工作在，FTP协议工作在。

二．判断题（20分，每个2分）No. 1 2 3 4 5 6 7 8 9 10 Answer1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（）2. 数据的物理结构是指数据在计算机内的实际存储形式。

（）3. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。

（）4. 数组不适合作为任何二叉树的存储结构。

（）5. B-树中所有结点的平衡因子都为零。

（）6. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。

（）7. 在OSI 参考模型中，最上层是物理层。

（）8. 在TCP 段头中，窗口数的大小由发送方决定。

（）9. 带宽的基本单位是bps,吞吐量的基本单位是Mbps。

（）10. 一个IPv4 地址表示193.168.125.0/30，其中，30 表示主机的位数。

（）三．选择题（30分，每个3分）No. 1 2 3 4 5 6 7 8 9 10 Answer1. int frog｛if(n==0)return 1;elsereturn （n+frog（n-1）/2）; ｝上述算法时间复杂度是多少（）A. lognB.nC. nlognD. (n)`22. 连续存储设计时，存储单元的地址（）。

2018年中科院信息工程研究所网络空间安全专业（083900）考试科目、参考书目一．研究方向01(全日制)密码理论与技术02(全日制)密码协议理论与技术03(全日制)信息对抗理论与技术04(全日制)云计算安全理论与技术05(全日制)多媒体理论与技术06(全日制)信息安全战略研究07(全日制)大数据存储与管理08(全日制)信息过滤与内容计算09(全日制)信息检索与数据挖掘10(全日制)分布式计算与并行处理11(全日制)威胁检测与信息对抗12(全日制)多媒体信息智能化处理13(全日制)密码工程与应用14(全日制)网络安全协议15(全日制)身份管理与网络信任技术16(全日制)版权与数据资产保护17(全日制)安全芯片技术18(全日制)智能终端安全19(全日制)移动通信与安全20(全日制)移动互联网安全21(全日制)物联网安全22(全日制)信号处理理论与技术23(全日制)电磁声光检测与防护24(全日制)信息保密技术25(全日制)工控系统安全26(全日制)网络体系结构与安全防护27(全日制)系统安全理论与技术28(全日制)信息保护技术29(全日制)可信计算30(全日制)智能信息设备安全31(全日制)软件安全分析理论与技术32(全日制)网络攻防技术33(全日制)安全态势感知技术34(全日制)网络安全评测二．初试考试科目01—06方向①101思想政治理论②201英语一③301数学一④801高等代数或863计算机学科综合（专业）07—12方向①101思想政治理论②201英语一③301数学一④863计算机学科综合（专业）13—18方向①101思想政治理论②201英语一③301数学一④801高等代数或859信号与系统或863计算机学科综合（专业）19—25方向①101思想政治理论②201英语一③301数学一④859信号与系统或863计算机学科综合（专业）26—34方向①101思想政治理论②201英语一③301数学一④863计算机学科综合（专业）三．参考书目801高等代数【1】北京大学编《高等代数》，高等教育出版社，1978年3月第1版，2003年7月第3版，2003年9月第2次印刷.【2】复旦大学蒋尔雄等编《线性代数》，人民教育出版社，1988.【3】张禾瑞，郝鈵新，《高等代数》，高等教育出版社，1997863计算机学科综合（专业）（1）数据结构【1】数据结构（C语言版）.严蔚敏，吴伟民编著，北京：清华大学出版社，2007年。

2016年中国科学院大学北京市培养单位863计算机学科综合[专业硕士]考研真题（回忆版）【说明】以下题目为多个回忆版本的综合，略有出入的地方以补充的形式给出。

一、单项选择题：（2分/题，一共80分。

这里不是按原题顺序写的，我想起来一个写一个的）1．栈的操作模拟，连续push3个元素后，pop一个，再getTop，问最后得到的这个是哪个元素。

2．设有一个n*n的对称矩阵A，将其下三角部分按行存储在一维数组B中，A[0][0]存在B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。

A．（i＋3）i/2B．（2n－i＋1）i/2C．XXXD．xxx记不清了。

3．稀疏矩阵存储的常用方式有哪两个？A．数组B．十字链表C．还有个啥我忘了4．给一堆字符串，应该都是姓氏的汉语拼音（什么fang、bai、an、tang之类的），然后问你按升序一趟二路归并排序之后的序列是啥。

补充：排序是按首字母序号升序排序的5．串的存储最常用的两种方式是？A．数组B．链表C．堆6．下列序列，用快排按升序排列，哪个的元素移动次数最多？A．{10，30，50，70，90}BCD都是这五个数换换顺序，具体是啥记不清了。

7．一个无向图，给出几个结点，和它们之间有哪些边。

让你选出哪个是正确的先深遍历序列。

8．下列有关机群的说法错误的是（）A．机群比多处理器具有更好的扩展性B．机群各个节点都有独立的主存C．一个进程的多个线程可以同时在集群的各个节点上运行D．忘了9．两个补码表示的负数，相加，让你指出结果是哪个。

补充：8位（或者7位）补码，好像是计算（-xx）＋80×2问结果，D选项是溢出。

10．流控滑动窗口协议中，可以直接发送而不必确认的数据是（）A．滑动窗口左边的数据B．滑动窗口右边的数据C．滑动窗口内的数据D．滑动窗口收缩的数据11．TCP连接中，用wireshark捕获了一个数据包，内容是seq:0，ack:1，ACKset1，SYNset1。

中科大计算机考研真题中科大计算机考研是众多计算机科学与技术专业学生追求的目标之一。

在这道真题中，我们将回顾一些历年的考题，并提供一些解析和思路，以帮助考生更好地准备考试。

本文共分为三个主题部分：操作系统、数据库和算法与数据结构。

一、操作系统1. 多道批处理系统是怎样实现作业调度的？请简要描述操作系统的作业调度过程。

解析：多道批处理系统是指一台计算机同时处理多个作业，而不需要人工干预。

作业调度是指操作系统根据一定的算法，决定当前执行哪个作业。

作业调度过程一般包括以下几个步骤：首先，操作系统根据作业的优先级和提交时间等信息，为每个作业分配一个初始的调度优先级。

其次，对于多个处于就绪状态的作业，操作系统根据调度算法，选择一个作业进行执行。

常见的调度算法有先来先服务（FCFS）、短作业优先（SJF）、最高响应比优先（HRRN）等。

最后，当一个作业执行完成或者处于阻塞状态时，操作系统会根据调度算法重新选择一个作业进行执行，直到所有作业完成。

2. 请解释死锁的概念，并说明死锁的产生条件和解决方法。

解析：死锁是指多个进程在竞争有限资源时，由于彼此之间的互斥和请求资源的非预期顺序等原因，导致都在等待对方释放资源，从而导致系统无法继续执行。

死锁的产生条件主要包括：互斥条件：进程对所请求的资源进行排他性控制，即一次只能有一个进程使用该资源。

持有和等待条件：进程已经持有了一个资源，但又请求额外的资源，而这些资源又被其他进程所占有。

不剥夺条件：其他进程不能强行剥夺一个进程已经持有的资源，只能由进程自己释放。

环路等待条件：多个进程之间形成了一个循环等待资源的关系。

死锁的解决方法主要有以下几种：鸵鸟算法：忽略死锁的存在，不进行处理。

适用于死锁发生概率极低的系统。

死锁检测与恢复：通过系统资源分配图等方法，检测死锁的发生，并进行资源回收和进程终止等操作，使系统恢复正常状态。

死锁预防：通过破坏死锁产生的四个条件之一，预防死锁的发生。

中科院计算机所试题中科院计算所2003年考研试题第一部分编译（40’）一、（1/01）*0*说明是什么语言画出DFA（10?）二、S→过程调用语句/数组的赋值语句（10?）过程调用语句为：id(id,id,…,id)赋值语句: id(id,…,id):=id(id,…,id)(a)写一个LR（1）方法（产生式不大于6个）(b)若在LR分析同时完成语义分析，中间代码生成，基于你的文法有什么困难？三、E→E*E/+E/-E/unsigned-integer为上面表达式产生栈机器代码，代码执行后，表达式值留在栈上，自己设计所需栈机器指令，并写清指令含义。

(10?)四、C语言中，a表示数组首址，而A * func ( ){return(a);}在linux上用gcc编译报告:第6行warning: return from incompatible pointer type(2) typedef int A[10][20]A a;A *func( ){return(}无类型方面错误(3) typedef int A[10][20]typedef int B[20]A a;B *func( ){return(a);}无类型方面错误(4) typedef int A[10][20]A a;func( ){Printf(“%d,%d,%d/n,a,a+1,}main( ){func( );}结果：134518112，134518192，134518912第二部分操作系统（40’）五. 1、操作系统内核有强内核和微内核，unix是前者，windowsNT是后者，简介微内核比强内核的优点。

（4?）（强内核：弱内核：各自优缺点：）2、若只有进程控制，其独立性表现在？引入线程后，独立性有何改变?（4?）3、请求调页存储系统确定页面大小的标准（4?）六、1.死锁的证明，在m个同类资源，n个进程共享它，每次进程只能获得或释放至多一个资源，问会不会发生死锁，若：(1)、设每个进程所需资源数为ri 1rlink=restore (5)+k,rpos+1,n-1-k);Return ptr;}postorder(TNODE*ptr){if(ptr=NULL) return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}四．（10分）已知有如下定义的静态链表：TYPE component=RecordData:elemtp;Next:0..maxsizeEndV AR STALIST:array[0..maxsize] of component;以及三个指针:aV指向头结点，p指向当前结点，pre指向的前驱结点，现要求静态链表中next域中的内容，使得该静态链表有双向链表功能，从当前结点P既能往后查找，也能往前查找(1)定义next中的内容。

1、M进制离散信源，平均信息量最大的概率分布为正态分布均匀分布瑞利分布指数分布2、数字通信系统，差错概率表示系统性能指标的有效性适应性可靠性标准性3、DSB、SSB、VSB已调信号带宽的大小为4、已知二进制数字信号码元长度为0.2us，若平均每2.5s产生一个错码，则平均误码率为8*10^(-8)5、下列哪种技术可以消除或减少码间串扰自动增益控制技术量化技术最佳接收技术均衡技术6、抽样可使模拟信号实现离散时域和频域的离散频域的离散时域的离散频谱的离散7在一个包含调制信道的数字通信系统中，接收端三种同步的顺序为载波同步位同步帧同步8不能采用包络检波解调的是ASK PSK FSK OOK9对一个纠错码而言，其编码效率越高，则表示引入的冗余越，通常其检错能力越多高长强少低少高10所谓匹配滤波器是指使信号特性与滤波器特性相匹配使滤波器特性与信号特性相匹配使滤波器特性与噪声特性相匹配使噪声特性与滤波器特性相匹配1、通常广义信道可以分为调制信道和编码信道，调制信道一般可以看成是一种信道，编码信道一般可以看成是一种信道2、由控制载波参数的不同，调制可以分为、和三种基本方式3、脉冲编码调制（PCM）方式的模拟信号数字化要经过、和三个过程4、热噪声的频域特性表现为时域特性表现为统计特性表现为5、根据香农公式，当信道容量一定时，信道带宽越宽，则对要求就越小6、调制制度增益G越大，表示性能越好，通常FM的调制制度增益G要AM的调制制度增益G7、由功率谱的数学表达式可知，随机序列的功率谱包括和两大部分8、由于数字调相信号分解为，因此数字调相可以采用来实现9、最大信噪比准则下，最佳线性滤波器又称为10、在调制技术中通常又将幅度调制称为，频率调制和相位调制称为三、某信源集有64个符号，每个符号等概率出现，且统计独立。

现将该信源发送的一系列符号通过带宽为16KHz的信道上进行传输，要求信道的信噪比不小于30dB，试求：（1）信道容量10 （2）无差错传输时最高的传输速率10四、某信源由A、B、C、D四符号组成，它们出现的概率分别为3/16,1/16,1/4,1/2，且每个符号均以二进制脉冲编码，既A-00，B-01,C-10,D-11，已知每脉冲宽度为0.5ms，求（1）该信息源的平均信息量7（2）该信息源的符号速率和信息速率（3）若信息源符号等概出现，则该信息源的信息速率五、在功率谱密度为N0/2的高斯白噪声的背景下，设计一个与下图周期为TB，幅度为A的信号波形相应的匹配滤波器，试求（1）可达到的最大输出信噪比时刻4（2）匹配滤波器的冲激响应和输出信号波形表达式，画出波形13（3）最大输出信噪比3六、已知一（2，1，2）卷积编码器输出与输入的关系为试画出该编码器的实现框图深度为4码树图编码器对应状态图前4个时刻网格图。