2012 年计算专业综合考研真题 一、选择题. 1、求整数 n(n≥0)阶乘的算法如下,其时间复杂度是( ) int fact(int n) { if (n<=1) return 1; return n*fact(n-1); } A. O(log2n) B. O(n) C. (nlog2n) D. O(n2 ) 2、已知操作符包括'和')'.将中缀表达式 a+b-a*((c+d)/e-f)+g 转换 为等价的后缀表达式 ab+acd+e/f-**-g+时, 用栈来存放暂时还不能确定运算次序的操 作符,若栈初始时为空,则转换过程中同时保存栈中的操作符的最大个数是( ) A. 5 B. 7 C. 8 D. 11 3、若一颗二叉树的前序遍历序列为 a, e, b, d, c,后续遍历序列为 b, c, d, e, a,则根节点的孩 子节点( ) A. 只有 e B. 有e、b C. 有e、c D. 无法确定 4、若平衡二叉树的高度为 6,且所有非叶节点的平衡因子均为 1,则该平衡二叉树的节点总 数为( ) A. 10 B. 20 C. 32 D. 33 5、对有 n 个节点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂 度( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 6、若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的 结构是( ) A. 存在,且唯一 B. 存在,且不唯一 C. 存在,可能不唯一 D. 无法确定是否存在 7、如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求源点 a 到其他各顶点的最短路径, 得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是 c,后续得到的 其余各最短路径的目标顶点依次是( ) 5 1 3 A. d, e, f B. e, d ,f C. f,d,e D. f,e,d 8、下列关于最小生成树的说法中,正确的是( ) Ⅰ、最小生成树的代价唯一 Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ、使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ、使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅰ、Ⅲ D. 仅Ⅱ、Ⅳ 9、已知一棵 3 阶B-树,如下图所示.删除关键字 78 得到一棵新 B-树,其最右叶结点中的 关键字是( ) A. 60 B. 60, 62 C. 62, 65 D. 65 1 10、在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序.下列 排序方法中,每一趟排序结束都至少能够确定一个元素最终位置的方法是( ) Ⅰ.简单选择排序 Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排序 Ⅴ.二路归并排序 A. 仅Ⅰ、Ⅲ、Ⅳ B. 仅Ⅰ、Ⅲ、Ⅴ C. 仅Ⅱ、Ⅲ、Ⅳ D. 仅Ⅲ、Ⅳ、Ⅴ 11.对一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是 ( ) A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 12、假定基准程序 A 在某计算机上的运行时间为 100 秒,其中 90 秒为 CPU 时间,其余为 I/O 时间. 若CPU 速度提高 50%, I/O 速度不变, 则运行基准程序 A 所耗费的时间是( ) A. 55 B. 60 C. 65 D. 70 13、假定编译器规定 int 和short 型长度分别为 32 位和 16 位,执行下列 C 语言语句: unsighned short x = 65530; unsigned int y = x; 得到 y 的机器数为( ) A. 0000 7FFAH B. 0000 FFFAH C. FFFF 7FFAH D. FFFF FFFAH 14、float 类型(即IEEE754 单精度浮点数格式)能表示的最大正整数是( ) A. 2126 - 2103 B. 2127 - 2104 C. 2127 - 2103 D. 2128 - 2104 15、某计算机存储器按字节编址,采用小端方式存放数据.假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位,并且数据按边界对齐存储.某C语言程序段如下: struct{ int a; char b; short c; }record; record.a = 273; 若record 变量的首地址为 0xC008,则地址 0xC008 中内容及 record.c 的地址分别是( ) A. 0x00、0xC00D B. 0x00、0xC00E C. 0x11、0xC00D D. 0x11、0xC00E 16、下列关于闪存(Flash 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 2 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、下列选项中,在I/O 总线的数据线上传输的信息包括( ) . Ⅰ I/O 接口中的命令字 . Ⅱ I/O 接口中的状态字 . Ⅲ 中断类型号 A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ 22、响应外部中断的过程,中断隐指令完成的操作,除保护断点外,还包括( ) . Ⅰ 关中断 . Ⅱ 保存通用寄存器的内容 . Ⅲ 形成中断服务程序入口地址并送 PC A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ 23、下列选项中,不可能在用户态发生的事件是( ) A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 24、 中断处理和子程序调用都需要压栈以保护现场, 中断处理一定会保存而子程序调用不需 要保存其内容的是( ) A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器 D. 通用地址寄存器 25、下列关于虚拟存储器的叙述中,正确的是( ) A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 26、操作系统的 I/O 子系统通常由四个层次组成,每一层明确定义了与邻近层次的接口.其 合理的层次组织排列顺序是( ) A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序 B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序 C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序 D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序 27、假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3,这些资源总数分别为 18、6、22.T0 时刻的资源分配情况如下表所示,此时存在的一个安全序列是( ) 已分配资源 资源最大需求 进程 R1 R2 R3 R1 R2 R3 P0 3 2 3 5 5 10 P1 4 0 3 5 3 6 P2 4 0 5 4 0 11 P3 2 0 4 4 2 5 P4 3 1 4 4 2 4 A P0,P2,P4,P1,P3 B P1,P0,P3,P4,P2 C P2,P1,P0,P3,P4 D P3,P4,P2,P1,P0 3 28、若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据,则下列关于此过程的 叙述中,正确的是( ) . Ⅰ 若该文件的数据不在内存,则该进程进入睡眠等待状态 . Ⅱ 请求 read 系统调用会导致 CPU 从用户态切换到核心态 .read Ⅲ 系统调用的参数应包含文件的名称 A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ和Ⅲ 29、一个多道批处理系统中仅有 P1 和P2 两个作业,P2 比P1 晚5ms 到达,它们的计算和 I/O 操作顺序如下: P1:计算 60ms,I/O80ms,计算 20ms P2:计算 120ms,I/O40ms,计算 40ms 若不考虑调度和切换时间,则完成两个作业需要的时间最少是( ) A. 240ms B. 260ms C. 340ms D. 360ms 30、 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中错误的 是( ) A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 31、下列关于进程和线程的叙述中,正确的是( ) A. 不管系统是否支持线程,进程都是资源分配的基本单位 B. 线程是资源分配的基本单位,进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不一的地址空间 32、下列选项中,不能改善磁盘设备 I/O 性能的是( ) A. 重排 I/O 请求次序 B. 在一个磁盘上设置多个分区 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,数据帧长度范围是 128~512 字节, 接收方总是以与数据帧等长 的帧进行确认.为使信道利用率达到最高,帧序号的比特数至少为( ) A. 5 B. 4 C. 3 D. 2 37、下列关于 IP 路由器功能的描述中,正确的是( ) . Ⅰ 运行路由协议,设备路由表 . Ⅱ 检测到拥塞时,合理丢弃 IP 分组 . Ⅲ 对收到的 IP 分组头进行差错校验,确保传输的 IP 分组不丢失 . Ⅳ 根据收到的 IP 分组的目的 IP 地址,将其转发到合适的输出线路上 A. 仅Ⅲ、Ⅳ B. 仅Ⅰ、Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ、Ⅳ D. 4 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 之间发送和接收电子邮件的过程如下图所示,则图中①、②、③阶段 分别使用的应用层协议可以是( ) A. SMTP、SMTP、SMTP B. POP3、SMTP、POP3 C. POP3、SMTP、SMTP D. SMTP、SMTP、POP3 二、问答题. 41、 (10 分)设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和200 个数据元素,各表中元素按升序排列.要求通过 5 次两两合并,将6个表最终合并成 1 个升序表,并在最坏情况下比较的总次数达到最小.请回答下列问题. (1)给出完整的合并过程,并求出最坏情况下比较的总次数. (2)根据你的合并过程,描述 N(N≥2)个不等长升序表的合并策略,并说明理由. 42、 (13 分)假定采用带头结点的单链表保存单词,当两个单词有相同的后时缀,则可共享 相同的后缀存储空间,例如,"loaging" 和"being",如下图所示. 设str1 和str2 分别指向两个单词所在单链表的头结点,链表结点结构为 ,请 设计一个时间上尽可能高效的算法, 找出由 str1 和str2 所指向两个链表共同后缀的起始位置 (如图中字符 i 所在结点的位置 p) .要求: (1)给出算法的基本设计思想. (2)根据设计思想,采用 C 或C++或java 语言描述算法,关键之处给出注释. (3)说明你所设计算法的时复杂度. 43、 (11 分)假设某计算机的 CPU 主频为 80MHz,CPI 为4,平均每条指令访存 1.5 次,主 存与 Cache 之间交换的块大小为 16B,Cache 的命中率为 99%,存储器总线宽带为 32 位.请回答下列问题. (1) 该计算机的 MIPS 数是多少?平均每秒 Cache 缺失的次数是多少?在不考虑 DMA 传送的情况下,主存带宽至少达到多少才能满足 CPU 的访存要求? (2)假定在 Cache 缺失的情况下访问主存时,存在 0.0005%的缺页率,则CPU 平均每 秒产生多少次缺页异常?若页面大小为 4KB,每次缺页都需要访问磁盘,访问磁 5 盘时 DMA 传送采用周期挪用方式,磁盘 I/O 接口的数据缓冲寄存器为 32 位,则 磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是多少? (3)CPU 和DMA 控制器同时要求使用存储器总线时,哪个优先级更高?为什么? (4)为了提高性能,主存采用 4 体低位交叉存储模式,工作时每 1/4 个存储周期启动 一个体,若每个体的存储周期为 50ns,则该主存能提供的最大带宽是多少? 44、 (12 分)某16 位计算机中,带符号整数用补码表示,数据 Cache 和指令 Cache 分离. 题44 表给出了指令系统中部分指令格式, 其中 Rs 和Rd 表示寄存器, mem 表示存储单 元地址, (x)表示寄存器 x 或存储单元 x 的内容. 题44 表指令系统中部分指令格式 名称 指令的汇编格式 指令功能 加法指令 ADD Rs, Rd (Rs)+(Rd)->Rd 算术/逻辑左移 SHL Rd 2*(Rd)->Rd 算术右移 SHR Rd (Rd)/2->Rd 取数指令 LOAD Rd, mem (mem)->Rd 存数指令 STORE Rs, mem (Rs)->mem 该计算机采用 5 段流水式执行指令,各流水段分别是取指(IF) ,译码/读寄存器(ID) 、 执行/计算有效地址(EX) 、访问存储器(M)和结果写回寄存器(WB) ,流水线采用"按序 发射,按序完成"方式,没有采用转发技术处理数据相关,并且同一个寄存器的读和写操作 不能在同一个时钟周期内进行.请回答下列问题: (1)若int 型变量 x 的值为-513,存放在寄存器 R1 中,则执行"SHL R1"后,R1 中的 内容是多少?(用十六进制表示) (2)若某个时间段中,有连续的 4 条指令进入流水线,在其执行过程中没有发生任何 阻塞,则执行这 4 条指令所需的时钟周期数为多少? (3)若高级语言程序中某赋值语句为 x = a+b, x、a 和b均为 int 型变量,它们的存储 单元地址分别表示为[x]、[a]和[b].该语句对应的指令序列及其在指令流水线中的执行过程 如题 44 图所示. I1 LOAD R1, [a] I2 LOAD R2, [b] I3 ADD R1, R2 I4 STORE R2, [x] 时间单元 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1 IF ID EX M WB I2 IF ID EX M WB I3 IF ID EX M WB I4 IF ID EX M WB 题44 图 指令序列及其执行过程示意图 则这 4 条指令执行过程中,I3 的ID 段和 I4 的IF 段被阻塞的原因各是什么? (4)若高级语言程序中某赋值语句为 x=x*2+a,x 和a均为 unsigned int 类型变量,它 们的存储单元地址分别表示为[x]、[a],则执行这条语句至少需要多少个时钟周期?要求模 仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图. 6 45、 (7 分)某请求分页系统的局部页面置换策略如下: 从0时刻开始扫描,每隔 5 个时间单位扫描一轮驻留集(扫描时间忽略不计) ,本 轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次分配 之前不被清空.当发生缺页时,如果该页曾被使用过且还在空闲页链表中,则重新放回 进程的驻留集中;否则,从空闲页框链表头部取出一个页框. 假设不考虑其它进程的影响和系统开销. 初始时进程驻留集为空. 目前系统空闲页 框链表中页框号依次为 32、15、21、41.进程 P 依次访问的<虚拟页号,访问时刻>为<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>.请回答下列问题. (1)访问<0,4>时,对应的页框号是什么? (2)访问<1,11>时,对应的页框号是什么?说明理由. (3)访问<2,14>时,对应的页框号是什么?说明理由. (4)该策略是否适合于时间局部性好的程序?说明理由. 46、 (8 分)某文件系统空间的最大容量为 4TB(1TB =240 ) ,以磁盘块为基本分配单元.磁 盘块大小为 1KB.文件控制块(FCB)包含一个 512B 的索引表区.请回答下列问题. 1)假设索引表区仅采用直接索引结构,索引表区存放文件占用的磁盘块号,索引表项 中块号最少占多少字节?可支持的单个文件最大长度是多少字节? 2)假设索引表区采用如下结构:第0~7 字节采用<起始块号,块数>格式表示文件创建 时预分配的连续存储空间.其中起始块号占 6B,块数占 2B;剩余 504 字节采用直接索 引结构,一个索引项占 6B,则可支持的单个文件最大长度是多少字节?为了使单个文 件的长度达到最大,请指出起始块号和块数分别所占字节数的合理值并说明理由. 47、 (9 分)主机 H 通过快速以太网连接 Internet,IP 地址为 192.168.0.8,服务器 S 的IP 地 址为 211.68.71.80.H 与S使用 TCP 通信时,在H在捕获的其中 5 个IP 数据报如下表 所示. 题47-a 表IP 分组的前 40 字节内容(十六进制) 1 45 00 00 30 01 9b 40 00 80 06 1d c8 c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00 2 45 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d0 37 e1 00 00 3 45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43 80 2b 32 00 00 4 45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80 e6 55 00 00 5 45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 57 d2 00 00 回答下列问题. (1)题47-a 表中的 IP 分组中,哪几个是由 H 发送的?哪几个完成了 TCP 连接建立过 程?哪几个在通过快速以太网传输时进行了填充? (2)根据题 47-a 表中的 IP 分组,分析 S 已经收到的应用层数据字节数是多少? (3)若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示,则该 IP 分组到达 H 时经过了多少个路由器? 7 题47-b 表 来自 S 的 分组 45 00 00 28 68 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06 13 88 a1 08 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 b7 d6 00 00 注:IP 分组头和 TCP 段头结构分别如题 47-a 图,题47-b 图所示. bit 0 8 16 24 32 版本 头部长度 服务类型 总长度 标识 标志 片偏移 生存时间(TTL) 协议 头部校验和 源IP 地址 目的 IP 地址 题47-a 图IP 分组头结构 8 源端口目的端口序号确认号数据 偏移 保留URGACKPSHRSTSYNFIN窗口校验和紧急指针选项(长度可变)填充题47-b 图TCP 段头结构
下载该文档
文档格式：PDF
更新时间：2014-07-29
下载次数：0
点击次数：1
2012 年计算专业综合考研真题 一、选择题. 1、求整数 n(n≥0)阶乘的算法如下,其时间复杂度是( ) int fact(int n) { if (n<=1) return 1; return n*fact(n-1); } A. O(log2n) B. O(n) C. (nlog2n) D. O(n2 ) 2、已知操作符包括'和')'.将中缀表达式 a+b-a*((c+d)/e-f)+g 转换 为等价的后缀表达式 ab+acd+e/f-**-g+时, 用栈来存放暂时还不能确定运算次序的操 作符,若栈初始时为空,则转换过程中同时保存栈中的操作符的最大个数是( ) A. 5 B. 7 C. 8 D. 11 3、若一颗二叉树的前序遍历序列为 a, e, b, d, c,后续遍历序列为 b, c, d, e, a,则根节点的孩 子节点( ) A. 只有 e B. 有e、b C. 有e、c D. 无法确定 4、若平衡二叉树的高度为 6,且所有非叶节点的平衡因子均为 1,则该平衡二叉树的节点总 数为( ) A. 10 B. 20 C. 32 D. 33 5、对有 n 个节点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂 度( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 6、若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的 结构是( ) A. 存在,且唯一 B. 存在,且不唯一 C. 存在,可能不唯一 D. 无法确定是否存在 7、如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求源点 a 到其他各顶点的最短路径, 得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是 c,后续得到的 其余各最短路径的目标顶点依次是( ) 5 1 3 A. d, e, f B. e, d ,f C. f,d,e D. f,e,d 8、下列关于最小生成树的说法中,正确的是( ) Ⅰ、最小生成树的代价唯一 Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ、使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ、使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅰ、Ⅲ D. 仅Ⅱ、Ⅳ 9、已知一棵 3 阶B-树,如下图所示.删除关键字 78 得到一棵新 B-树,其最右叶结点中的 关键字是( ) A. 60 B. 60, 62 C. 62, 65 D. 65 1 10、在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序.下列 排序方法中,每一趟排序结束都至少能够确定一个元素最终位置的方法是( ) Ⅰ.简单选择排序 Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排序 Ⅴ.二路归并排序 A. 仅Ⅰ、Ⅲ、Ⅳ B. 仅Ⅰ、Ⅲ、Ⅴ C. 仅Ⅱ、Ⅲ、Ⅳ D. 仅Ⅲ、Ⅳ、Ⅴ 11.对一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是 ( ) A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 12、假定基准程序 A 在某计算机上的运行时间为 100 秒,其中 90 秒为 CPU 时间,其余为 I/O 时间. 若CPU 速度提高 50%, I/O 速度不变, 则运行基准程序 A 所耗费的时间是( ) A. 55 B. 60 C. 65 D. 70 13、假定编译器规定 int 和short 型长度分别为 32 位和 16 位,执行下列 C 语言语句: unsighned short x = 65530; unsigned int y = x; 得到 y 的机器数为( ) A. 0000 7FFAH B. 0000 FFFAH C. FFFF 7FFAH D. FFFF FFFAH 14、float 类型(即IEEE754 单精度浮点数格式)能表示的最大正整数是( ) A. 2126 - 2103 B. 2127 - 2104 C. 2127 - 2103 D. 2128 - 2104 15、某计算机存储器按字节编址,采用小端方式存放数据.假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位,并且数据按边界对齐存储.某C语言程序段如下: struct{ int a; char b; short c; }record; record.a = 273; 若record 变量的首地址为 0xC008,则地址 0xC008 中内容及 record.c 的地址分别是( ) A. 0x00、0xC00D B. 0x00、0xC00E C. 0x11、0xC00D D. 0x11、0xC00E 16、下列关于闪存(Flash 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 2 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、下列选项中,在I/O 总线的数据线上传输的信息包括( ) . Ⅰ I/O 接口中的命令字 . Ⅱ I/O 接口中的状态字 . Ⅲ 中断类型号 A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ 22、响应外部中断的过程,中断隐指令完成的操作,除保护断点外,还包括( ) . Ⅰ 关中断 . Ⅱ 保存通用寄存器的内容 . Ⅲ 形成中断服务程序入口地址并送 PC A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ 23、下列选项中,不可能在用户态发生的事件是( ) A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 24、 中断处理和子程序调用都需要压栈以保护现场, 中断处理一定会保存而子程序调用不需 要保存其内容的是( ) A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器 D. 通用地址寄存器 25、下列关于虚拟存储器的叙述中,正确的是( ) A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 26、操作系统的 I/O 子系统通常由四个层次组成,每一层明确定义了与邻近层次的接口.其 合理的层次组织排列顺序是( ) A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序 B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序 C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序 D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序 27、假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3,这些资源总数分别为 18、6、22.T0 时刻的资源分配情况如下表所示,此时存在的一个安全序列是( ) 已分配资源 资源最大需求 进程 R1 R2 R3 R1 R2 R3 P0 3 2 3 5 5 10 P1 4 0 3 5 3 6 P2 4 0 5 4 0 11 P3 2 0 4 4 2 5 P4 3 1 4 4 2 4 A P0,P2,P4,P1,P3 B P1,P0,P3,P4,P2 C P2,P1,P0,P3,P4 D P3,P4,P2,P1,P0 3 28、若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据,则下列关于此过程的 叙述中,正确的是( ) . Ⅰ 若该文件的数据不在内存,则该进程进入睡眠等待状态 . Ⅱ 请求 read 系统调用会导致 CPU 从用户态切换到核心态 .read Ⅲ 系统调用的参数应包含文件的名称 A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ和Ⅲ 29、一个多道批处理系统中仅有 P1 和P2 两个作业,P2 比P1 晚5ms 到达,它们的计算和 I/O 操作顺序如下: P1:计算 60ms,I/O80ms,计算 20ms P2:计算 120ms,I/O40ms,计算 40ms 若不考虑调度和切换时间,则完成两个作业需要的时间最少是( ) A. 240ms B. 260ms C. 340ms D. 360ms 30、 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中错误的 是( ) A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 31、下列关于进程和线程的叙述中,正确的是( ) A. 不管系统是否支持线程,进程都是资源分配的基本单位 B. 线程是资源分配的基本单位,进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不一的地址空间 32、下列选项中,不能改善磁盘设备 I/O 性能的是( ) A. 重排 I/O 请求次序 B. 在一个磁盘上设置多个分区 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,数据帧长度范围是 128~512 字节, 接收方总是以与数据帧等长 的帧进行确认.为使信道利用率达到最高,帧序号的比特数至少为( ) A. 5 B. 4 C. 3 D. 2 37、下列关于 IP 路由器功能的描述中,正确的是( ) . Ⅰ 运行路由协议,设备路由表 . Ⅱ 检测到拥塞时,合理丢弃 IP 分组 . Ⅲ 对收到的 IP 分组头进行差错校验,确保传输的 IP 分组不丢失 . Ⅳ 根据收到的 IP 分组的目的 IP 地址,将其转发到合适的输出线路上 A. 仅Ⅲ、Ⅳ B. 仅Ⅰ、Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ、Ⅳ D. 4 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 之间发送和接收电子邮件的过程如下图所示,则图中①、②、③阶段 分别使用的应用层协议可以是( ) A. SMTP、SMTP、SMTP B. POP3、SMTP、POP3 C. POP3、SMTP、SMTP D. SMTP、SMTP、POP3 二、问答题. 41、 (10 分)设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和200 个数据元素,各表中元素按升序排列.要求通过 5 次两两合并,将6个表最终合并成 1 个升序表,并在最坏情况下比较的总次数达到最小.请回答下列问题. (1)给出完整的合并过程,并求出最坏情况下比较的总次数. (2)根据你的合并过程,描述 N(N≥2)个不等长升序表的合并策略,并说明理由. 42、 (13 分)假定采用带头结点的单链表保存单词,当两个单词有相同的后时缀,则可共享 相同的后缀存储空间,例如,"loaging" 和"being",如下图所示. 设str1 和str2 分别指向两个单词所在单链表的头结点,链表结点结构为 ,请 设计一个时间上尽可能高效的算法, 找出由 str1 和str2 所指向两个链表共同后缀的起始位置 (如图中字符 i 所在结点的位置 p) .要求: (1)给出算法的基本设计思想. (2)根据设计思想,采用 C 或C++或java 语言描述算法,关键之处给出注释. (3)说明你所设计算法的时复杂度. 43、 (11 分)假设某计算机的 CPU 主频为 80MHz,CPI 为4,平均每条指令访存 1.5 次,主 存与 Cache 之间交换的块大小为 16B,Cache 的命中率为 99%,存储器总线宽带为 32 位.请回答下列问题. (1) 该计算机的 MIPS 数是多少?平均每秒 Cache 缺失的次数是多少?在不考虑 DMA 传送的情况下,主存带宽至少达到多少才能满足 CPU 的访存要求? (2)假定在 Cache 缺失的情况下访问主存时,存在 0.0005%的缺页率,则CPU 平均每 秒产生多少次缺页异常?若页面大小为 4KB,每次缺页都需要访问磁盘,访问磁 5 盘时 DMA 传送采用周期挪用方式,磁盘 I/O 接口的数据缓冲寄存器为 32 位,则 磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是多少? (3)CPU 和DMA 控制器同时要求使用存储器总线时,哪个优先级更高?为什么? (4)为了提高性能,主存采用 4 体低位交叉存储模式,工作时每 1/4 个存储周期启动 一个体,若每个体的存储周期为 50ns,则该主存能提供的最大带宽是多少? 44、 (12 分)某16 位计算机中,带符号整数用补码表示,数据 Cache 和指令 Cache 分离. 题44 表给出了指令系统中部分指令格式, 其中 Rs 和Rd 表示寄存器, mem 表示存储单 元地址, (x)表示寄存器 x 或存储单元 x 的内容. 题44 表指令系统中部分指令格式 名称 指令的汇编格式 指令功能 加法指令 ADD Rs, Rd (Rs)+(Rd)->Rd 算术/逻辑左移 SHL Rd 2*(Rd)->Rd 算术右移 SHR Rd (Rd)/2->Rd 取数指令 LOAD Rd, mem (mem)->Rd 存数指令 STORE Rs, mem (Rs)->mem 该计算机采用 5 段流水式执行指令,各流水段分别是取指(IF) ,译码/读寄存器(ID) 、 执行/计算有效地址(EX) 、访问存储器(M)和结果写回寄存器(WB) ,流水线采用"按序 发射,按序完成"方式,没有采用转发技术处理数据相关,并且同一个寄存器的读和写操作 不能在同一个时钟周期内进行.请回答下列问题: (1)若int 型变量 x 的值为-513,存放在寄存器 R1 中,则执行"SHL R1"后,R1 中的 内容是多少?(用十六进制表示) (2)若某个时间段中,有连续的 4 条指令进入流水线,在其执行过程中没有发生任何 阻塞,则执行这 4 条指令所需的时钟周期数为多少? (3)若高级语言程序中某赋值语句为 x = a+b, x、a 和b均为 int 型变量,它们的存储 单元地址分别表示为[x]、[a]和[b].该语句对应的指令序列及其在指令流水线中的执行过程 如题 44 图所示. I1 LOAD R1, [a] I2 LOAD R2, [b] I3 ADD R1, R2 I4 STORE R2, [x] 时间单元 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1 IF ID EX M WB I2 IF ID EX M WB I3 IF ID EX M WB I4 IF ID EX M WB 题44 图 指令序列及其执行过程示意图 则这 4 条指令执行过程中,I3 的ID 段和 I4 的IF 段被阻塞的原因各是什么? (4)若高级语言程序中某赋值语句为 x=x*2+a,x 和a均为 unsigned int 类型变量,它 们的存储单元地址分别表示为[x]、[a],则执行这条语句至少需要多少个时钟周期?要求模 仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图. 6 45、 (7 分)某请求分页系统的局部页面置换策略如下: 从0时刻开始扫描,每隔 5 个时间单位扫描一轮驻留集(扫描时间忽略不计) ,本 轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次分配 之前不被清空.当发生缺页时,如果该页曾被使用过且还在空闲页链表中,则重新放回 进程的驻留集中;否则,从空闲页框链表头部取出一个页框. 假设不考虑其它进程的影响和系统开销. 初始时进程驻留集为空. 目前系统空闲页 框链表中页框号依次为 32、15、21、41.进程 P 依次访问的<虚拟页号,访问时刻>为<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>.请回答下列问题. (1)访问<0,4>时,对应的页框号是什么? (2)访问<1,11>时,对应的页框号是什么?说明理由. (3)访问<2,14>时,对应的页框号是什么?说明理由. (4)该策略是否适合于时间局部性好的程序?说明理由. 46、 (8 分)某文件系统空间的最大容量为 4TB(1TB =240 ) ,以磁盘块为基本分配单元.磁 盘块大小为 1KB.文件控制块(FCB)包含一个 512B 的索引表区.请回答下列问题. 1)假设索引表区仅采用直接索引结构,索引表区存放文件占用的磁盘块号,索引表项 中块号最少占多少字节?可支持的单个文件最大长度是多少字节? 2)假设索引表区采用如下结构:第0~7 字节采用<起始块号,块数>格式表示文件创建 时预分配的连续存储空间.其中起始块号占 6B,块数占 2B;剩余 504 字节采用直接索 引结构,一个索引项占 6B,则可支持的单个文件最大长度是多少字节?为了使单个文 件的长度达到最大,请指出起始块号和块数分别所占字节数的合理值并说明理由. 47、 (9 分)主机 H 通过快速以太网连接 Internet,IP 地址为 192.168.0.8,服务器 S 的IP 地 址为 211.68.71.80.H 与S使用 TCP 通信时,在H在捕获的其中 5 个IP 数据报如下表 所示. 题47-a 表IP 分组的前 40 字节内容(十六进制) 1 45 00 00 30 01 9b 40 00 80 06 1d c8 c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00 2 45 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d0 37 e1 00 00 3 45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43 80 2b 32 00 00 4 45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80 e6 55 00 00 5 45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 57 d2 00 00 回答下列问题. (1)题47-a 表中的 IP 分组中,哪几个是由 H 发送的?哪几个完成了 TCP 连接建立过 程?哪几个在通过快速以太网传输时进行了填充? (2)根据题 47-a 表中的 IP 分组,分析 S 已经收到的应用层数据字节数是多少? (3)若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示,则该 IP 分组到达 H 时经过了多少个路由器? 7 题47-b 表 来自 S 的 分组 45 00 00 28 68 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06 13 88 a1 08 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 b7 d6 00 00 注:IP 分组头和 TCP 段头结构分别如题 47-a 图,题47-b 图所示. bit 0 8 16 24 32 版本 头部长度 服务类型 总长度 标识 标志 片偏移 生存时间(TTL) 协议 头部校验和 源IP 地址 目的 IP 地址 题47-a 图IP 分组头结构 8 源端口目的端口序号确认号数据 偏移 保留URGACKPSHRSTSYNFIN窗口校验和紧急指针选项(长度可变)填充题47-b 图TCP 段头结构