《全国硕士研究生入学统一考试计算机专业基础综合真题解析.pdf》由会员分享，可在线阅读，更多相关《全国硕士研究生入学统一考试计算机专业基础综合真题解析.pdf（15页珍藏版）》请在三一文库上搜索。
1、1 / 15 2018年全国硕士研究生入学统一考试 计算机学科专业基础综合试卷 一、单项选择题：140 小题，每小题2 分，共 80 分。下列每题给出的四个选项中，只 有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。b5E2RGbCAP 1已知程序如下： ints(int n return (n ? 0 : s(n-1 +n 。 void main( cout 。 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 Amain(-S(1-S(0 B S(0-S(1-main( p1EanqFDPw Cmain(-S(0-S(1 D S(1-S(0-main(DXD
2、iTa9E3d 【参考答案】D 【考查知识点】栈的基本概念和函数调用的原理。 2 先序序列为a,b,c,d的不同二叉树的个数是 A13B 14C15D16 【参考答案】C 【考查知识点】二叉树的基本概念。 3下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是 A24，10，5 和 24，10，7B24，10，5 和 24，12，7 C24，10，10 和 24，14，11 D24，10，5 和 24，14， 6 【参考答案】C 【考查知识点】哈夫曼树的原理。 4现在有一颗无重复关键字的平衡二叉树 ，顶点集V=V0,V1,V2,V3，边集E=,， , 若从顶点V0
3、 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是 5PCzVD7HxA A2 B3 C4 D5 【参考答案】D 【考查知识点】图的深度优先遍历。 6求下面带权图的最小 B(V1,V4 C(V2,V3 D(V3,V4 【参考答案】A 【考查知识点】最小生成树算法的Prim 算法和 Kruskal 算法。 7下列选项中，不能构成折半查找中关键字比较序列的是 A500，200，450，180 B500，450，200， 180 C180，500，200，450 D180， 200， 500，450 【参考答案】A 【考查知识点】二分查找算法。 8已知字符串S为 “ abaabaabacac
4、aabaabcc” . 模式串t 为 “ abaabc ” , 采用 KMP 算法进行 匹配，第一次出现“ 失配 ”(si != ti 时， i=j=5, 则下次开始匹配时，i 和j 的值分别是 xHAQX74J0X Ai=1，j=0 Bi=5，j=0 Ci=5， j=2 Di=6， j=2 【参考答案】C 【考查知识点】模式匹配 主存与缓存分成相同大小的数据块。(2 主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的 块数与缓存的总块数相等。(3 主存中某区的一块存入缓存时只能存入缓存中块号相 同的位置。rqyn14ZNXI 16假定编译器将赋值语句“ x=x+3 。
5、” 转换为指令 ” add xaddt, 3” ，其中 xaddt 是 x 对应 的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ， 且 Cache 使用直写 kavU42VRUs A8.1ms B12.2ms C16.3ms D20.5ms 【参考答案】B 【考查知识点】磁盘访问时间计算。 21在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口 之间交换的信息不可能是( y6v3ALoS89 A打印字符B主存地址C设备状态D控制命令 【参考答案】A 【考查知识点】程序中断I/O 方式。 22内部异常 (内中断 可分为故障 (f
6、ault 、陷阱 (trap和终止 (abort三类。下列有关内 部异常的叙述中，错误的( M2ub6vSTnP A内部异常的产生与当前执行指令相关 B内部异常的检测由CPU 内部逻辑实现 C内部异常的响应发生在指令执行过程中 D内部异常处理的返回到发生异常的指令继续执行 【参考答案】A 【考查知识点】内部异常概念。 23处理外部中断时，应该由操作系统保存的是( A程序计数器 (PC的内容 B通用寄存器的内容 6 / 15 C块表 (TLB 的内容 DCache中的内容 【参考答案】A 【考查知识点】外部中断处理过程。 24假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内
7、核态 (系统态 的是 ( ADIV R0 ，R1。(R0/(R1 R0 BINT n ；产生软中断 CNOT R0 ；寄存器R0 的内容取非 DMOV R0,addr ；把地址处的内存数据放入寄存器R0 中 【参考答案】C 【考查知识点】CPU 用户态和内核态概念。 25下列选项中会导致进程从执行态变为就绪态的事件是 操作 B申请内存失败 C启动 I/O 设备 D被高优先级进程抢占 【参考答案】D 【考查知识点】进程间各状态的转化。 26若系统S1 采用死锁避免方法，S2 采用死锁检测方法，下列叙述中正确的是 ，且 |data|。现要求设 计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等
8、的节点，仅保留第一次出现 的节点而删除其余绝对值相等的节点。sQsAEJkW5T 例如若给定的单链表head如下 删除节点后的head为 8 / 15 要求 (1给出算法的基本思想 (2使用 c 或 c+语言，给出单链表节点的数据类型定义。 (3根据设计思想，采用c 或 c+语言描述算法，关键之处给出注释。 (4说明所涉及算法的时间复杂度和空间复杂度。 【参考答案】 (1 算法思想： 定义一个大小为N 的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值 的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值 相等的节点，需将此节点删除。GMsIasNXkA
9、(2 节点的数据结构定义如下： typedef struct Node Int data。 Struct Node * next 。 Node 。 (3 int an 。 / 全局数组标志节点的绝对值的值是否出现过 void DeleteABSEqualNode(Node * head memset(a,0,n。 / 初始化为0 if (head = NULL return NULL 。 Node * p = head 。 Node * r = head 。 while (p != NULL 9 / 15 if (aabs(p-data = 1 / 如果此绝对值已经在节点值的绝对值中出现过 /
10、 则删除当前节点 r-next = p-next 。 delete p。 p = r-next 。 else /否则，将数组中对应的元素置1，并将指针指向下一个元素 aabs(p-data = 1。 r = p。 p = p-next 。 return head。 (4只遍历一次链表，所以时间复杂度为O(n ， 因为申请大小为n 的数组，所以空间复杂度为O(n， 写出图 G 的邻接矩阵A( 行、列下标从0开始 (2求 A 2，矩阵 A2中位于 0 行 3 列元素值的含义是什么？ (3若已知具有n(n=2 个顶点的邻接矩阵为B，则 B m(2 非零元素的含义是 10 / 15 什么？ 【参考答案
11、】 (1邻接矩阵为 01100 10011 10010 01101 01030 、左移一位 (left 、右移一位 (right3 种操作，控制信号为 Srop,SR 的输出信号Srout 控制； ALU 可实现直送A(mova 、A 加 B(add、A 减 B(sub、 A 与 B(and 、 A 或 B(or 、非A(not 、 A 加1(inc7 种操作，控制信号为ALUop 。 7EqZcWLZNX 11 / 15 请回答下列问题。 (1图中哪些寄存器是程序员可见的？为何要设置暂存器T？ (2控制信号 ALUop 和 SRop的位数至少各是多少？ (3控制信号 Srout 所控制邮件的
12、名称或作用是什么？ (4端点 中，哪些端点须连接到控制部件的输出端？ (5为完善单总线数据通路，需要在端点中相应的端点之间添加必要的连线。写 出连线的起点和终点，以正确表示数据的流动方向。lzq7IGf02E (6为什么二路选择器MUX 的一个输入端是2？ 【参考答案】 (1) 图中程序员可见的寄存器有通用寄存器 R0R3 和程序计数器PC；设置暂存器T 用 于暂存数据总线发送的数据。zvpgeqJ1hk (2) ALUop 和 SRop 的位数分别为3,2。 (3) Srout 所控制的部件作用是控制计算机运算结果的输出。 (4) 须连接到控制部件的输出端端点有。 (5) ， 。 (6) 使
13、 PC 自增 2 以获取下一条指令地址。 【考查知识点】寄存器相关概念及寄存器的操作，单总线结构 44.该机的指令系统最多可定义多少条指令？ (2假定 inc、shl 和 sub指令的操作码分别为01H、 02H 和 03H，则以下指令对应的机 器代码各是什么？ inc R1 。R1 + 1 R1 shl R2,R1 。 (R1 ,R2 。 (R1 (R2 R3 (3假定寄存器X 的输入和输出控制信号分别为Xin 和 Xout，其值为1 表示有效，为0 表示无效 操作。写出题44 图 a 中标号处的控制信号或控制信号的 取值。1nowfTG4KI (4指令 “ sub R1,R3,(R2”和“
14、 inc R1 ”的执行阶段至少各需要多少个时钟周期？ 【参考答案】 (1) 128 (2) 0280H，04A8H ，06EEH (3) 0，mov，mova，left， read，sub， mov， Srout。 (4) 至少各需要8 和 7 个时钟周期。 【考查知识点】指令的格式与寻址方式，指令执行过程 45. 有 A、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案 和向对方提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件， B 的信箱最多放N 个邮件。初始时A 的信箱中有x 个邮件 从 A 的信箱中取出一个邮件； 回答问题并提出一个新问题；
15、将新邮件放入B 的信箱； B While(TRUE 从 B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱； 14 / 15 Code End 当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。 请添加必要的信号量和P、V P(fullA 。 P(mutexA Get a mail from A_mailbox ； V(mutexA 。 V(fullA 。 Answer the question and raise a question。 P(emptyB。 P(mutexB send the mail to B； V(mutexB 。 V(emptyB 。 B While(TRUE 15 / 15 P(fullB 。 P(mutexB Get a mail from B_mailbox ； V(mutexB 。 V(fullB 。 Answer the question and raise a question。 P(emptyA 。 P(mutexA send the mail to A； V(mutexA 。 V(emptyA 。 Code End 【考查知识点】考察了利用信号量进程同步问题。 申明： 所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。