2015年计算机408统考考研真题及答案解析.pdf

返回 相似
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
点击查看更多>>
资源描述:
2015年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题 1~ 40小题,每小题 2分,共 80分。下列每题给出的四个选项中。只有一个选项符合题 目要求。 1.已知程序如下 int Sint n { returnn, , , }。若从顶点 v0。开始对图进行深度优先遍历,则可能得到的不同遍历序列个数 是 A. 2 B. 3 C. 4 D. 5 6.求下面带权图的最小 代价 生成树时,可能是克鲁斯卡尔 Kruskal算法第 2次选中但 不. 是普里姆 Prim 算法 从 v4开始 第 2次选中的边是 A. v1, v3 B. v1, v4 C. v2, v3 D. v3, v4 7.下列选项中, 不. 能构成折半查找中关键字比较序列的是 A. 500, 200, 450, 180 B. 500, 450, 200, 180 C. 180, 500, 200, 450 D. 180, 200, 500, 450 R.已知字符串 s为 “abaabaabacacaabaabcc”,模式串 t为 “abaabc5’。采用 KMP算法进行匹配,第一次出现 “失 配 ”s[i]≠t[j]时, ij5,则下次开始匹配时, i和 j的值分别是 A. i1, j0 B. i5, j0 C. i5, j2 D. i6, j2 9.下列排序算法中,元素的移动次数与关键字的初始排列次序无关的是 A.直接插入排序 B. 起泡排序 C.基数排序 D. 快速排序 10.已知小根堆为 8, 15, 10, 21, 34, 16, 12,删除关键字 8之后需重建堆,在此过程中,关键字之间 的比较次数是 A. 1 B. 2 C. 3 D. 4 11.希尔排序的组内排序采用的是 A.直接插入排序 B. 折半插入排序 C.快速排序 D. 归并排序 12.计算机硬件能够直接执行的是 Ⅰ .机器语言程序 Ⅱ .汇编语言程序 Ⅲ .硬件描述语言程序 A.仅 Ⅰ B. 仅 Ⅰ 、 Ⅱ C.仅 Ⅰ 、 Ⅲ D. Ⅰ 、 Ⅱ 、 Ⅲ 13.由 3个 “1”和 5个 “0”组成的 8位二进制补码,能表示的最小整数是 A. -126 B. -125 C. -32 D. -3 14.下列有关浮点数加减运算的叙述中,正确的 是 Ⅰ .对阶操作不会引起阶码上溢或下溢 Ⅱ .右规和尾数舍入都可能引起阶码上溢 Ⅲ .左规时可能引起阶码下溢 Ⅳ .尾数溢出时结果不一定溢出 A.仅 Ⅱ 、 Ⅲ B. 仅 Ⅰ 、 Ⅱ 、 Ⅳ C.仅 Ⅰ 、 Ⅲ 、 Ⅳ D. Ⅰ 、 Ⅱ 、 Ⅲ 、 Ⅳ 15.假定主存地址为 32位,按字节编址,主存和 Cache之间采用直接映射方式,主存块大小为 4个字,每 字 32位,采用回写 Write Back方式,则能存放 4K字数据的 Cache的总容量的位数至少是 A. 146K B. 147K C. 148K D. 158K 16.假定 编译器将赋值语句 “xx3; ”转换为指令 “add xaddr, 3”,其中, xaddr是 x对应的存储单元地址。 若执行该指令的计算机采用页式虚拟存储管理方式,并配有相应的 TLB,且 Cache使用直写 Write Through方 式,则完成该指令功能需要访问主存的次数至少是 A. 0 B. 1 C. 2 D. 3 17.下列存储器中,在工作期间需要周期性刷新的是 A. SRAM B. SDRAM C. ROM D. FLASH 18.某计算机使用 4体交叉编址存储器,假定在存储器总线上出现的主存地址 十 进制 序列为 8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000,则可能发生访存冲突的地址对是 A. 8004和 8008 B. 8002和 8007 C. 8001和 8008 D. 8000和 8004 19.下列有关总线定时的叙述中,错误的是 A.异步通信方式中,全互锁协议的速度最慢 B.异步通信方式中,非互锁协议的可靠性最差 C.同步通信方式中,同步时钟信号可由各设备提供 D.半同步通信方式中,握手信号的采样由同步时钟控制 20.若磁盘转速为 7200转 /分,平均寻道时间为 8 ms,每个磁道包含 1000个扇区,则访问一个扇区的平均 存取时间大约是 A. 8.1 ms B. 12.2 ms C. 16.3 ms D. 20.5 ms 21.在采用中断 I/O方式控制打印输出的情况下, CPU和打印控制接口中的 I/O端口之间交换的信息不可能 是 A.打印字符 B. 主存地址 C.设备状态 D. 控制命令 22.内部异常 内中断 可分为故障 fault、陷阱 trap和终止 abort三类。下列有关内部异常的叙述中,错 误的是 A.内部异常的产生 与当前执行指令相关 B.内部异常的检测由 CPU内部逻辑实现 C.内部异常的响应发生在指令执行过程中 D.内部异常处理后返回到发生异常的指令继续执行 23.处理外部中断时,应该由操作系统保存的是 A.程序计数器 PC的内容 B. 通用寄存器的内容 C.快表 TLB中的内容 D. Cache中的内容 24.假定下列指令已装入指令寄存器,则执行时 不. 可能导致 CPU从用户态变为内核态 系统态 的是 A. DIV R0, R1 ; R0/R1→R0 B. INT n ; 产生软中断 C. NOT R0 ;寄存器 R0的内容取非 D. MOV R0, addr;把地址 addr处的内存数据放入寄存器 R0中 25.下列选项中,会导致进程从执行态变为就绪态的事件是 A.执行 Pwait操作 B. 申请内存失败 C.启动 I/O设备 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。若进程要访问的下一页的页号为 7,依据 LRU算法,应淘汰页的页号是 A. 2 B. 3 C. 4 D. 8 28.在系统内存中设置磁盘缓冲区的主要目的是 A.减少磁盘 I/O次数 B. 减少平均寻道时间 C.提高磁盘数据可靠性 D. 实现设备无关性 29.在文件的索引节点 中存放直接索引指针 10个,一级和二级索引指针各 1个。磁盘块大小为 1 KB,每个 索引指针占 4个字节。若某文件的索引节点已在内存中,则把该文件偏移量 按字节编址 为 1234和 307400处所 在的磁盘块读入内存,需访问的磁盘块个数分别是 A. 1、 2 B. 1、 3 C. 2、 3 D. 2、 4 30.在请求分页系统中,页面分配策略与页面置换策略 不. 能组合使用的是 A.可变分配,全局置换 B. 可变分配,局部置换 C.固定分配,全局置换 D. 固定分配,局部置换 31.文件系统用位图法表示磁盘空间的分配情 况,位图存于磁盘的 32~ 127号块中,每个盘块占 1024个字 节,盘块和块内字节均从 0开始编号。假设要释放的盘块号为 409612,则位图中要修改的位所在的盘块号和块 内字节序号分别是 A. 81、 1 B. 81、 2 C. 82、 1 D. 82、 2 32.某硬盘有 200个磁道 最外侧磁道号为 0,磁道访问请求序列为 130, 42, 180, 15, 199,当前磁头 位于第 58号磁道并从外侧向内侧移动。按照 SCAN调度方法处理完上述请求后,磁头移过的磁道数是 A. 208 B. 287 C. 325 D. 382 33.通过 POP3协议接收邮件时,使用的传输层服务类型是 A.无连接不可靠的数据传输服务 B.无连接可靠的数据传输服务 C.有连接不可靠的数据传输服务 D.有连接可靠的数据传输服务 34.使用两种编码方案对比特流 01100111进行编码的结果如下图所示,编码 1和编码 2分别是 A. NRZ和曼彻斯特编码 B. NRZ和差分曼彻斯特编码 C. NRZI和曼彻斯特编码 D. NRZI和差分曼彻斯特编码 35.主机甲通过 128 kbps卫星链路,采用滑动窗口协议向主机乙发送数据,链路单 向传播延迟为 250 ms, 帧长为 1000字节。不考虑确认帧的开销,为使链路利用率不小于 80%,帧序号的比特数至少是 A. 3 B. 4 C. 7 D. 8 36.下列关于 CSMA/CD协议的叙述中, 错误 . . 的是 A.边发送数据帧,边检测是否发生冲突 B.适用于无线网络,以实现无线链路共享 C.需要根据网络跨距和数据传输速率限定最小帧长 D.当信号传播延迟趋近 0时,信道利用率趋近 100% 37.下列关于交换机的叙述中,正确的是 A.以太网交换机本质上是一种多端口网桥 B.通过交换 机互连的一组工作站构成一个冲突域 C.交换机每个端口所连网络构成一个独立的广播域 D.以太网交换机可实现采用不同网络层协议的网络互联 38.某路由器的路由表如下表所示 目的网络 下一跳 接口 169.96.40.0/23 169.96.40.0/25 169.96.40.0/27 0.0.0.0/0 176.1.1.1 176.2.2.2 176.3.3.3 176.4.4.4 S1 S2 S3 S4 若路由器收到一个目的地址为 169.96.40.5的 IP分组,则转发该 IP分组的接口 是 A. S1 B. S2 C. S3 D. S4 39.主机甲和主机乙新建一个 TCP连接,甲的拥塞控制初始阈值为 32 KB,甲向乙始终以 MSS1 KB大小 的段发送数据,并一直有数据发送;乙为该连接分配 16 KB接收缓存,并对每个数据段进行确认,忽略段传输 延迟。若乙收到的数据全部存入缓存,不被取走,则甲从连接建立成功时刻起,未发生超时的情况下,经过 4 个 RTT后,甲的发送窗口是 A. 1 KB B. 8KB C. 16KB D. 32KB 40.某浏览器发出的 HTTP请求报文如下 GET/index.html HTTP/1.1 Host www.test.edu.cn Connection Close Cookie 123456 下列叙述中, 错误 . . 的是 A.该浏览器请求浏览 index.html B. index,html存放在 www.test.edu.cn上 C.该浏览器请求使用持续连接 D.该浏览器曾经浏览过 www.test.edu.cn 二、综合应用题 41~ 47小题,共 70分。 41. 15分 用单链表保存 m个整数,结点的结构为 ,且 |data|≤nn为正整数 。现要求设计一个 时间复杂度尽可能高效的算法,对于链表中 data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝 对值相等的结点。例如,若给定的单链表 head如下 则删除结点后的 head为 要习之 1给出算法的基本设计思想。 2使用 C或 C语言,给出单链表结点的数据类型定义。 3根据设计思想,采用 C或 C语言描述算法,关键之处给出注释。 4说明你所设计算法的时间复杂度和空间复杂度。 42. 8分 已知含有 5个顶点的图 G如 下图所示。 请回答下列问题。 1写出图 G的邻接矩阵 A行、列下标均从 0开始 。 2求 A2,矩阵 A2中位于 0行 3列元素值的含义是什么 3若已知具有 nn≥2个顶点的图的邻接矩阵为 B,则 Bm2≤m≤n中非零元素的含义是什么 43. 13分 某 16位计算机的主存按字节编址,存取单位为 16位;采用 16位定长指令字格式; CPU采用单总 线结构,主要部分如下图所示。图中 R0~ R3为通用寄存器; T为暂存器; SR为移位寄存器,可实现直送 mov、 左移一位 left和右移一位 right3种操作,控制信号为 SRop, SR的输出由信号 SRout控制; ALU可实现直送 Amova、 A加 Badd、 A减 Bsub、 A与 Band、 A或 Bor、非 Anot、 A加 line7种操作,控制信号为 ALUop。 请回答下列问题。 1图中哪些寄存器是程序员可见的 为何要设置暂存器 T 2控制信号 ALUop和 SRop的位数至少各是多少 3控制信号 SRout所控制部件的名称或作用是什么 4端点 ① ~ ⑨ 中,哪些端点须连接到控制部件的输出端 5为完善单总线数据通路,需要在端点 ① ~ ⑨ 中相应的端点之间 添加必要的连线。写出连线的起点和终点,以正确表示数据的流动方向。 6为什么二路选择器 MUX的一个输入端是 2 44. 10分 题 43中描述的计算机,其部分指令执行过程的控制信号如题 44图 a所示。 题 44图 a部分指令的控制信号 该机指令格式如题 44图 b所示,支持寄存器直接和寄存器间接两种寻址方式,寻址方式位分别为 0和 1,通 用寄存器 R0~ R3的编号分别为 0、 1、 2和 3。 题 44图 b指令格式 请回答下列问题。 1该机的指令系统最多可定义多少条指令 2假定 inc、 shl和 sub指令的操作码分别为 01H、 02H和 03H,则以下指令对应的机器代码各是什么 ① inc R1 ; R11→R1 ② sh1 R2, R1 ; R1linkNULL { mp-link-data0 p-link-data -p-link一 data; if*qm0 //判断该结点的 data是否已 //出现过 { *qm1; //首次出现 pp-link; //保留 } else //重复出现 { rp-link; //删除 p-linkr-link; freer; } } freeq; } 【 1、 2、 3的评分说明】 ① 若考生设计的算法满足题目的功能要求且正 确,则 1、 3根据所实现算法的时间复杂度给分,细则见 下表 时间复杂度 分数 说明 Om 11 对链表进行一趟扫描,且采用时间复杂度为 O1的方法判断 |data|是否是首次出现。 Om 8 对链表进行一趟扫描,且采用时间复杂度 O 1的方法判断 |data|是否是首次出现。 O m 5 对链表进行多趟扫描,例如采用顺序查找算法,对每个结点在 当前链表中进行查找,删除重复出现的结点。 ② 若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路,但在算法实现中能 够表达出算 法思想且正确的,可参照 ① 的标准给分。 ③ 若算法的基本设计思想描述或算法实现中部分正确,可参照 ① 中各种情况的相应给分标准酌情给分。 ④ 若考生给出的单链表结点的数据类型定义与题目中所给的结点形式不完全相同,酌情给分。 ⑤ 参考答案中只给出了使用 C语言的版本,使用 C语言的答案视同使用 C语言。 4参考答案所给算法的时间复杂度为 Om,空间复杂度为 On。 【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致,可给分。 42. 【答案要点】 1图 G的邻 接矩阵 A如下                  01011 10110 01001 11001 10110 A 2A2如下                  31221 13013 20220 21231 13013 2A 0行 3列的元素值 3表示从顶点 0到顶点 3之间长度为 2的路径共有 3条。 3Bm2≤m≤n中位于 i行 j列 0≤i, j≤n-1的非零元素的含义是图中从顶点 i到顶点 j长度为 m的路径条数。 【评分说明】 ① 若考生给出的邻接矩阵 A中,结点与行、列的对应次序与本参考答案不完全一致,只要正确,同样给分。 问题 2中,考生所给的答案中顶点编号要与其所给的邻接矩阵相对应 。 ② 若考生给出的矩阵 A及 A2部分正确,酌情给分。 ③ 若考生分别说明矩阵 B2、 B3、 、 Bn中非零元素的含义,同样给分。 ④ 若考生给出的 Bn2≤m≤n中非零元素的含义部分正确,酌情给分。 43. 【答案要点】 1程序员可见寄存器为通用寄存器 R0~ R3和 PC。因为采用了单总线结构,因此,若无暂存器 T,则 ALU 的 A、 B端口会同时获得两个相同的数据,使数据通路不能正常工作。 【评分说明】回答通用寄存器 R0~ R3,给分;回答 PC,给分;部分正确,酌情给分。设置暂存器 T的原 因若回 答用于暂时存放端口 A的数据,则给分,其他答案,酌情给分。 2ALU共有 7种操作,故其操作控制信号 ALUop至少需要 3位;移位寄存器有 3种操作,其操作控制信号 SRop至少需要 2位。 3信号 SRout所控制的部件是一个三态门,用于控制移位器与总线之间数据通路的连接与断开。 【评分说明】只要回答出三态门或者控制连接 /断开,即给分。 4端口 ① 、 ② 、 ③ 、 ⑤ 、 ⑧ 须连接到控制 部件输出端。 【评分说明】答案包含 ④ 、 ⑥ 、 ⑦ 、 ⑨ 中任意一个,不给分;答案不全酌情给分。 5连线 1, ⑥ → ⑨ ;连线 2, ⑦ → ④ 。 【评分说明】回答除上述连线以外的其他连线,酌情给分。 6因为每条指令的长度为 16位,按字节编址,所以每条指令占用 2个内存单元,顺序执行时,下条指令地 址为 PC2。 MUX的一个输入端为 2,可便于执行 PC2操作。 44. 【答案要点】 1指令操作码有 7位,因此最多可定义 27128条指令。 2各条指令的机器代码分别如下 ① “inc R1”的机器码为 0000001 0 01 0 00 0 00,即 0240H。 ② “sh1 R2, R1”的机器码为 0000010 0 10 0 01 0 00,即 0488H。 ③ “sub R3, R1, R2”的机器码为 0000011 0 11 1 01 0 10,即 06EAH。 3各标号处的控制信号或控制信号取值如下 ① 0; ② mov; ③ mova; ④ left; ⑤ read; ⑥ sub; ⑦ mov; ⑧ SRout。 【评分说明】答对两个给分。 4指令 “sub R1, R3, R2”的执行阶段至少包含 4个时钟周期; 指令 “inc R1”的执行阶段至少包含 2个时钟周期。 45. 【答案要点】 semaphore Full_A x ; semaphore Empty_A M-x; semaphore Full_B y ; semaphore Empty_B N-y; semaphore mutex_A 1 ; semaphore mutex_B 1 ; //Fuu_A表示 A的信箱中的邮件数量 //Empty_A表示 A的信箱中还可存放的邮件数量 //Full_B表示 B的信箱中的邮件数量 //Empty_B表示 B的信箱中还可存放的邮件数量 //mutex_A用于 A的信箱互斥 //mutex_B用于 B的信箱互斥 CoBegin A{ whileTRUE{ PFull_A; Pmutex_A; 从 A 的信箱中取出一个邮件; Vmutex_A; VEmpty_A; 回答问题并提出一个新问题; PEmpty_B; Pmutex_B; 将新邮件放入 B 的信箱; Vmutex_B; VFull_B; } } B{ whileTRUE{ PFull_B; Pmutex_B; 从 B 的信箱中取出一 个邮件; Vmutex_B; VEmpty_B; 回答问题并提出一个 新问题; PEmpty_A; Pmutex_A; 将新邮件放入 A 的 信箱; Vmutex_A; VFull_A; } } CoEnd 【评分说明】 ① 每对信号量的定义及初值正确,给分。 ② 每个互斥信号量的 P、 V操作使用正确,各给分。 ③ 每个同步信号量的 P、 V操作使用正确,各给分。 ④ 其他答 案酌情给分。 46. 【答案要点】 1页和页框大小均为 4 KB。进程的虚拟地址空间大小为 232/212220页。 2210*4/212页目录所占页数 220*4/212页表所占页数 1025页。 3需要访问一个二级页表。因为虚拟地址 0100 0000H和 0111 2048H的最高 10位的值都是 4,访问的是同一 个二级页表。 【评分说明】用其他方法计算,思路和结果正确同样给分。 47. 【答案要点】 1DHCP服务器可为主机 2~主机 N动态分配 IP地址的最 大范围是 111.123.15.5~ 111.123.15.254;主机 2 发送的封装 DHCPDiscover报文的 IP分组的源 IP地址和目的 IP地址分别是 0.0.0.0和 255.255.255.255。 2主机 2发出的第一个以太网帧的目的 MAC地址是 ff-ff-ff-ff-ff-ff;封装主机 2发往 Internet的 IP分组的以太 网帧的目的 MAC地址是 00-al-al-al-al-al。 3主机 1能访问 WWW服务器,但不能访问 Internet。由于主机 1的子网掩码配置正确而默认网关 IP地址被 错 误地配置为 111.123.15.2正确 IP地址是 111.123.15.1,所以主机 1可以访问在同一个子网内的 WWW服务器, 但当主机 1访问 Internet时,生机 1发出的 IP分组会被路由到错误的默认网关 111.123.15.2,从而无法到达目的主 机。
展开阅读全文

copyright@ 2018-2019 考拉文库网站版权所有
经营许可证编号:陕ICP备18022950号-1