1、2015 年考研计算机专业（基础综合）真题试卷及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 已知程序如下：int S(int n)return(n=0)?0：S(n-1)+n ，void main()coutS(1)；程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是_。（A）main()S(1)S(0)（B） S(0)S(1)main()（C） main()S(0)S(1)（D）S(1)S(0)main()2 先序序列为 a，b，c ，d 的不同二叉树的个数是 _。（A）13（B）
2、14（C） 15（D）163 下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_。（A）24，10，5 和 2，4，10，7（B） 24，10，5 和 24，12，7（C） 24，10，10 和 24，14，11（D）24，10，5 和 24，14，64 现有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是_。（A）根结点的度一定为 2（B）树中最小元素一定是叶结点（C）最后插入的元素一定是叶结点（D）树中最大元素一定是无左子树5 设有向图 G=(V，E)，顶点集 V=V0，V 1，V 2，V
3、 3，边集E=V 0，V 1，V 0， V1，V 0，V 3，V 1，V 3。若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是_。（A）2（B） 3（C） 4（D）56 求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是_。（A）(V 1，V 3)（B） (V1，V 4)（C） (V2，V 3)（D）(V 3，V 4)7 下列选项中，不能构成折半查找中关键字比较序列的是_。（A）500，200，450，180（B） 500，450，200，180（C） 180，500，
4、200，450（D）180，200，500，4508 已知字符串 S 为“abaabaabacacaabaabcc“，模式串 t 为“abaabc“ 。采用 KMP 算法进行匹配，第一次出现“ 失配 ”(sitj)时，i=j=5，则下次开始匹配时，i 和 j 的值分别是_。（A）i=1 ，j=0（B） i=5，j=0（C） i=5，j=2（D）i=6 ，j=29 下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是_。（A）直接插入排序（B）起泡排序（C）基数排序（D）快速排序10 已知小根堆为 8，15，10，21，34，16，12，删除关键字 8 之后需重建堆，在此过程中，关键字之
5、间的比较次数是_。（A）-1（B） 2（C） 3（D）411 希尔排序的组内排序采用的是_。（A）直接插入排序（B）折半插入排序（C）快速排序（D）归并排序12 计算机硬件能够直接执行的是_。机器语言程序汇编语言程序硬件描述语言程序（A）仅（B）仅 、（C）仅 、（D）、13 由 3 个“1”和 5 个“0”组成的 8 位二进制补码，能表示的最小整数是 _。（A）-126（B） -125（C） -32（D）-314 下列有关浮点数加减运算的叙述中，正确的是_。对阶操作不会引起阶码上溢或下溢右规和尾数舍入都可能引起阶码上溢左规时可能引起阶码下溢尾数溢出时结果不一定溢出（A）仅、（B）仅 、（C）
6、仅 、（D）、15 假定主存地址为 32 位，按字节编址，主存和 Cache 之间采用直接映射方式，主存块大小为 4 个字，每字 32 位，采用回写(Write Back) 方式，则能存放 4K 字数据的 Cache 的总容量的位数至少是_。（A）146k（B） 147K（C） 148K（D）158K16 假定编译器将赋值语句“x=x+3 ；“转换为指令“add xaddr，3“，其中 xaddr 是 x对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的 TLB，且 Cache 使用直写(Write Through)方式，则完成该指令功能需要访问主存的次数至少是_。
7、（A）0（B） 1（C） 2（D）317 下列存储器中，在工作期间需要周期性刷新的是_。（A）SRAM（B） SDRAM（C） ROM（D）FLASH18 某计算机使用 4 体交叉编址存储器，假定在存储器总线上出现的主存地址(十进制)序列为 8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生访存冲突的地址对是_。（A）8004 和 8008（B） 8002 和 8007（C） 8001 和 8008（D）8000 和 800419 下列有关总线定时的叙述中，错误的是_。（A）异步通信方式中，全互锁协议最慢（B）异步通信方式中，非互锁协议的可靠性
8、最差（C）同步通信方式中，同步时钟信号可由各设备提供（D）半同步通信方式中，握手信号的采样由同步时钟控制20 若磁盘转速为 7200 转分，平均寻道时间为 8ms，每个磁道包含 1000 个扇区，则访问一个扇区的平均存取时间大约是_。（A）81ms（B） 122ms（C） 163ms（D）205ms21 在采用中断 IO 方式控制打印输出的情况下，CPU 和打印控制接口中的 IO端口之间交换的信息不可能是_。（A）打印字符（B）主存地址（C）设备状态（D）控制命令22 内部异常(内中断) 可分为故障(fault)、陷阱(trap)和终止(abort) 三类。下列有关内部异常的叙述中，错误的是_
9、。（A）内部异常的产生与当前执行指令相关（B）内部异常的检测由 CPU 内部逻辑实现（C）内部异常的响应发生在指令执行过程中（D）内部异常处理后返回到发生异常的指令继续执行23 处理外部中断时，应该由操作系统保存的是_。（A）程序计数器(PC)的内容（B）通用寄存器的内容（C）块表 (TLB)中的内容（D）Cache 中的内容24 假定下列指令已装入指令寄存器。则执行时不可能导致 CPU 从用户态变为内核态(系统态 )的是 _。（A）DIV R0，R1；(R0)(RI)R0（B） INT n 产生软中断（C） NOT R0 寄存器 R0 的内容取非（D）MOV R0，addr ；把地址 add
10、r 处的内存数据放入寄存器 R0 中25 下列选项中，会导致进程从执行态变为就绪态的事件是（A）执行 P(wait)操作（B）申请内存失败（C）启动 IO 设备（D）被高优先级进程抢占26 若系统 S1 采用死锁避免方法， S2 采用死锁检测方法。下列叙述中，正确的是_。S1 会限制用户申请资源的顺序，而 S2 不会S1 需要进程运行所需资源总量信息，而 S2 不需要S1 不会给可能导致死锁的进程分配资源，而 S2 会（A）仅、（B）仅 、（C）仅 、（D）、27 系统为某进程分配了 4 个页框，该进程己访问的页号序列为2，0，2，9，3，4，2，8，2，4，8，4，5。若进程要访问的下一页的
11、页号为 7，依据 LRU 算法，应淘汰页的页号是_。（A）2（B） 3（C） 4（D）828 在系统内存中设置磁盘缓冲区的主要目的是_。（A）减少磁盘 IO 次数（B）减少平均寻道时间（C）提高磁盘数据可靠性（D）实现设备无关性29 在文件的索引结点中存放直接索引指针 10 个，一级和二级索引指针各 1 个。磁盘块大小为 1KB，每个索引指针占 4 个字节。若某文件的索引结点已在内存中，则把该文件偏移量(按字节编址)为 1234 和 307400 处所在的磁盘块读入内存，需访问的磁盘块个数分别是_。（A）1，2（B） 1，3（C） 2，3（D）2，430 在请求分页系统中，页面分配策略与页面置
12、换策略不能组合使用的是_。（A）可变分配，全局置换（B）可变分配，局部置换（C）固定分配，全局置换（D）固定分配，局部置换31 文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的 32127 号块中，每个盘块占 1024 个字节，盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612，则位图中要修改的位所在的盘块号和块内字节序号分别是_。（A）81、1（B） 81、2（C） 82、1（D）82、232 某硬盘有 200 个磁道(最外侧磁道号为 0)，磁道访问请求序列为：130，42，180，15，199，当前磁头位于第 58 号磁道并从外侧向内侧移动。按照SCAN 调度方法处
13、理完上述请求后，磁头移过的磁道数是_。（A）208（B） 287（C） 325（D）38233 通过 POP3 协议接收邮件时，使用的传输层服务类型是_。（A）无连接不可靠的数据传输服务（B）无连接可靠的数据传输服务（C）有连接不可靠的数据传输服务（D）有链接可靠的数据传输服务34 使用两种编码方案对比特流 01100111 进行编码的结果如下图所示，编码 1 和编码 2 分别是_。（A）NRZ 和曼彻斯特编码（B） NRZ 和差分曼彻斯特编码（C） NRZI 和曼彻斯特编码（D）NRZI 和差分曼彻斯特编码35 主机甲通过 128kbps 星链路，采用滑动窗口协议向主机乙发送数据，链路单向传
14、播延迟为 250ms，帧长为 1000 字节。不考虑确认帧的开销，为使链路利用率不小于 80，帧序号的比特数至少是_。（A）3（B） 4（C） 7（D）836 下列关 CSMACD 协议的叙述中，错误的是 _。（A）边发送数据帧，边检测是否发生冲突（B）适用于无线网络，以实现无线链路共享（C）需要根据网络跨距和数据传输速率限定最小帧长（D）当信号传播延迟趋近 0 时，信道利用率趋近 10037 下列关于交换机的叙述中，正确的是_。（A）以太网交换机本质上是一种多端口网桥（B）通过交换机互连的一组工作站构成一个冲突域（C）交换机每个端口所连网络构成一个独立的广播域（D）以太网交换机可实现采用不同
15、网络层协议的网络互联38 某路由器的路由表如下表所示：若路由器收到一个目的地址为169，96405 的 IP 分组，则转发该口分组的接口是 _。（A）S1（B） S2（C） S3（D）S439 主机甲和主机乙新建一个 TCP 连接，甲的拥塞控制初始阈值为 32KB，甲向乙始终以 MSS=1KB 大小的段发送数据，并一直有数据发送；乙为该连接分配 16KB接收缓存，并对每个数据段进行确认，忽略段传输延迟。若乙到的数据全部存入缓存，不被取走，则甲从连接建立成功时刻起，未发送超时的情况下，经过 4 个RTT 后，甲的发送窗口是_。（A）1KB（B） 8KB（C） 16KB（D）32KB40 某浏览器
16、发出的 HTFP 请求报文如下： 下列叙述中，错误的是_。（A）该浏览器请求浏览 indexhtml（B） Index html 存放在 wwwtestedu cn 上（C）该浏览器请求使用持续连接（D）该浏览器曾经浏览过 wwwtesteducn二、综合应用题41-47 小题，共 70 分。40 用单链表保存 m 个整数，结点的结构为：dlatalink，且datan(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下： 则删除结点后的 head 为： 要求
17、：41 给出算法的基本设计思想。42 使用 C 或 C+语言，给出单链表结点的数据类型定义。43 根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。44 说明你所设计算法的时间复杂度和空间复杂度。44 已知含有 5 个顶点的图 G 如下图所示。 请回答下列问题：45 写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。46 求 A2，矩阵 A2 中位于 0 行 3 列元素值的含义是什么?47 若己知具有 n(n2)个顶点的图的邻接矩阵为 B，则 Bm(2mn)中非零元素的含义是什么?47 某 16 位计算机的主存按字节编码，存取单位为 16 位；采用 16 位定长指令字格式；C
18、PU 采用单总线结构，主要部分如下图所示。图中 R0R3 为通用寄存器；T为暂存器；SR 为移位寄存器，可实现直送 (mov)、左移一位(left)和右移一位(right)3种操作，控制信号为 SRop，SR 的输出由信号 SRout 控制；ALU 可实现直送A(mova)、A 加 B(add)、A 减 B(sub)、A 与 B(and)、A 或 B(or)、非 A(not)、A 加1(inc)7 种操作，控制信号为 ALUop。请回答下列问题：48 图中哪些寄存器是程序员可见的?为何要设置暂存器 T?49 控制信号 ALUop 和 SRop 的位数至少各是多少?50 控制信号 SRout 所
19、控制部件的名称或作用是什么?51 端点 中，哪些端点须连接到控制部件的输出端?52 为完善单总线数据通路，需要在端点 中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。53 为什么二路选择器 MID(的一个输入端是 2?53 某 16 位计算机的主存按字节编码，存取单位为 16 位；采用 16 位定长指令字格式；CPU 采用单总线结构，主要部分如下图所示。图中 R0R3 为通用寄存器；T为暂存器；SR 为移位寄存器，可实现直送 (mov)、左移一位(left)和右移一位(right)3种操作，控制信号为 SRop，SR 的输出由信号 SRout 控制；ALU 可实
20、现直送A(mova)、A 加 B(add)、A 减 B(sub)、A 与 B(and)、A 或 B(or)、非 A(not)、A 加1(inc)7 种操作，控制信号为 ALUop。以上描述的计算机，其部分指令执行过程的控制信号如下图所示。该机指令格式如下图所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为 0 和 1，通用寄存器 R0R3 的编号分别为 0、1、2 和 3。请回答下列问题：54 该机的指令系统最多可定义多少条指令?55 假定 inc、shl 和 sub 指令的操作码分别为 01H、02H 和 03H，则以下指令对应的机器代码各是什么?inc R1；R1+1R1shl
21、 R1，R2；(R1)1R2sub R3；(R1)，R2 ；(R1)-(R2)R356 假设寄存器 X 的输入和输出控制信号分别为 Xin 和 Xout，其值为 1 表示有效，为 0 表示无效(例如，PCout=1 表示 PC 内容送总线)；存储器控制信号为 MEMop，用于控制存储器的读(read)和写(write)操作。写出题图 a 中标号 处的控制信号或控制信号的取值。57 指令“sub R1，R3，(R2)”和“inc R1”的执行阶段至少各需要多少个时钟周期?58 有 A、B 两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的
22、邮箱中。假设 A 的信箱最多放 M 个邮件，B 的信箱最多放 N 个邮件。初始时 A 的信箱中有 x 个邮件(0x M)，B 的信箱中有 y 个(0yN)。辩论者每取出一个邮件，邮件数减1。A 和 B 两人的操作过程描述如下：CoBeginCoEnd 当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和 P、V(或wait、signal)操作，以实现上述过程的同步。要求写出完整过程，并说明信号量的含义和初值。58 某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示： 请回答下列问题：59 页和页框
23、的大小各为多少字节?进程的虚拟地址空间大小为多少页?60 假定页目录项和页表项均占 4 个字节，则进程的页目录和页表共占多少页?要求写出计算过程。61 若某指令周期内访问的虚拟地址为 0100 0000H 和 0111 2048H，则进行地址转换时共访问多少个二级页表?要求说明理由。61 某网络拓扑如图所示，其中路由器内网接口、DHCP 服务器、WWW 服务器与主机 1 均采用静态 IP 地址配置，相关地址信息见图中标注；主机 2主机 N 通过DHCP 服务器动态获取 IP 地址等配置信息。请回答下列问题：62 DHCP 服务器可为主机 2主机 N 动态分配 IP 地址的最大范围是什么?主机
24、2、使用 DHCP 协议获取 IP 地址的过程中，发送的封装 DHCP Discover63 若主机 2 的 ARP 表为空，则该主机访问 Internet 时，发出的第一个以太网帧的目的 MAC 地址是什么?封装主机 2 发往 Internet 的 IP 分组的以太网帧的目的 MAC地址是什么?64 若主机 1 的子网掩码和默认网关分别配置为 2552552550 和111123152，则该主机是否能访问 WWW 服务器?是否能访问 Internet?请说明理由。2015 年考研计算机专业（基础综合）真题试卷答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的
25、四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A2 【正确答案】 B3 【正确答案】 D4 【正确答案】 D5 【正确答案】 D6 【正确答案】 C7 【正确答案】 A8 【正确答案】 C9 【正确答案】 C10 【正确答案】 C11 【正确答案】 A12 【正确答案】 A13 【正确答案】 B14 【正确答案】 D15 【正确答案】 C16 【正确答案】 B17 【正确答案】 B18 【正确答案】 D19 【正确答案】 C20 【正确答案】 B21 【正确答案】 B22 【正确答案】 D23 【正确答案】 B24 【正确答案】 C25 【正确答案】 D26 【正确答案】 B2
26、7 【正确答案】 A28 【正确答案】 A29 【正确答案】 B30 【正确答案】 C31 【正确答案】 C32 【正确答案】 C33 【正确答案】 D34 【正确答案】 A35 【正确答案】 B36 【正确答案】 B37 【正确答案】 A38 【正确答案】 C39 【正确答案】 A40 【正确答案】 C二、综合应用题41-47 小题，共 70 分。41 【正确答案】 算法的基本设计思想算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为datan，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同时检查 qdata
27、的值，如果为 0，则保留该结点，并令qdata =1；否则，将该结点从链表中删除。42 【正确答案】 使用 C 语言描述的单链表结点的数据类型定义typedef struct nodeint data；struct node*link；NODE；Typedef NODE *PNODE。43 【正确答案】 算法实现void func (PNODE h，int n)PNODE p=h，r，int *q，m；q=(int *)malloc(sizeof(int)*(n 十 1)；申请 n+1 个位置的辅助空间for(int i=0，in+1，i+)数组元素初值置 0*(q+i)=0；while(p-
28、link!=NULL)m=p- link-data0?p- link-data：-p- link- data；if(*(q+m)=0)判断该结点的 data 是否己出现过*(q+m)=1，首次出现p=p-link；保留else重复出现r=p-link；删除P-link=r-finkfree(r)；44 【正确答案】 算法的时间复杂度为 O(m)，空间复杂度为 O(n)。45 【正确答案】 图 G 的邻接矩阵 A 如下：46 【正确答案】 A 2 如下： 0 行 3 列的元素值 3 表示从顶点 0 到顶点3 之间长度为 2 的路径共有 3 条。47 【正确答案】 B m(2mn)中位于 i 行
29、j 列(0j， jn-1)的非零元素的含义是：图中从顶点 i 到顶点 j 长度为 m 的路径条数。48 【正确答案】 程序员可见寄存器为通用寄存器(R0R3)和 PC。因为采用了单总线结构，因此，若无暂存器 T，则 ALU 的 A、 B 端口会同时获得两个相同的数据，使数据通路不能正常工作。49 【正确答案】 ALU 共有 7 种操作，故其操作控制信号 ALUop 至少需要 3 位；移位寄存器有 3 种操作，其操作控制信号 SRop 至少需要 2 位。50 【正确答案】 信号 SRout 所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。51 【正确答案】 端口、 、 须
30、连接到控制部件输出端。52 【正确答案】 连线 1， ；连线 2，。53 【正确答案】 因为每条指令的长度为 16 位，按字节编址，所以每条指令占用2 个内存单元，顺序执行时，下条指令地址为(PC)+2。MUX 的一个输入端为 2，可便于执行(PC)+2 操作。54 【正确答案】 指令操作码有 7 位，因此最多可定义 27=128 条指令。55 【正确答案】 各条指令的机器代码分别如下：“inc R1”的机器码为：0000001 0 01 0 00 0 00，即 0240H。“sbl R2，R1”的机器码为： 0000010 0 10 0 01 0 00，即 0488H。“sub R3， (R
31、1)，R2”的机器码为： 0000011 0 11 1 01 0 10，即 06EAH。56 【正确答案】 各标号处的控制信号或控制信号取值如下：0；mov；mova；left ；read；sub；mov；Srout。57 【正确答案】 指令“sub R1，R3，(R2)”的执行阶段至少包含 4 个时钟周期；指令“inc R1”的执行阶段至少包含 2 个时钟周期。58 【正确答案】 semaphore Full_A=x；Full_A 表示 A 的信箱中的邮件数量semaphore Empty_A=M-x；Empty_A 表示 A 的信箱中还可存放的邮件数量semaphore Full_B；y；
32、Full_B 表示 B 的信箱中的邮件数量 semaphore Empty_B；N-y；Empty_B 表示 B 的信箱中还可存放的邮件数量 semaphore mutex_A=1；mutex_A 用于 A 的信箱互斥 semaphore mutex_B=1；mutex_B 用于 B 的信箱互斥 Cobegin59 【正确答案】 页和页框大小均为 4KB。进程的虚拟地址空间大小为 2322 12=220页。60 【正确答案】 (2 10*4)2 12(页目录所占页数)+(2 20*4)2 12(页表所占页数)=1025页。61 【正确答案】 需要访问一个二级也表。因为虚拟地址 0100 000
33、0H 和 0111 2048H 的最高 10 位的值都是 4，访问的是同一个二级页表。62 【正确答案】 DHCP 服务器可为主机 2主机 N 动态分配 IP 地址的最大范围是：11112315511112315254；主机 2 发送的封装 DHCP Discover报文的 IP 分组的源 IP 地址和目的 IP 地址分别是 0000 和255255255255。63 【正确答案】 主机 2 发出的第一个以太网帧的目的 MAC 地址是 if-if-if-if-if-if；封装主机 2 发往 Internet 的 IP 分组的以太网帧的目的 MAC 地址是 00-a1-a1-a1-a1-a1。64 【正确答案】 主机 1 能访问 WWW 服务器，但不能访问 Internet。由于主机 1的子网掩码配置正确而默认网关 IP 地址被错误地配置为 111123152( 正确 IP地址是 111123151)，所以主机 1 可以访问在同一个子网内的 WWW 服务器，但当主机 1 访问 Internet 时，主机 1 发出的 IP 分组会被路由到错误的默认网关(111 123152) ，从而无法到达目的主机。
