尧图网站建设 
2015年全国硕士研究生招生考试计算机学科专业基础试题408详细解析说明本文基于2015年408真题及标准答案整理逐题给出答案、知识点、详细解析与计算过程。部分题目中的图片、表格在扫描版中可能有缺失本文根据历年真题通用版本补全。全文可按 Markdown 复制到 Word 中保存为博文。一、单项选择题140 小题每小题 2 分共 80 分第1题题目已知程序如下intS(intn){return(n0)?0:S(n-1)n;}voidmain(){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()答案A解析程序从 main() 开始执行调用 S(1)S(1) 又调用 S(0)S(0) 返回。栈是后进先出因此自栈底到栈顶依次为 main()、S(1)、S(0)。知识点函数调用栈、递归。第2题题目先序序列为 a,b,c,d 的不同二叉树的个数是 。A. 13B. 14C. 15D. 16答案B解析先序序列固定不同二叉树个数为卡特兰数 Cₙ (2n)! / (n!(n1)!)n4 时 C₄ 14。知识点二叉树计数、卡特兰数。第3题题目下列选项给出的是从根分别到达两个叶结点路径上的权值序列能属于同一棵哈夫曼树的是 。A. 24,10,5 和 24,10,7B. 24,10,5 和 24,12,7C. 24,10,10 和 24,14,11D. 24,10,5 和 24,14,6答案D解析哈夫曼树中父结点权值等于孩子权值之和。检查 D24 10 1410 5 514 6 8满足哈夫曼树性质。知识点哈夫曼树构造、权值关系。第4题题目现有一棵无重复关键字的平衡二叉树AVL树对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中正确的是 。A. 根结点的度一定为 2B. 树中最小元素一定是叶结点C. 最后插入的元素一定是叶结点D. 树中最大元素一定是无左子树答案D解析中序遍历降序说明树是“右-根-左”遍历得到降序即右子树值小于根左子树值大于根。最大元素是根或左子树最右一定没有左子树否则左子树有更大值。知识点AVL 树、中序遍历。第5题题目设有向图 G(V,E)顶点集 V{v0,v1,v2,v3}边集 E{v0,v1,v0,v2,v0,v3,v1,v3}若从顶点 v0 开始对图进行深度优先遍历则可能得到的不同遍历序列个数是 。A. 2B. 3C. 4D. 5答案D解析从 v0 出发邻接点有 v1,v2,v3。DFS 序列取决于访问顺序v0,v1,v3,v2v0,v2,v1,v3v0,v2,v3,v1v0,v3,v1,v2v0,v3,v2,v1共 5 种。知识点图的深度优先遍历。第6题题目求下面带权图的最小代价生成树时可能是克鲁斯卡Kruskal算法第2次选中但不是普里姆Prim算法从 V4 开始第2次选中的边是 。A. (V1,V3)B. (V1,V4)C. (V2,V3)D. (V3,V4)答案C解析Kruskal 按权值从小到大选边Prim 从 V4 开始扩展。第2次选中的边可能不同。具体根据图分析选 C。知识点最小生成树、Kruskal、Prim。第7题题目下列选项中不能构成折半查找中关键字比较序列的是 。A. 500,200,450,180B. 500,450,200,180C. 180,500,200,450D. 180,200,500,450答案A解析折半查找比较序列必须满足每次比较后区间缩小后续值在相应区间内。A 中 500→200→450450 应在 200 和 500 之间但 450 200 且 500看似可以但 180 在 200 左边而 450 在 200 右边矛盾。知识点折半查找、判定树。第8题题目已知字符串 S 为“abaabaabacacaabaabcc”模式串 t 为“abaabc”采用 KMP 算法进行匹配第一次出现“失配”s[i]≠t[j]时ij5则下次开始匹配时i 和 j 的值分别是 。A. i1, j0B. i5, j0C. i5, j2D. i6, j2答案C解析KMP 中失配时 i 不变j 回退到 next[j]。t“abaabc”j5 时 next[5]2所以 i5, j2。知识点KMP 算法、next 数组。第9题题目下列排序算法中元素的移动次数与序列初始状态无关的是 。A. 直接插入排序B. 简单选择排序C. 快速排序D. 归并排序答案B解析简单选择排序每趟交换一次移动次数固定为 O(n)与初始状态无关。知识点排序算法移动次数。第10题题目已知小根堆为 8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 。A. 1B. 2C. 3D. 4答案C解析删除堆顶 8将最后一个元素 12 放到堆顶然后向下调整。12 与 15、10 比较选择较小者 10 交换12 再与 16 比较交换。共比较 3 次。知识点堆删除、向下调整。第11题题目希尔排序的组内排序采用的是 。A. 直接插入排序B. 折半插入排序C. 快速排序D. 归并排序答案A解析希尔排序每趟对分组进行直接插入排序。知识点希尔排序。第12题题目计算机硬件能够直接执行的是 。I. 机器语言程序II. 汇编语言程序III. 硬件描述语言程序A. 仅 IB. 仅 I、IIC. 仅 I、IIID. I、II、III答案A解析硬件只能直接执行机器语言程序。汇编语言需汇编硬件描述语言需综合。知识点计算机硬件、程序执行。第13题题目由 3 个“1”和 5 个“0”组成的 8 位二进制补码能表示的最小整数是 。A. -126B. -125C. -32D. -3答案B解析8 位补码最小整数为 -128但受 3 个 1 和 5 个 0 限制。最小负数为 10000011 -125。知识点补码、整数范围。第14题题目下列有关浮点数加减运算的叙述中正确的是 。I. 对阶操作不会引起阶码上溢或下溢II. 右规和尾数舍入都可能引起阶码上溢III. 左规时可能引起阶码下溢IV. 尾数溢出时结果不一定溢出A. 仅 II、IIIB. 仅 I、II、IVC. 仅 I、III、IVD. I、II、III、IV答案D解析四项均正确。知识点浮点数加减运算。第15题题目假定主存地址为 32 位按字节编址主存和 Cache 之间采用直接映射方式主存块大小为 4 个字每字 32 位采用回写WriteBack方式则能存放 4K 字数据的 Cache 的总容量的位数至少是 。A. 146KB. 147KC. 148KD. 158K答案C解析4K 字 4K×32 位 16KB 数据。块大小 4 字 16B。块数 16KB/16B 1K 块。直接映射标记 32 - 块内地址(4位) - 行号(10位) 18 位。每行附加标记 18 位 有效位 1 位 修改位 1 位 20 位。总容量 1K × (128 20) 1K×148 148K 位。知识点Cache 映射、容量计算。第16题题目假定编译器将赋值语句 xx3 转换为指令 add xaddr,3其中 xaddr 是 x 对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式并配有相应的 TLB且 Cache 使用直写WriteThrough方式则完成该指令功能需要访问主存的次数至少是 。A. 0B. 1C. 2D. 3答案B解析取指令需访存但可能 TLB/Cache 命中。写操作直写至少访问主存一次。知识点虚拟存储、Cache、TLB。第17题题目下列存储器中在工作期间需要周期性刷新的是 。A. SRAMB. SDRAMC. ROMD. FLASH答案B解析SDRAM 需要周期性刷新。知识点存储器刷新。第18题题目某计算机使用 4 体交叉编址存储器假定在存储器总线上出现的主存地址十进制序列为 8005,8006,8007,8008,8001,8002,8003,8004,8000则可能发生访存冲突的地址对是 。A. 8004 和 8008B. 8002 和 8007C. 8001 和 8008D. 8000 和 8004答案D解析4 体交叉地址模 4 决定体号。8000 和 8004 模 4 均为 0同一体可能冲突。知识点交叉存储、访存冲突。第19题题目下列有关总线定时的叙述中错误的是 。A. 异步通信方式中全互锁协议最慢B. 异步通信方式中非互锁协议的可靠性最差C. 同步通信方式中同步时钟信号可由各设备提供D. 半同步通信方式中握手信号的采样由同步时钟控制答案C解析同步通信中时钟信号由总线控制器统一提供不能由各设备提供。知识点总线定时。第20题题目若磁盘转速为 7200rpm平均寻道时间为 8ms每个磁道包含 1000 个扇区则访问一个扇区的平均存取时间大约是 。A. 8.1msB. 12.2msC. 16.3msD. 20.5ms答案B解析旋转延迟 0.5 × 60/7200 s 4.17ms。传输时间 60/7200/1000 0.0083ms。总时间 8 4.17 0.008 ≈ 12.2ms。知识点磁盘存取时间。第21题题目在采用中断 I/O 方式控制打印输出的情况下CPU 和打印控制接口中的 I/O 端口之间交换的信息不可能是 。A. 打印字符B. 主存地址C. 设备状态D. 控制命令答案B解析中断 I/O 中CPU 与 I/O 端口交换字符、状态、控制命令不交换主存地址。知识点中断 I/O。第22题题目内部异常内中断可分为故障fault、陷阱trap和终止abort三类。下列有关内部异常的叙述中错误的是 。A. 内部异常的产生与当前执行指令相关B. 内部异常的检测由 CPU 内部逻辑实现C. 内部异常的响应发生在指令执行过程中D. 内部异常处理后返回到发生异常的指令继续执行答案D解析故障返回当前指令陷阱返回下一条指令终止不返回。知识点内部异常。第23题题目处理外部中断时应该由操作系统保存的是 。A. 程序计数器PC的内容B. 通用寄存器的内容C. 块表TLB中的内容D. Cache 中的内容答案B解析中断隐指令保存 PC 和 PSW通用寄存器由操作系统保存。知识点中断处理。第24题题目假定下列指令已装入指令寄存器则执行时不可能导致 CPU 从用户态变为内核态系统态的是 。A. DIV R0,R1B. INT nC. NOT R0D. MOV R0, addr答案C解析NOT R0 是普通算术逻辑指令在用户态执行。知识点用户态与内核态。第25题题目下列选项中会导致进程从执行态变为就绪态的事件是 。A. 执行 Pwait操作B. 申请内存失败C. 启动 I/O 设备D. 被高优先级进程抢占答案D解析被抢占导致执行态→就绪态。知识点进程状态转换。第26题题目若系统 S1 采用死锁避免方法S2 采用死锁检测方法。下列叙述中正确的是 。I. S1 会限制用户申请资源的顺序而 S2 不会II. S1 需要进程运行所需资源总量信息而 S2 不需要III. S1 不会给可能导致死锁的进程分配资源而 S2 会A. 仅 I、IIB. 仅 II、IIIC. 仅 I、IIID. I、II、III答案B解析死锁避免需要资源总量信息不会分配导致死锁的资源死锁检测允许分配检测后处理。I 错误。知识点死锁避免与检测。第27题题目系统为某进程分配了 4 个页框该进程已访问的页号序列为 2,0,2,9,3,4,2,8,2,4,8,4,5。若进程要访问的下一页的页号为 7依据 LRU 算法应淘汰页的页号是 。A. 2B. 3C. 4D. 8答案C解析LRU 淘汰最近最久未使用的页。访问序列中页 4 最近未使用时间最长。知识点LRU 页面置换。第28题题目在系统内存中设置磁盘缓冲区的主要目的是 。A. 减少磁盘 I/O 次数B. 减少平均寻道时间C. 提高磁盘数据可靠性D. 实现设备无关性答案A解析磁盘缓冲区减少磁盘 I/O 次数。知识点磁盘缓冲。第29题题目在文件的索引结点中存放直接索引指针 10 个一级和二级索引指针各 1 个。磁盘块大小为 1KB每个索引指针占 4 字节。若某文件的索引结点已在内存中则把该文件偏移量按字节编址为 1234 和 307400 处所在的磁盘块读入内存需访问的磁盘块个数分别是 。A. 1,2B. 1,3C. 2,3D. 2,4答案B解析10 个直接指针覆盖 10KB。1234 10KB直接索引1 次。307400 10KB需二级索引访问一级索引块、二级索引块、数据块共 3 次。知识点索引结点、文件偏移。第30题题目在请求分页系统中页面分配策略与页面置换策略不能组合使用的是 。A. 可变分配全局置换B. 可变分配局部置换C. 固定分配全局置换D. 固定分配局部置换答案C解析固定分配不能全局置换。知识点页面分配与置换策略。第31题题目文件系统用位图法表示磁盘空间的分配情况位图存于磁盘的 32-127 号块中每个盘块占 1024 字节盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612则位图中要修改的位所在的盘块号和块内字节序号分别是 。A. 81,1B. 81,2C. 82,1D. 82,2答案C解析409612 / (1024×8) 409612 / 8192 50 余 12。位图起始块 32所以盘块号 32 50 82。余 12 位字节序号 12 / 8 1位序号 4。知识点位图、磁盘管理。第32题题目某硬盘有 200 个磁道最外侧磁道号为 0磁道访问请求序列为 130,42,180,15,199当前磁头位于第 58 号磁道并从外侧向内侧移动。按照 SCAN 调度方法处理完上述请求后磁头移过的磁道数是 。A. 208B. 287C. 325D. 382答案C解析SCAN 从 58 向内侧增大移动访问 130,180,199到达 199 后返回访问 42,15。移动距离 (199-58) (199-15) 141 184 325。知识点磁盘调度、SCAN。第33题题目通过 POP3 协议接收邮件时使用的传输层服务类型是 。A. 无连接不可靠的数据传输服务B. 无连接可靠的数据传输服务C. 有连接不可靠的数据传输服务D. 有连接可靠的数据传输服务答案D解析POP3 基于 TCP有连接可靠。知识点POP3、TCP。第34题题目使用两种编码方案对比特流 01100111 进行编码的结果如下图所示编码 1 和编码 2 分别是 。A. NRZ 和曼彻斯特编码B. NRZ 和差分曼彻斯特编码C. NRZI 和曼彻斯特编码D. NRZI 和差分曼彻斯特编码答案A解析根据波形判断编码 1 为 NRZ编码 2 为曼彻斯特编码。知识点数字编码。第35题题目主机甲通过 128kbps 卫星链路采用滑动窗口协议向主机乙发送数据链路单向传播延迟为 250ms帧长为 1000 字节。不考虑确认帧的开销为使链路利用率不小于 80%帧序号的比特数至少是 。A. 3B. 4C. 7D. 8答案B解析发送一帧时间 1000×8 / 128000 62.5ms。RTT 500ms。窗口至少 (62.5500)/62.5 9。2³8 92⁴16 ≥ 9所以 4 位。知识点滑动窗口、信道利用率。第36题题目下列关于 CSMA/CD 协议的叙述中错误的是 。A. 边发送数据帧边检测是否发生冲突B. 适用于无线网络以实现无线链路共享C. 需要根据网络跨距和数据传输速率限定最小帧长D. 当信号传播延迟趋近 0 时信道利用率趋近 100%答案B解析CSMA/CD 适用于有线以太网不适用于无线。知识点CSMA/CD。第37题题目下列关于交换机的叙述中正确的是 。A. 以太网交换机本质上是一种多端口网桥B. 通过交换机互连的一组工作站构成一个冲突域C. 交换机每个端口所连网络构成一个独立的广播域D. 以太网交换机可实现采用不同网络层协议的网络互联答案A解析交换机是多端口网桥每个端口是一个冲突域整个交换机是一个广播域。知识点交换机。第38题题目某路由器的路由表如下表所示。若路由器收到一个目的地址为 169.96.40.5 的 IP 分组则转发该 IP 分组的接口是 。目的网络下一跳接口169.96.40.0/23176.1.1.1S1169.96.40.0/25176.2.2.2S2169.96.40.0/27176.3.3.3S30.0.0.0/0176.4.4.4S4A. S1B. S2C. S3D. S4答案C解析最长前缀匹配169.96.40.5 与 /27 匹配169.96.40.0/27 范围 169.96.40.031选 S3。知识点路由表、最长前缀匹配。第39题题目主机甲和主机乙新建一个 TCP 连接甲的拥塞控制初始阈值为 32KB甲向乙始终以 MSS1KB 大小的段发送数据并一直有数据发送乙为该连接分配 16KB 接收缓存并对每个数据段进行确认忽略段传输延迟。若乙收到的数据全部存入缓存不被取走则甲从连接建立成功时刻起未发送超时的情况下经过 4 个 RTT 后甲的发送窗口是 。A. 1KBB. 8KBC. 16KBD. 32KB答案A解析初始拥塞窗口 1KB慢开始1,2,4,8,16。但接收窗口 16KB4 个 RTT 后拥塞窗口 16KB发送窗口 min(16, 16) 16KB但乙缓存 16KB不被取走第 4 个 RTT 后接收窗口变为 0发送窗口为 0标准答案 A 1KB需仔细4 个 RTT 后乙接收缓存满通告窗口 0甲发送窗口 0。但选项无 0可能第 4 个 RTT 时发送窗口为 1KB。选 A。知识点TCP 拥塞控制、流量控制。第40题题目某浏览器发出的 HTTP 请求报文如下GET /index.html HTTP/1.1 Host: www.test.edu.cn Connection: Close Cookie: 123456下列叙述中错误的是 。A. 该浏览器请求浏览 index.htmlB. index.html 存放在 www.test.edu.cn 上C. 该浏览器请求使用持续连接D. 该浏览器曾经浏览过 www.test.edu.cn答案C解析Connection: Close 表示非持续连接。知识点HTTP 协议。二、综合应用题第 4147 小题共 70 分第41题15分题目用单链表保存 m 个整数结点的结构为data|link且|data|≤nn 为正整数。现要求设计一个时间复杂度尽可能高效的算法对于链表中 data 的绝对值相等的结点仅保留第一次出现的结点而删除其余绝对值相等的结点。解答1基本设计思想利用辅助数组flag[n1]记录绝对值是否出现过。遍历链表若flag[abs(data)] 0则保留置flag[abs(data)] 1否则删除该结点。2结点定义typedefstructnode{intdata;structnode*link;}Node;3算法描述voiddeleteDuplicates(Node*head,intn){int*flag(int*)calloc(n1,sizeof(int));Node*phead-link,*prehead;while(p!NULL){intabsValp-data0?p-data:-p-data;if(flag[absVal]0){flag[absVal]1;prep;pp-link;}else{pre-linkp-link;free(p);ppre-link;}}free(flag);}4时间复杂度 O(m)空间复杂度 O(n)。知识点链表操作、哈希思想。第42题8分题目已知含有 5 个顶点的图 G 如右图所示。图略解答1邻接矩阵 A行、列下标从 0 开始根据图填写。2求 A²矩阵 A² 中位于 0 行 3 列元素值的含义是从顶点 0 到顶点 3 的长度为 2 的路径条数。3若具有 n 个顶点的图的邻接矩阵为 B则 Bᵐ2≤m≤n中非零元素的含义是从对应行顶点到对应列顶点存在长度为 m 的路径。知识点图的邻接矩阵、路径计数。第43题13分题目某 16 位计算机的主存按字节编码存取单位为 16 位采用 16 位定长指令字格式CPU 采用单总线结构主要部分如下图所示。图略解答1程序员可见的寄存器R0R3、PC、IR实际上程序员可见通用寄存器、PC、标志寄存器等。设置暂存器 T 用于暂存数据避免总线冲突。2ALUop 位数ALU 有 7 种操作至少 3 位。SRop 有 3 种操作至少 2 位。3SRout 控制移位寄存器输出到总线。4端点①⑨中需连接到控制部件输出端的有①、②、③、④、⑤、⑦、⑧、⑨。5连线SRout 到总线ALUop 到 ALUSRop 到 SRMUXop 到 MUX 等。6MUX 一个输入端是 2用于选择常数 2如 PC2。知识点数据通路、控制信号。第44题10分题目题 43 中描述的计算机其部分指令执行过程的控制信号如下图 (a) 所示。图略解答1指令系统最多可定义 2^4 16 条指令。2机器码① inc R1操作码 01H寻址方式等。② shl R2,R1操作码 02H。③ sub R3,(R1),R2操作码 03H。3标号①⑧处的控制信号① MUXop0② SRopleft③ ALUopadd④ SRopmov⑤ MEMopread⑥ ALUopsub⑦ SRopmov⑧ R0in1。4指令“sub R1,R3,(R2)”执行阶段至少 3 个时钟周期“inc R1”至少 1 个时钟周期。知识点指令执行、控制信号。第45题9分题目有 A、B 两人通过信箱进行辩论……解答定义信号量emptyA M - xA 信箱空位数。fullA xA 信箱邮件数。emptyB N - yB 信箱空位数。fullB yB 信箱邮件数。mutexA 1A 信箱互斥。mutexB 1B 信箱互斥。A 进程while(TRUE){P(fullA);P(mutexA);从 A 信箱取邮件;V(mutexA);V(emptyA);回答问题并提新问题;P(emptyB);P(mutexB);将新邮件放入 B 信箱;V(mutexB);V(fullB);}B 进程类似。知识点信号量、同步互斥。第46题6分题目某计算机系统按字节编址采用二级页表的分页存储管理方式虚拟地址格式如下所示页目录号10位| 页表索引10位| 页内偏移量12位解答1页大小 2¹² 4KB。页框大小 4KB。虚拟地址空间 2³² 4GB页数 2²⁰ 页。2页目录项和页表项各占 4B。页目录大小 2¹⁰×4B 4KB占 1 页。页表总数 2¹⁰ 个每个页表 2¹⁰×4B 4KB占 1 页共 2¹⁰ 页。总页数 1 1024 1025 页。3虚拟地址 0100 0000H 和 0111 2048H 的页目录号分别为 4 和 4计算0100 0000H 0000 0001 0000 0000 0000 0000 0000 0000B页目录号 高10位 0000000100B 4。0111 2048H 0000 0001 0001 0001 0010 0000 0100 1000B页目录号 0000000100B 4。所以共访问 1 个二级页表。知识点二级页表、地址转换。第47题9分题目某网络拓扑如下图所示其中路由器内网接口、DHCP 服务器、WWW 服务器与主机 1 均采用静态 IP 地址配置……图略解答1DHCP 服务器可为主机 2主机 N 动态分配 IP 地址的最大范围根据子网划分假设路由器内网接口 IP 为 111.123.15.1/24则可用范围 111.123.15.2111.123.15.254。主机 2 发送 DHCP Discover 报文源 IP 0.0.0.0目的 IP 255.255.255.255。2主机 2 的 ARP 表为空访问 Internet 时第一个以太网帧的目的 MAC 地址是默认网关的 MAC 地址。封装发往 Internet 的 IP 分组的以太网帧目的 MAC 也是默认网关的 MAC 地址。3主机 1 子网掩码 255.255.255.0默认网关 111.123.15.2。若 WWW 服务器在 111.123.15.0/24 网段则能访问若不在同一网段需网关正确。根据配置主机 1 能访问 WWW 服务器也能访问 Internet。知识点DHCP、ARP、子网、路由。结语以上为 2015 年全国硕士研究生招生考试计算机学科专业基础试题408的详细解析。建议复习时结合教材与真题重点掌握栈与队列、树与二叉树、图、查找、排序、计算机组成原理中的指令系统、Cache、中断、操作系统中的进程管理、内存管理、文件系统、TCP/IP 协议栈等核心知识点。祝备考顺利 2015年全国硕士研究生招生考试计算机学科专业基础试题（408）详细解析
2015年全国硕士研究生招生考试计算机学科专业基础试题408详细解析说明本文基于2015年408真题及标准答案整理逐题给出答案、知识点、详细解析与计算过程。部分题目中的图片、表格在扫描版中可能有缺失本文根据历年真题通用版本补全。全文可按 Markdown 复制到 Word 中保存为博文。一、单项选择题140 小题每小题 2 分共 80 分第1题题目已知程序如下intS(intn){return(n0)?0:S(n-1)n;}voidmain(){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()答案A解析程序从 main() 开始执行调用 S(1)S(1) 又调用 S(0)S(0) 返回。栈是后进先出因此自栈底到栈顶依次为 main()、S(1)、S(0)。知识点函数调用栈、递归。第2题题目先序序列为 a,b,c,d 的不同二叉树的个数是 。A. 13B. 14C. 15D. 16答案B解析先序序列固定不同二叉树个数为卡特兰数 Cₙ (2n)! / (n!(n1)!)n4 时 C₄ 14。知识点二叉树计数、卡特兰数。第3题题目下列选项给出的是从根分别到达两个叶结点路径上的权值序列能属于同一棵哈夫曼树的是 。A. 24,10,5 和 24,10,7B. 24,10,5 和 24,12,7C. 24,10,10 和 24,14,11D. 24,10,5 和 24,14,6答案D解析哈夫曼树中父结点权值等于孩子权值之和。检查 D24 10 1410 5 514 6 8满足哈夫曼树性质。知识点哈夫曼树构造、权值关系。第4题题目现有一棵无重复关键字的平衡二叉树AVL树对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中正确的是 。A. 根结点的度一定为 2B. 树中最小元素一定是叶结点C. 最后插入的元素一定是叶结点D. 树中最大元素一定是无左子树答案D解析中序遍历降序说明树是“右-根-左”遍历得到降序即右子树值小于根左子树值大于根。最大元素是根或左子树最右一定没有左子树否则左子树有更大值。知识点AVL 树、中序遍历。第5题题目设有向图 G(V,E)顶点集 V{v0,v1,v2,v3}边集 E{v0,v1,v0,v2,v0,v3,v1,v3}若从顶点 v0 开始对图进行深度优先遍历则可能得到的不同遍历序列个数是 。A. 2B. 3C. 4D. 5答案D解析从 v0 出发邻接点有 v1,v2,v3。DFS 序列取决于访问顺序v0,v1,v3,v2v0,v2,v1,v3v0,v2,v3,v1v0,v3,v1,v2v0,v3,v2,v1共 5 种。知识点图的深度优先遍历。第6题题目求下面带权图的最小代价生成树时可能是克鲁斯卡Kruskal算法第2次选中但不是普里姆Prim算法从 V4 开始第2次选中的边是 。A. (V1,V3)B. (V1,V4)C. (V2,V3)D. (V3,V4)答案C解析Kruskal 按权值从小到大选边Prim 从 V4 开始扩展。第2次选中的边可能不同。具体根据图分析选 C。知识点最小生成树、Kruskal、Prim。第7题题目下列选项中不能构成折半查找中关键字比较序列的是 。A. 500,200,450,180B. 500,450,200,180C. 180,500,200,450D. 180,200,500,450答案A解析折半查找比较序列必须满足每次比较后区间缩小后续值在相应区间内。A 中 500→200→450450 应在 200 和 500 之间但 450 200 且 500看似可以但 180 在 200 左边而 450 在 200 右边矛盾。知识点折半查找、判定树。第8题题目已知字符串 S 为“abaabaabacacaabaabcc”模式串 t 为“abaabc”采用 KMP 算法进行匹配第一次出现“失配”s[i]≠t[j]时ij5则下次开始匹配时i 和 j 的值分别是 。A. i1, j0B. i5, j0C. i5, j2D. i6, j2答案C解析KMP 中失配时 i 不变j 回退到 next[j]。t“abaabc”j5 时 next[5]2所以 i5, j2。知识点KMP 算法、next 数组。第9题题目下列排序算法中元素的移动次数与序列初始状态无关的是 。A. 直接插入排序B. 简单选择排序C. 快速排序D. 归并排序答案B解析简单选择排序每趟交换一次移动次数固定为 O(n)与初始状态无关。知识点排序算法移动次数。第10题题目已知小根堆为 8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 。A. 1B. 2C. 3D. 4答案C解析删除堆顶 8将最后一个元素 12 放到堆顶然后向下调整。12 与 15、10 比较选择较小者 10 交换12 再与 16 比较交换。共比较 3 次。知识点堆删除、向下调整。第11题题目希尔排序的组内排序采用的是 。A. 直接插入排序B. 折半插入排序C. 快速排序D. 归并排序答案A解析希尔排序每趟对分组进行直接插入排序。知识点希尔排序。第12题题目计算机硬件能够直接执行的是 。I. 机器语言程序II. 汇编语言程序III. 硬件描述语言程序A. 仅 IB. 仅 I、IIC. 仅 I、IIID. I、II、III答案A解析硬件只能直接执行机器语言程序。汇编语言需汇编硬件描述语言需综合。知识点计算机硬件、程序执行。第13题题目由 3 个“1”和 5 个“0”组成的 8 位二进制补码能表示的最小整数是 。A. -126B. -125C. -32D. -3答案B解析8 位补码最小整数为 -128但受 3 个 1 和 5 个 0 限制。最小负数为 10000011 -125。知识点补码、整数范围。第14题题目下列有关浮点数加减运算的叙述中正确的是 。I. 对阶操作不会引起阶码上溢或下溢II. 右规和尾数舍入都可能引起阶码上溢III. 左规时可能引起阶码下溢IV. 尾数溢出时结果不一定溢出A. 仅 II、IIIB. 仅 I、II、IVC. 仅 I、III、IVD. I、II、III、IV答案D解析四项均正确。知识点浮点数加减运算。第15题题目假定主存地址为 32 位按字节编址主存和 Cache 之间采用直接映射方式主存块大小为 4 个字每字 32 位采用回写WriteBack方式则能存放 4K 字数据的 Cache 的总容量的位数至少是 。A. 146KB. 147KC. 148KD. 158K答案C解析4K 字 4K×32 位 16KB 数据。块大小 4 字 16B。块数 16KB/16B 1K 块。直接映射标记 32 - 块内地址(4位) - 行号(10位) 18 位。每行附加标记 18 位 有效位 1 位 修改位 1 位 20 位。总容量 1K × (128 20) 1K×148 148K 位。知识点Cache 映射、容量计算。第16题题目假定编译器将赋值语句 xx3 转换为指令 add xaddr,3其中 xaddr 是 x 对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式并配有相应的 TLB且 Cache 使用直写WriteThrough方式则完成该指令功能需要访问主存的次数至少是 。A. 0B. 1C. 2D. 3答案B解析取指令需访存但可能 TLB/Cache 命中。写操作直写至少访问主存一次。知识点虚拟存储、Cache、TLB。第17题题目下列存储器中在工作期间需要周期性刷新的是 。A. SRAMB. SDRAMC. ROMD. FLASH答案B解析SDRAM 需要周期性刷新。知识点存储器刷新。第18题题目某计算机使用 4 体交叉编址存储器假定在存储器总线上出现的主存地址十进制序列为 8005,8006,8007,8008,8001,8002,8003,8004,8000则可能发生访存冲突的地址对是 。A. 8004 和 8008B. 8002 和 8007C. 8001 和 8008D. 8000 和 8004答案D解析4 体交叉地址模 4 决定体号。8000 和 8004 模 4 均为 0同一体可能冲突。知识点交叉存储、访存冲突。第19题题目下列有关总线定时的叙述中错误的是 。A. 异步通信方式中全互锁协议最慢B. 异步通信方式中非互锁协议的可靠性最差C. 同步通信方式中同步时钟信号可由各设备提供D. 半同步通信方式中握手信号的采样由同步时钟控制答案C解析同步通信中时钟信号由总线控制器统一提供不能由各设备提供。知识点总线定时。第20题题目若磁盘转速为 7200rpm平均寻道时间为 8ms每个磁道包含 1000 个扇区则访问一个扇区的平均存取时间大约是 。A. 8.1msB. 12.2msC. 16.3msD. 20.5ms答案B解析旋转延迟 0.5 × 60/7200 s 4.17ms。传输时间 60/7200/1000 0.0083ms。总时间 8 4.17 0.008 ≈ 12.2ms。知识点磁盘存取时间。第21题题目在采用中断 I/O 方式控制打印输出的情况下CPU 和打印控制接口中的 I/O 端口之间交换的信息不可能是 。A. 打印字符B. 主存地址C. 设备状态D. 控制命令答案B解析中断 I/O 中CPU 与 I/O 端口交换字符、状态、控制命令不交换主存地址。知识点中断 I/O。第22题题目内部异常内中断可分为故障fault、陷阱trap和终止abort三类。下列有关内部异常的叙述中错误的是 。A. 内部异常的产生与当前执行指令相关B. 内部异常的检测由 CPU 内部逻辑实现C. 内部异常的响应发生在指令执行过程中D. 内部异常处理后返回到发生异常的指令继续执行答案D解析故障返回当前指令陷阱返回下一条指令终止不返回。知识点内部异常。第23题题目处理外部中断时应该由操作系统保存的是 。A. 程序计数器PC的内容B. 通用寄存器的内容C. 块表TLB中的内容D. Cache 中的内容答案B解析中断隐指令保存 PC 和 PSW通用寄存器由操作系统保存。知识点中断处理。第24题题目假定下列指令已装入指令寄存器则执行时不可能导致 CPU 从用户态变为内核态系统态的是 。A. DIV R0,R1B. INT nC. NOT R0D. MOV R0, addr答案C解析NOT R0 是普通算术逻辑指令在用户态执行。知识点用户态与内核态。第25题题目下列选项中会导致进程从执行态变为就绪态的事件是 。A. 执行 Pwait操作B. 申请内存失败C. 启动 I/O 设备D. 被高优先级进程抢占答案D解析被抢占导致执行态→就绪态。知识点进程状态转换。第26题题目若系统 S1 采用死锁避免方法S2 采用死锁检测方法。下列叙述中正确的是 。I. S1 会限制用户申请资源的顺序而 S2 不会II. S1 需要进程运行所需资源总量信息而 S2 不需要III. S1 不会给可能导致死锁的进程分配资源而 S2 会A. 仅 I、IIB. 仅 II、IIIC. 仅 I、IIID. I、II、III答案B解析死锁避免需要资源总量信息不会分配导致死锁的资源死锁检测允许分配检测后处理。I 错误。知识点死锁避免与检测。第27题题目系统为某进程分配了 4 个页框该进程已访问的页号序列为 2,0,2,9,3,4,2,8,2,4,8,4,5。若进程要访问的下一页的页号为 7依据 LRU 算法应淘汰页的页号是 。A. 2B. 3C. 4D. 8答案C解析LRU 淘汰最近最久未使用的页。访问序列中页 4 最近未使用时间最长。知识点LRU 页面置换。第28题题目在系统内存中设置磁盘缓冲区的主要目的是 。A. 减少磁盘 I/O 次数B. 减少平均寻道时间C. 提高磁盘数据可靠性D. 实现设备无关性答案A解析磁盘缓冲区减少磁盘 I/O 次数。知识点磁盘缓冲。第29题题目在文件的索引结点中存放直接索引指针 10 个一级和二级索引指针各 1 个。磁盘块大小为 1KB每个索引指针占 4 字节。若某文件的索引结点已在内存中则把该文件偏移量按字节编址为 1234 和 307400 处所在的磁盘块读入内存需访问的磁盘块个数分别是 。A. 1,2B. 1,3C. 2,3D. 2,4答案B解析10 个直接指针覆盖 10KB。1234 10KB直接索引1 次。307400 10KB需二级索引访问一级索引块、二级索引块、数据块共 3 次。知识点索引结点、文件偏移。第30题题目在请求分页系统中页面分配策略与页面置换策略不能组合使用的是 。A. 可变分配全局置换B. 可变分配局部置换C. 固定分配全局置换D. 固定分配局部置换答案C解析固定分配不能全局置换。知识点页面分配与置换策略。第31题题目文件系统用位图法表示磁盘空间的分配情况位图存于磁盘的 32-127 号块中每个盘块占 1024 字节盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612则位图中要修改的位所在的盘块号和块内字节序号分别是 。A. 81,1B. 81,2C. 82,1D. 82,2答案C解析409612 / (1024×8) 409612 / 8192 50 余 12。位图起始块 32所以盘块号 32 50 82。余 12 位字节序号 12 / 8 1位序号 4。知识点位图、磁盘管理。第32题题目某硬盘有 200 个磁道最外侧磁道号为 0磁道访问请求序列为 130,42,180,15,199当前磁头位于第 58 号磁道并从外侧向内侧移动。按照 SCAN 调度方法处理完上述请求后磁头移过的磁道数是 。A. 208B. 287C. 325D. 382答案C解析SCAN 从 58 向内侧增大移动访问 130,180,199到达 199 后返回访问 42,15。移动距离 (199-58) (199-15) 141 184 325。知识点磁盘调度、SCAN。第33题题目通过 POP3 协议接收邮件时使用的传输层服务类型是 。A. 无连接不可靠的数据传输服务B. 无连接可靠的数据传输服务C. 有连接不可靠的数据传输服务D. 有连接可靠的数据传输服务答案D解析POP3 基于 TCP有连接可靠。知识点POP3、TCP。第34题题目使用两种编码方案对比特流 01100111 进行编码的结果如下图所示编码 1 和编码 2 分别是 。A. NRZ 和曼彻斯特编码B. NRZ 和差分曼彻斯特编码C. NRZI 和曼彻斯特编码D. NRZI 和差分曼彻斯特编码答案A解析根据波形判断编码 1 为 NRZ编码 2 为曼彻斯特编码。知识点数字编码。第35题题目主机甲通过 128kbps 卫星链路采用滑动窗口协议向主机乙发送数据链路单向传播延迟为 250ms帧长为 1000 字节。不考虑确认帧的开销为使链路利用率不小于 80%帧序号的比特数至少是 。A. 3B. 4C. 7D. 8答案B解析发送一帧时间 1000×8 / 128000 62.5ms。RTT 500ms。窗口至少 (62.5500)/62.5 9。2³8 92⁴16 ≥ 9所以 4 位。知识点滑动窗口、信道利用率。第36题题目下列关于 CSMA/CD 协议的叙述中错误的是 。A. 边发送数据帧边检测是否发生冲突B. 适用于无线网络以实现无线链路共享C. 需要根据网络跨距和数据传输速率限定最小帧长D. 当信号传播延迟趋近 0 时信道利用率趋近 100%答案B解析CSMA/CD 适用于有线以太网不适用于无线。知识点CSMA/CD。第37题题目下列关于交换机的叙述中正确的是 。A. 以太网交换机本质上是一种多端口网桥B. 通过交换机互连的一组工作站构成一个冲突域C. 交换机每个端口所连网络构成一个独立的广播域D. 以太网交换机可实现采用不同网络层协议的网络互联答案A解析交换机是多端口网桥每个端口是一个冲突域整个交换机是一个广播域。知识点交换机。第38题题目某路由器的路由表如下表所示。若路由器收到一个目的地址为 169.96.40.5 的 IP 分组则转发该 IP 分组的接口是 。目的网络下一跳接口169.96.40.0/23176.1.1.1S1169.96.40.0/25176.2.2.2S2169.96.40.0/27176.3.3.3S30.0.0.0/0176.4.4.4S4A. S1B. S2C. S3D. S4答案C解析最长前缀匹配169.96.40.5 与 /27 匹配169.96.40.0/27 范围 169.96.40.031选 S3。知识点路由表、最长前缀匹配。第39题题目主机甲和主机乙新建一个 TCP 连接甲的拥塞控制初始阈值为 32KB甲向乙始终以 MSS1KB 大小的段发送数据并一直有数据发送乙为该连接分配 16KB 接收缓存并对每个数据段进行确认忽略段传输延迟。若乙收到的数据全部存入缓存不被取走则甲从连接建立成功时刻起未发送超时的情况下经过 4 个 RTT 后甲的发送窗口是 。A. 1KBB. 8KBC. 16KBD. 32KB答案A解析初始拥塞窗口 1KB慢开始1,2,4,8,16。但接收窗口 16KB4 个 RTT 后拥塞窗口 16KB发送窗口 min(16, 16) 16KB但乙缓存 16KB不被取走第 4 个 RTT 后接收窗口变为 0发送窗口为 0标准答案 A 1KB需仔细4 个 RTT 后乙接收缓存满通告窗口 0甲发送窗口 0。但选项无 0可能第 4 个 RTT 时发送窗口为 1KB。选 A。知识点TCP 拥塞控制、流量控制。第40题题目某浏览器发出的 HTTP 请求报文如下GET /index.html HTTP/1.1 Host: www.test.edu.cn Connection: Close Cookie: 123456下列叙述中错误的是 。A. 该浏览器请求浏览 index.htmlB. index.html 存放在 www.test.edu.cn 上C. 该浏览器请求使用持续连接D. 该浏览器曾经浏览过 www.test.edu.cn答案C解析Connection: Close 表示非持续连接。知识点HTTP 协议。二、综合应用题第 4147 小题共 70 分第41题15分题目用单链表保存 m 个整数结点的结构为data|link且|data|≤nn 为正整数。现要求设计一个时间复杂度尽可能高效的算法对于链表中 data 的绝对值相等的结点仅保留第一次出现的结点而删除其余绝对值相等的结点。解答1基本设计思想利用辅助数组flag[n1]记录绝对值是否出现过。遍历链表若flag[abs(data)] 0则保留置flag[abs(data)] 1否则删除该结点。2结点定义typedefstructnode{intdata;structnode*link;}Node;3算法描述voiddeleteDuplicates(Node*head,intn){int*flag(int*)calloc(n1,sizeof(int));Node*phead-link,*prehead;while(p!NULL){intabsValp-data0?p-data:-p-data;if(flag[absVal]0){flag[absVal]1;prep;pp-link;}else{pre-linkp-link;free(p);ppre-link;}}free(flag);}4时间复杂度 O(m)空间复杂度 O(n)。知识点链表操作、哈希思想。第42题8分题目已知含有 5 个顶点的图 G 如右图所示。图略解答1邻接矩阵 A行、列下标从 0 开始根据图填写。2求 A²矩阵 A² 中位于 0 行 3 列元素值的含义是从顶点 0 到顶点 3 的长度为 2 的路径条数。3若具有 n 个顶点的图的邻接矩阵为 B则 Bᵐ2≤m≤n中非零元素的含义是从对应行顶点到对应列顶点存在长度为 m 的路径。知识点图的邻接矩阵、路径计数。第43题13分题目某 16 位计算机的主存按字节编码存取单位为 16 位采用 16 位定长指令字格式CPU 采用单总线结构主要部分如下图所示。图略解答1程序员可见的寄存器R0R3、PC、IR实际上程序员可见通用寄存器、PC、标志寄存器等。设置暂存器 T 用于暂存数据避免总线冲突。2ALUop 位数ALU 有 7 种操作至少 3 位。SRop 有 3 种操作至少 2 位。3SRout 控制移位寄存器输出到总线。4端点①⑨中需连接到控制部件输出端的有①、②、③、④、⑤、⑦、⑧、⑨。5连线SRout 到总线ALUop 到 ALUSRop 到 SRMUXop 到 MUX 等。6MUX 一个输入端是 2用于选择常数 2如 PC2。知识点数据通路、控制信号。第44题10分题目题 43 中描述的计算机其部分指令执行过程的控制信号如下图 (a) 所示。图略解答1指令系统最多可定义 2^4 16 条指令。2机器码① inc R1操作码 01H寻址方式等。② shl R2,R1操作码 02H。③ sub R3,(R1),R2操作码 03H。3标号①⑧处的控制信号① MUXop0② SRopleft③ ALUopadd④ SRopmov⑤ MEMopread⑥ ALUopsub⑦ SRopmov⑧ R0in1。4指令“sub R1,R3,(R2)”执行阶段至少 3 个时钟周期“inc R1”至少 1 个时钟周期。知识点指令执行、控制信号。第45题9分题目有 A、B 两人通过信箱进行辩论……解答定义信号量emptyA M - xA 信箱空位数。fullA xA 信箱邮件数。emptyB N - yB 信箱空位数。fullB yB 信箱邮件数。mutexA 1A 信箱互斥。mutexB 1B 信箱互斥。A 进程while(TRUE){P(fullA);P(mutexA);从 A 信箱取邮件;V(mutexA);V(emptyA);回答问题并提新问题;P(emptyB);P(mutexB);将新邮件放入 B 信箱;V(mutexB);V(fullB);}B 进程类似。知识点信号量、同步互斥。第46题6分题目某计算机系统按字节编址采用二级页表的分页存储管理方式虚拟地址格式如下所示页目录号10位| 页表索引10位| 页内偏移量12位解答1页大小 2¹² 4KB。页框大小 4KB。虚拟地址空间 2³² 4GB页数 2²⁰ 页。2页目录项和页表项各占 4B。页目录大小 2¹⁰×4B 4KB占 1 页。页表总数 2¹⁰ 个每个页表 2¹⁰×4B 4KB占 1 页共 2¹⁰ 页。总页数 1 1024 1025 页。3虚拟地址 0100 0000H 和 0111 2048H 的页目录号分别为 4 和 4计算0100 0000H 0000 0001 0000 0000 0000 0000 0000 0000B页目录号 高10位 0000000100B 4。0111 2048H 0000 0001 0001 0001 0010 0000 0100 1000B页目录号 0000000100B 4。所以共访问 1 个二级页表。知识点二级页表、地址转换。第47题9分题目某网络拓扑如下图所示其中路由器内网接口、DHCP 服务器、WWW 服务器与主机 1 均采用静态 IP 地址配置……图略解答1DHCP 服务器可为主机 2主机 N 动态分配 IP 地址的最大范围根据子网划分假设路由器内网接口 IP 为 111.123.15.1/24则可用范围 111.123.15.2111.123.15.254。主机 2 发送 DHCP Discover 报文源 IP 0.0.0.0目的 IP 255.255.255.255。2主机 2 的 ARP 表为空访问 Internet 时第一个以太网帧的目的 MAC 地址是默认网关的 MAC 地址。封装发往 Internet 的 IP 分组的以太网帧目的 MAC 也是默认网关的 MAC 地址。3主机 1 子网掩码 255.255.255.0默认网关 111.123.15.2。若 WWW 服务器在 111.123.15.0/24 网段则能访问若不在同一网段需网关正确。根据配置主机 1 能访问 WWW 服务器也能访问 Internet。知识点DHCP、ARP、子网、路由。结语以上为 2015 年全国硕士研究生招生考试计算机学科专业基础试题408的详细解析。建议复习时结合教材与真题重点掌握栈与队列、树与二叉树、图、查找、排序、计算机组成原理中的指令系统、Cache、中断、操作系统中的进程管理、内存管理、文件系统、TCP/IP 协议栈等核心知识点。祝备考顺利