2012年计算机408统考真题_408计算机统考历年真题_2009-2025计算机408统考真题

2012年计算机408统考真题 第 1 页，共 8 页II. 所有权值最小的边一定会出现在所有的最小生成树中 III. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 IV. 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 A. 仅I B. 仅II C. 仅1、III D. 仅II、IV 9. 已知一棵3阶B-树，如下图所示。删除关键字78得到一棵新B-树，其最右叶结点中 的关键字是 。 10 A. 60 B. 60 62 C. 62,65 D. 65 10. 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下 列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是 。 I. 简单选择排序 II. 希尔排序 III. 快速排序 v. IV. 堆排序 二路归并排序 A. 仅I、III、IV B. 仅I、 III、 V C. 仅II、 III、 IV D. 仅III、 IV、 V 11. 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处 是 A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 12.假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为 1/0时间。若CPU速度提高50%, 1/0速度不变，则运行基准程序A所耗费的时间是 。 A. 55s B. 60s C. 65s D. 70s 13. 假定编译器规定int和short型长度分别为32位和16位，执行下列C语言语句： unsigne!d sho工t x=65530; urii:i:i,gped . inl;. ·Y": 幻 得到y的机器数为 。 A. 0000 7FFAH 气 B. 0000 FFFAH C. FFFF 7FFAH D. FFFF FFFAH 14. float类型（即IEEE 754单精度浮点数格式）能表示的最大正整数是 。 A. i126_ 2 103 B. i121i104 C. i121_i103 D. i12si104 15. 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下： st工uct{ int a; cha工 b; sho工 t c; } record; recerd.a=273; 若record变量的首地址为OxC008,则地址OxC008中内容及record.c的地址分别为 。 A. OxOO、 OxCOOD B. OxOO、OxCOOE 2012年计算机408统考真题 第 2 页，共 8 页C. Oxll、OxCOOD D. Oxll、OxCOOE 16. 下列关于闪存CFal sh Memory)的叙述中，错误的是 。 A. 信息可读可写，并且读、写速度一样快 B. 存储元由MOS管组成，是一种半导体存储器 C. 掉电后信息不丢失，是一种非易失性存储器 D. 采用随机访问方式，可替代计算机外部存储器 17. 假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。 若Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为 0, 4, 8, 2, 0, 6, 8, 6, 4, 8 时，命中Cache的次数是 。 A. 1 B. 2 C. 3 D. 4 18. 某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码 法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5 和6个微命令，则操作控制字 段至少有 。 A. 5位 B. 6位 C. 15位 D. 33位 19. 某同步总线的时钟频率为100MHz, 宽度为32位，地址／数据线复用，每传输一个地 址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次 “ 主存写 ”总线事 务传输128位数据所需要的时间至少是 。 A. 20ns B. 40ns C. 50ns D. 80ns 20. 下列关于USB总线特性的描述中，错误的是 。 A. 可实现外设的即插即用和热拔插 B. 可通过级联方式连接多台外设 C. 是一种通信总线，连接不同外设 D. 同时可传输2位数据，数据传输率高 21. 下列选项中，在1/0总线的数据线上传输的信息包括 。 I. 10/ 接口中的命令字 II. 1/0接口中的状态字 III. 中断类型号 A. 仅I、II B. 仅I、III C. 仅II、III D. I、II、III 22. 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括 。 I. 关中断 II. 保存通用寄存器的内容 III. 形成中断服务程序入口地址并送PC A. 仅I、II B. 仅I、III C. 仅II、III D. I、II、III 23. 下列选项中，不可能在用户态发生的事件是 。 A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 24. 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不 需要保存其内容的是 。 A. 程序计数器 B. 程序状态字寄存器 c. 通用数据寄存器 D. 通用地址寄存器 25. 下列关于虚拟存储器的叙述中，正确的是 。 A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 26. 操作系统的10/ 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。 2012年计算机408统考真题 第 3 页，共 8 页其合理的层次组织排列顺序是 A. 用户级I/0软件、设备无关软件、设备驱动程序、中断处理程序 B. 用户级I/0软件、设备无关软件、中断处理程序、设备驱动程序 C. 用户级I/0软件、设备驱动程序、设备无关软件、中断处理程序 D. 用户级1/0软件、中断处理程序、设备无关软件、设备驱动程序 27. 假设5个进程 P。、P1 、P2 、P3 、P4 共享三类资源 R 1 、R 2 、R 3 , 这些资源总数分别为18、 6、22。TO时刻的资源分配情况如下表所示，此时存在的一个安全序列是 。 已分配资源 资源最大需求 进程 R1 R2 R3 R, R2 R3 。 p 3 2 3 5 5 10 P1 4 。 3 5 3 6 P2 4 。 5 4 。 II Pi 2 。 4 4 2 5 P4 3 1 4 4 2 4 A. Po, P2, P4, Pr, P3 B. P1, Po, P3, P4, P2 。 C. P2, P1, Po, P3, P4 D. P3, P4, P2, P1, P 28. 若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的 叙述中，正确的是 。 I. 若该文件的数据不在内存中，则该进程进入睡眠等待状态 II. 请求read系统调用会导致CPU从用户态切换到核心态 III. read系统调用的参数应包含文件的名称 A. 仅I、II B. 仅I、III C. 仅II、III D. I、II和III 29. 一个多道批处理系统中仅有P1 和P2 两个作业，P2 比P1晚5ms到达，它们的计算和1/0 操作顺序如下： Pi : 计算60ms, 1/08 0ms, 计算20ms P2 : 计算120ms, 1/04 0ms, 计算40ms 若不考虑调度和切换时间，则完成两个作业需要的时间最少是 A. 240ms B. 260ms C. 340ms D. 360ms 30. 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错 误的是 A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 31. 下列关于进程和线程的叙述中，正确的是 。 A. 不管系统是否支待线程，进程都是资源分配的基本单位 B. 线程是资源分配的基本单位，进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不同的地址空间 32. 下列选项中，不能改善磁盘设备1/0性能的是 A. 重排1/0请求次序 B. 在一个磁盘上设置多个分区 2012年计算机408统考真题 第 4 页，共 8 页C. 预读和滞后写 D. 优化文件物理块的分布 33. 在 TCP/IP体系结构中， 直接为ICMP提供服务的协议是 。 A. PPP B. IP C. UDP D. TCP 34. 在物理层接口特性中， 用于描述完成每种功能的事件发生顺序的是 。 A. 机械特性 B. 功能 特性 C. 过程特性 D. 电气特性 35. 以太网的MAC 协议提供的是 。 A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 36. 两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据， 数据传输速率为 16kbps, 单向传播时延为270ms, 数据帧长度范围是12s�s12字节， 接收方总是以与数据帧等 长的帧进行确认。 为使信道利用率达到最高， 帧序号的比特数至少为 。 A. 5 B. 4 C. 3 D. 2 37. 下列关千IP路由器功能 的描述中， 正确的是 。 I. 运行路由协议， 设置路由表 II. 监测到拥塞时， 合理丢弃IP分组 III. 对收到的IP分组头进行差错校验， 确保传输的IP分组不丢失 IV. 根据收到的IP分组的目 的 IP地址， 将其转发到合适的输出线路上 A. 仅III、.IV B. 仅I、 II、 III c. 仅I、II、IV D. I、II、III、IV 38. ARP协议的功能是 。 A. 根据IP地址查询MAC地址 B. 根据MAC地址查询IP地址 C. 根据域名查询IP地址 D. 根据IP地址查询域名 39. 某主机的IP地址为180.80.77.55, 子网掩码为255.255.252.0。 若该主机向其所在子网 发送广播分组 ， 则目的地址可以是 A. 180.80.76.0 B. 180.80.76.255 C. 180.80.77.255 D. 180.80.79.255 40. 若用户1 与用户2之间发送和接收电子邮件的过程如下图所示， 则图中＠、＠、©阶 段分别使用的应用层协议可以是 。 用户1的 用户2的 用户l 邮件服务器 邮件服务器 用户2 —©一§ A. SMTP、 SMTP、 SMTP B. POP3、SMTP、POP3 C. POP3、 SMTP、 SMTP D. SMTP、 SMTP、 POP3 二、综合应用题（第41-47题， 共70分） 41. 设有6个有序表A、B、C、D、E、F, 分别含有10、35、40、50、60和200个数据 元素， 各表中元素按升序排列。 要求通过5次两 两合并， 将6个表最终合并成1个升序表， 并 在最坏情况下比较的总次数达到最小。 请回答下列问题。 1)给出完整的合并过程， 并求出最坏情况下比较的总次数。 2)根据你的合并过程， 描述N(N?::2)个不等长升序表的合并策略， 并说明理由。 42. 假定采用带头结点的 单链表保存单词， 当两个单词有相同的后缀时， 则可共享相同的 2012年计算机408统考真题 第 5 页，共 8 页后缀存储空间， 例如，"loading"和"being" 的存储映像如下图所示。 strl str2 I I I, 设strl和str2分别指向两个 单词所在单链表的头结点，链表结点结构为 扫ta ne灶 请设计 一个时间上尽可能高效的算法， 找出由strl和str2 所指向两个链表共同后缀的起始位置（如图 中字符i所在结点的位置p)。 要求： 1)给出算法的基本设计思想。 2)根据设计思想， 采用C或C++或Java语言描述算法， 关键之处给出注释。 3)说明你所 设计算法的时间复杂度 。 43.假 定某计算机的CPU主频为80MHz,CP为I 4,平均每条指令访存1.5次，主存与Cache 之间交换的块大小为 16B,Cache的命中率为99%, 存储器总线宽度为32位。请回答下列问题。 1) 该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送 的情况下， 主存带宽至少达到多少才能满足CPU的访存要求？ 2)假定在Cache缺失的情况下访问主存时， 存在0.0005%的缺页率 ， 则CPU平均每秒产 生多少次缺页异常？若页面大小为4KB, 每次缺页都需要访问磁盘， 访问磁盘时DMA传送采 用周期挪用方式， 磁盘1/0接口的数 据缓冲寄存器为32 位， 则磁盘1/0接口平均每秒发出的 DMA请求次数至少是多少？ 3) CPU和DMA控制器同时要求使用存储器总线时， 哪个优先级更高？为什么？ 4)为了提高性能，主存采用四体低位交叉存储模式，工作时每1/4个存储周期启动一个体。 若每个体的存储周期为50ns, 则该主存能提供的最大带宽是多少？ 44. 某16位计算机中， 带符号整数用补码表示， 数据Cca he和指令Cca he分离。 题44表 给出了指令系统中部分指令格式， 其中Rs和Rd表示寄存器， mem表示存储单元地址，(x)表 示寄存器x或存储单元x的内容。 指令系统中部分指令格式 名称 指令的汇编格式 指令功能 加法指令 ADD Rs, Rd (Rs)+ (Rd)->Rd 算术I逻辑左移 SHL Rd 2*(Rd)->Rd 算术右移 SHR Rd (Rd)/2->Rd 取数指令 LOAD Rd,mem (mem)->Rd 存数指令 STORE Rs, mem (Rs)->mem 该计算机采用5段流水方式执行指令， 各流水段分别是取指OF)、 译码／读 寄存器(ID)、 执行／计算有效地址(EX)、 访问存储器CM)和结果写回寄存器(WB),流水线采用 “按序发 射， 按序完成 ” 方式， 没有采用转发技术处理数据相关， 并且同一个寄存器的读和写操作不能 在同一个时钟周期内进行。 请回答下列问题： 1)若int型变量x的值为-513, 存放在寄存器Rl中， 则执行指令"SHR Rl"后，Rl 的 内容是多少？ （用十六进制表示） 2)若某个时间段中， 有连续的4条指令进入流水线，在其 执行过程中没有发生任何阻塞， 则执行这4 条指令所需的时钟周期数为多少？ 2012年计算机408统考真题 第 6 页，共 8 页3)若高级语言程序中某赋值语句为X=a+ b, X 、 a和b均为int型变量，它们的存储单 元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在指令流水线中的执行过程如下 图所示。 I1 LOAD Rl, [a] Ii LOAD R2, [b] l ADD Rl,R2 3 14 STORE R2, [x] 时间单元 指令 I 2 3 4 5 6 7 8 9 10 11 12 13 14 I1 IF ID EX M WB IF ID EX M WB Ii !3 IF ID EX M WB Li IF ID EX M WB 则这 4条指令执行过程中，l 的ID段和l4的IF段被阻塞的原因各是什么？ 3 4)若高级语言程序中某赋值语句为x=x*2 + a, x和a均为unsignedint类型变量，它们的 存储单元地址分别表示为[x]、[a], 则执行这条语句至少需要多少个时钟周期？要求模仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。 45. 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单 位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入 到 空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用 过且还在空闲页链表中，那么重新放回进程的驻留集中；否则，从空闲页框链表头部取出一 个页框。 假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。 目前系统空闲页框链表 中页框号依次为32、 15、 21、 41。进程P依次访问的＜虚拟页号，访问时刻＞是,< 3, 2>,< O, 4>,< O,6 >,< I, 11>,< O, 13>,< 2, 14>。请回答下列问题。 1)访问<0,4>时，对应的页框号是什么？说明理由。 2)访问时，对应的页框号是什么？说明理由。 3)访问<2,14>时，对应的页框号是什么？说明理由。 4)该策略是否适合于时间局部性好的程序？说明理由。 46. 某文件系统空间的最大容量为4TB CITB =2 40B), 以磁盘块为基本分配单位。磁盘块 大小为IKB。文件控制块(FCB)包含一个512B的索引表区。请回答下列问题。 1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中 块号最少占多少字节？可支持的单个文件最大长度是多少字节？ 2)假设索引表区采用如下结构：第0-7字节采用＜起始块号，块数＞格式表示文件创建时 预分配的连续存储空间，其中起始块号占6B , 块数占2B; 剩余504字节采用直接索引结构， 一个索引项占6B, 那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最 大，请指出起始块号和块数分别所占字节数的合理值并说明理由。 47. 主机H通过快速以太网连接Internet, IP地址为192.168.0.8, 服务器S的IP地址为 211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。 2012年计算机408统考真题 第 7 页，共 8 页题 47-a表 编号 分组的前 字节内容（十六进制） IP 40 45000030 Ol 9b4000 8006 lde8 c0a80008 d3444750 Ob d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d bO0 0 00 2 43000030 00004000 31066e83 d3444750 c0a80008 13 88 Ob d9 eO5 9 9fef 84 6b 41 c6 70 12 16d O 37e l 00 00 3 45000028 019c4000 80061def c0a80008 d3444750 Ob d9 13 88 84 6b 41 c6 eO 59 9ffU 50 fU 43 80 2b 32 00 00 4 45000038 019d4000 8006 ldde c0a80008 d3444750 Ob d9 13 88 84 6b 41c 6 eO 599 ffU 50 18 43 80 e65 5 00 00 5 45000028 68114000 3106067a d3444750 c0a80008 13 88 Ob d9 eO5 99 ffU 84 6b 41 d6 50 10 16 dO 57d 2 00 00 回答下列问题。 题 表中的 分组中， 哪几个是由 发送的？哪儿个完成了 连接建立过程？ 1) 47-a IP H TCP 哪儿个在通过快速以太网传输时进行了填充？ 根据题 表中的 分组， 分析 已经收到的应用层数据字节数是多少？ 2) 47-a IP S 若题 表中的某个 分组在 发出时的前 字节如题 表所示，则该 分组到 3) 47-a IP S 40 47-b IP 达 时经过了多少个路由器？ H 题 47-b表 来自S的分组 45 00 00 28 68 11 40 00 40 06e c ad d3 44 475 0 ca 76 0 I 06 13 88 al 08 eO 59 9ffil 84 6b 41 d6 50 10 16 dO b7d 6 00 00 注： 分组头和 段头结构分别如题 图和题 图所示。 IP TCP 47a- 47-b bit OI I I I I I I I 8I I I I I I I I 16I I I I I I I I 2I4 I I I I I I I 3I I I 言 版本i 服务类型 总长度 标识 标志I 片偏移 生存时间(TTL)I 协议 头部校验和 源 地址 IP 目的 地址 IP 题 图 分组头结构 47-a IP 位 32 位 0 8 16 24 31 ! I 源端口 目的端口 序号 的 I 20� 固定首部 首 TC 部 P 数据 窗口 保留 偏移 检验和 紧急指针 选项（长度可变） 填充 题 图 段头结构 47-b TCP 2012年计算机408统考真题 第 8 页，共 8 页