2018复旦大学计算机考研专业课复习解答

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【考查知识点】图的深度优先遍历。

一、单项选择题： 1-40 题，每题 20 分共 80 分。

在每个小题给出的四个选项中 选正确答案。

1 、若元素 a 、b 、c 、d 、e 、f 依次进栈，允许进栈、退栈操作交替进行，但不允 许连续三次进行退栈工作，则不可能得到的出栈序列是（）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可 能得到的顺顺序是（）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（） 在下列所示的平衡二叉树中插入关键字 48后得到一棵新平衡二叉树， 在新平 衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（）在一棵度数为4的树T 中，若有20个度为4的结点，10个度为3的结点，1 个度为2的结点，10个度为1的结点，则树T 的叶结点个数是（） A 、 dcebfa B 、 cbdaef C 、 bcaefd D 、afedcb 2、 A 、 bacde B 、 dbace C 、 dbcae D 、ecbad 3、4、A 、 13， 48B 、 24， 48C 、 24， 53D 、24， 90 5、A 、 41B 、 82C 、113D 122 &对n （n>=2）个权值均不相同的字符构成哈弗曼树，关于该树的叙述中，错误的是（）该树一定是一棵完全二交叉树中任一非叶结点的权值一定不小于下一层任一结点的权值若无向图G=（V.E ）中含7个顶点，则保证图G 在任何情况下都是连通的, 则需要的边数最少是（）A 、21对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）B 、C 、已知一个长度为16的顺序表L ,其元素按关键字有序排列，若采用折半查找 法查找一个不存在的元素，则比较次数最多的是（）B 、C 、B 、 树中一定没有度为1的结点C 、 树中两个权值最小的结点一定是兄弟结点7、 B 、 15 C 、16 8、 9、10、采用递归方式对顺序表进行快速排序， 下列关于递归次数的叙述中，正确的 是 递归次数于初始数据的排列次数无关每次划分后，先处理较长的分区可以减少递归次数（勤思考研）递归次数与每次划分后得到的分区处理顺序无关第一趟：2, 12, 16, 5, 第二趟：2, 12, 5, 10, 第三趟：2, 5, 10, 12, 则采用的排序方法可能是 A. 冒泡排序法 B. 希尔排序法 C. 归并排序法D. 基数排序法 12.下列选项中，能缩短程序执行时间的措施是（） 1.提高CPU 时钟频率2.优化通过数据结构3.优化通过程序 A. 仅1和2 B. 仅1和3 C, 仅2和3 D. 1,2,313. 假定有4个整数用8位补码分别表示r 仁FEH r2=F2H, r3=90H , r4=F8H,若将运算结果存放在一个8位寄存器中，则下列运算会发生益处的是（）A. r1 x r2B. r2 x r3C. r1 x r4D. r2 x r4 14.假定变量i ,f,d 数据类型分别为int, float,double （i nt 用补码表示，float和double 用IEEE754单精度和双精度浮点数据格式表示），已知i=785 ,()B 、C 、 每次划分后，先处理较短的分区可以减少递归次数11、对一组数据（2，12, 16, 88, 5, 10）进行排序，若前三趟排序结果如下：（）10， 16, 8888 88f=1.5678e3 , d=1.5e100,若在32位机器中执行下列关系表达式，则结果为真的是（）(I)i==( in t)(float)l (ll)f==(float)(i nt)f (lll)f==(float)(double)f(IV)(d+f)-d==fA. 仅l和llB. 仅l和lllC. 仅ll和lllD. 仅lll和lV15.假定用若干个2K x 4位芯片组成一个8K x 8为存储器，则0B1FH所在芯片的最小地址是（）A.OOOOHB.0600HC.0700HD.0800H16.下列有关RAM和ROM得叙述中正确的是（） l RAM是易失性存储器，ROM是非易失性存储器II RAM和ROM都是采用随机存取方式进行信息访问Ill RAM 和ROlW可用做CacheIV RAM和ROMP需要进行刷新A.仅I和IIB.仅II 和IllC.仅I , II , Ill精选文库D.仅II , III , IV17.下列命令组合情况，一次访存过程中，不可能发生的是（）A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中，Cache命中，Page未命中18.下列寄存器中，反汇编语言程序员可见的是（）A.存储器地址寄存器（MAR）B.程序计数器（PC）C.存储区数据寄存器（MDR）D.指令寄存器（IR）19.下列不会引起指令流水阻塞的是（）A.数据旁路B.数据相关C.条件转移D.资源冲突20.下列选项中的英文缩写均为总线规范的是（）A. PCI、CRT USB EISAB. ISA、CPI、VESA EISAC. ISA、SCSk RAM MIPSD. ISA、EISA、PCI、P CI-Ex press21、单级中断系统中, 中断服务程序执行顺序是（）I保护现场II开中断III关中断IV保存断点V中断事件处理VI恢复现场VII 中断返回A、I->V->VI->II->VIIB、III->I->V->VIIC、III->IV->V->VI->VIIIV->I->V->VI->VII22、假定一台计算机的显示存储器用DRAMS片实现，若要求显示分辨率为1600*1200,颜色深度为24位，帧频为85HZ现实总带宽的50卿来刷新屏幕, 则需要的显存总带宽至少约为（）A、245Mb psB、979Mb psC、1958Mb ps7834Mb ps23、下列选项中，操作S提供的给应程序的接口是（）A、系统调用B、中断C、库函数原语24、下列选项中，导制创进新进程的操作是（）I用户登陆成功II设备分配III启动程序执行A、仅I和IIB 、仅 II 和 IIIC 、仅I 和IIID I 、 II 、 III25、设与某资源相关联的信号量初值为 3,当前值为1,若M 表示该资源的可用 个数， 0，1, 2,26、下列选项中，降低进程优先权级的合理时机是（） 进程长期处于就绪列队 进程从就绪状态转为运行状态27、进行PO 和P1的共享变量定义及其初值为（） booleam flag[2] 。

本科华科电信，12年考上交电子系失败收场，之后找工作到某运营商，在工作期间跨考复旦大学计算机专业硕士成功录取，初试359，复旦计算机专硕考数学一专业课408 英语二政治，各科分数分别是111 111 75 62，初试成绩至少是专硕前五，初试和学硕的区别就是英语。

自觉得我的考研路有点特别，但是两次考研的经历有些感悟，希望和大家分享，希望对大家有启发。

一、是否考研是否决定考研需要根据自己的具体情况，想好自己要走的路。

如果是单纯想多学点东西，想进入IT行业，能入行就可以考虑直接工作了，工作中学到实用的东西绝对比读研多。

如果要搞学术，优先考虑出国，其次是国内读研读博。

如果是要进入体制内或其他对学历有硬性要求的地方，一些学历可以转化为职称的地方，那就刷学历吧。

如果想去大型IT公司又绝对没实力想在学校继续深造的可以考虑考研。

还有学历情结、名校情结等等原因。

我的情况是大四的考研失利导致错失找工作的最佳时期，进入运营商做后台，对工作不满想通过考研换专业换行业，提升自己专业能力的，其实最佳选择或许是本科找份合适的工作。

好了，先思考一下是否要考研，如果你决定考研了再往下看。

二、考研专业本科电子信息工程跨考计算机。

本身对电信的核心专业课就没有感觉。

第一次的考研失利及在运营商的工作经历让我对通信失去兴趣，当前互联网行业发展迅速，自身对计算机也比较兴趣，决定考研计算机。

总之，是要根据自己的兴趣和能力等具体情况选择。

PS.个人觉得当前最好的行业是金融，工科跨考金融的同学都令我佩服不已。

三、学硕专硕国家政策上是希望学硕做科研，专硕搞工程项目，实际中现在学硕和专硕的区别越来越小，实际最大的区别就是“钱”和“时间”！就是专硕学制短、奖学金少。

一些学校的某些专业已经一视同仁了，具体情况看学校的专业。

大趋势是学硕和专硕的待遇趋于一致，近些年但是一直在变化。

复旦计算机学硕3年，专硕2.5年，专硕奖学金少。

考学硕过专硕线科研调剂到专硕。

某年1.根据给出的文法写描述相应的语言，判断是否为二义S->aSbs|bSaS|ε；是二义，例：abab2.计算条件概率(全概率公式,做火车飞机轮船。

分别×××，迟到概率×××，已知迟到了，求坐火车来的概率）3.计算一定数量的指令通过给出的一条流水线的时间，计算吞吐量和最大吞吐量（已知流水线4ns一段，共5段，先16条指令通过，完毕后再26条通过）4.用差分法推导一个多项式的递归计算方法，说明这种算法的优点f(t)=(at^3+bt^2+ct+d) ti=i/n(i=1,2,3,....n)5.一个1024*16K的存储器，用DDR和EPROM两种芯片构成，前者占四分之三，两种芯片的大小各为128*8位，128*16位，计算两种芯片各要多少片，EPROM 的首地址是多少？6.考欧拉图给一张图，最少添几条线成为欧拉图。

有几种画法？(找奇数顶点）7.证明一个代数系统是群，判断正规子群G={(x,y)|x不为0, x,y都属于R},定义运算(x,y)●(z,w)=(xz,xw+y)证明[G;●]是群。

H={(1,y)|y属于R},是不是G的正规子群？8，9.软件测试有关的问题，软件结构设计的问题（选择）10.文件系统中冗余的概念和关系数据库中冗余的概念（具体是问：文件系统中不可消除的数据冗余；关系数据库中应该避免的数据冗余）11.分布式数据库中的三层透明性是什么（写出名词即可）12.两个NP语言L1,L2的并和差是否属于NP，证明或举反例~~是~~不是13.移动窗口协议端对端延迟1.25s,已知带宽*Mbps,每个帧的容量1KB,若要充分利用，应该为帧安排几位的序号字段？14.描述一个X86系统中的中断处理过程，主要是根据中断向量N和中断向量表来查中断处理子程序的入口USEINT.（写出过程，实模式or保护模式任选）1.G={(a,b)|a<>0} H={(1,x)} 在G中定义运算(x,y)*(w,z)=(xw,xz+y)求证H为G的正规子群2. 原理：一个32位浮点数分S, M, E三段，其值为(-1)^S * 1.M* 2^(E-128) ;问最大、小正负数分别是多少，且给出二进制表示。

进京赶考之复试（一）此刻坐在回归阜阳的火车上，似乎恢复了平静，心里有很多话要说，呵呵，只是想随便写点什么，恩恩，我喜欢的流水账。

从11号下午官网公布院系分数线，到13号下午报到，着实让我各种措手不及。

又期待又害怕的复试终于来了。

想想12号还真是丰富的一天呢，甚至都来不及向张老师、葛老师道谢！阿丹三姐夫和陪我买衣服；不点桂林请吃饭（祝贺面试取得第一名的好成绩，你俩好好地啊）；丫头们各种鼓励和支持；善良的媳妇带我去吃晚饭，我知道，我从来都不是一个人在奋斗！终于一个人拎着大包小包到了火车站，那治安、那戒备，哎哟喂，不错啊。

言归正传，额，晚上的火车，我决定不跟周围的人过分的热络，（用室友的话说，我就是话唠，和谁都有聊不完的天），一个人抱着电脑看看专业课，我是多认真的从教育学原理看到中教史跳过外教史看教育心理学和教育研究方法啊，（实践证明，我又一次巧妙地忽略重点有木有），还好给力的是，身边坐了五个男生，一点都不养眼，我就可以专心看书了，掠过奇葩男的搭讪。

还好有个学妹比我提前到北京（原谅我不能说出她的名字），这给了我一种无形的安全感。

因为抱着电脑看了一夜，早上实在困得不行，昏昏欲睡的状态在火车进站时才有所缓解，学妹给我发信息，乘坐387路公交，到明光桥北站下车，她因为要去打探专业复试信息，我们学校的一个进修老师接的我，我第一次为如此霸道的之路方式而折服，专业适合路痴二十年啊。

短信内容：“明光桥北站下车后直行100米左右，进入北邮西门入校园，进门后左转100米左右再右转直行，从北邮校园穿至其东门，对面就是师大西门，我去那儿接你”，啊啊，我竟然神奇般的找到了。

（火车站47路是直接可以到师大东门的，但是离住的地方很远）。

L老师真是人才，把我送到宾馆，交代了一些话后，就让我好好休息，超级感动啊！这三天真是麻烦老师了！匆忙洗漱，激动了一会倒下就睡着了，迷迷糊糊中听到一阵急促的敲门声，半晌未果，就隐隐约约的传来断断续续的啜泣声，刚开始以为是男女朋友吵架呢，就选择性忽略了，可是声音越来越大，使我不由得纠结起来，问还是不问？人生地不熟的地，还是不要多管闲事了吧？！用被子把头蒙上，竟会有种于心不忍的感觉，于是起身开门，隔壁的一看起来很小的女孩蹲在地上哭，她当时背着书包，下意识的联想到复试，果不其然，心理学面试刚结束，我把她带进房间，给她倒了一杯水，这孩子竟然哭的更厉害了，好吧，我就安静的让她发泄一会儿。

2018年复旦大学硕士研究生入学考试试题960回忆版（注意：所有的阿拉伯数字标号不是确切题号，仅作为分隔题目使用）数据结构部分一、填空题（一空2分）1、三对角矩阵元素地址的计算：求三对角矩阵（行优先存储）A[1...100，1...100]中的第66行第65列元素在一维数组B[1...258]中的位置；2、考察一个字符序列的KMP失效序列；3、顺序队列假溢出判断条件,队列存在[0....m-1]的数组中（front初始为-1）；4、度为K的树，1个n1,2个n2...k个nk,求叶节点个数；5、线索二叉树（前序、中序、后序都要懂，才能根据题目做出判断）；根结点右子树的最左的无左子树结点的前驱是根结点左子树最右无右子树的结点，问这棵树不可能是一颗________序线索化二叉树；6、AVL树RL型旋转（其它三种也得会）；7、哈希表n个同义词冲突用线性探测法，求总的查找和比较次数；8、快速排序，堆排序，归并排序的空间复杂度从优到劣依次是_____；9、n个结点的有向图，图是连通的，那么图中至少有多少条边；10、对邻接矩阵存储的图，BFS的时间复杂度；二、简答题1、两个字符串S1,S2的长度分别为m（主串）,n（子串），利用KMP算法求出最大的公共序列；推导复杂度（4分）；2、给段代码让判断是否可以正确的得到一个带权无向图的最小生成树（破圈法）；3、迪杰斯特拉算法填空；（一空2分，共5个空10分）；4、装填因子0.75，10个关键字，冲突后用链地址法处理，用除留余数法自己构造哈希函数，画哈希表，并计算查找成功和不成功时的平均查找长度；5、AVL树本来平衡，然后查找K失败，插入K后一定会使得树高增加吗？为什么？6、n个关键字，只要求得到排序后的前k（n>>k）个最小值，问在希尔排序，快速排序，插入排序、堆排序....这些排序算法中选哪个好，为什么；给定一个序列，只要排序后的前两个数，用你之前选择的排序算法计算总的比较次数；三、算法设计题（每题15分）1、在AVL树中，设计一个用非递归的方法从大到小输出所有关键值不小于给定值x的结点信息，代码要给出注释，说明算法思想。

2018年复旦大学计算机系计算机技术考研考试科目、招生人数招生院系：计算机科学技术学院
院系说明：本院拟招收学术学位推免生35人，拟招收专业学位推免生36人。

专业代码085211专业名称(专业学位)计算机技术招生人数158
研究方向01 (全日制)软件工程与系统软件
02 (全日制)网络与信息安全
03 (全日制)数据科学与数据工程
04 (全日制)智能媒体计算
05 (全日制)人机交互与协同计算
06 (全日制)应用算法与应用密码
07 (全日制)智能信息处理
08 (全日制)大数据技术与应用
09 (全日制)临床医学信息处理
考试科目①101思想政治理论②204英语二③302数学二④960计算机专业知识复试科目
计算机专业知识考试方式口试
计算机编程上机考试考试方式实验同等学力加试科目
软件工程考试方式笔试
算法设计与分析考试方式笔试复试成绩占入学考
试总成绩权重
50%
1.外语口语（含听力）为复试必考科目，思想政治品德、思维表达能力等也均为复试必备注
须考核项目。

2018考研专业课知识点解析：计算机数据结构复习从计算机统考大纲数据结构部分及其相关知识点可以看出：数据结构占了45分，和计算机组成原理部分同一个比重，这足以体现计算机专业研究生选拔对数据结构课程的重视程度。

针对这样的情况，相关专家为我们的考生们精心准备了一些数据结构复习的建议。

统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现；能够对算法进行基本的时间复杂度和空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JA V A语言设计程序与实现算法的能力。

当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。

下面我们来解析一下知识点：线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。

链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。

栈、队列和数组可以考查的知识点相比链表来说要多一些。

最基本的，是栈与队列FILO 和FIFO的特点。

比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。

其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。

再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。

这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。

复旦大学考研常见问题汇总——报考复旦，这些考研常识需提前知晓！关于考研，你或许会有这些疑惑：暑假来了，该如何复习？硕士报名及现场确认有哪些问题需要注意？硕士全日制与非全日制有何区别，不甚了解？学校、专业该怎么选？学硕与专硕又有什么不同？（要知道，专业硕士是在09年之后才有的，学硕和专硕有一定的差别，总结起来就是学硕用于学术研究，专硕更适用于实践在工作中。

）等等这些问题，鸿知复旦考研网（）都为有需要的你做了解答。

考研是场持久战，亦是一场信息战，了解各种考研资讯与考研常识，是考研成功必不可少的准备之一。

本网站还有更详细的关于复旦你想知道的各种信息，例如：复旦大学有几个校区，地址在何处？复旦大学的重点学科是什么，排名如何？复旦历年研究生学费及各类奖学金的情况等等。

欲知更多复旦大学考研真题资料，请点击进入【复旦考研真题答案】。

【先睹为快】一、2019考研新变化有哪些？1.招生人数和报考人数都增高此前，教育部公布的《学位与研究生教育发展“十三五”规划》中指出：中国2020年将建成亚太区域研究生教育中心，在学研究生总规模将达到290万人，千人注册研究生数达到2人，专业学位硕士招生占比达60%左右。

保持研究生规模适度增长，以此计算，此后每年的研究生扩招增幅近5%。

增幅5%这个数据是如何得出的呢？以2017年为例来看一下：2017年全年研究生教育招生80.5万人，在学研究生263.9万人（包括推免和博士），毕业生57.8万人。

根据2020年在读研究生招生290万人，按此推算，每年招生人数的增幅近5%。

同时，报考人数的数据却是这样的：全国考研人数总数：2016年全国考研人数177万，2017年较16年增长24万达到201万，2018年较2017年增长37万达到238万，加上考研的热度一直飙升，有人预计2019考研人数将可能达到280万。

2.学硕难度加大，专硕越来越热从“十二五”规划开始，教育部即提出积极发展专业硕士研究生教育，且在招生名额上有所倾斜，所以专硕规模扩大是必然趋势。