2017年中科院计算机学科综合(专业)863考研真题
2017 年招收攻读硕士学位研究生入学统一考试试题
科目名称:计算机学科综合(专业)
考生须知:
1. 本试卷满分为150 分, 全部考试时间总计180 分钟。
2.所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效。
一、单项选择题
（选择题太多，没有时间抄写下来。
题目的主要考察内容是数据结构和组成原理）
二、综合应用题
41．物理内存分配的系统，空闲内存块有：
10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB 。
有内存请求序列：12KB,10KB,9KB 。
分别使用首次适应(first fit),循环首次适应(next fit)，最坏适应(worst fit) ，最佳适应(best fit)分配策略进行内存分配。
请问各分配策略使用后的空闲内存块序列？
42. 简述使用了swapping 内存交换技术及分页内存管理的系统，在读取不在物理内存中的某有效虚拟地址的整个过程。
43. 一机器主频是8MHz, 每个机器周期占用4个时钟周期，每条指令执行时间平均是2.5个机器周期。
1）机器的平均指令执行速度是多少MIPS ？
2）机器的主频速度快，那么机器速度就快。这种说法正确吗？为什么？
3）机器的某进程共运行时间是100s ，其中CPU 运行75s ，其余是I/O访问时间。若机器的CPU 速度提升50%，I/O速度不变。该进程需要运行多少时间？
4）如果CPU 和DMA 控制器同时要求总线传输，请问谁的优先级高？为什么？
44. 某机器字长16位，主存空间大小是128KB ，按字编址。
1）请问地址寄存器（MAR ）和数据寄存器（MDR ）各需要多少位？
2）机器若选用8K×16的RAM 芯片，共需要几片？并写出每片RAM 地址范围？
3）机器为协调CPU 与主存的速度使用了Cache ，请问主存与Cache 进行数据交换的基本单位是什么？使用该粒度的原因？
4）若直接映射Cache ，共容量是4KB ，块是8个字，请设计主存的地址格式？
45. （题目的文字及表格较多，没完整抄写下来）
某网络使用OSPF 路由协议，有R 路由器与A 、B 、C 、D 路由器等设备互联，并提供了R 路由器的路由表，和B 路由器的LSA 路由通告。
问题考察的主要是访问某IP 时的下一个跳转点，及R 路由器的路由表根据B 路由器的LSA 路由通告的最短路径原的更新。
46．图G 的邻接矩阵是[ 046∞∞∞∞05∞∞∞∞∞043∞∞
∞∞0∞3∞∞∞∞03∞∞∞∞∞0]
请画出该图。求图G 的关键路径及路径长度。
47．有1000＊1000的稀疏矩阵，其中仅有0.01%非零。
1）设计哈希表作为存储结构，把哈希函数给出。
2）设计查找矩阵的哈希算法，设冲突时用链表法。语言使用C/C++或Java 。
3）在等概率查找下，查找成功的平均查找长度是多少？
北京航空航天大学计算机学院计算机学科专业基础 综合历年考研真题汇编 最新资料，WORD格式，可编辑修改！ 目录 说明：2007～2008的科目名称为“计算机专业综合”，代码分别为461和961；2009～2014年的科目代码与名称为“408计算机学科专业基础综合”；2015年起，科目代码与名称改为“961计算机学科专业基础综合”，本书书名以此为准。
2014年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解 一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。 1．下列程常段的时间复杂度是（） count＝0; for（k＝1;k<＝n; k*2） for（j＝1;j<＝n;j+1） count++; A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2） 【答案】C 【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为log2n；内部循环的退出条件是j>n,对于j，每次循环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog2n），即选C。 2．假设栈初始为空，将中缀表达式a() b c d e f g +*-*转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（） A．(+*- B．(+-* C．(+*-* D．+-* 【答案】B 【解析】中缀表达式转后缀表达式遵循以下原则： （1）遇到操作数，直接输出； （2）栈为空时，遇到运算符，入栈； （3）遇到左括号，将其入栈； （4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号， 左括号不输出； （5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶 元素，然后将该运算符入栈； （6）最终将栈中的元素依次出栈，输出。 所以扫描到’/’，入栈‘描到’+’,由于’+’优先级比’/’低，所以将’/’弹出，’+’入栈；扫描到’*’,优先级比’+’高，入栈；扫描到’（‘,入栈;扫描到’-‘,将栈中优先级更高的’*’弹出，‘-’ 入栈;扫描到’*’,优先级比’-‘高，入栈。所以扫描到f的时候，栈中元素为：(+-*
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）问你此时指令执行时间，第三问问这
中国科学院大学计算机考研经验 1.专业基本情况（含报考人数，录取人数，报录比；） 专业基本情况：对于咱们报考中科院计算机的考生来说，毋容置疑是考863计算机学科综合考试的，其中包含数据结构、计算机网络、计算机操作系统、计算机组成原理四门课，也是我们常说的四大门。 简介：计算所拥有"计算机科学与技术"、"网络空间安全"两个一级学科，包括计算机系统结构、计算机软件与理论、计算机应用技术、信息安全等多个专业方向。可研究大数据、人工智能、计算机视觉、机器学习、图形图像处理、移动计算和可持续计算、并行处理体系结构、分布式操作系统等众多研究方向。 报考人数比例：对于报考中科院计算所的考生每年大约三四百人，如果没有意外，每年进入复试的人数大约是八十人左右，最后录取人数大约五十人左右。根据这个数字，按每年报考三百人，录取五十人计算，报录比为6:1，进入复试的比例为3.75:1。整体来说有点难度，但难度不大。 2. 每年录取分数线是多少，近三年为例； 2019年 复试线总分为：322 录取最低分数线：322 2018年 复试线总分为：304 录取最低分数线：309 2017年 复试线总分为：320 录取最低分数线：321
3. 写出公共课与专业课的官方参考书目； 4. 公共课与专业课的备考经验，今年专业课更改的情况与复习方式； 对于公共课： 数学：是考研的一大关，我们要及早进入数学的复习，第一轮：数学的复习过程是先把课本过一遍，基本知识点弄会，课后习题要做一遍；第二轮：买一本数学复习全书，跟着全书把知识点弄一遍，对应全书的习题要弄懂，特别是例题讲解；第三轮：要做真题，做真题，一定要多做真题，把近十年的真题全做一遍，做懂，做会。 英语：是个长久战，也要尽早进入复习，英语可以报个辅导，跟着老师的步伐走，英语重点在作文和阅读，要多练习，前提肯定是要先过单词的关，多做真题。政治：非常建议报个班，政治是最不好复习的，尤其是自己复习，根本抓不住重点，有老师跟着，可以帮我们提取重点，分析热点。 对于专业课： 首先是复习顺序：建议顺序为数据结构、操作系统、计算机组成原理、计算机网络 对于数据结构是注重逻辑理解，将逻辑结构和物理结构理解透彻，对于每一种数据结构要知道怎么通过顺序存储和链式存储实现，对于涉及数据结构的算法，要理解过程中的每一步；后面三科比较偏文，所以需要识记，操作系统是最为简单的一个科目，需要对操作系统的线程、进程、临界区保护等热点热考的考点理解透彻，识记东西较多；组成原理中需要逻辑理解的内容较多，主要偏重计算机硬件内部结构，以及在硬件上怎么进行计算机执行的，主要还是抓住重点，进行结构和内容的识记；计算机网络虽然内容多，但是能考的考点比较少，所以重点比较突出。 5. 复试的过程与经验。
803计算机学科基础综合 ——此内容为零一教育为您收集整理，如需详细资料可以关注我们的微信公共号（零一计算机圈、零一职业规划） 一、考查目标 计算机学科基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、考试形式和试卷结构 1、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2、答题方式 答题方式为闭卷、笔试。 3、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 4、试卷题型结构 单项选择题80分(40小题，每小题2分) 综合应用题70分 三、考查内容 数据结构 【考查目标】 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) （四）简单选择排序
北京邮电大学2018年专业课803计算机学科基础综合考试大纲 新祥旭考研：十年专注考研一对一辅导 803计算机学科基础综合 一、考查目标 计算机学科基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、考试形式和试卷结构 1、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2、答题方式 答题方式为闭卷、笔试。 3、试卷内容结构 数据结构 45分 计算机组成原理 45分 操作系统 35分 计算机网络 25分 4、试卷题型结构 单项选择题 80分(40小题，每小题2分) 综合应用题 70分 三、考查内容 数据结构 【考查目标】 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)
中国科学院大学2020考研大纲：863计算机学科 综合(专业) 计算机学科综合考研大纲公布了没？考研大纲频道为大家提供中国科学院大学2019考研大纲：863计算机学科综合(专业)，更多考 研资讯请关注我们网站的更新! 中国科学院大学2019考研大纲：863计算机学科综合(专业) 一、考试形式 闭卷，笔试，考试时间180分钟，总分150分。 二、试卷结构 题型：概念题(填空、选择、判断、简答)，应用题(计算、画图、分析、设计)等。 三、考试科目 数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占25%。 四、数据结构 (一)考试大纲 1、绪论 (1)数据结构的基本概念，数据的逻辑结构、存储结构。 (2)算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 (1)线性表的定义、基本操作。 (2)线性表的存储结构(包括顺序存储结构、链式存储结构)及操 作实现。
(3)线性表的应用。 3、栈与队列 (1)栈与队列的基本概念、基本操作。 (2)栈与队列的存储结构(包括顺序存储结构、链式存储结构)及操作实现。 (3)栈与队列的应用。 4、数组和广义表 (1)数组、广义表的基本概念、多维数组的实现。 (2)特殊矩阵(包括对称矩阵、稀疏矩阵)的压缩存储。 5、树与二叉树 (1)树、二叉树、森林的基本概念和性质。 (2)树、二叉树、森林的存储结构(包括顺序存储结构、链式存储结构)。 (3)树、二叉树、森林的遍历和转换操作。 (4)线索二叉树的基本概念和构造。 (5)哈夫曼(Huffman)树和哈夫曼编码。 6、图 (1)图的基本概念和性质。 (2)图的存储结构(包括邻接矩阵、邻接表、十字链表、邻接多重表)。 (3)图的遍历操作(包括深度优先遍历、广度优先遍历)。 (4)图的最小生成树，最短路径，关键路径，拓扑排序。 7、查找
经过一年多的复习艰辛，初试的失望，等待成绩的焦躁不安，复试的忐忑，最终终于如愿以偿考上自己向往的中科院，心中有喜悦也有感恩。一路走来真的不容易，在这里把自己的一些经验和感悟给大家说一下，希望能够帮助后来的考研学子，也是对曾经给过我指导和帮助的热心人的感恩。 首先自我介绍，我是来自一个普通二本里的三本学生，软件工程专业，至于学费我想大家都知道。我今年的考研分数：数学105 英语61 政治70 专业课92 报考学校：中科院计算所。如果你是大牛考名校那就不要参考了，因为，我很平庸，报的也不是大学。而如果你也像我一样不是很优秀，又希望考上全公费另外还有零花钱去旅游得同学，你可以参考。 我的基本情况就是以上那些，在一个普通二本里的三本学习，大家可以想想学习环境，但是我想说，事在人为，只要努力就能改变命运。大学期间担任班长创建社团，连续2年国家励志和一次学校一等奖学金，大学前三年积极参加各种活动，数学建模大赛，IT创新大赛，河南省863软件大赛等活动。专业上领导社团成员并参与三个软件的开发工作。各类级别证书二十多项。我说这些不是炫耀自己，我只是证明，出身在那里不重要，重要的是你努力没有，你奋斗没有，你有没有被现实屈服。我不聪明但我一直在努力。我相信努力可以改变一些命运。所以不论你在那里上学，学校如何，都不要抱怨，而是要问自己是否努力过。Q1：为何选择中科院？ 第一全公费，我的目的很明确，每月1000-2000的补助。远远领先名校奖学金。 第二，就业好，北京的计算所最好也最难考，对我们这样的有点出身歧视。而京外所好点。我报的沈阳计算所，每年毕业不到50人，全部百分之百就业，就在前几天复试时。公寓老师说，你们毕业月薪过万没啥了不起。最好的今年有几个签百度的，据说年薪22w。 第三，复试容易。大学要选导师，这里不用，第一年在中国科技大学或者北京中科院学习一年再回来选导师。复试这几年几乎是百分之百接受。今年生源不好，招收调剂的了，前几年从不招收。所以上线300就能录取。当然这也是我算好的，算定今年分数不高。如何计算，参看我的考研数据分析。 第四，中科院导师每人最多带三个人，一般二个。项目多，做不完的项目。保证培养质量。 第五，无论在那个所上，毕业证学位证全国统一，都是中国科学院授予。没有地方的名字。 第六，生活条件好，除了上学期间不用担心钱不够花外，住宿是宾馆的标间配置，三人间。三个床。缺点：生活单调，有钱没地方花。地理位置偏僻荒凉。不过就在所里一年半，努力学习专业技术也是很好的地方。 Q2：中科院是不是有特殊要求？ 没有任何特殊要求，我们复试很多都是跨考的，比如数学系的，生物的。没有动手能力也不歧视。只要以后肯学，中国科技大学加上中科院会把你调教成专业能手的。相比大学，不用提前联系导师，具有考过初试，就不用再操心的好处。前提分数达到他们所里要求的复试线而不是国家线。 Q3: 能不能推荐几个性比价高的研究所？ 第一，我报考的沈阳计算所。专业研究计算机，数控机床很领先。今年所有学科升级为国家一级学科。首批国家工程博士培养单位。就业100%，就业单位所主页有详细历年介绍。不过分数线比较起伏，但是不管如何都比北京的好考。2013个人预测比国家线多出20分以上，因为今年比较低。估计2014年比国家线多出10分左右。详细情况参考历年数据。 第二，成都计算所，这个单位比较特殊。每年招不满，很大程度上由于专制为企业。其实，研究生培养还是中科院。就业也很好，就是招生的人不如沈阳计算所多。如果你很没有把握，只是抱着过线的心，那就考虑他吧。
北京邮电大学2018年硕士研究生入学考试试题 考试科目：计算机学科基础综合 请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。 ②不允许使用计算器 一、 单项选择题（每小题2分，共80分） 1. 算法分析的作用是 A ．分析算法的效率 B ．分析算法中的输入和输出的关系 C ．分析算法是否正确 D ．分析算法能否转换为计算机语言 2. 设某数据对象(,)DR D R =，其数据元素集合为{}12345,,,,D a a a a a =，关系R 表达为 {}1,|4,3,2,1i i R a a i +==，DR 是 A ．集合结构 B ．线性结构 C. ．树结构 D ．图结构 3. 若线性表最常用的运算是删除第一个元素、在末尾插入新元素，则最适合的存储方式 是 A ．顺序表 B ．带尾指针的单循环链表 C ．单链表 D ． 带头指针的单循环链表 4. 数组通常具有两种基本操作是 A ．插入和删除元素 B ．插入和查找元素 C ．修改和删除元素 D ． 查找和修改元素 5. 已知字符串""pqppqpqp ,它的nextval 数组值是 A ．01021040 B ．01021243 C ．01122240 D ．01122343 6. 一棵二叉树的先序遍历序列为abcde ，中序遍历序列为cbade ，则该二叉树对应的森林 所包含的树的棵树是 A ．1 B ．2 C ．3 D ．5 7. 若高度为n 的二叉树恰有n 个结点，则满足此条件的二叉树树形有 A ．2种 B. 2n 种 C. 12n ? 种 D. 21n ?种 8. n 个顶点的无向连通图用邻接矩阵存储，矩阵中非零元素的个数最少是 A ．2n B ．1n ? C ． n D ．()21n ? 9. 下列关于图的遍历的叙述中，错误的是 A ．图的深度优先遍历不适用于有向图
一、微电子学院简介 中国科学院大学微电子学院成立于2013年，以中科院微电子所为主承办单位，中科院半导体所、中科院上海高研院、中科院上海微系统所、中科院电子所、中科院声学所参与共同建设，覆盖从设计、制造、设备和材料等微电子技术领域的绝大部分学科方向，是目前国内综合研究能力最高，设备最完善，学科覆盖最广的微电子学院，也是首批国家示范性微电子学院建设单位之一。微电子学院硕士研究生招生专业包括：微电子学与固体电子学（080903，由微电子所代招）、电子与通信工程（085208）、集成电路工程（085209）、计算机技术（085211）。 2019年预计招收硕士研究生共240人，实际招生人数以当年度下达的指标数为准。微电子学院欢迎并鼓励学习微电子专业及信息与通信工程类、计算机类、自动化类、软件类、光电技术、物理与应用物理学、材料学等相关专业的同学报考。 二、中国科学院大学计算机技术专业招生情况、考试科目 三、中国科学院大学计算机技术专业分数线 四、中国科学院大学计算机技术专业考研参考书目 856电子线路 1、Robert L.Boylestad, Louis Nashelsky（作者）, 李立华, 李永华(译者)，模拟电子技术，电子工业出版社; 第1版(2008年6月1日)，国外电子与通信教材系列
2、童诗白、华成英，模拟电子技术基础（第五版），高等教育出版社，2015年 3、(美)John F.Wakerly 林生葛红金京林（翻译）数字设计:原理与实践(原书第4版) ，机械工业出版社，2007 年5月 4、阎石，数字电子技术基础（第六版），高等教育出版社，2016年 859信号与系统 郑君里等，《信号与系统》，上下册，高等教育出版社，2011年3月，第三版。 奥本海姆等，《信号与系统》，电子工业出版社，2013，第二版。 863计算机学科综合（专业） 1、计算机网络（第七版）. 谢希仁编著，北京：电子工业出版社，2017年。 五、中国科学院大学计算机技术专业复试原则 1、专业考核 重点考查考生大学学习情况及对专业知识掌握的深度和广度，对知识灵活运用的程度以及考生的实验技能和实际动手能力等，了解考生从事科研工作的潜力和创新能力。专业课复试范围：考核《半导体物理》、《半导体集成电路》、《信号与系统》、《电子线路》等方面的综合基础知识，注重基本概念和知识面。 2、英语听力和口语考核 主要考核考生运用英语知识与技能进行听说交际的能力，由我所组织专家进行考核。听力要求考生能听懂日常生活中的通知、讲话、一般性谈话或讨论等。口语要求考生能用英语回答有关日常生活、家庭、工作、学习等方面的问题，并能就某个话题进行连续性的英语表达。 3、思想政治品德考核 思想政治品德主要考核考生的政治态度、思想表现、道德品质等方面的基本情况。 4、综合素质考核 考核考生的工作学习态度、团队合作精神、人文素养、沟通和交流能力等方面的基本素质。 六、中国科学院大学计算机技术专业录取原则以及录取名单（2018） 总成绩＝初试成绩/5×50％＋复试成绩×50％ 其中，复试成绩＝专业考核×95%＋外语测试×5%，复试总成绩采用百分制，60分为及格。复试成绩不合格者，不予录取。同时参考思想政治品德和综合素质考核。同一类型考生的考核优先级按总成绩（初试＋复试）从高到低依次择优录取，体现第一志愿考生优先的原则。
一、软件研究所简介 中国科学院软件研究所成立于1985年，是一所致力于计算机科学理论和软件高新技术的研究与发展的综合性基地型研究所。 作为中国科学院大学研究生培养单位之一，2019年预计在计算机科学与技术(A+)[ 在全国第四轮学科评估中，计算机科学与技术一级学科被评为A+，软件工程（0835）一级学科被评为A-.]、软件工程(A-)和网络空间安全[ 网络空间安全为2016年新增一级学科。]等一级学科招收79名学术型硕士研究生；在软件工程专业领域招收16名全日制专业学位硕士生。2019年预计招收硕士研究生95人，其中推荐免试研究生70人左右。最终招生人数以正式下达的招生计划文件为准，招收推免生人数以最后推免系统确认的录取人数为准。 二、中国科学院大学计算机应用技术专业招生情况、考试科目 三、中国科学院大学计算机应用技术专业分数线 四、中国科学院大学计算机应用技术专业考研参考书目
863.计算机学科综合（专业） 1、计算机网络（第七版）. 谢希仁编著，北京：电子工业出版社，2017年。 考试要求： 1. 掌握计算机网络的基本概念、基本原理和基本方法； 2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理； 3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。 五、中国科学院大学计算机应用技术专业复试原则 复试成绩＝笔试（含上机考核成绩）成绩×50％＋面试成绩×50％ 思想品德考核（调阅考生档案或政审）及体检不作量化计入总成绩。有严重违纪记录的即视为思想品德考核不合格。 复试采取分组差额复试，复试与录取比例约为1.2:1。复试主要包括： 1）笔试（机试） 主要考核考生对本学科专业理论知识和应用技能掌握程度，利用所学理论发现、分析和解决问题的能力，对本学科发展动态的了解以及在本专业领域发展的潜力等。各复试组可根据情况增加上机实践考核，分数计入笔试成绩（权重为50%）。笔试考试时间2小时（不含上机考核时间）。笔试（含机试）采取百分制，低于60分为不合格。 2）面试 3）面试主要对考生的英语听说能力、专业素养、创新能力和综合素质等进行考查。每个考生的面试时间一般不少于20分钟，其中英语听说能力测试时间5分钟左右。面试计分采取百分制，其中英语听说测试成绩占10%。面试成绩低于60分为不合格。 六、中国科学院大学计算机应用技术录取原则以及录取名单（2018） 考生总成绩＝初试总成绩/5×60％＋复试成绩×40％ 各组根据考生总成绩，按学位类别分别由高到低依次进行拟录取。优先拟录取第一志愿考生。有特殊学术专长或具有突出培养潜质者，以及在科研和相关实践中表现特别突出者，经复试小组提议（附说明材料），所教育领导小组审核同意，可予以优先考虑录取。 凡具有下列情况之一的考生，均不予录取： l 思想品德考核不合格； l 体检不合格； l 复试阶段，笔试（含上机考核）成绩或面试成绩不合格； l
中国科学院大学硕士研究生入学考试 《计算机学科综合(专业)》考试大纲 一、考试形式 闭卷，笔试，考试时间180分钟，总分150分。 二、试卷结构 题型，如：概念题（填空、选择、判断、简答），应用题（计算、画图、分析、设计）等。 三、考试科目 数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占25%。 四、数据结构 （一）考试大纲 1、绪论 （1）数据结构的基本概念，数据的逻辑结构、存储结构。 （2）算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 （1）线性表的定义、基本操作。 （2）线性表的实现及应用，包括顺序存储结构、链式存储结构(单链表、循环链表和双向链表)的构造原理，在两种存储结构上对线性表实施的主要的操作(三种链表的建立、插入和删除、检索等)的算法设计与实现。 3、堆栈与队列 （1）堆栈与队列的基本概念、基本操作。 （2）堆栈与队列的顺序存储结构、链式存储结构的构造原理。 （3）在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现。 4、数组和广义表 （1）数组的概念、多维数组的实现。 （2）对称矩阵和稀疏矩阵的压缩存储。 （3）广义表的基本概念。 5、树与二叉树 （1）树的概念和性质。 （2）二叉树的概念、性质和实现。 （3）二叉树的顺序存储结构和链式存储结构。 （4）遍历二叉树。 （5）线索二叉树的基本概念和构造。 （6）树和森林的存储结构、遍历。 （7）二叉排序树。
（8）平衡二叉树。 （9）哈夫曼(Huffman)树和哈夫曼编码。 6、图 （1）图的基本概念。 （2）图的存储，包括邻接矩阵法、邻接表法。 （3）图的遍历操作，包括深度优先搜索、广度优先搜索。 （4）最小生成树，最短路径，关键路径、拓扑排序算法的原理与实现。 7、文件及查找 （1）数据文件的基本概念、基本操作。 （2）顺序查找法、分块查找法、折半查找方法的原理与实现。 （3）B树及其基本操作、B+树的基本概念。 （4）散列(Hash)表。 （5）字符串模式匹配的算法原理与实现。 8、排序 （1）排序的基本概念。 （2）直接插入排序、折半插入排序、气泡排序、简单选择排序、快速排序、堆排序、二路归并排序、基数排序、外部排序算法的原理、复杂度。 （3）排序算法的应用。 （二）考试要求 1.掌握数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 （三）主要参考书目 1、数据结构（C语言版）. 严蔚敏，吴伟民编著，北京：清华大学出版社，2007年。 五、计算机组成原理 （一）考试大纲 1、计算机系统概论 （1）计算机发展历史 （2）计算机系统层次结构 计算机系统的基本组成，计算机硬件的基本组成，计算机软件和硬件的关系，计算机的工作过程 （3）计算机性能指标 2、数据的表示和运算 (1) 数制与编码 进位计数制及其相互转换，真值和机器数，BCD码，字符与字符串，校验码 (2) 定点数的表示和运算 定点数的表示，定点数的运算（定点数的位移运算，原码定点数的加减运算，补码定点数的加/减运算，定点数的乘除运算，定点数运算器组成） (3) 浮点数的表示和运算 浮点数的表示，IEEE754标准，浮点数的加/减运算，浮点运算器 (4) 算术逻辑单元ALU
中科院计算机技术研究所1998年硕士生入学试题 数据结构和程序设计 (要求：算法题目写注解) 一.填空(15分,每空一分) 1.用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是__和__; 若只设尾指针,则出队和入队的时间复杂度分别是__和__. 2.设广义表L=( (),() ) ,则head(L)是___;tail(L)是___;L的长度是___;深度是___. 3.深度为h的完全二*树至少有__个结点;至多有__个结点;h和结点总数n之间的关系是__. 4.在n个记录的有序顺序表中进行折半查找,最大的比较次数是___. 5.在一棵m阶B+树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是___. 6.n个顶点的连通图用邻接矩阵表示时,该矩阵至少有__个非零元素. 二.请在下列各题中选择一个正确的答案(20分,每题2分) 1.算法的时间复杂度取决于 a.问题的规模 b.待处理数据的初态 c.both a and b 2.消除递归不一定需要使用栈,此说法 a.true b.false 3.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测? a.k-1 b.k c.k=1 d.k(k+1)/2 4.若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是: a.快速排序 b.堆排序 c.归并排序 d.直接插入排序 5.用ISAM和VSAM组织文件属于: a.顺序文件 b.索引文件 c.散列文件 6.若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 a.存在 b.不存在 7.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是 a.n b.2n-1 c.2n d.n-1 8下述二*树中,那一种满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序: a.二*排序树 b.哈夫曼树 c.AVL树 d.堆 9.以知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的个元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下限应为: a.O(klog2(k)) b.O(klog2(n)) c.O(nlog2(k)) d.O(nlog2(n)) 10.在叶子数目和权值相同的所有二*树中,最优二*树定是完全二*树,该说法: a.正确 b.错误
中国科学院大学 2017 年招收攻读硕士学位研究生入学统一考试试题科目名称:计算机学科综合(专业) 考生须知: 1.本试卷满分为 150 分,全部考试时间总计 180 分钟。 2.所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。 一、单项选择题 （选择题太多，没有时间抄写下来。 题目的主要考察内容是数据结构和组成原理） 二、综合应用题 41．物理内存分配的系统，空闲内存块有： 10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB。 有内存请求序列：12KB,10KB,9KB。 分别使用首次适应(first fit),循环首次适应(next fit)，最坏适应(worst fit)，最佳适应(best fit)分配策略进行内存分配。 请问各分配策略使用后的空闲内存块序列？ 42.简述使用了swapping内存交换技术及分页内存管理的系统，在读取不在物理内存中的某有效虚拟地址的整个过程。 43.一机器主频是8MHz, 每个机器周期占用4个时钟周期，每条指令执行时间平均是2.5个机器周期。 1）机器的平均指令执行速度是多少MIPS ？ 2）机器的主频速度快，那么机器速度就快。这种说法正确吗？为什么？
3）机器的某进程共运行时间是100s，其中CPU运行75s，其余是I/O访问时间。若机器的CPU速度提升50%，I/O速度不变。该进程需要运行多少时间？4）如果CPU和DMA控制器同时要求总线传输，请问谁的优先级高？为什么？ 44.某机器字长16位，主存空间大小是128KB，按字编址。 1）请问地址寄存器（MAR）和数据寄存器（MDR）各需要多少位？ 2）机器若选用8K×16的RAM芯片，共需要几片？并写出每片RAM地址范围？ 3）机器为协调CPU与主存的速度使用了Cache，请问主存与Cache进行数据交换的基本单位是什么？使用该粒度的原因？ 4）若直接映射Cache，共容量是4KB，块是8个字，请设计主存的地址格式？ 45.（题目的文字及表格较多，没完整抄写下来） 某网络使用OSPF路由协议，有R路由器与A、B、C、D路由器等设备互联，并提供了R路由器的路由表，和B路由器的LSA路由通告。 问题考察的主要是访问某IP时的下一个跳转点，及R路由器的路由表根据B 路由器的LSA路由通告的最短路径原的更新。 46．图G的邻接矩阵是 [046∞∞∞∞05∞∞∞∞∞043∞∞∞∞0∞3∞∞∞∞03∞∞∞∞∞0] 请画出该图。求图G的关键路径及路径长度。 47．有1000＊1000的稀疏矩阵，其中仅有0.01%非零。1）设计哈希表作为存储结构，把哈希函数给出。
2017年中科院计算机学科综合(专业)863考研真题 2017 年招收攻读硕士学位研究生入学统一考试试题 科目名称:计算机学科综合(专业) 考生须知: 1. 本试卷满分为150 分, 全部考试时间总计180 分钟。 2.所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效。 一、单项选择题 （选择题太多，没有时间抄写下来。 题目的主要考察内容是数据结构和组成原理） 二、综合应用题 41．物理内存分配的系统，空闲内存块有： 10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB 。 有内存请求序列：12KB,10KB,9KB 。 分别使用首次适应(first fit),循环首次适应(next fit)，最坏适应(worst fit) ，最佳适应(best fit)分配策略进行内存分配。 请问各分配策略使用后的空闲内存块序列？ 42. 简述使用了swapping 内存交换技术及分页内存管理的系统，在读取不在物理内存中的某有效虚拟地址的整个过程。 43. 一机器主频是8MHz, 每个机器周期占用4个时钟周期，每条指令执行时间平均是2.5个机器周期。 1）机器的平均指令执行速度是多少MIPS ？ 2）机器的主频速度快，那么机器速度就快。这种说法正确吗？为什么？ 3）机器的某进程共运行时间是100s ，其中CPU 运行75s ，其余是I/O访问时间。若机器的CPU 速度提升50%，I/O速度不变。该进程需要运行多少时间？
4）如果CPU 和DMA 控制器同时要求总线传输，请问谁的优先级高？为什么？ 44. 某机器字长16位，主存空间大小是128KB ，按字编址。 1）请问地址寄存器（MAR ）和数据寄存器（MDR ）各需要多少位？ 2）机器若选用8K×16的RAM 芯片，共需要几片？并写出每片RAM 地址范围？ 3）机器为协调CPU 与主存的速度使用了Cache ，请问主存与Cache 进行数据交换的基本单位是什么？使用该粒度的原因？ 4）若直接映射Cache ，共容量是4KB ，块是8个字，请设计主存的地址格式？ 45. （题目的文字及表格较多，没完整抄写下来） 某网络使用OSPF 路由协议，有R 路由器与A 、B 、C 、D 路由器等设备互联，并提供了R 路由器的路由表，和B 路由器的LSA 路由通告。 问题考察的主要是访问某IP 时的下一个跳转点，及R 路由器的路由表根据B 路由器的LSA 路由通告的最短路径原的更新。 46．图G 的邻接矩阵是[ 046∞∞∞∞05∞∞∞∞∞043∞∞ ∞∞0∞3∞∞∞∞03∞∞∞∞∞0] 请画出该图。求图G 的关键路径及路径长度。 47．有1000＊1000的稀疏矩阵，其中仅有0.01%非零。 1）设计哈希表作为存储结构，把哈希函数给出。 2）设计查找矩阵的哈希算法，设冲突时用链表法。语言使用C/C++或Java 。 3）在等概率查找下，查找成功的平均查找长度是多少？
《计算机学科综合(专业)》考试大纲 一、考试形式 闭卷，笔试，考试时间180分钟，总分150分。 二、试卷结构 题型，如：概念题（填空、选择、判断、简答），应用题（计算、画图、分析、设计）等。 三、考试科目 数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占25%。 四、数据结构 （一）考试大纲 1、绪论 （1）数据结构的基本概念，数据的逻辑结构、存储结构。 （2）算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 （1）线性表的定义、基本操作。 （2）线性表的实现及应用，包括顺序存储结构、链式存储结构(单链表、循环链表和双向链表)的构造原理，在两种存储结构上对线性表实施的主要的操作(三种链表的建立、插入和删除、检索等)的算法设计与实现。 3、堆栈与队列 （1）堆栈与队列的基本概念、基本操作。 （2）堆栈与队列的顺序存储结构、链式存储结构的构造原理。 （3）在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现。 4、数组和广义表 （1）数组的概念、多维数组的实现。 （2）对称矩阵和稀疏矩阵的压缩存储。 （3）广义表的基本概念。 5、树与二叉树 （1）树的概念和性质。 （2）二叉树的概念、性质和实现。 （3）二叉树的顺序存储结构和链式存储结构。 （4）遍历二叉树。 （5）线索二叉树的基本概念和构造。 （6）树和森林的存储结构、遍历。 （7）二叉排序树。 （8）平衡二叉树。 （9）哈夫曼(Huffman)树和哈夫曼编码。
6、图 （1）图的基本概念。 （2）图的存储，包括邻接矩阵法、邻接表法。 （3）图的遍历操作，包括深度优先搜索、广度优先搜索。 （4）最小生成树，最短路径，关键路径、拓扑排序算法的原理与实现。 7、文件及查找 （1）数据文件的基本概念、基本操作。 （2）顺序查找法、分块查找法、折半查找方法的原理与实现。 （3）B树及其基本操作、B+树的基本概念。 （4）散列(Hash)表。 （5）字符串模式匹配的算法原理与实现。 8、排序 （1）排序的基本概念。 （2）直接插入排序、折半插入排序、气泡排序、简单选择排序、快速排序、堆排序、二路归并排序、基数排序、外部排序算法的原理、复杂度。 （3）排序算法的应用。 （二）考试要求 1.掌握数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 （三）主要参考书目 1、数据结构（C语言版）. 严蔚敏，吴伟民编著，北京：清华大学出版社，2007年。 五、计算机组成原理 （一）考试大纲 1、计算机系统概论 （1）计算机发展历史 （2）计算机系统层次结构 计算机系统的基本组成，计算机硬件的基本组成，计算机软件和硬件的关系，计算机的工作过程 （3）计算机性能指标 2、数据的表示和运算 (1) 数制与编码 进位计数制及其相互转换，真值和机器数，BCD码，字符与字符串，校验码 (2) 定点数的表示和运算 定点数的表示，定点数的运算（定点数的位移运算，原码定点数的加减运算，补码定点数的加/减运算，定点数的乘除运算，定点数运算器组成） (3) 浮点数的表示和运算 浮点数的表示，IEEE754标准，浮点数的加/减运算，浮点运算器 (4) 算术逻辑单元ALU 串行加法器和并行加法器，算术逻辑单元ALU的功能和结构 3、存储器系统
2019年中国科学院大学862计算机学科综合(非专业)考研初试大纲 《计算机学科综合(非专业)》考试大纲 本《计算机学科综合(非专业)》考试大纲适用于中国科学院大学非计算机科学与技术一级学科下各专业的硕士研究生入学考试。《计算机学科综合(非专业)》主要内容包括数据结构、操作系统和计算机网络三大部分。要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的理解;掌握各种数据结构的定义和实现算法;掌握操作系统和计算机网络所涉及的关键内容，并具有综合运用所学知识分析问题和解决问题的能力。 一、考试内容 数据结构 1、绪论 (1)数据结构的基本概念，数据的逻辑结构、存储结构。 (2)算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 (1)线性关系、线性表的定义，线性表的基本操作。 (2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。 3、堆栈与队列 (1)堆栈与队列的基本概念、基本操作。 (2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。 (3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。 4、串
(1)串的基本概念、串的基本操作和存储结构。 (2)串的模式匹配算法和改进的KMP算法 5、数组和广义表 (1)数组的概念，以及表示和实现 (2)矩阵(对称矩阵和稀疏矩阵)的压缩存储 (3)广义表的基本概念 6、树与二叉树 (1)树的定义和性质 (2)二叉树的概念、性质和实现 (3)遍历二叉树和线索二叉树 (4)树和森林 (5)赫夫曼树及其应用 (6)回溯法与树的遍历 (7)树的计数 7、图 (1)图的定义，基本概念，图的分类，常用名词术语。 (2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。 (3)图的遍历操作。 (4)图的连通性、最小生成树 (5)最短路径的计算 (6)AOV网与拓扑排序。 8、查找