tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> >>

王道模拟试题(后3套,正式版)


予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

【特别说明】
本次编著《王道 6 套模拟题》的时间较为仓促,而且各科编者的时间也非常零散,因此在内容质 量上我们或许做得不够出色,在此对广大的道友表示诚挚的歉意!但不管怎么说,我们也已尽最大努 力来帮助大家冲刺 2012 年的专业课。希望道友们能抓住最后的 20 天,调整好心态,认真总结之前的 复习内容。考试结束后,也希望你们能偶尔上上王道论坛帮助未来考研的师弟师妹们。 真心地祝愿各位道友考研成功!予人玫瑰 手留余香

王道计算机统考模拟试题1

第4套

一、单项选择题:第 1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选 项最符合试题要求。
1. 设有一个 10 阶对称矩阵 A,采用压缩存储方式,以行序为主存储,a1,1 为第一个元素,其存储地址为 1,每个元素占一个地址空间,则 a8,5 的地址是( A.13 2. B.33 C.18 D.40 )。 ) 。

循环队列用数组 A[0…m-1]存放其元素值,头尾指针分别为 front 和 rear,front 指向队头元素,rear 指向队尾元素的下一个元素,则当前队列中的元素个数是( A.(rear-front+m)%m C.read-front-1 B.(rear-front+1)%m D.read-front )个叶子结点。 )棵 C.19 D.20

3. 4.

若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点,则该二叉树共有( A.17 树。 A. 1 B. 2 C. 3 D. 4 )。 D. 7 ) 。 D. 有环的 C. 无环的 D. n -2e
2

B.18

某二叉树结点的中序序列为 BDAECF,后序序列为 DBEFCA,则该二叉树对应的森林包括(

5.

利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树后,要查找元素 30 要进行 元素间的比较次数是( A. 4 B. 5 C. 6

6. 7. 8.

一个有 n 个顶点和 n 条边的无向图一定是( A. 连通的 A. e B. 2e B. 不连通的 C. n -e
2

一个含有 n 个顶点和 e 条边的简单无向图,其邻接矩阵存储中零元素的个数是(

)。

散列表的地址范围为 0-17,散列函数为 H(k)=k mod 17。采用线性探测法处理冲突,将关键字序列 26,25,72,38,8,18,59 依次存储到散列表中。元素 59 存放在散列表中的地址是( A.8 B.9 C.10 D.11 )个。 )。

9.

下列关于散列表的说法中,不正确的有(

I. 散列表的平均查找长度与处理冲突方法无关 II. 在散列表中,“比较”操作一般也是不可避免的 III. 散列表在查找成功时的平均查找长度与表长有关 IV. 若在散列表中删除一个元素,只需简单地将该元素删除即可 A. 1 B. 2 C. 3 D. 4 10. 对一组数据(25,84,21,47,15,27,68,35,20)进行排序,前三趟的排序结果如下: 第一趟:20,15,21,25,47,27,68,35,84 第二趟:15,20,21,25,35,27,47,68,84

1

欢迎各位道友在【计算机考研交流专区】交流模拟题中的疑问和问题。

~ 1 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 )。 C.归并排序

第 4~6 套

第三趟:15,20,21,25,27,35,47,68,84 则所采用的排序方法是( A.选择排序 B.希尔排序 D.快速排序 ) 。

11. 已知待排序的 n 个元素可分为 n/k 个组,每个组包含 k 个元素,且任一组内的各元素均分别大于前一 组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( A.O(nlog2n) B.O(nlog2k) C.O(klog2n) D.O(klog2k)

12. 某工作站采用时钟频率 f 为 15MHz、处理速率为 10MIPS 的处理机来执行一个已知混合程序。假定该 混合型程序平均每条指令需要 1 次访存,且每次存储器存取为 1 周期延迟,试问此计算机的有效 CPI 是( A.2.5 A.4.59375 ) B.2 C.1.5 D.1 ) 。 C.-4.59375 D.20.59375 )片。

13. 按 IEEE754 标准规定的 32 位浮点数(单精度浮点数)41A4C000H 对应的十进制数是( B.-20.59375

14. 设某按字节编址的计算机已配有00000H~07FFFH的ROM区,地址线为20位,现再用16K× 8位的RAM 芯片构成剩下的RAM区08000H~FFFFFH,则需要这样的RAM芯片( A. 61 B. 62 C. 63 D. 64 ) 。
7

15. 设存储器容量为32字,字长为64位。模块数m=4,采用低位交叉方式。存储周期T=200ns,数据总线 宽度为64位,总线传输周期r=50ns。该交叉存储器的带宽是(
7 7 7

A.32 × 10 bit/s B.8 × 10 bit/sC.73 × 10 bit/s D.18 × 10 bit/s 16. 虚拟存储器中的页表有快表和慢表之分,下面关于页表的叙述中正确的是( ) 。 A.快表与慢表都存储在主存中,但快表比慢表容量小 B.快表采用了优化的搜索算法,因此查找速度快 C.快表比慢表的命中率高,因此快表可以得到更多的搜索结果 D.快表采用高速存储器件组成,按照查找内容访问,因此比慢表查找速度快 17. 下列关于各种寻址方式获取操作数快慢的说法中,正确的是( ) 。 I.立即寻址快于堆栈寻址 A.I 和 IV B.II 和 III II.堆栈寻址快于寄存器寻址 C.I、III 和 IV D.III 和 IV III.寄存器一次间接寻址快于变址寻址 IV.变址寻址快于一次间接寻址 18. 在计算机体系结构中,CPU 内部包括程序计数器 PC、存储器数据寄存器 MDR、指令寄存器 IR 和存 储器地址寄存器 MAR 等。若 CPU 要执行的指令为:MOV R0, #100(即将数值 100 传送到寄存器 R0 中) ,则 CPU 首先要完成的操作是( A. 100->R0 ) 。 ) 。 B. 100->MDR C. PC->MAR D. PC->IR B.用多级译码来区分 D.任意存放 ) 。 B. 400MB/s C. 600MB/s ) 。 D. 800MB/s

19. 当微指令采用分段编码时,我们将互斥性微命令( A.放在同一段中 C.放在不同段中 数据传输速率是( A. 200MB/s

20. 在 32 位总线系统中,若时钟频率为 500MHz,传送一个 32 位字需要 5 个时钟周期,则该总线系统的

21. 下列关于中断和 DMA 的说法中,错误的有(

I.程序中断过程是由硬件和中断服务程序共同完成的 II.每条指令的执行过程中,每个指令周期要检查一次有无中断请求 III.检测有无 DMA 请求,一般安排在一条指令执行过程的末尾 IV.中断服务程序的最后一条指令是无条件转移指令 A. III 和 IV B. I、III 和 IV C. IV ) 。 D. II 和 IV 22. 以下关于通道的叙述中,不正确的是( A.通道程序存放在主存而不是通道中 B.通道方式下,除故障外不再需要采用中断 C.CPU 通过执行 I/O 指令来启动通道

~ 2 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

D.通道程序是由通道来执行的 23. 在操作系统的以下功能中,不需要硬件支持的是( I.中断系统 A. III 和 IV II.时钟管理 III.地址映射 B. II、III 和 IV ) 。 D. 只有 IV IV.页面调度 C. I 和 IV ) 。

24. 以下描述中,哪个不是多线程系统的特长, ( A. 利用线程并行地执行矩阵乘法运算 B. Web 服务器利用线程请求 HTTP 服务

C. 键盘驱动程序为每一个正在运行的应用配备一个线程,用来响应相应的键盘输入 D. 基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作。 25. 如果系统中所有进程是同时到达的,则平均周转时间最短的调度算法是( A. 先来先服务 C. 优先级调度 A. 0、1 B. 1、0 B. 短进程优先 D. 时间片轮转 ) 。 C. 1、1 D. 1、由用户确定 ) 。 ) 。

26. 在使用信号量机制实现互斥和同步时,互斥信号量和同步信号量的初值分别为( 27. 有两个并发进程如下面所示,对于这段程序的运行,正确的说法是(
int x,y,z,t,u; P1(){ while(1){ x=1; y=0; if(x>=1) y=y+1; z=y; } } } P2(){ while(1){ x=0; t=0 if(x<=1) t=t+2; u=t; }

A. 程序能正确运行,结果唯一 C. 程序不能正确运行,结果不确定 28. 分页系统中的页面是( A. 用户所能感知的 C. 编译程序所能感知的 29. 下列说法中,正确的是( )。 ) 。

B. 程序不能正确运行,可能有两种结果 D. 程序不能正确运行,可能会死锁

B. 操作系统所能感知的 D. 链接装配程序所能感知的

I. 先进先出(FIFO)页面置换算法可能会产生Belady现象。 II. 最近最少使用(LRU)页面置换算法可能会产生Belady现象。 III. 在进程运行时,如果它的工作集页面都在虚拟存储器内,能够使该进程有效地运行,否则会出现 频繁的页面调入/调出现象。 IV. 在进程运行时,如果它的工作集页面都在主存储器内,能够使该进程有效地运行,否则会出现频 繁的页面调入/调出现象。 A. I和III A.应用程序 B. I和IV B.存储介质 C. II和III )确定的。 C.外存容量 D.存储介质和操作系统 )个磁道。 D. 248 )是不正确的。 D. II和IV 30. 物理文件的组织方式是由(

31. 设一个磁道访问请求序列为 55,58,39,18,90,160,150,38,184,磁头的起始位置为 100,若采用 SSTF(最 短寻道时间优先)算法,则磁头移动( A. 55 B. 184 C. 200 32. 下列有关设备管理概念的叙述中, (

I. 通道可视为一种软件,其作用是提高了 CPU 的利用率 II. 编制好的通道程序是存放在主存储器中的 III. 用户给出的设备编号是设备的物理号

~ 3 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 B.I 和 IV C.II、III 和 IV ) 。

第 4~6 套

IV. 来自通道的 I/O 中断事件应该由设备管理负责 A.I 和 III I. II. D.II 和 III 33. 正确描述网络体系结构中的分层概念的是( 保持网络灵活且易于修改 所有的网络体系结构都使用相同的层次名称和功能

III. 把相关的网络功能组合在一层中 IV. 定义各层的功能以及功能的具体实现 A.I 和 III B. I 和 IV ) 。 C. I、III 和 IV D. I、II 和 III 34. 下列叙述中,正确的是( 条逻辑连接 B.虚电路的连接是临时性连接,当会话结束时就释放这种连接 C.数据报服务不提供可靠传输,但可以保证分组的有序到达 D.数据报服务中,每个分组在传输过程中都必须携带源地址和目的地址 35. 考虑建立一个 CSMA/CD 网,电缆长度为 1km,不使用中继器,传输速率为 1Gbps,电缆中信号的传 播速率是 200 000km/s,则该网络中最小帧长是( A.10 000bit B. 1000bit C. 5 000bit ) 。 D.200.10.1.75 ) 。 D. 源 IP 地址 ) 。 D. 20 000bit

A.电路交换是真正的物理线路交换,而虚电路交换是逻辑上的连接,且一条物理线路只可以进行一

36. 在某个子网中给一共四台主机分配 IP 地址 (子网掩码均为 255.255.255.224) 其中一台因 IP 地址分配 , 不当而存在通信故障。这一台主机 IP 地址是( A.200.10.1.60 A. 总长度 I. II. B.200.10.1.65 B. 首部校验和 C.200.10.1.70 C. 生存时间 ) 。

37. 在 IP 分组传输的过程中(不包括 NAT 情况) ,以下 IP 分组头中的域保持不变的是( 38. 下列关于 TCP 协议的叙述中,错误的是( TCP 是一个点到点的通信协议 TCP 提供了无连接的可靠数据传输

III. TCP 将来自上层的字节流组织成 IP 数据报,然后交给 IP 协议 IV. TCP 将收到的报文段组成字节流交给上层 A. I 和 III B. I、II 和 III C. II 和 III D. I、II、III 和 IV 39. 在基于 TCP/IP 模型的分组交换网络中,每个分组都可能走不同的路径,所以在分组到达目的主机后 应该重新排序;又由于不同类型的物理网络的 MTU 不同,所以一个分组在传输的过程中也可能需要 分段,这些分段在到达目的主机后也必须重组。对于分组的排序和分段的重组,下列说法正确的是 ( ) 。 A. 排序和重组工作都是由网络层完成 B. 排序和重组工作都是由传输层完成 C. 排序工作由网络层完成,而重组工作由传输层完成 D. 排序工作由传输层完成,而重组工作由网络层完成 40. 某用户登录 www.google.com,从协议分析的角度,浏览器的第一步操作( A. IP 地址解析 B. 域名解析 C. 建立 TCP 连接 ) 。 D. 会话连接建立

二、综合应用题:第 41~47 小题,共 70 分。
41. (11 分)已知一图如下图所示:

(1)写出该图的邻接矩阵。

~ 4 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

(2)写出全部拓扑序列。 (3)以 V1 为源点,以 V8 为终点,给出所有事件允许发生的最早时间和最晚时间,并给出关键路径。 (4)求 V1 结点到各点的最短路径和距离。 42. (12 分)已知长度为 n(n>1)的单链表,表头指针为 L,结点结构由 data 和 next 两个域构成,其中 data 域为字符型。试设计一个在时间和空间两方面都尽可能高效的算法,判断该单链表是否中心对称 (例如 xyx、xxyyxx 都是中心对称的) ,要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C++或 Java 语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 43. (11 分)下图是一个简化的 CPU 与主存连接结构示意图(图中省略了所有多路选择器) 。其中有一个 累加寄存器 AC、 一个状态寄存器和其他四个寄存器: 主存地址寄存器 MAR、 主存数据寄存器 MDR、 程序计数器 PC 和指令寄存器 IR,各部件及其之间的连线表示数据通路,箭头表示信息传送方向。

主存储器

a AC

c +1

b

d ALU

状态寄存器

微操作信 号发生器

一个简化的 CPU 与主存连接结构示意图 要求: (1)请写出图中 a、b、c、d 四个寄存器的名称。 (2)简述图中指令从主存取到控制器的过程。 (3)说明数据从主存取出、运算、写回主存所经过的数据通路(假定数据地址已在 MAR 中) 。 44. (11 分)设某计算机有 4 级中断 A、B、C、D,其硬件排队优先级次序为 A>B>C>D。如表所示列出 了执行每级中断服务程序所需的时间。 中断服务程序所需的时间 中断服务程序 A B C D (1)如何为各级中断服务程序设置屏蔽码? (2)如果 A、B、C、D 分别在 6us、8us、10us、0us 时刻发出中断请求,请画出 CPU 执行中断服务 程序的序列。 (3)基于上题,请计算上述 4 个中断服务程序的平均执行时间。 45. (7分)兄弟俩共同使用一个账号,每次限存或取10元,存钱与取钱的进程分别如下所示: int amount=0; SAVE(){ int m1; m1=amount; TAKE(){ int m2; m2=amount; m2=m2-10; amount=m2; } 所需时间 5us 15us 3us 12us

如果以执行中断服务程序的时间作为确定中断优先级的尺度:时间越短优先级越高。

~ 5 ~

予人玫瑰

手留余香 m1=m1+10; amount=m1;

王道 2012 年最后 6 套模拟试题

第 4~6 套

} 由于兄弟俩可能同时存钱和取钱, 因此两个进程是并发的。 若哥哥先存了两次钱, 但在第三次存钱时, 弟弟在取钱。请问: (1)最后账号 amount 上面可能出现的值? (2)如何用 P、V 操作实现两并发进程的互斥执行? 46. (8分)如果磁盘的每个磁道分成9个块,现有一文件有A、B、…、I共9个记录,每个记录的大小与块 的大小相等,若磁盘转速为6000RPM,每读出一块后需要2.5ms的处理时间。若忽略其他辅助时间, 试问: (1)如果将这些记录顺序存放在一磁道上,则顺序读出该文件需多少时间? (2)若要求顺序读出的时间最短,则应该如何安排文件的存放位置。 47. (9分)下图是三个计算机局域网A、B和C,分别包含10台,8台和5台计算机,通过路由器互联,并 通过该路由器的接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为 61.60.21.80的互联网地址) 。局域网A和局域网B公用一个C类网络IP地址202.38.60.0,并将此IP地址中 主机地址的高两位作为子网编号。局域网A的子网编号为01,局域网B的子网编号为10。IP地址的低六 位作为子网中的主机编号。局域网C的网络号是202.36.61.0。请回答下列问题:

(1)为每个网络的计算机和路由器的端口分配 IP 地址,并写出三个网段的子网掩码。 (2)列出路由器的路由表。 (3)若局域网 B 中的一主机要向局域网 B 广播一个分组,写出该分组的目的 IP 地址。 (4)若局域网 B 中的一主机要向局域网 C 广播一个分组,写出该分组的目的 IP 地址。

~ 6 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

第4套 答案与解析
一、单项选择题
1. 【分析】 【单科书 P70】 本题考查特殊矩阵的存储。 对于考查特殊矩阵存储的这类题型, 建议画出草图, 【解答】B。数组下标从 1 开始,只存储其下三角元素,在 a8,5 的前面有 7 行,第 1 行有 1 个元素, 第 2 行有 2 个元素,…,第 7 行有 7 个元素,这 7 行共有(1+7)× 7/2=28 个元素,在第 8 行中,a8,5 的前面 有 4 个元素,所以,a8,5 前面有 28+4=32 个元素,其地址为 33。 2. 【分析】【单科书 P59】本题考查循环队列的性质。 【解答】A。分 rear>front 和 rear<front 两种情况讨论:①当 rear>front 时,队列中元素个数为 rear-front=(rear-front+m)%m;②当 rear<front 时,队列中元素个数为 m-(front-rear) =(rear-front+m)%m。综 合①、②可知,A 选项正确。 【另解】特殊值代入法:对于循环队列,C 和 D 无取 MOD 操作,显然错误,直接排除。设 front=0、 rear=1,则队列中存在一个元素 A[0],代入 AB 两项,显然仅有 A 符合。 【说明】不同的教材对队尾指针的定义可能不同,有的定义其指向队尾元素,有的定义其指向队尾元 素的下一元素,不同的定义会导致不同的答案,考题中通常都会特别说明。 3. 【分析】【单科书 P89】本题考查完全二叉树的性质。深度为 n 的完全二叉树前面 n-1 层对应的是满 【解答】A。完全二叉树第 5 层共有 24=16 个结点。第 6 层最左边有 3 个叶子结点,对应第 5 层最左 边 2 个结点,所以第 5 层右边有 16-2=14 个叶子结点,因此共有 17 个叶子结点。 【说明】对于此类题,建议画出草图的片段部分进行求解,比较形象且不易出错。 4. 【分析】 【单科书 P96】本题考查由遍历序列确定二叉树、森林与二叉树的转换。由后序序列和中序序 【解答】C。根据后序序列,A 是二叉树的根结点。根据中序遍历序列,则二叉树的形态一定如下图 左所示。对于 A 的左子树,由后序序列可知,因为 B 比 D 后被访问,因此,B 必为 D 的父结点,又由中 序序列可知,D 是 B 的右儿子。对于 A 的右子树,同理可确定结点 E、C、F 的关系。此二叉树的形态如 下图右所示。
A

并尽量结合“平移”的思想,以形象的方式思考,这样就不易出错。

二叉树。完全二叉树中的非叶结点与其左、右孩子的编号有具体的公式计算。

列可以唯一的确定一棵二叉树,然后再根据该二叉树确定对应的森林。

A B D E C F

B、D

E、C 、F

再根据二叉树与森林的对应关系。森林中树的棵数即为其对应二叉树(向右上旋转 45o 后)中根结点 A 及其“右兄弟”数。可知此森林中有 3 棵树,根结点分别为 A、C 和 F。 【提示】由二叉树求森林中树的个数、或求各棵树形等,应将二叉树向右上旋转 45o,然后再根据森 林和二叉树的转换规则来描绘出森林中的树形。 5. 【分析】 【单科书 P100】本题考查二叉排序树的构造和查找。利用逐点插入法建立二叉排序树是从空 【解答】 按题中数据的输入次序, B。 建立的二叉排序树如下图所示。 查找元素 30 的比较次数为 5 次。
50 43 20 35 30 45 65 75 72 85

树开始,通过查找,将每个结点作为一个叶结点插入。

6.

【分析】 【单科书 P150】本题考查图的基本性质。n 个顶点构成连通图至少需要 n-1 条边(生成树) ,

~ 7 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

但若再增加 1 条边,则必然会构成环。 【解答】D。如果一个无向图有 n 个顶点和 n-1 条边,可以使它连通但没有环(即生成树) ,但再加一 条边,在不考虑重边的情形下,就必然会构成环。 7. 【分析】【单科书 P154】本题考查邻接矩阵存储的定义。无向图的邻接矩阵是对称的,即图中的任一 【解答】D。一个含有 n 个顶点和 e 条边的简单无向图的邻接矩阵为 n× 矩阵,共有 n2 个元素,其中 n 非零元素个数为 2e,则零元素个数为 n2-2e。 8. 【分析】 【单科书 P209】本题考查散列表的构造过程。任何散列函数都不可能绝对的避免冲突,因此 【解答】D。将前面各元素分别放入散列表中,其中 8、9、10 的位置分别存放 25、26、8。元素 59 经过哈希函数计算应该存入位置 59 mod 17 = 8,有冲突,采用线性探测再散列,依次比较 9、10、11,发 现 11 为空,所以将其放入地址 11 中。 9. 【分析】 【单科书 P208】本题考查散列表的性质。散列表的构造、冲突处理方法、平均查找长度等考 【解答】C。不同冲突处理方法对应的平均查找长度是不同的,I 错误。散列查找的思想是通过散列函 数计算地址,然后再比较关键字确定是否查找成功,II 正确。平均查找长度与填装因子(即表中记录数与 表长之比)有关,III 错误。在开放定址的情况下,不能随便删除表中的某个元素(只能标记为删除状态) , 否则可能会导致搜索路径被众多,IV 错误。 10. 【分析】 【单科书 P232 等】本题考查各种排序算法的排序过程。 【解答】 观察序列变化, D。 发现第 1 趟排序序列位置变化很大, 所以不可能是选择排序和归并排序。 又发现第 2 趟排序 15 和 20 交换了位置,所以不可能是希尔排序。只可能是快速排序。 11. 【分析】本题考查内部排序算法的性质。在基于比较的排序方法中,每次比较两个关键字后,仅出现 两种可能的转移, 因此可用一棵二叉树来描述比较判定过程, 可以证明: 当文件的 k 个关键字随机分布时, 任何借助于“比较”的排序算法,至少需要 O(klog2k)的时间。 【解答】B。因组与组之间已有序,故将 n/k 个组分别排序即可,基于比较的排序方法每组的时间下 界为 O(klog2k),则全部时间下界为 O(nlog2k)。 12. 【分析】 【单科书 P11】本题考查计算机的性能指标。CPI 指执行一条指令所需的时钟周期。 【解答】C。CPI=15MHz/10× 6 = 1.5。这里的存储器延迟为迷惑项,与 CPI 的计算无关。 10 13. 【分析】单科书 P46】 【 本题考查 IEEE754 标准的浮点数。 单精度浮点数 (float) 与双精度浮点数 (double) 都采用隐含尾数最高数位的方法, 故可多表示一位尾数。临时浮点数又称为扩展精度浮点数,无隐含位。 在单精度浮点数中, 最高位为数符位; 其后是 8 位阶码, 2 为底, 以 用移码表示, 阶码的偏置值为 127; 其后 23 位是尾数数值位。对于规格化的二进制浮点数,数值的最高位总是“1”,为了能使尾数多表示一位 有效值,将这个“1”隐含,因此尾数数值实际上是 24 位。隐含的“1”是一位整数。在浮点格式中表示出来的 23 位尾数是纯小数,用原码表示。 【解答】 41A4C000H 写成二进制为 0100 0001 1010 0100 1100 0000 0000 0000, D。 第一位为符号位 0, 表示是正数。之后的 8 位 1000 0011 表示阶码,真值为(100)B,即 4。剩下的是隐含了最高 1 的尾数,故而 为 1.010 0100 1100 0000 0000 0000,数值左移四位后整数部分 10100 表示为 20。 14. 【分析】 【单科书P87】本题考查存储芯片的扩展。 【解答】B。RAM区的地址范围为:0000 1000 0000 0000 0000 ~ 1111 1111 1111 1111 1111,由此可知 RAM区的大小为31× 32KB,(31× 32KB)/16KB=62。 15. 【分析】 【单科书P91】本题考查交叉存储器的性能分析。在低位交叉存储器中,连续的地址分布在相 邻的块中,而同一模块内的地址都是不连续的。这种存储器采用分时启动的方法,可以在不改变每个模块 存取周期的前提下,提高整个主存的速度。 【解答】C。低位交叉存储器连续读出 4 个字所需的时间为:t =T+(m-1)*r =200 ns+3*50 ns =350 ns =3.5× -7s。故带宽为:W=64× 10 4b/(3.5× -7s)=73× 7b/s。 10 10 16. 【分析】 【单科书 P103】本题考查快表和慢表的关系。快表又称 TLB,采用高速相联存储器来存储可 点都是散列表中比较重要的问题。 采用合理的冲突处理方法,为冲突的关键字寻找下一个“空”位置。 条边 ai,j 对应邻接矩阵中的两个非零元素 A[i][j]和 A[j][i]。

~ 8 ~

予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第 4~6 套 能需要使用的页的对应表项。而慢表存储在内存中。 【解答】 快表采用的是相联存储器, D。 而不是依赖搜索算法来查找的, 慢表通常是依赖于查找算法, 故A和B错误。快表的命中率有可能高于慢表,但快表仅是慢表的一个部分拷贝,不能够得到比慢表更多的 结果,因此C错误。 17. 【分析】 【单科书 P132】本题考查各种寻址方式的原理。因此访问寄存器的速度通常访问主存的数十 倍,因此获取操作数快慢主要取决于寻址方式的访存次数。 【解答】C。立即寻址操作数在指令中,不需要任何访问寄存器或内存,取数最快,I 正确。堆栈寻址 可能是硬堆栈(寄存器)或软堆栈(内存),采用软堆栈时比寄存器寻址慢,II 错误。寄存器一次间接寻址先访 问寄存器得到地址,然后再访问主存;而变址寻址访问寄存器 IX 后,还要将 A 和(IX)相加(相加需要消 耗时间) ,在根据相加的结果访存,显然后者要慢一点,III 错误。一次间接寻址需要两次访存,显然慢于 变址寻址,IV 正确。 18. 【分析】 【单科书 P152】本题考查取指周期完成的操作。取指周期完成的微操作序列是公共的操作, 与具体指令无关。CPU 首先需要取指令,取指令阶段的第一个操作就是将指令地址(程序计数器 PC 中的 内容)送往存储器地址寄存器。 【解答】C。题干中虽然给出了一条具体的指令“MOV R0, #100”,实际上 CPU 首先要完成的操作是取 指令,与具体指令是没有关系的。 19. 【分析】 【单科书 P169】本题考查字段直接编码的特点。互斥性微命令是指不能同时或不能在同一个 CPU 周期内并行执行的微命令,反之则是可以并行执行的微命令。 【解答】A。字段直接编码将微指令的操作控制字段分成若干段,将一组互斥的微命令放在一个字段 内,通过对这个字段的译码,便可对应每一个微命令。这样,各个字段的译码输出都是可以并行执行的微 命令,这种编码方式提高了微指令的并行执行能力。 20. 【分析】 【单科书 P202】本题考查总线的性能指标。总线的最大数据传输率又称总线带宽,即每秒传 输的字节数。总线带宽=总线宽度 X 总线频率。 【解答】B。由于传送 4 个字节的数据需要 5 个时钟周期,5B*500MHz÷ 5=400MB/s。 21. 【分析】 【单科书 P228】本题考查中断方式和 DMA 方式。 【解答】A。程序中断过程由硬件(如向量地址形成部件)和中断服务程序共同完成的,I 正确。每条 指令周期的末尾,CPU 统一扫描各个中断源,然后通过判优来决定响应哪个中断源,II 正确。CPU 在每个 总线周期结束后检查是否有 DMA 请求, 错误。 III 中断服务程序的最后一条指令通常是中断返回指令 RETI, 返回被中断的现场,以继续执行原程序。该指令在恢复现场后,也就是此时 CPU 中所有寄存器都已恢复 到中断之间的状态,因此该指令不需要进行无条件转移,只需通知 CPU 开始从 PC 中取指,进入新的取指 周期即可,IV 错误。 22. 【分析】 【单科书 P234】本题考查通道的基本工作过程。通道的基本工作过程:用户程序使用访管指 令进入操作系统管理程序;CPU 通过管理程序组织一个通道程序,并用 I/O 指令启动通道;通道执行通道 指令,完成 I/O 操作;通道程序结束后向 CPU 发中断请求。 【解答】B。通道程序放与主存之中,由 CPU 执行 I/O 指令启动通道,通道执行通道程序。在整个传 输过程中,数据传输结束时,需要中断来处理。 23. 【分析】 【单科书 P11】本题考查操作系统功能的实现。对于此类题型,需要掌握各个选项的基本原理 才能正确解答。 【解答】D。中断处理流程的前 3 个步骤是由硬件直接实现(隐指令)的;时钟管理需要硬件计数器 保持时钟的运行;地址映射中需要基地址(或页表)寄存器和地址加法器的支持。页面调度是由相关调度 算法完成,不需要硬件支持。 【注意】页面调度算法仅计算需要调入或置换的目标页面,调入过程(例如缺页中断处理过程)才是 与硬件相关的。 24. 【分析】 【单科书 P27】本题考查多线程的特点。线程最直观的理解就是“轻量级进程”,引入线程后, 线程成为 CPU 独立调度的基本单位,进程是资源拥有的基本单位。 【解答】C。引入多线程是为了更好的并发执行,键盘属于慢速外设,它无法并发执行,因此仅用一

~ 9 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

个线程来处理整个系统的键盘输入即可。 25. 【分析】 【单科书 P38】本题考查各调度算法的特点。 【解答】B。平均周转时间=各进程周转时间之和/进程数,因为每个进程的执行时间都是固定的,所 以变化的是等待时间,只有短进程优先算法能最小化等待时间。 26. 【分析】 【单科书 P51】本题考查信号量机制。注意互斥信号量和同步信号量的区别。信号量机制是每 年考题的重点,这就要求考生能在理解的基础上熟练应用和掌握信号量。 【解答】 互斥信号量的初值为 1, 操作成功则将其改成 0 , 操作成功将其改成 1。 D。 P V 实现同步时, 信号量的初值应根据具体情况来确定,若期望的消息尚未产生,则对应的初值应为 0;若期望的消息已经 存在,则信号量的初值应设为一个非 0 的正整数。 27. 【分析】本题考查进程的并发执行。要求分析程序运行的结果,通常会涉及到同步、互斥、饥饿和死 锁。因此考生要理解同步和互斥、饥饿和死锁的区别,并能根据程序分析。 【解答】C。本题中两个进程不能正确地工作,运行结果的可能性,详见下面说明。 1. x=1; 2. y=0; 3. if(x>=1) y=y+1; 4. z=y; 5. x=0; 6. t=0 7. if(x<=1) t=t+2; 8. u=t;

不确定的原因是由于使用了公共的变量 x,考察程序中与 x 变量有关的语句共四处,若执行的顺序是 1->2->3->4->5->6->7->8 时,结果是 y=1,z=1,t=2,u=2,x=0;当并发执行过程是 1->2->5->6->3->4->7->8 时, 结果是 y=0,z=0,t=2,u=2,x=0;若执行的顺序是 5->6->7->8->1->2->3->4 时,结果是 y=1,z=1,t=2,u=2,x=1;若 执行的顺序是 5->6->1->2->7->8->3->4 时,结果是 y=1,z=1,t=0,u=0,x=1;可见结果有多种可能性。 28. 【分析】 【单科书 P132】本题考查分页系统的原理。分页是由操作系统完成的。 【解答】 分页系统中由逻辑地址向物理地址的转换是系统借助硬件系统自动实现的, B。 对用户透明, 对编译程序和链接装配程序透明(在相同的系统里) 。只有操作系统可以感知页面的存在,在内存管理过 程中,操作系统要为用户进程分配内存、回收内存。所以操作系统是页面最直接的接触者,它将页面从计 算机系统到用户进行了隔离。 29. 【分析】【单科书 P151】本题考查页面置换算法与抖动、Belady 现象。 【解答】 I正确, B。 举例如下: 页面走向为1,2,3,4,1,2,5,1,2,3,4,5 时, 当分配3 帧时产生9 次缺页中断, 分配4 帧时产生10 次缺页中断。最近最少使用法不会产生Belady 现象,II错误。若页面在内存中,不会 产生缺页中断,也即不会出现页面的调入/调出,而不是虚拟存储器(包括作为虚拟内存那部分硬盘),故 III错误、IV正确。 30. 【分析】本题考查文件的物理结构。 【解答】D。物理文件的组织是文件管理的内容,而文件管理是操作系统的主要功能之一;此外存储 介质的特性也决定了文件的物理结构,如磁带机只能采用顺序存放方式。 31. 【分析】 【单科书 P215】本题考查磁盘的调度算法。SSTF 即最短寻道时间优先算法,该算法优先考 虑与当前位置最接近的磁道访问请求,会导致“饥饿”现象。 【解答】D。对于 SSTF 算法,寻道序列应为:100,90,58,55,39,38,18,150,160,184,移动磁道次数依次 为 10,32,3,16,1,20,132,10,24,故磁头移动的总数为 248。 32. 【分析】 【单科书 P239 等】本题考查设备管理的知识点。通道作为一种特殊的硬件或者处理器,具有 诸多特征,它与一般处理器的区别、以及与 DMA 方式的区别要认真理解。 【解答】A。通道是一种硬件、或特殊的处理器,它有自身的指令,故 I 错误。通道没有自己的内存, 通道指令存放在主机的内存中,也就是说通道与 CPU 共享内存,故 II 正确。为了实现设备独立性,用户 使用逻辑设备号来编写程序,故 III 错误。来自通道的 I/O 中断事件是属于输入/输出的问题,故应该由设 备管理负责,故 IV 正确。综上,I、III 错误。 33. 【分析】 【单科书 P9】本题考查网络体系结构的原则和特点。典型的如 OSI 参考模型,就很好地体现 了网络体系结构设计的初衷。 【解答】A。网络体系结构是抽象的,它不包括各层协议及功能的具体实现细节。分层使得各层次之

~ 10 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

间相对独立,各层仅需关注该层需要完成的功能,保持了网络的灵活性和封装性,但网络的体系结构并没 有规定层次的名称和功能必须一致。 34. 【分析】 【单科书 P30】本题考查几种交换技术。电路交换、分组交换、报文交换及数据报服务、虚电 路服务这些易混知识点容易出串联性选择题,要在对比中加深理解和记忆。 【解答】D。电路交换是真正的物理线路交换,例如电话线路;虚电路交换是多路复用技术,每一条 物理线路可以进行多条连接,是逻辑上的连接,因此 A 错误。虚电路不只是临时性的,它提供的服务包括 永久性虚电路(PVC)和交换型虚电路(SVC) 。其中前者是一种提前定义好的,基本上不需要任何建立时 间的端点之间的连接,而后者是端点之间的一种临时性连接,这些连接只持续所需的时间,并且当会话结 束时就取消这种连接,因此 B 错误。数据报服务是无连接的,不提供可靠性保障,也不保证分组的有序到 达,虚电路服务提供可靠性,且保证分组的有序到达,因此 C 错误。数据报服务中,每个分组在传输过程 中都必须携带源地址和目的地址;而虚电路服务中,在建立连接后,分组只需携带虚电路标识,而不必带 有源地址和目的地址。 35. 【分析】 【单科书 P71】本题考查 CSMA/CD 协议的最小帧长。在发送的同时要进行冲突检测,这就要 求在能检测出冲突的最大时间内数据不能发送完毕,否则冲突检测不能有效地工作。所以,当发送的数据 帧太短时,必须进行填充。最小帧长=数据传输速率×争用期。 【解答】 争用期=网络中两站点最大的往返传播时间 2τ=2×(1/200 000)=0.00 001; A。 最小帧长=1000 000 000× 0.00 001=10 000bit。 36. 【分析】 【单科书 P116】本题考查子网划分与子网掩码。一个子网中的所有主机的子网号应该相同, 因此若因 IP 地址分配不当,则应联想到可能 子网号分配错误。 【解答】A。这 4 个 IP 地址都是 C 类地址,前 3 个字节是网络号,224 用二进制表示是 1110 0000, 因此子网号长度为 3。 4 个 IP 地址的最后一个字节的二进制表示分别是 0011 1100, 这 0100 0001, 0100 0110, 0100 1011。考察子网号部分(第 4 字节的前 3 位) ,选项 B、C 和 D 都是 010,而选项 A 是 001。 37. 【分析】 【单科书 P112】本题考查 IP 分组的首部字段含义。如果题目没有说明不考虑 NAT,都认为 源目的 IP 地址和目的 IP 地址都是可以改变的,否则都是不能改变的。 【解答】D。A 选项:当 IP 分组的长度超过该网络的 MTU 时需要分片,总长度将改变,故 A 错误; B 选项:IP 分组每经过一跳,都会改变其首部检验和,故 B 错误;C 选项:每经过一个路由器,生存时间 减 1,故 C 错误;D 选项:在不考虑 NAT 时,源 IP 地址和目的 IP 地址都不会变化。 38. 【分析】 【单科书 P165】本题考查对 TCP 协议的理解。TCP 是在不可靠的 IP 层之上实现可靠的数据 传输协议,它主要解决传输的可靠、有序、无丢失和不重复的问题,其主要特点是:①TCP 是面向连接的 传输层协议。 ②每一条 TCP 连接只能有两个端点, 每一条 TCP 连接只能是端对端的 (进程—进程) ③TCP 。 提供可靠的交付服务,保证传送的数据无差错、不丢失、不重复且有序。④TCP 提供全双工通信,允许通 信双方的应用进程在任何时候都能发送数据,为此 TCP 连接的两端都设有发送缓存和接收缓存。⑤TCP 是面向字节流的,虽然应用程序和 TCP 的交互是一次一个数据块(大小不等) ,但 TCP 把应用程序交下来 的数据看成仅仅是一连串的无结构的字节流。 【解答】B。I:IP 协议才是点到点的通信协议(也说是主机—主机) ,而 TCP 是端到端的协议,故 I 错误;II:TCP 提供面向连接的可靠数据传输服务,故 II 错误;III:IP 数据报不是由传输层来组织的,而 应该由网络层加上 IP 数据报的首部来形成 IP 数据报,故 III 错误;IV:前面已经分析,正确。综上,I、 II 和 III 都是错误的。 39. 【分析】 【单科书 P113、P169】本题考查 PDU 在对等层间的处理。PDU 中装载的是哪一层的数据, 就有哪一层来处理该数据,而 PDU 所在的层只负责传输该数据。 【解答】D。IP 网络是分组交换网络,每个分组的首部都包含了完整的源地址和目的地址,以便途经 的路由器为每个 IP 分组进行路由,即便是同一个源站点向同一个目的站点发出的多个 IP 分组也并不一定 走同一条路径, 亦即这些 IP 分组到达目的站点的顺序可能不一定按序到达, 目的站点的传输层必须进行排 序;而一个较大的 IP 分组在传输的过程中,由于途经物理网络的 MTU 可能比较小,一个 IP 分组可能将 分成若干个分组,每个分组都有完整的首部,与普通的 IP 分组没有区别地传输。按照网络对等层通信的原 则,接收站点的网络层收到的 IP 分组必须与发送站点发送的 IP 分组相同,所以接收站点的网络层必须把

~ 11 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

沿途被分片的分组进行重组,还原成原来的 IP 分组。所以重组工作是由网络层完成的。 40. 【分析】 【单科书 P199】本题考查对 WWW 服务的理解。如果用户直接使用域名去访问一个 WWW 服务器,其过程是:域名解析、建立 TCP 连接、传输数据、释放连接。 【解答】B。只有获得服务器的 IP 地址后,WWW 浏览器才能与 WWW 服务器建立连接开始后续的 交互。因此从协议执行过程来说,访问 WWW 服务器的第一步是域名解析。

二、综合应用题
41. 【分析】本题考查图的邻接矩阵存储表示、拓扑排序、关键路径和最短路径。拓扑排序、关键路径和 最短路径是图应用中最重要的知识点(常考题型,综合题考图章节的概率也很大) ,特别是后两者也是难 点。读者应熟练掌握此类题的解法。 【解答】 (1)该图对应的邻接矩阵如下: ∞ ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 3 10 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 2 ∞ ∞ 6 ∞ ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞ (2)只有顶点 V1 的入度为 0,由此可以得到两个拓扑序列:V1,V2,V3,V4,V6,V5,V7,V8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 和 V1,V3,V2,V4,V6,V5,V7,V8。 (3)关键路径共有 3 条,长 17。依次为:V1->V2->V4->V6->V8,V1->V3->V5->V7->V8, V1->V2->V4->V6->V5->V7->V8。 事件 最早发生时间 最晚发生时间 活动 最早开始时间 最晚开始时间 时间余量 V1-V2 0 0 0 V1 0 0 V2 2 2 V1-V3 0 0 0 V3 3 3 V2-V4 2 2 0 V4 7 7 V3-V4 3 4 1 V5 13 13 V3-V5 3 3 0 V6 11 11 V7 16 16 V8 17 17 V6-V5 11 11 0 V5-V7 13 13 0 V6-V8 11 11 0 V7-V8 16 16 0

V4-V6 7 7 0

(4)顶点 V1 到其它各顶点的最短路径和距离为:2(V1->V2) ,3(V1->V3) ,6(V1->V3->V4) ,12 (V1->V3->V4->V6->V5) ,10(V1->V3->V4->V6) ,15(V1->V3->V4->V6->V5->V7) ,16 (V1->V3->V4->V6->V5->V7->V8 或 V1->V3->V4->V6->V8) 。 42. 【分析】本题考查单链表的应用。思路 1(借助栈,空间复杂度高) :将表的前半部分依次进栈,依次 访问后半部分时,从栈中弹出一个元素,进行比较。思路 2(类似折纸的思想,算法复杂) :找到中间位置 的元素,将后半部分的链表就地逆置,然后前半部分从前往后、后半部分从后往前比较,比较结束后再恢 复(题中没有说不能改变链,故可不恢复) 。 【解答】为了让算法更简单,这里采用思路 1,思路 2 中的方法留给有兴趣的读者。 (1)算法的基本设计思想: ①借助辅助栈,将链表的前一半元素依次进栈。注意 n 为奇数时要特殊处理。 ②在处理链表的后一半元素时,当访问到链表的一个元素后,就从栈中弹出一个元素,两元素比较, 若相等,则将链表中下一元素与栈中再弹出元素比较,直至链表到尾。 ③若栈是空栈,则得出链表中心对称的结论;否则,当链表中一元素与栈中弹出元素不等时,结论为 链表非中心对称。 (2)算法的实现如下:
typedef struct LNode{ ElemType data; struct LNode *next; //链表结点的结构定义 //结点数据 //结点链接指针

~ 12 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

} *LinkList; int Str_Sym(LinkList L,int n){ //本算法判断带头结点的单链表是否是中心对称 Stack s;initstack(s); LNode *q,*p=L->next; for(int i=1;i<n/2;i++){ Push(p); p=p->next; } if(n%2==1) p=p->next; while(p!=null){ q=pop(s); else break; } if(empty(s)) return 1; else return 0; } //栈空,则说明对称 //否则不对称 //若 n 为奇数,需要特殊处理 //后一半表依次和前一半表比较 //出栈一个结点 //不等则跳出循环 //初始化栈 //q 指向出栈元素,p 工作指针 //前一半结点入栈

if(q->data==p->data) p=p->next;//相等则继续比较下一个结点

(3)算法的时间复杂度为 O(n),空间复杂度为 O(n)。 43. 【分析】本题考查数据通路和指令执行过程。读者应牢固掌握指令的执行过程和原理,并能根据指令 的执行过程和特点了解控制器中各个寄存器的连接方式。 【解答】 (1)b 单向连接微控制器,由微控制器的作用不难得知 b 是指令寄存器(IR) 和 c 直接连 ;a 接主存,只可能是 MDR 和 MAR,c 到主存是单向连接,a 和主存双向连接,根据指令执行的特点,MAR 只单向给主存传送地址,而 MDR 既存放从主存中取出的数据又要存放将要写入主存的数据,因此 c 为主 存地址寄存器(MAR) 为主存数据寄存器(MDR) 具有自动加 1 的功能,且单向连接 MAR,不难 ,a 。d 得出为程序计数器(PC) 。 因此,a 为 MDR、b 为 IR、c 为 MAR、d 为 PC。 (2)先从程序计数器(PC)中取出指令地址,将指令地址送入主存地址寄存器(MAR) ,在相关的 控制下从主存中取出指令送至主存数据寄存器(MDR) ,然后将 MDR 中的指令送至指令寄存器(IR) ,最 后流向微控制器,供微控制器分析并执行指令。 因此,取指令的数据通路为:PC→MAR,M(MAR)→MDR→IR→控制器 (3)(2) 和 的分析类似, 根据 MAR 中的地址去主存取数据, 将取出的数据送至主存数据寄存器 (MDR) , 然后将 MDR 中的数据送至 ALU 进行运算,运算的结果送至累加器(AC) ,运算结束后将 AC 中的结果送 至 MDR,最后将 MDR 中的数据写入主存。 因此,从主存取出、运算和写回主存所经过的数据通路分别为:MAR→M,M(MAR)→MDR→ALU, ALU→AC,AC→MDR→M(MAR)。 44. 【分析】本题考查中断处理次序。中断响应次序和中断处理次序是两个不同的概念。中断响应次序也 称为硬件排队次序,它是不可改变的。在不改变硬件排队电路的前提下,可以通过改变中断屏蔽字来改变 中断处理的优先级,使原来级别较低的中断源变成较高的级别。 【解答】 (1)由题意,可知中断处理的次序为 C>A>D>B。屏蔽码中的“1”表示屏蔽该中断源的中断请 求,“0”表示没有屏蔽,各中断服务程序的屏蔽码如下表所示。 中断源 A B C 中断屏蔽码 A 1 0 1 B 1 1 1 C 0 0 1 D 1 0 1

~ 13 ~

予人玫瑰

手留余香 D

王道 2012 年最后 6 套模拟试题 0

第 4~6 套

1

0

1

(2)各级中断发出的中断请求信号的时刻,画出 CPU 执行中断服务程序的序列,如下图所示。第 0us 时,D 请求到来,由于没有其他的中断请求,所以开始执行中断服务程序 D。第 6us 时,A 请求到来,A 的优先级高于 D,转去执行中断服务程序 A。第 8us 时,B 请求到来,由于 B 的优先级低于 A,所以不响 应 B 请求,继续执行中断服务程序 A。第 10us 时,C 请求到来,C 的优先级最高,虽然此时中断服务程序 A 还没结束,也必须暂停转去执行中断服务程序 C。中断服务程序 C 所需时间为 3us,当第 13us 时,中断 服务程序 C 执行完毕,返回执行中断服务程序 A。第 14us 时,中断服务程序 A 执行完毕(共执行 5us) , 返回执行中断服务程序 D。第 20us 时,中断服务程序 D 执行完毕(共执行 12us) ,返回现行程序。因为 B 请求还存在,所以此时开始执行中断服务程序 B,直至 35us 结束(共执行 15us) 。

(3)在 35us 时间内,完成了 4 级中断的处理,所以平均执行时间为 35/4=8.75us。 45. 【分析】本题考查PV操作实现进程的互斥。 【解答】(1)哥哥存两次钱后,共享变量amount的值为20。哥哥的第三次存钱与弟弟的取钱同时进 行,如果两者顺序执行,则最后amount的值为20;如果在一个进程的执行过程中,进行CPU调度,转去执 行另一进程,则最后amount的值取决于amount=m1及amount=m2的执行先后次序,若前者先执行,则最后 amount的值为10, 若后者先执行, 则最后amount的值为30。 因此, 最后账号amount上面可能出现的值有10、 20、30。 (2)在上述问题中,共享变量amount是一个临界资源,为了实现两并发进程对它的互斥访问,可为 它设置一初值为1的互斥信号量mutex,并将上述算法修改为:
int amount=0; semaphore mutex=1; cobegin{ process SAVE(){ int m1; P(mutex); m1=amount; m1=m1+10; amount=m1; V(mutex); } process TAKE(){ int m2; P(mutex); m2=amount; m2=m2-10; amount=m2; V(mutex); } //互斥访问amount变量的信号量

~ 14 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

} coend

46. 【分析】本题考查磁盘的性能分析及优化。 【解答】(1)每分钟6000转,则旋转1周所需的时间为10ms,旋转1个记录需10/9ms。 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9

由于记录是顺序存放的,读完A记录后需2.5ms完成对数据的处理,此时磁头已转到序号为4的块上, 但第二次应读B记录,则磁盘需空转大半圈回到序号为2的块。同理,对C、D、…、I的读操作也需花费额 外的旋转时间,故读出9个记录需花费的时间为10× 9+2.5=92.5ms。 (2)在(1)中,由于额外的旋转时间导致了读取记录的时间较长,为了减少额外的旋转时间,可以 对记录块的存放顺序作修改,考虑到每读取一个记录后需2.5ms的数据处理时间,磁盘旋转3块所需的时间 是3.33ms,因此可以每间隔3块存放相应的记录块,即1存放A、5存放B、9存放C、4存放D、8存放E、3存 放F、7存放G、2存放H、6存放I,如下图所示。 A 1 H 2 F 3 D 4 B 5 I 6 G 7 E 8 C 9

此时,读出整个文件需要的时间为(4*10/9)*8+1.11+2.5=39.16ms。 47. 【分析】本题考查路由器地址分配的一般原则、路由表的结构、子网划分和子网掩码。首先应根据题 意给出局域网 A 和局域网 B 的子网, 这里局域网 A 的编号为 01, 也就是 202.38.60.01000000, 202.38.60.64, 即 一般选择该网络最小的地址分配给路由器的接口 a,即 201.38.60.01000001,即 202.38.60.65,子网掩码为 255.255.255.192。同理局域网 B 的子网编号为 10,202.38.60.10000000,即 202.38.60.128,接口 b 的地址为 202.38.60.10000001,即 202.38.60.129,子网掩码是 255.255.255.192。对于局域网 C,接口 c 的地址为 202.38.61.1, 子网掩码为 255.255.255.0。 问题 1)-2)就可以求解了, 针对问题 3)-4), 也就是子网的广播地址, 对于局域网 B, 其广播地址为 202.38.60.10111111, 202.38.60.191, 即 对于局域网 C, 就是标准的 202.38.61.255。 【解答】 (1)路由器 a 路由器 b 路由器 c 路由器 d 的子网掩码为 255.255.255.0。 (2)路由器的路由表如下: 目的网络地址 202.38.60.64 202.38.60.128 202.38.61.0 61.0.0.0 子网掩码 255.255.255.192 255.255.255.192 255.255.255.0 255.0.0.0 下一跳地址 直接 直接 直接 直接 接口 a b c d 202.38.60.65 202.38.60.129 202.38.61.1 61.60.21.80 255.255.255.192 255.255.255.192 255.255.255.0 255.0.0.0

可知,局域网 A 的子网掩码为 255.255.255.192;局域网 B 的子网掩码为 255.255.255.192;局域网 C

~ 15 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 0.0.0.0 0.0.0.0

第 4~6 套

61.60.21.80

d

(3)202.38.60.191。 (4)202.38.61.255。

~ 16 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

王道计算机统考模拟试题

第5套

一、单项选择题:第 1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选 项最符合试题要求。
1. 2. 一个栈的输入序列为 1,2,3,…,n,输出序列的第一个元素是 i,则第 j 个输出元素是( A.i-j-1 执行( B. i-j C.j-i+1 D.不确定 B.广度优先搜索图 D.深度优先搜索图 )。 )。 C.n D.2n-1 )操作时,需要使用队列作为辅助存储空间。 )。

A.查找哈希表 C.前序(根)遍历二叉树 3. 4. A.log2n B.2
n

有 n 个结点,并且高度为 n 的二叉树的数目为(

在常用的描述二叉排序树的存储结构中,关键字值最大的结点是( A. 左指针一定为空 C. 左右指针均为空 B. 右指针一定为空 D. 左右指针均不为空 )。 C. 6 D. 7

5. 6.

含有 20 个结点的平衡二叉树的最大深度为( A. 4 B. 5

设无向图 G=(V,E)和 G’=(V’,E’),如果 G’是 G 的生成树,则下面说法错误的是( A. G’是 G 的子图 C. G’是 G 的极小连通子图且 V=V’ B. G’是 G 的连通分量 D. G’是 G 的一个无环子图

) 。

7.

在有向图 G 的拓扑序列中,若顶点 Vi 在顶点 Vj 之前,则下列情形不可能出现的是( A.G 中有弧<Vi,Vj> C.G 中没有弧< Vi,Vj> B.G 中有一条从 Vi 到 Vj 的路径 D.G 中有一条从 Vj 到 Vi 的路径 ) 。 D. 37/12,49/12

) 。

8.

具有 12 个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的 平 均查找长度依次为( A. 37/12,49/13 B. 35/12,39/13 C. 37/13,49/13

9.

对关键字序列{23,17,72,60,25,8,68,71,52}进行堆排序,输出两个最小关键字后的剩余堆是 A.{23,72,60,25,68,71,52} C.{71,25,23,52,60,72,68} A. nlog2n、log2n A.插入排序和快速排序 C.选择排序和归并排序 B. n、log2n B.{23,25,52,60,71,72,68} D.{23,25,68,52,60,72,71} ) 。 C. nlog2n、n D. n 、log2n ) 。
2



) 。

10. 对 n 个关键字进行快速排序,最大递归深度和最小递归深度分别为( 11. 下列排序方法中,时间性能与待排序记录的初始状态无关的是( B.归并排序和快速排序 D.插入排序和归并排序 ) 。

12. 以下有关计算机运算速度衡量指标的描述中,正确的是( A. MIPS 大的机器一定比 MIPS 小的机器快 B. CPU 的主频越高速度越快 C. 执行不同的程序,测得的同一台计算机的 CPI 可能不同 D. CPU 执行程序的时间就是观测到用户程序的执行时间

13. 对于相同位数(设为 N 位,且各包含 1 位符号位)的二进制补码小数和十进制小数,二进制小数 能表示的数的个数/十进制小数所能表示的个数为( A.(0.2)
N

) 。 D.(0.02)N-1

B. (0.2)

N-1

C. (0.02)N ) 。

14. 下列关于机器零的说法,正确的是(

A. 发生“下溢”时,浮点数被当做机器零,机器将暂停运行,转去处理“下溢” B. 只有以移码表示的阶码时,才能用全 0 表示机器零的阶码 C. 机器零属于规格化的浮点数

~ 17 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 ) 。

第 4~6 套

D. 定点数中的零也是机器零 15. 下列的说法中,正确的是( I.双端口存储器可以同时访问同一区间、同一单元 II.双端口存储器当两个端口的地址码相同时,必然会发生冲突 III.高位多体交叉存储器的设计依据了程序的局部性原理 IV.高位四体交叉存储器可能在一个存储周期内连续访问四个模块 A. ( I和III ) 。 B. 4FFFH C. 5FFFH D. 7FFFH ) 。 B. II和III C.I和IV D.只有I 16. 假定用若干个8K× 8位的芯片组成一个32K× 32位的存储器,则地址41F0H所在芯片的最大地址是 A. 0000H

17. 下列叙述中,不符合 RISC 指令系统的设计思想的是( A.指令长度固定、只有 Load/Store 指令可以访存 B.指令种类较少且功能单一、多用硬布线控制实现 C.设置大量的通用寄存器、指令和数据按边界对齐存放 D.采用流水线技术、数据寻址方式种类丰富

18. 某计算机的指令系统中共有 110 条不同的指令,当采用微程序控制方式时,控制存储器中具有的微程 序数目至少是( A.109 ) 。 B.110 C.111 ) 。 D.113

19. 下列关于微指令编码方式的说法中,错误的是(

I.字段直接编码可以用较少的二进制信息表示较多的微操作命令信号,例如有两组互斥微命令中, 微命令个数分别为 8 和 9,则只分别需要 3 位和 4 为即可表示 II.直接编码无须进行译码,微指令的微命令字段中每一位都代表一个微命令 III.垂直型微指令以较长的微程序结构换取较短的微指令结构,因而执行效率高、灵活性强都高于 水平型微指令 IV.字段间接编码中,一个字段的译码输出需要依靠另外某一个字段的输入 A.I、III 和 IV B.II、III 和 IV C.II 和 IV ) 。 D.I、II、III 和 IV 20. 下列关于总线仲裁方式的说法中,正确的有(

I.独立请求方式响应时间最快,是以增加处理机开销和增加控制线数为代价的 II.计数器定时查询方式下,有一根总线请求(BR)和一根设备地址线,若每次计数都从 0 开始,则设 备号小的优先级高 III.链式查询方式对电路故障最敏感 IV.分布式仲裁控制逻辑分散在总线各部件中,不需要中央仲裁器 A.III 和 IV B.I、III 和 IV C.I、II 和 IV D.II、III 和 IV 21. 设 CPU 与 I/O 设备以中断方式进行数据传送,CPU 响应中断时,该 I/O 设备接口控制器送给 CPU 的中断向量表(中断向量表存放中段向量)的指针是 0800H,0800H 单元中的值为 1200H。则该 I/O 设备的中断服务程序在主存中的入口地址为( ) 。 A.0800H B.0801H C.1200H D.1201H ) 。 22. 关于外中断(故障除外)和 DMA,下列哪个说法是正确的( I.DMA 请求和中断请求同时发生时,响应 DMA 请求 II.DMA 请求、非屏蔽中断、可屏蔽中断都要在当前指令结束之后才能被响应 III.非屏蔽中断请求优先级最高,可屏蔽中断请求优先级最低 IV.如果不开中断,所有中断请求均不能响应 V. 在 DMA 方式中,数据的传送完全不用 CPU 干预 A. I 和 V A.用户程序 B. I 和 IV C. I D. II 和 III ) 。 23. 当中断发生后,进入中断处理的程序属于(

B.可能是用户程序,也可能是 OS 程序

~ 18 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 ) 。

第 4~6 套

C.OS 程序

D.单独的程序,即不是用户程序也不是 OS 程序

24. 下列关于进程和线程的叙述中,正确的是( II. 一个进程可包含多个线程,各线程共享栈

I. 一个进程可包含多个线程,各线程共享进程的虚拟地址空间 III. 当一个多线程进程中某个线程被阻塞后,整个进程都将被阻塞 IV. 当一个多线程进程中某个线程被阻塞后,该阻塞进程将被撤销 A.I、II、III B.I、III C.II、III ) 。 运行时间 2 1 0.5 0.2 C. 0.925 D. 2 ) 。 D.II、IV 25. 现有 4 个作业 J1,J2,J3,J4,它们的提交时间和运行时间如下表所示,系统按单道方式运行且采用短作 业优先算法,则平均周转时间是( 作业号 J1 J2 J3 J4 A. 2.5 B. 2.1 提交时间 8 8.4 8.8 9

26. 有两个优先级相同的并发程序 P1 和 P2,它们的执行过程如下所示,假设,当前信号量 s1=0,s2=0. 当前的 z=2,进程运行结束后,x、y 和 z 的值分别是(
进程 P1 … y:=1; y:=y+2; z:=y+1; V(s1); P(s2); y:=z+y; … … 进程 P2 … x:=1 x:=x+1; P(s1); x:=x+y; z:=x+z; V(s2); … …

A. 5,9,9

B. 5,9,4

C. 5,12,9 Allocation A B 1 0 0 0 1 C 2 2 5 4 4

D. 5,12,4 Max A 5 5 4 4 4 2 2 B 5 3 0 5 4 C 9 6 11 A 2 Available B 3 C 3

27. 假设系统有 5 个进程,A、B、C 三类资源。某时刻进程和资源状态如下:

P1 P2 P3 P4 P5

2 4 4 2 3

下面叙述正确的是( ) 。 A. 系统不安全 B. 该时刻,系统安全,安全序列为<P1,P2,P3,P4,P5> C. 该时刻,系统安全,安全序列为<P2,P3,P4,P5,P1> D. 该时刻,系统安全,安全序列为<P4,P5,P1,P2,P3> 28. 下列关于页式存储的说法中,正确的是( ) 。 I.在页式存储管理中,若关闭 TLB,则每访问一条数据都要访问 2 次内存。 II.页式存储管理不会产生内部碎片 III.页式存储管理当中的页面是用户可以感知的 IV.页式存储方式可以采用静态重定位

~ 19 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

A.I、II 和 IV B.I 和 IV C.I D.I 和 III 在虚拟分页存储管理系统中,若进程访问的页面不在主存,且主存中没有可用的空闲帧时,系统 正确的处理顺序为( ) 。 A.决定淘汰页 -> 页面调出 -> 缺页中断 -> 页面调入 B.决定淘汰页 -> 页面调入 -> 缺页中断 -> 页面调出 C.缺页中断 -> 决定淘汰页 -> 页面调出 -> 页面调入 D.缺页中断 -> 决定淘汰页 -> 页面调入 -> 页面调出 若用 8 个字(字长 32 位,且字号和位号都从 0 开始计数)组成的位示图管理内存,假定用户归 还一个块号为 100 的内存块时,它对应位示图的位置为( ) 。 A.字号为 3,位号为 5 B.字号为 4,位号为 4 C.字号为 3,位号为 4 D.字号为 4,位号为 5 假如一个 FCB 块的大小是 64 字节。盘块的大小为 1KB,则在每个盘块中能存放的最大 FCB 数是 ( ) 。 A. 64 B. 1 C. 1000 D. 16 下列关于设备独立性的论述中,正确的是( ) 。 A. 设备独立性是 I/O 设备具有独立执行 I/O 功能的一种特性 B. 设备独立性是指用户程序独立于具体使用的物理设备的一种特性 C. 设备独立性是指独立实现设备共享的一种特性 D. 设备独立性是指设备驱动独立于具体使用的物理设备的一种特性 对于可靠服务和不可靠服务,正确的理解是( ) 。 A. 可靠服务是通过高质量的连接线路来保证数据可靠传输 B. 如果网络本身是不可靠的,那么用户只能尝试使用并无更好的办法 C. 可靠性是相对的,不可能完全保证数据准确传输到目的地 D. 对于不可靠的网络,可以通过应用或用户来保障数据传输的正确性 一个传输数字信号的模拟信道的信号功率是 0.62W, 噪音功率是 0.02W, 频率范围是 3.5-3.9MHz, 该信道的最高数据传输速率是( ) 。 A. 1Mbps B. 2Mbps C. 4Mbps D. 8Mbps 在 CSMA/CD 协议中,下列指标与冲突时间没有关系的是( ) 。 A.检测一次冲突所需要的最长时间 B.最小帧长度 C.最大帧长度 D.最大帧碎片长度 用以太网交换机连接的一组工作站( ) 。 A.同属于一个冲突域,但不属于一个广播域 C. 不属于一个冲突域,也不属于一个广播域 C.不属于一个冲突域,但同属于一个广播域 D.同属于一个冲突域,也同属于一个广播域 一台主机的 IP 地址为 11.1.1.100,子网掩码为 255.0.0.0。现在用户需要配置该主机的默认路由。 经过观察发现,与该主机直接相连的路由器具有如下 4 个 IP 地址和子网掩码: I. IP 地址:11.1.1.1,子网掩码:255.0.0.0 II. IP 地址:11.1.2.1,子网掩码:255.0.0.0 III. IP 地址:12.1.1.1,子网掩码:255.0.0.0 IV. IP 地址:13.1.2.1,子网掩码:255.0.0.0 问 IP 地址和子网掩码可能是该主机默认路由的是( ) 。 A. I 和 II B. I 和 III C. I、III 和 IV D. III 和 IV 设有以下 4 条路由:172.18.129.0/24,172.18.130.0/24,172.18.132.0/24,172.18.133.0/24,如果进 行路由聚合,能覆盖这 4 条路由地址的是( ) 。 A. 172.18.128.0/21 B. 172.18.128.0/22 C. 172.18.130.0/22 D.172.18.132.0/23

~ 20 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

39. TCP 协议中,发送双方发送报文的初始序号分别为 X 和 Y,在第一次握手时发送方发送给接收 方报文中,正确的字段是( ) 。 A.SYN=1,序号=X B. SYN=1,序号=X+1,ACKX=1 C. SYN=1,序号=Y D. SYN=1,序号=Y,ACKY+1=1 40. 一台域名服务器希望解析域名 www.google.com,如果这台主机配置的 DNS 地址为 a,Internet 的 根域名服务器为 b,而存储域名 www.google.com 与其 IP 地址对应关系的域名服务器为 c,那么 这台主机通常先查询( ) 。 A. 域名服务器 a B. 域名服务器 b C. 域名服务器 c D. 不确定 二、综合应用题:第 41~47 小题,共 70 分。
41. (11 分)使用散列函数 hashf(x)=x mod 11,把一个整数值转换成散列表下标,现要把数据: 1,13,12,34,38,33,27,22 插入到散列表中。 (1)使用链地址的冲突处理方法来构造散列表。 (2)分别计算等概率情况下,查找成功和查找不成功所需的平均探查长度。 (3)若查找关键字 34,则需要依次与哪些关键字比较。 42. (12 分)设 m+n 个元素顺序存放在数组 A[1..m+n]中,前 m 个元素递增有序,后 n 个元素递增有序, 试设计一个在时间和空间两方面都尽可能高效的算法,使得整个顺序表递增有序,要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C++或 Java 语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 43. (10 分)设某计算机有变址寻址、间接寻址和相对寻址等寻址方式,一个指令字长等于一个存储字。 设当前指令的地址码部分为 001AH,正在执行的指令所在地址为 1F05H,变址寄存器中的内容为 23A0H。已知存储器的部分地址及相应内容如下表所示。 地址 001AH 1F05H 1F1FH 内容 23A0H 2400H 2500H 地址 23A0H 23BAH 内容 2600H 1748H

(1)当执行取数指令时,如为变址寻址方式,取出的数为多少? (2)如为间接寻址,取出的数为多少? (3)设计算机每取一个存储字 PC 自动加 1,转移指令采用相对寻址,当执行转移指令时,转移地址 为多少?若希望转移到 23A0H,则指令的地址码部分应设为多少? 44. (13 分)现有 4 级流水线,分别完成取指、指令译码并取数、运算、回写四步操作。假设完成各部操 作的时间依次为 100ns、100ns、80ns、50ns。请问: (1)流水线的操作周期应设计为多少? (2)若相邻两条指令发生数据相关,而且在硬件上不采取措施,那么第 2 条指令要推迟多少时间进 行? (3)如果在硬件设计上加以改进,至少需要推迟多少时间? 45. (8分)某系统由R1、R2和R3共3种资源,在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情 况如下表所示,此时系统的可用资源向量为(2,1,2)。试问: 进程 P1 P2 P3 P4 最大资源需求量 R1 3 6 3 4 R2 2 1 1 2 R3 2 3 4 2 1 4 2 0 已分配资源数量 R1 R2 0 1 1 0 R3 0 1 1 2

(1)系统是否处于安全状态?如安全,请给出一个安全序列。

~ 21 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

(2)如果此时 P1 和 P2 均发出资源请求向量 Request(1,0,1),为了保证系统的安全性,应该如何分配 资源给这两个进程?说明你所采用策略的原因。 (3)如果(2)中两个请求立即得到满足后,系统此刻是否处于死锁状态。 46. (7分)设一个没有设置快表的虚拟页式存储系统,页面大小为100字节。一个仅有460个字节的程序 有下述内存访问序列(下标从0开始):10、11、104、170、73、309、185、245、246、434、358、 364,为该程序分配有2个可用页帧(Page frame)。试问: (1)试叙述缺页中断与一般中断的主要区别? (2)若分别采用 FIFO 和 LRU 算法,试计算访问过程中发生多少次缺页中断? (3)若一次访存的时间是 10ms,平均缺页中断处理时间为 25ms,为使该虚拟存系统的平均有效访 问时间不大于 22ms,则可接受的最大缺页中断率是多少? 47. (9分) 主机A向主机B连续发送了3个TCP报文段。 第1个报文段的序号为90, 第2个报文段的序号为120, 第3个报文段的序号为150。请回答: (1)第 1、2 个报文段携带了多少字节的数据? (2)主机 B 收到第 2 个报文段后,发回的确认中的确认号应该是多少? (3)如果主机 B 收到第 3 个报文段后,发回的确认中的确认号是 200,试问 A 发送的第 3 个报文段 中的数据有多少字节? (4)如果第 2 个报文段丢失,而其他两个报文段正确到达了主机 B。那么主机 B 在第 3 个报文段到 达后,发往主机 A 的确认报文中的确认号应该是多少?

~ 22 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

第5套 答案与解析
一、单项选择题
1. 【分析】 【单科书 P53】本题考查出栈序列的特征。若输出序列的第一个元素是 i,则只能说明前面 i-1 个元素均已入栈,而第 j 个出栈元素的序号却无法确定。若假设输出序列的第一个元素是 n,则能否确定 第 j 个输出元素的序号,请读者仔细思考。 【解答】D。当第 i 个元素第一个出栈时,则 i 之前的元素可以依次排在 i 之后出栈,但剩余的元素可 以在此时进栈并且也会排在 i 之前的元素出栈,所以第 j 个出栈的元素是不确定的。 2. 【分析】 【单科书 P66 等】本题考查队列的应用。队列通常应用在需要逐层或逐行的问题,以保存下 【解答】B。图的广度优先搜索类似于树的层序遍历(形象地想象成一个扇形,以搜索起点为中心, 逐层向相连的外圈搜索) ,同样需要借助于队列。前序遍历二叉树是一个递归的过程,通常可以借助于栈, 将递归算法转换为非递归算法。图的深度优先搜索类似于树的前序遍历,也是一个递归的过程,通常也可 以借助栈来实现。 3. 【分析】 【单科书 P89】考查二叉树的性质。若将二叉树的左、右子树颠倒,就成为另一棵不同的二叉 【解答】D。由题可得,每层有一个结点,从根结点往下,每个结点都有做左孩子右孩子两种情况, 由概率知识可得,二叉树共有 2n-1 种树形。 【另解】画草图。n 个结点且高度为 n 的二叉树中,相邻层(每层一个结点)之间有一条边,共有 n-1 条。每条边既可以指向左也可以指向右,共有 2n-1 种指法,对应 2n-1 种树形。 4. 【分析】 【单科书 P109】本题考查二叉排序树的性质。二叉排序树中关键字值大小关系为:左子树< 【解答】B。在二叉排序树的存储结构中,每个结点由三部分构成,其中左(或右)指针指向比该结 点的关键字值小(或大)的结点。关键字值最大的结点一定位于二叉排序树的最右位置上,因此它的右指 针一定为空。 5. 【分析】 【单科书 P114】本题考查平衡二叉树的性质。高度一定的平衡二叉树在结点最多的情况下为 【解答】C。在平衡二叉树的结点最少情况下,递推公式为 N0=0,N1=1,N2=2,Nh=1+Nh-1+Nh-2(h 为平衡二叉树高度,Nh 为构造此高度的平衡二叉树所需最少结点数)。通过递推公式可得,构造 5 层平衡 二叉树至少需 12 个结点,构造 6 层至少需要 20 个。 6. 【分析】 【单科书 P151】本题考查图的生成树的性质。生成树首先要满足树的全部性质,其次图的生 【解答】B。连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中的顶点的所 有边都加上,所以,连通分量中可能存在回路。 【注意】极大连通子图是无向图(不一定连通)的连通分量,极小连通子图是连通无向图的生成树。 极小和极大是在满足连通前提下,针对边的数目而言的。极大连通子图包含连通分量的全部边;极小连通 子图(生成树)包含连通图的全部顶点,且使其连通的最少边数。 7. 【分析】 【单科书 P171】本题考查拓扑序列的性质。拓扑排序的应用举例:本书的各章节作为顶点, 各章节的先学后学关系作为边,构成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某 章节时,其预备知识已在前面的章节里介绍过。 【解答】D。选项 D 中的情况是不可能出现的,因此若 G 中有一条 Vj 到 Vi 的路径,则在图的拓扑序 列中顶点 Vj 应该在顶点 Vi 之前。以分析中的示例说明:若有一条 Vj 到 Vi 的路径,说明 Vj 是 Vi 的先学章 节,则拓扑排序 Vj 应该在 Vi 的前面,显然矛盾。 8. 【分析】 【单科书 P198】本题考查折半查找的平均查找长度。注意:失败结点是虚构的,不能算入查 【解答】A。假设有序表中元素为 A[0…11],不难画出对它所对应的折半查找判定树如下图所示,圆 找次数,当查找到虚构结点上面的圆圈结点,即能判断是否查找失败。 成树必然包含图的全部顶点。 满二叉树,在结点最少的情况下也满足一定的条件。也可以反过来推理。 根结点<右子树。 树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。 一步的处理顺序,以及应用于缓冲区、OS 调度等。

~ 23 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

圈是查找成功结点,方形是虚构的查找失败结点。从而可以求出查找成功的 ASL=(1+2× 2+3× 4+4× 5)/12 =37/12,查找失败的 ASL=(3× 3+4× 10)/13。
5 2 0 1 3 4 6 7 9 8 10 11

9.

【分析】 【单科书 P237】本题考查堆排序的执行过程。堆排序是一种树形选择排序方法,注意区别堆

与二叉排序树。对序列建立初始堆后,堆排序就是一个反复筛选的过程。堆排序的这类题,考生应通过画 图来掌握堆排序的执行过程,而不需要掌握具体算法。 【 解 答 】 D 。 筛 选 法 初 始 建 堆 为 {8,17,23,52,25,72,68,71,60} , 输 出 8 后 重 建 的 堆 为 {17,25,23,52, 60,72,68,71},输出 17 后重建的堆为{23,25,68,52,60,72,71}。读者在解题时一定要画草图。 10. 【分析】 【单科书 P232】本题考查快速排序的递归深度。快速排序过程构成一个递归树,递归深度即 为递归树的高度。 【解答】B。当枢轴值每次都将子表等分时,此时递归树的高为log 2 n;当枢轴值每次都是子表的最大 值或最小值时,此时递归树退化为单链表,树高为 n。 11. 【分析】 【单科书 P244】本题考查各种内部排序算法的性能。读者应从排序的原理上理解掌握初始状 态对排序算法时间性能的影响,而不应是死记硬背。 【解答】C。选择排序在最好、最坏、平均情况下的时间性能均为 O(n2),归并排序在最好、最坏、平 均情况下的时间性能均为 O(nlog2n)。 12. 【分析】 【单科书 P10】本题考查计算机的性能指标。 【解答】C。整机的速度是由多个指标综合衡量的,某个指标的高低并不能完全决定机器的速度,故 A、B 错误。在一个用户程序执行过程中,可能会插入运行其他程序,所以观测到用户程序的执行时间要 大于其真正的 CPU 执行时间,故 D 错误。在不同的程序中,各类指令所占的比例是有可能不同的,因此 测得的 CPI 有可能不同,C 正确。 13. 【分析】 【单科书 P21】本题考查进位计数制以及有关的数学知识。本题结果说明并不是任何十进制小 数都可以用二进制表示,仅有(0.2)N-1 的概率率可以精确的用二进制表示。 【解答】B。N 位二进制补码定点小数(含 1 位符号位)可以表示 2N 个数,十进制的可以表示 2*10N-1 个数(最高位只能取 0 或 1 以表示正负) 。二者的商为(0.2)N-1。 【说明】这里可以联想到 PCM 中的抽样或调制过程( 《计算机网络》。 ) 14. 【分析】 【单科书 P46】本题考查机器零。当浮点运算结果在 0 到最小正数之间(正下溢)或最大负数 到 0 之间(负下溢)时,浮点数值趋于 0,计算机仅将其当做机器零处理。 【解答】B。只有当数据发生“上溢”,才会终止运算操作,转去进行溢出处理,A 错误。规格后化可 以判断运算结果是否上溢出(超过表示范围) ,但和机器零没有关联,C 错误。定点数中所表示的 0,是实 实在在的 0(坐标轴上的) ,而不是趋近 0 的机器零,D 错误。在各种数码的表示法中,移码相当于真值在 坐标轴上整体右移至正区间内,当移码表示的阶码全 0 时,为阶码表示的最小负数,此时直接认为浮点数 是机器零,B 正确。 15. 【分析】 【单科书P91】本题考查几种存储器。高位多体交叉存储器仍然是顺序存储器。 【解答】C。双端口RAM的两个端口具有2组相互独立的地址线、数据线和读写控制线,因此可以同 时访问同一区间、同一单元,I正确;当两个端口同时对相同的单元进行读操作时,则不会发生冲突,II错 误。高位多体交叉存储器由于是在单个存储器中字是连续存放的,所以不能保证程序的局部性原理;而低 位多体交叉存储器由于是交叉存放,所以能很好的满足程序的局部性原理,III错误。高位四体交叉存储器 虽然不能满足程序的连续读取,但仍可能一次连续读出彼此地址相差一个存储体容量的4个字,只是这么 读的概率较小,IV正确。 16. 【分析】 【单科书P86】本题考查存储器的扩展。对于此类题,首先应确定芯片的扩展方式,计算地址

~ 24 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

时不用考虑位扩展的方向,然后列出各组芯片的地址分配,确定给定地址所在的地址范围。 【解答】C。用8K× 8位的芯片组成一个32K× 32位的存储器,每行中所需芯片数为4,每列中所需芯片 数为4,各行芯片的地址分配如下: 第一行(4个芯片并联) :0000H~1FFFH 第二行(4个芯片并联) :2000H~3FFFH 第三行(4个芯片并联) :4000H~5FFFH 第四行(4个芯片并联) :6000H~7FFFH 故,地址为41F0H所在芯片的最大地址即5FFFH。 17. 【分析】 【单科书 P137】本题考查 RISC 的特点以及与 CISC 的区别。对于考查 RISC 特点的题型,要 注意区分其中是否混入了 CISC 的特点。 【解答】 采用流水线技术属于 RISC 的思想, RISC 的指令寻址方式种类少 D。 但 (通常限制在 2-3 种) , 以防止降低编译和执行的效率。其他项均属于 RISC 的思想。 18. 【分析】 【单科书 P169】通常一条机器指令对应一个微程序。由于任何一条机器指令的取指令操作都 是相同的(不考虑多字长指令) ,因此可以将取指操作抽取出来编成一个独立的微程序,这个微程序只负 责将指令从主存中取出送至指令寄存器。此外,也可以编出对应间址周期的微程序和中断周期的微程序, 但这类公用微程序并非必须的,可以用其他指令代替。 【解答】C。公用微程序中取指令是必须的,故而至少有 111 个微程序。 19. 【分析】 【单科书 P169】本题考查微指令的编码方式。编码的是对微指令的控制字段进行编码,以形 成控制信号;目的是在保证速度的情况下,尽量缩短微指令字长。 【解答】A。微命令个数为 8 时,需要 4 位,假设只用 3 位,将会造成每个编码都会输出一个微命令, 事实上,微命令的编码需要预留一个字段表示不输出,I 错误。垂直型微指令的缺点是微程序长、执行速 度慢、工作效率低,III 错误。字段间接编码中的一个字段的某些微命令还需由另一个字段中的某些微命令 来解释,即受到某一个字段的译码输出,IV 错误。 20. 【分析】 【单科书 P205】本题考查总线仲裁。理解三种仲裁方式的原理、线数和优缺点。 【解答】B。独立请求方式每个设备均由一对总线请求线和总线允许线,总线控制逻辑复杂,但响应 速度快,I 正确。计数器定时方式采用一组设备地址线(约 log2n) 错误。链式查询方式对硬件电路故障 ,II 敏感,且优先级不能改变,III 正确。分布式仲裁方式不需要中央仲裁器,每个主模块都有自己的仲裁号和 仲裁器,多个仲裁器竞争使用总线,IV 正确。 21. 【分析】 【单科书 P229】本题考查中断向量。中断向量就是中断服务程序的入口地址,所以需要找到 指定的中断向量,而中断向量是保存在中断向量表中的。 【解答】C。0800H 是中断向量表的地址,所以 0800H 的内容即是中断向量。 22. 【分析】 【单科书 P233】本题考查外中断方式和 DMA 方式的区别。中断方式具有对异常时间的处理 能力,而 DMA 方式仅局限于完成传送数据块的能力。 【解答】C。和中断方式相比,DMA 连接的是高速设备,其优先级高于中断请求,以防止数据丢失, I 正确。DMA 请求的响应时间可以发生在每个机器周期结束时,只要 CPU 不占用总线,而中断请求的响 应时间只能发生在每条指令执行完毕,II 错误。通常情况下,DMA 的优先级要高于外中断,所以 DMA 优 先级一般要比非屏蔽中断请求要高,III 错误。如果不开中断,非屏蔽中断(以及内中断)仍可响应,IV 错误。在 DMA 方式的预处理和后处理中,需要 CPU 的干预,只是在传送的过程中不需要 CPU 的干预, V 错误。 23. 【分析】 【单科书 P12】本题考查中断的处理过程和作用。当中断或异常发生时,通过硬件实现将运行 在用户态的 CPU 立即转入到核心态。 【解答】C。中断发生时,若被中断的是用户程序,系统将从目态转入管态,在管态下进行中断的处 理;若被中断的是低级中断,则仍保留在管态,而用户程序只能在目态下运行,因此进入中断处理的程序 只能是 OS 程序。 24. 【分析】 【单科书 P27】本题考查线程的实现方式。考生要注意掌握进程与线程的区别和联系,以及在 具体执行中线程与进程扮演的角色和线程的属性。

~ 25 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

【解答】B。在多线程模型中,进程依然是资源分配的基本单元,而线程是最基本的 CPU 执行单元, 它们共享进程的逻辑地址空间,但各个线程有自己的栈空间。故 I 对、II 错。在多对一线程模型中,一个 线程被阻塞了,则整个进程都将被阻塞,III 对、IV 错。假如 IV 对的话,凡是遇到等待 I/O 输出的线程, 都被撤销,这显然是不合理的。 25. 【分析】 【单科书 P38】本题考查短进程优先调度算法和平均周转时间。 【解答】B。J1 第一个执行,J1 在 10:00 执行完毕;之后调度 J4;接着调度 J3;最后调度 J2。故平均 周转时间=(2+3.3+1.9+1.2)/4=2.1。 26. 【分析】 【单科书 P50】本题考查并发进程的特点,并结合信号量进行同步的原理。 【解答】C。由于进程并发,所以进程的执行具有不确定性,在 P1、P2 执行到第一个 P、V 操作前, 应该是相互无关的。现在考虑第一个对 s1 的 P、V 操作,由于进程 P2 是 P(s1)操作,所以它必须等待 P1 执行完 V(s1)操作以后才可继续运行, 此时的 x、 z 值分别是 3,3,4, y、 当进程 P1 执行完 V(s1)以后便在 P(s2) 上阻塞,此时 P2 可以运行直到 V(s2),此时的 x、y、z 值分别是 5,3,9,进程 P1 继续运行直到结束,最终 的 x、y、z 值分别为 5,12,9。 27. 【分析】 【单科书 P72】本题考查系统的安全状态和安全序列。 【解答】D。当 Available 为(2,3,3)时,可以满足 P4,P5 中任一进程的需求;这两个进程结束后释放 资源,Available 为(7,4,11)此时可以满足 P1,P2,P3 中任一进程的需求,故该时刻系统处于安全状态,安 全序列中只有 D 满足条件。 28. 【分析】 【单科书 P132 等】本题考查页式存储的相关知识。页式存储是内存管理部分最重要的知识点 之一,对于页式存储,无论选择、分析还是计算题,都比较常见。不仅要知道简单的原理和优缺点,更要 深入理解页式存储的各方面特点和具体操作处理过程。 【解答】C。关闭了 TLB 之后,每访问一条数据都要先访问页表(内存中) ,得到物理地址后,再访 问一次内存进行相应操作,I 正确。凡是分区固定的都会产生内部碎片,而无外部碎片,II 错误。页式存 储管理对于用户是透明的,III 错误。静态重定位是在程序运行之前由装配程序完成的,而页式存储管理方 案在运行过程中可能改变程序位置,IV 错误。 29. 【分析】 【单科书 P150】本题考查虚拟分页存储管理中缺页中断的处理过程。在内存管理中,一定要 特别注意区分基本分页与请求分页、基本分段与请求分段的管理方式下,具体的地址变换过程。 【解答】C。缺页中断的处理流程为:产生缺页中断后;首先去内存寻找空闲物理块,若内存没有空 闲物理块,使用页面置换算法决定淘汰页面,然后调出该淘汰页面;最后再调入该进程欲访问的页面。整 个流程可归纳为:缺页中断->决定淘汰页->页面调出->页面调入。 30. 【分析】 【单科书 P207】本题考查位示图。对于此类题,为了避免出错,建议画出草图求解。 【解答】C。先求出块号为 100 所在的字号,0~31 在字号 0,32~63 在字号 1,64~95 在字号 2,96~127 在字号 3,所以块号 100 在字号 3。接下来求出第 100 块在字号 3 的哪一位,字号 3 的第 0 位是第 96 块, 以此类推第 100 块在字号 3 的第 4 位。或者,字号=100/32=3,位号=100%32=4。 31. 【分析】 【单科书 P192】本题考查 FCB 的存储。 【解答】D。FCB 的存放是不能分开的,所以 1KB 大小的盘块能存放的 FCB 数为 1024/64=16。 32. 【分析】 【单科书 P247】本题考查设备独立性的定义。 【解答】B。设备独立性的定义就是指用户程序独立于具体物理设备的一种特性,引入设备的独立性 是为了提高设备分配的灵活性和设备的利用率等。 33. 【分析】 【单科书 P12】本题考查对可靠服务和不可靠服务的理解。在网络的传输过程中,数据出错是 很难避免的,只有通过检错、纠错、应答机制才能保证数据正确地传输,这种数据传输是可以准确地到目 的地的。 【解答】D。不可靠服务是出于速度、成本等原因的考虑,而忽略了应该有的数据传输的保证机制, 但是可以通过应用或用户判断数据的准确性, 再通知发送方采取措施, 从而把不可靠的服务变为可靠服务。 34. 【分析】 【单科书 P27】本题考查奈氏定理的应用。题干已说明是有噪声的信道,因此应联系到香农定 理,而对于无噪声的信道,则应联系到奈奎斯特定理。奈奎斯特就是在采样定理和无噪声的基础上,提出 了奈氏准则:Cmax=f
采样

×log2N=2f×log2N,其中 f 表示带宽。而香农公式给出了有噪声信道的容量:

~ 26 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

Cmax=W× 2(1+S/N),其中 W 为信道的带宽。它指出,想提高信息的传输速率,应设法提高传输线路的带 log 宽或者设法提高所传信号的信噪比。 【解答】B。首先计算信噪比 S/N=0.62/0.02=31;带宽 W=3.9-3.5=0.4MHz,由香农公式可知最高数据 传输率 V=W× 2(1+S/N)=0.4× 2(1+31)=2Mbps。 log log 35. 【分析】【单科书 P70】本题考查 CSMA/CD 协议中冲突时间的概念。以太网端到端的往返时延称为 冲突时间。为了确保站点在发送数据的同时能检测到可能存在的冲突,CSMA/CD 总线网中所有数据帧都 必须大于一个最小帧长。任何站点收到帧长小于最小帧长的帧就把它当做无效帧立即丢弃。站点在发送帧 后至多经过 2τ(争用期)就可以知道所发送的帧是否遭到了碰撞。因此,最小帧长的计算公式为:最小帧 长=数据传输速率× 争用期。而最大帧碎片长度不得超过最小帧长。 【解答】C。冲突时间就是能够进行冲突检测的最长时间,它决定了最小帧的长度和最大帧碎片的长 度,而最大帧的长度受限于数据链路层的 MTU。 36. 【分析】 【单科书 P88】本题考查以太网交换机。广播域是指彼此接收广播消息的一组网络中的设备; 冲突域是指连接到同一个物理介质的一组设备,若有两台设备同时访问介质,结果就是两个信号冲突。网 络中各层设备能否隔离冲突域 (或广播域) 与其转发数据的原理有关。 网络层设备路由器, 能隔离冲突域, 也能隔离广播域;数据链路层设备以太网交换机、网桥,只能隔离冲突域,但不能隔离广播域;物理层设 备集线器、中继器,既不能隔离冲突域,也不能隔离隔离广播域。 【解答】C。以太网交换机的每个端口都具有自身的冲突域。连接到同一个交换机的设备具有同一个 广播域。 37. 【分析】 【单科书 P116】本题考查默认路由的配置。所有的网络都必须使用子网掩码,同时在路由器 的路由表中也必须有子网掩码这一栏。一个网络如果不划分子网,就使用默认子网掩码。默认子网掩码中 1 的位置和 IP 地址中的网络号字段 net-id 正好相对应。 【解答】 主机地址是一个标准的 A 类地址, A。 其网络地址为 11.0.0.0。 选项 I 的网络地址为 11.0.0.0, 选项 II 的网络地址为 11.0.0.0,选项 III 的网络地址为 12.0.0.0,选项 IV 的网络地址为 13.0.0.0,因此,和 主机在同一网络的是选项 I 和选项 II。 38. 【分析】 【单科书 P118】本题考查路由聚合的计算。路由聚合将网络前缀都相同的连续的 IP 地址组成 一个地址块,它可以包括多个 A、B、C 类网络,并在网络地址后面指明网络前缀的位数。CIDR 虽然不 使用子网但分配到一个 CIDR 地址块的组织,但仍然可以在本组织内根据需要划分出一些子网。 【解答】A。由于前两个字节和最后一个字节都一样,则只比较第三个字节即可,转化为二进制: 129→10000001;130→10000010;132→10000100;133→10000101。显然,这四个数字只有前五位是完全 相同的,因此汇聚后的网络的第三个字节应该是 10000000→128。聚合后的网络的掩码中 1 的数量应该有 8+8+5=21,因此答案是 172.18.128.0/21。 39. 【分析】 【单科书 P167】本题考查 TCP 连接建立的三次握手。 【解答】A。TCP 连接的建立采用三次握手,第一次握手发送方发给接收方的报文中应设定 SYN=1, 序号=X,表明传输数据的第一个数据字节的序号是 X。 40. 【分析】 【单科书 P189】本题考查域名解析的过程。主机发出 DNS 查询报文时,该报文首先被送往该 本地域名服务器。本地域名服务器不能立即回答该查询时,就以 DNS 客户的身份向某一根域名服务器查 询。若根域名服务器也没有该主机的信息时(但此时其一定知道该主机的授权域名服务器的 IP 地址) ,有 两种做法:1)递归查询:根域名服务器向该主机的授权域名服务器发送 DNS 查询报文,查询结果再逐级 返回给原主机;2)迭代查询:根域名服务器把授权域名服务器的 IP 地址返回给本地域名服务器,由本地 域名服务器再去查询。 【解答】A。不管采用何种查询方式,首先都要查询本地域名服务器。该主机配置的 DNS 地址 a 即为 其本地域名服务器地址。

二、综合应用题
41. 【分析】本题考查散列表的构造方法。采用链地址法构造散列表时,在直接计算出关键字对应的哈希 地址后,将关键字结点插入到此哈希地址所在的链表中。 【解答】 (1)由 hashf(x)=x mod 11 可知,散列地址空间是 0 到 10。链地址法构造的表如下:

~ 27 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

(2)在链地址表中查找成功时,查找关键字为 33 的记录需进行 1 次探测,查找关键字为 22 的记录 需进行 2 次探测,依此类推。因此: ASL 成功=(1× 4+2× 3+3)/8=13/8 查找失败时,对于 0 地址,探测 33,22 和 NULL 结点后确定元素不在表中,所以其探测次数为 3;对 于 1 地址,其探测次数为 4;3 地址探测次数为 1,以此类推……。 (本题对查找到空结点也算 1 次) ASL 失败=(3+4+2+1+3+1+1+1+1+1+1)/11=19/11。 (3)由(1)可知,查找关键字 34,需要依次与关键字 1,12,34 进行比较。 【扩展】对同样一组关键字,设定相同的散列函数,则不同处理冲突方法将得到不同的散列表,它们 的平均查找长度也不同,本题若采用线性探查法处理冲突,题目应如何解答? 42. 【分析】本题考查顺序表的应用。在序列基本有序的情况下,通常采用直接插入排序法。 【解答】 (1)算法的基本设计思想: 将数组 A 看成是两个长度分别为 m 和 n 的有序表 L1 和 L2, 只需要将 L2 中的每个元素依次向前插入 到前面有序数组部分中的合适位置即可。插入过程如下: ①取表 L2 中的第一个元素 A[m+1],暂存在 temp 中,让 temp 前插到合适的位置。 ②重复过程①,继续插入 A[m+2],A[m+3],…,A[m+n],直到数组 A 整体有序。 (2)算法的实现如下:
void InsertSort(int A[],int m,int n){ ElemType temp; temp=A[i]; for(int j=i-1;j>=1&&temp<a[j];j--)//向前查找待插入位置 A[j+1]=A[j]; A[j+1]=temp; } } //向后挪位 //复制到插入位置 //辅助变量,暂存待插入元素

for(int i=m+1;i<=m+n;i++){ //将 L2 中的元素依次插入到前面有序部分

(3) 本算法的时间复杂度由 m 和 n 共同决定, 最内层循环的 A[j+1]=A[j]为基本语句。 在最坏情况下, 即 L2 中的所有元素均小于 L1 中的最小元素,则对于 L2 中的每个元素,为了找到其插入位置都需要做 m 次移动,故时间复杂度为 O(mn)。空间复杂度为 O(1)。 43. 【分析】本题考查指令的寻址方式。前两小题涉及数据寻址,其最终目的是寻址操作数,第 3 小题 涉及指令寻址,其目的是寻址下一条将要执行的指令地址。下表列出了基本的寻址方式,其中偏移寻址包 括变址寻址、基址寻址和相对寻址三种方式。 寻址方式 立即寻址 寄存器寻址 直接寻址 间接寻址 寄存器间接寻址 偏移寻址 规则 操作数=A EA=R EA=A EA=(A) EA=(R) EA=(R)+A 主要优点 无需访问存储器 无需访问存储器 简单 寻址空间大 寻址空间大 灵活 主要缺点 操作数范围受限 寻址空间受限 寻址空间受限 多次访问主存 多访问一次主存 复杂

~ 28 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

特别注意相对寻址方式中的 PC 值更新的问题:根据历年统考真题,通常在取出当前指令后立即将 PC 的内容加 1(或加增量) ,使之变成下条指令的地址。 【解答】 (1)变址寻址时,操作数 S=((Rx)+A)=(23A0H+001AH)=(23BAH)=1748H。 (2)间接寻址时,操作数 S=((A))=((001AH))=(23A0H)=2600H。 (3)转移指令使用相对寻址,因为指令字长等于存储字长,PC 每取出一条指令后自动加 1,因此转 移 地 址 =(PC)+1+A=1F05H+1+001AH=1F20H 。 若 希 望 转 移 到 23A0H , 则 指 令 的 地 址 码 部 分 应 为 23A0H-(PC)-1=23A0H-1F05H-1=049AH。 44. 【分析】 本题考查流水线的技术。 编者以为今年组成原理部分的大题极有可能会来自中央处理器这章, 而且考到流水线的概念很大,因此读者务必牢固掌握。 【解答】 (1)流水线操作的时钟周期 t 应按四步操作中的最长时间来考虑,所以 t=100ns。 (2)两条指令发生数据相关冲突情况如下: ADD R1,R2,R3 SUB R4,R1,R5
时钟 指令 ADD

# R2+R3 -> R1 # R1-R5 -> R4

两条指令在流水线中执行情况如下表所示:
1 取指 2 指令译码 并取数 取指 3 运算 指令译码 并取数 4 写回 运算 写回 5 6 7

SUB

ADD 指令在时钟 4 时将结果写入寄存器堆(R1),但 SUB 指令在时钟 3 时读寄存器堆(R1)。本来 ADD 指令应先写入 R1,SUB 指令后读 R1,结果变成 SUB 指令先读 R1,ADD 指令后写 R1,因而发生两条指 令间数据相关。如果硬件上不采取措施,第 2 条指令 SUB 至少应推迟 2 个操作时钟周期(2× 100ns) ,即将 SUB 指令中的指令译码并取数阶段推迟到 ADD 指令的写回阶段之后才能保证不会出错。如下表所示:
时钟 指令 ADD 1 取指 2 指令译码 并取数 取指 3 运算 4 写回 指令译码 并取数 运算 写回 5 6 7

SUB

(3)如果硬件上加以改进,可只延迟 1 个操作时钟周期(100ns) 。因为在 ADD 指令中,运算阶段就 已经得到结果了, 因此可以通过数据旁路技术在运算结果一得到的时候将结果快速送入寄存器 R1, 而不需 要等到写回阶段完成。流水线中执行情况如下图所示:
时钟 指令 ADD 1 取指 2 指令译码 并取数 取指 3 运算 (并采用数据旁路技 术写入寄存器 R1) 4 写回 指令译码并 取数 运算 写回 5 6 7 取指

SUB

45. 【分析】本题考查采用银行家算法避免死锁。 【解答】(1)利用安全性算法对时刻的资源分配情况进行分析,可得到如下表所示的安全性检测情 况。可以看出,此时存在一个安全序列{P2,P3,P4,P1},故该系统是完全的。 进程 R1 P2 P3 P4 2 6 8 Work R2 1 2 3 R3 2 3 4 R1 2 1 4 Need R2 0 0 2 R3 2 3 0 R1 4 2 0 Allocation R2 1 1 0 R3 1 1 2 R1 6 8 8 Work + Allocation R2 2 3 3 R3 3 4 6 True True True Finish

~ 29 ~

予人玫瑰 P1

手留余香 8 3

王道 2012 年最后 6 套模拟试题 6 2 2 2 1 0

第 4~6 套

0

9

3

6

True

(2)若此时P1发出资源请求Request1(1,0,1),按银行家算法进行检查: Request1(1,0,1) ≤ Need1(2,2,2) Request1(1,0,1) ≤ Available(2,1,2) 试分配并修改相应的数据结构,由此形成的资源分配情况如下表所示: 进程 P1 P2 P3 P4 Allocation R1 2 4 2 0 R2 0 1 1 0 R3 1 1 1 2 R1 1 2 1 4 Max R2 2 0 0 2 R3 1 2 3 0 1 1 1 R1 Available R2 R3

再利用安全性算法检查系统是否安全,可用资源Available(1,1,1)已不能满足任何进程,系统进入不安 全状态,此时系统不能将资源分配给P1。 若此时P2发出资源请求Request2(1,0,1),按银行家算法进行检查: Request2(1,0,1) ≤ Need2(2,0,2) Request2(1,0,1) ≤ Available(2,1,2) 试分配并修改相应的数据结构,由此形成的资源分配情况如下表所示: 进程 P1 P2 P3 P4 Allocation R1 1 5 2 0 R2 0 1 1 0 R3 0 2 1 2 R1 2 1 1 4 Max R2 2 0 0 2 R3 2 1 3 0 1 1 1 R1 Available R2 R3

再利用安全性算法检查系统是否安全,安全性检查情况如下表所示。可以看出,此时存在一个安全序 列{P2,P3,P4,P1},故该状态是完全的,可立即给P2申请的资源分配给它。 进程 R1 P2 P3 P4 P1 1 6 8 8 Work R2 1 2 3 3 R3 1 3 4 6 R1 1 1 4 2 Need R2 0 0 2 2 R3 1 3 0 2 R1 5 2 0 1 Allocation R2 1 1 0 0 R3 2 1 2 0 R1 6 8 8 9 Work + Allocation R2 2 3 3 3 R3 3 4 6 6 True True True True Finish

(3)如果(2)中两个请求立即得到满足,此刻系统并没有立即进程死锁状态,因为这时所有进程没 有提出新的资源申请, 全部进程均没有因资源请求没得到满足而进入阻塞状态。 只有当进程提出资源请求, 且全部进程都进入阻塞状态时,系统才处于死锁状态。 46. 【分析】本题考查缺页中断和页面置换算法。 【解答】(1)缺页中断是一种特殊的中断,它与一般中断的区别是:①在指令执行期间产生和处理 中断信号。CPU通常在一条指令执行完后检查是否有中断请求,而缺页中断是在指令执行时间,发现所要 访问的指令或数据不在内存时产生和处理的;②一条指令在执行期间可能产生多次缺页中断。如一条读取 数据的多字节指令,指令本身跨越两个页面,若指令后一部分所在页面和数据所在页面均不在内存,则该 指令的执行至少产生两次缺页中断。 (2)每个页面大小为100字节,则页面的访问顺序如下: 10 0 11 0 104 1 170 1 73 0 309 3 185 1 245 2 246 2 434 4 458 4 364 3

采用FIFO算法的页面置换情况如下表,共产生缺页中断6次。

~ 30 ~

予人玫瑰

手留余香 0 0 0 0

王道 2012 年最后 6 套模拟试题 1 1 0 1 1 0 0 1 0 3 3 1 0 √ 1 1 0 0 0 1 3 3 0 1 √ 1 1 3 0 √ 1 3 1

第 4~6 套

走向 块号1 块号2 淘汰 缺页 走向 块号1 块号2 淘汰 缺页

2 2 3 1 √ 2 2 1 3 √

2 2 3

4 4 2 3 √

4 4 2

3 3 4 2 √

√ 0 0 0 0

√ 1 1 0

采用LRU算法的页面置换情况如下表,共产生缺页中断7次。 2 2 1 4 4 2 1 √ 4 4 2 3 3 4 2 √





(3)设可接受的最大缺页中断率为ρ。若要访问页面在内存中,一次访问的时间是10ms(访问内存页 表)+10ms(访问内存)=20ms。如果不在内存,所花时间为10ms(访问内存页表)+25ms(中断处理)+10ms(访问 内存页表)+10ms(访问内存)=55ms。平均有效访问时间: 20ms× (1-ρ)+55ms×ρ≤22ms,得可接受的最大缺页中断率ρ为5.7%。 47. 【分析】本题考查TCP首部的序号和确认号字段。TCP首部的序号字段是用来保证数据能有序提交给 应用层,序号是建立在传送的字节流之上;确认号字段是期望收到对方的下一个报文段的数据的第一个字 节的序号。 【解答】 (1)第1个报文段的序号是90,说明其传送的数据从字节90开始,第2个报文段的序号是120, 说明其传送的数据从字节120开始,即第1个报文段的数据为第90~119号字节,共30字节。同理,可得出第 2个报文段的数据为30个字节。 (2)主机B收到第2个报文段后,期望收到A发送的第3个报文段,第3个报文段的序号字段为150,故 发回的确认中的确认号为150。 (3)主机B收到第3个报文段后发回的确认中的确认号为200,则说明已收到第199号字节,故第3个报 文段的数据为第150~199号字节,共50字节。 (4)TCP默认使用累计确认,即TCP只确认数据流中至第一个丢失(或未收到)字节为止的字节。题 中,第2个报文段丢失,故主机B应发送第2个报文段的序号120。

~ 31 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

王道计算机统考模拟试题

第6套

一、单项选择题:第 1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选 项最符合试题要求。
1. 2. 若已知一个栈的入栈序列是 1,2,3,4。其出栈序列为 p1,p2,p3,p4,则 p2,p4 不可能是( A.2、 4 B.2、 1 C.4、 3 D.3、 4 )。 在链式队列的出队操作中,需要修改尾指针的情况发生在( A.队列为空队列时 C.队列只剩一个元素的时候 3. 4. A.250 B.500 B.变成满队列的时候 D.任何时候 )。 )。 D.501 )。

一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( C.254

由某种序列可以唯一的确定一棵二叉树,不能唯一的确定一棵二叉树是( A.先序序列和中序序列 C.中序序列和层序序列 B.后序序列和中序序列 D.先序序列和层序序列

5.

分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( A. (100,80, 90,60,120,110,130) C.(100,60,80,90,120,110,130) B. (100,120,110,130,80,60,90) D. (100,80, 60, 90,120,130,110) )。

)。

6.

由 4 棵树组成的森林中,第一、第二、第三和第四棵树中的结点数分别为 30、10、20、5,当把森林 转换成二叉树后,对应二叉树中根结点的右子树的左子树的结点数为( A. 29 B. 9 B.n 2. acfdeb B.4 C. 25 C.n-1 3. aedfcb 4. aefdbc D. 19 )棵生成树。 ) 。 D.1 5. aecfdb D.2 )次(假设

7. 8.

如果具有 n 个顶点的图是一个环,则它有( A.n2 1. aebfdc A.5

如右图所示,在下面的 5 个序列中,符合深度优先遍历的序列有多少个( C.3

9.

在一棵含有 n 个关键字的 m 阶 B-树中进行查找,至多需要读盘( 读一次盘就能将整个结点取出) 。 A.log2n C.1+log m /2 [(n+1)/2] A.1,5,15,20,35,10,30,10 C.1,5,10,15,35,30,10,20 B.1+log2n D. 1+log n/2 [(m+1)/2]

10. 一组数据(30,20,10,15,35,1,10,5),用堆排序(小顶堆)的筛选方法建立的初始堆为( B.1,10,30,10,5,15,35,20 D.A、B 和 C 均不正确 ) 。

)。

11. 一组经过第一趟 2-路归并排序后的记录的关键字为{25,50,15,35,80,85,20,40,36,70} ,其中包含 5 个长 度为 2 的有序表,用 2-路归并排序方法对该序列进行第二趟归并后的结果为( A. 15,25,35,50,80,20,85,40,70,36 C. 15,25,50,35,80,85,20,36,40,70 I. 指令缓冲器 II. 移位器 V. 乘法器 B.IV、V 和 VI ) B.IMUL 有符号数乘法指令 D.ADD 加法指令 B. 15,25,35,50,20,40,80,85,36,70 D. 15,25,35,50,80,20,36,40,70,85 ) 。 III. 通用寄存器 VI. 先行进位链 C. III 和 IV D. I、II、V 和 VI

12. 对汇编语言程序员来说,以下部件中不透明的是( IV. 中断字寄存器 A.I、II 和 III 指令不可能是(

13. 在补码表示的机器中,若寄存器 R 中原存的数为 9EH,执行一条指令后现存的数为 CFH,则表明该 A.XOR 异或运算指令 C.SAR 算术右移指令

14. 已知 C 程序中,某类型为 int 的变量 x 的值为-1088。程序执行时,x 先被存放在 16 位寄存器 R1 中,

~ 32 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题 B. FFBCH C. 0FBCH ) 。

第 4~6 套

然后被进行算术右移 4 位的操作。则此时 R1 中的内容(以十六进制表示)的是( A. FBC0H D. 87BCH 15. 下列关于DRAM和SRAM的说法中,错误的是(

) 。

I. SRAM不是易失性存储器,而DRAM是易失性存储器 II. DRAM比SRAM集成度更高,因此读写速度也更快 III.主存只能由DRAM构成,而高速缓存只能由SRAM构成 IV.与SRAM相比,DRAM由于需要刷新,所以功耗较高 A. II、III和IV B. I、III和IV C. I、II和III D. I、II、III和IV ) 。 16. 在Cache和主存构成的两级存储体系中,Cache的存取时间是100ns,主存的存取时间是 1000ns,如果 希望有效(平均)存取时间不超过 Cache 存取时间15%,则 Cache的命中率至少应为( A.90% B.98% C.95% D.99%

17. 设相对寻址的转移指令占两个字节,第一字节是操作码,第二字节是相对位移量(用补码表示) ,若 CPU 每当从存储器取出一个字节时,即自动完成(PC)+1→PC。若当前 PC 的内容为 2008H,要求转移 到 2001H,则该转移指令第二字节的内容为( A.05H B.07H C.F8H ) 。 C.程序状态字寄存器 D.时序电路 18. 下列部件不属于控制器的是( A.指令寄存器 ) 。 D.F7H

B.程序计数器

19. 已知一台时钟频率为 2GHz 的计算机的 CPI 为 1.2。某程序 P 在该计算机上的指令条数为 4× 9。若在 10 该计算机上,程序 P 从开始启动到执行结束所经历的时间是 4s,则运行 P 所用 CPU 时间占整个 CPU 时间的百分比大约是( A. 40% A.PCI B. 60% B.USB ) 。 C. 80% ) 。 D.ISA C.EISA D. 100%

20. 下列计算机总线是串行总线的是(

21. 某机有四级中断,优先级从高到低为 1→2→3→4。若将优先级顺序修改,改后 1 级中断的屏蔽字为 1101,2 级中断的屏蔽字为 0100,3 级中断的屏蔽字为 1111,4 级中断的屏蔽字为 0101,则修改后的 优先顺序从高到低为( A.1→2→3→4 ) 。 C.1→3→4→2 ) 。 ) 。 D.2→1→3→4 B.3→1→4→2

22. 外部设备打印机适合于连接的通道是( A. 数组多路通道 B. 字节多路通道 A. 由进程的程序结构决定 C. 与进程调度策略有关 24. ( A. 时间片轮转 C. 短进程优先 A. 没有进程进入临界区 23. 并发进程运行时,其推进的相对速度是(

C. 选择通道 D. 任意一种通道

B. 由进程自己的代码控制 D. 在进程创建时确定的 B. 先来先服务 D. 优先级调度 ) 。 B. 有一个进程进入临界区 D. 有一个进程在等待进入 ) 。

)调度算法有利于 CPU 繁忙型的进程,而不利于 I/O 繁忙型的进程

25. 对于两个并发进程,设互斥信号量为 mutex,若 mutex=0,则表示( C. 有一个进程进入临界区,另一个进程等待进入 A. 系统资源总数 C. 用户最大需求数 I.动态分区分配 IV.简单段页式 A. I、II 和 V

26. 利用银行家算法进行安全序列检查时,不需要的参数是( B. 满足系统安全的最少资源数 D. 用户已占有的资源数 ) 。 III.虚拟页式 VI.虚拟段式 C. 只有 III II.简单页式 V.简单段式 B. III 和 IV

27. 下列哪些存储分配方案可能使系统抖动, (

D.III 和 VI

28. 一个 64 位的计算机系统中,地址线宽为 64 位,实际使用的虚拟地址空间的大小是 248,若采用虚拟

~ 33 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题
13

第 4~6 套

页式存储管理,每页的大小为 2 ,即 8KB,页表表项长为 8 字节,采用多级页表进行管理,那么多 级页表的级次最小是( A. 3 B. 4 C. 5 ) 。 D. 6 )为主要目标。 B. 提高存储空间的利用率 D. 提高换入、换出速度

29. 对外存对换区的管理应以( A. 提高系统吞吐量 C. 降低存储费用

30. 设有一个记录文件,采用链接分配方式,逻辑记录的固定长度为 100B,在磁盘上存储时采用记录成组 分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存,要修改第 22 个逻辑记录共需启动 磁盘( A. 3 )次。 B. 4 C. 5 D. 6 ) 。

31. 从下列关于目录检索的说法中,正确的是(

A. 由于 Hash 具有较快的检索速度,故现代操作系统中都用它来替代传统的顺序检索法 B. 在利用顺序检索法时,对树型目录应采用文件的路径名,且应从根目录开始逐级检索 C. 在利用顺序检索法时,只要路径名的一个分量名未找到,便应停止查找 D. 在顺序检索法时的查找完成后,即可得到文件的物理地址 32. I/O 中断是 CPU 与通道协调工作的一种手段,所以在( A. CPU 执行“启动 I/O”指令而被通道拒绝接收 B. 通道接收了 CPU 的启动请求 C. 通道完成了通道程序的执行 D. 通道在执行通道程序的过程中 33. 在不同网络结点的对等层之间通信需要的是( A. 模块接口 B. 对等层协议 ) 。 B. 1800 bps C. 2400 bps D. 3600 bps ) 。 D. 电信号 C. 服务原语 )时,便要产生中断。

34. 现采用调相和调幅相结合的调制方式,载波有四种相位变化和两种幅度变化,调制速率是 600 波特, 那么数据速率是( A.1200 bps

35. 设待传送数据总长度为 L 位,分组长度为 P 位,其中头部开销长度为 H 位,源结点到目的结点之间的 链路数为 h, 每个链路上的延迟时间为 D 秒, 数据传输率为 B bps, 电路交换建立连接的时间为 S 秒, 则电路交换方式传送完所有数据需要的时间是( A.hD+L/B 秒 B. S+hD+L/B 秒 ) 。 D. S+L/B 秒 C. S+hD+PL/((P-H)B)秒 ) 。

36. 以太网中,当数据传输率提高时,帧的发送时间就会相应的缩短,这样可能会影响到冲突的检测。为 了能有效地检测冲突,可以使用的解决方案有( A.减少电缆介质的长度或减少最短帧长 B.减少电缆介质的长度或增加最短帧长 C.增加电缆介质的长度或减少最短帧长 D.增加电缆介质的长度或增加最短帧长 37. 在因特网中, 分组从源结点到目的结点可能要经过多个网络和路由器。 IP 在传输过程中 (不考虑 NAT) , IP 地址的变化情况是( ) 。 A.源地址和目的地址都不会发生变化 B.源地址有可能发生变化而目的地址不会发生变化 C.源地址不会发生变化而目的地址有可能不会发生变化 D.源地址和目的地址都有可能发生变化 38. 关于 TCP 和 UDP 端口,下列说法正确的是( ) 。 A. TCP 和 UDP 分别拥有自己的端口号,它们互不干扰,可以共存于同一台主机 B. TCP 和 UDP 分别拥有自己的端口号,但它们不能共享于同一台主机 C. TCP 和 UDP 的端口没有本质区别,它们可以共存于同一台主机 D. TCP 和 UDP 的端口没有本质区别,它们互不干扰,不能共存于同一台主机

~ 34 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

39. 一个长度为 3000 字节的 UDP 数据报。在数据链路层使用以太网来进行传输,为了正确传输,则需要 将其拆分成( A.2 )个 IP 数据片。 B.3 C.4 D.不拆分 ) 。 B. 高性能 WWW 服务器 D. 本地域名服务器

40. 下列哪种技术可以最有效地降低访问 WWW 服务器的时延( A. 高速传输线路 C. WWW 高速缓存

二、综合应用题:第 41~47 小题,共 70 分。 41. (10 分)下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一 圈,去掉圈上权最大的边” ,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路) 。 42. (13 分)n 个整数存放在一维数组 L[1…n]中。试设计一个在时间和空间两方面都尽可能高效的算 法,找出数组 L 中的第 k 小元素(即从小到大排序后处于第 k 个位置的元素) 。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C++或 Java 语言描述算法,关键之处给出注释。 43. (12 分)假设有两个整数 x 和 y,x=-68,y=-80,采用补码形式(含 1 位符号位)表示,x 和 y 分 别存放在寄存器 A 和 B 中。另外,还有两个寄存器 C 和 D。A、B、C、D 都是 8 位的寄存器。请 回答下列问题: (要求最终用十六进制表示二进制序列) (1)寄存器 A 和 B 中的内容分别是什么? (2)x 和 y 相加后的结果存放在 C 寄存器中,寄存器 C 中的内容是什么?此时,溢出标志位 OF 是什么?符号标志位 SF 是什么?进位标志位 CF 是什么? (3)x 和 y 相减后的结果存放在 D 寄存器中,寄存器 D 中的内容是什么?此时,溢出标志位 OF 是什么?符号标志位 SF 是什么?进位标志位 CF 是什么? 44. (11 分)设某机中,CPU 的地址总线 A15~A0,数据总线 D7~D0(A0、D0 为最低位) 。存储器地 址空间为 3000H~67FFH。 其中 3000H~4FFFH 为 ROM 区, 选用 4K× 的 ROM 芯片; 2 5000H~67FFH 为 RAM 区,选用 2K× 的 SRAM 芯片。请问: 4 (1)组成该存储器需要多少片 ROM 芯片和 SRAM 芯片? (2)ROM 芯片、SRAM 芯片各需连接 CPU 的哪几根地址线和数据线? (3)应如何设置片选信号,分别写出各片选信号的逻辑表达式。 45. (7分)系统有5个进程,其就绪时刻(指在该时刻已进入就绪队列)、服务时间如下表所示。分 别计算采用先来先服务、短作业优先、高响应比优先的平均周转时间和带权周转时间。 进程 P1 P2 P3 P4 P5 就绪时刻 0 2 4 6 8 服务时间 3 6 4 5 2

46. (8 分)有一文件系统如图 1 所示。根目录常驻内存,目录文件组织成链接文件,不设文件控制 块,普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占 2 个字节,共 4 个字节) 。若下级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指示其 文件控制块的磁盘地址。每个目录文件磁盘块的最后 4 个字节供拉链使用。下级文件在上级目录 文件中的次序在图中为从左至右。每个磁盘块有 512 字节,与普通文件的一页等长。

~ 35 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

图1 图2 普通文件的文件控制块组织如图 2 所示,其中,每个磁盘地址占 2 个字节,前 10 个地址直接指 示该文件前 10 页的地址。第 11 个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文 件页地址;第 12 个地址指示二级索引表地址,二级索引表中每个地址指示一个一级索引表地址;第 13 个地址指示三级索引表地址,三级索引表中每个地址指示一个二级索引表地址。请问: (1)一个普通文件最多可有多少个文件页? (2)若要读文件 J 中的某一页,最多启动磁盘多少次? (3)若要读文件 W 中的某一页,最少启动磁盘多少次? (4)就(3)而言,为最大限度减少启动磁盘的次数,可采用什么方法?此时,磁盘最多启动多 少次? 47. (9分)考虑某路由器具有下列路由表项: 网络前缀 142.150.64.0/24 142.150.71.128/28 142.150.71.128/30 142.150.0.0/16 下一跳 A B C D

(1)假设路由器接收到一个目的地址为 142.150.71.132 的 IP 分组, 请确定该路由器为该 IP 分组

选择的下一跳,并解释说明。 (2)在上面的路由器由表中增加一条路由表项, 该路由表项使以 142.150.71.132 为目的地址的 IP 分组选择“A”作为下一跳,而不影响其他目的地址的 IP 分组转发。 (3)在上面的路由表中增加一条路由表项,使所有目的地址与该路由表中任何路由表项都不匹 配的 IP 分组被转发到下一跳“E” 。 (4)将 142.150.64.0/24 划分为 4 个规模尽可能大的等长子网,给出子网掩码及每个子网的可分 配地址范围。

~ 36 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

第6套 答案与解析
一、单项选择题 1. 【分析】【单科书 P53】本题考查出入栈序列。 【解答】C。对于 A,可能的顺序是:1 入,1 出,2 入,2 出,3 入,3 出,4 入,4 出。对于 B,可能的顺序是: 1 入,2 入,3 入,3 出,2 出,4 入,4 出,1 出。对于 D,可能的顺序是:1 入,1 出,2 入,3 入,3 出,2 出,4 入,4 出。C 则没有对应的序列。 【另解】对于 D 选项,p2 为最后一个入栈元素 4,则只有 p1 或 p3 出栈的元素有可能为 3(请读者分 两种情况自行思考),而 p4 绝不可能为 3。读者在解答此类题时,一定要注意出栈序列中的“最后一个入 栈元素”,这样可以节省答题的时间。 2. 【分析】【单科书 P61】本题考查链式队列的操作特点。链队列有头、尾两个指针:插入元素时,在 链队列尾部插入一个新结点,并且修改尾指针;删除元素时,在链队列头部删除一个结点,并且修改头指 针。因此,通常出队操作是不需要修改尾指针的。 【解答】C。当链式队列中只有一个元素时,当这唯一的一个元素出队时,则需要将尾指针置为 NULL (不带头结点)或指向头结点(带头结点)。 【另解】排除法。变成空队后还进行出队操作则出错,A 错误;链队列理论上不存在队列满的情况, B 错误;通常情况下,出队操作仅修改队头指针,D 错误;只可能选 C。 3. 【分析】【单科书 P90】本题考查二叉树的度与叶结点数的关系。对于完全二叉树,只有最后一个非 【解答】 由二叉树结点的公式: 0+n1+n2= n0+n1+(n0-1)=2n0+n1-1, D。 N=n 因为 n=1001, 所以 1002=2n0+n1, 在完全二叉树中,n1 只能取 0 或 1,在本题中只能取 0,故 n0=501。 4. 【分析】【单科书 P96】本题考查由遍历序列构造二叉树。由遍历序列构造二叉树的思想就是找到根 结点, 然后将序列划分成左、 右子树, 如此递归地进行下去。 前序序列和中序序列、 后序序列和中序序列、 或中序序列和层序序列可唯一确定一个二叉树。 【解答】D。先序序列和层序序列不能唯一的确定一棵二叉树,层序序列第 1 次访问根结点,先序序 列为 NLR,虽然能找到根结点,但无法划分左、右子树。
1 2 3 3 2 1 2 3 3 1 1 2 1 2 3

叶结点的度为 1,其他非叶结点度只可能为 2。

如上图所示的 5 棵不同的二叉树,其对应的先序序列和层序序列是相同的。 5. 【分析】 【单科书 P100】本题考查二叉排序树的构造过程。利用逐点插入法建立二叉排序树是从空树 【解答】C。画出三个选项 ABC 构造的二叉排序树的草图即可知道答案,C 和 AB 构造的树形不同; 再画出最后一个选项 D 构造的二叉排序树即可验证答案,D 和 AB 两项的相同。 6. 【分析】【单科书 P104】本题考查森林与二叉树的转换。先将森林中的每一棵树转换为二叉树,再将 【解答】B。将这四棵树转换为二叉树后,第一棵树的根结点变成二叉树的根结点,第二棵树的根结 点变成了根结点的右孩子,第二棵树中剩下的结点变成了其根结点的左子树。 7. 【分析】 【单科书 P151】本题考查图的生成树。n 个顶点的生成树是具有 n-1 条边的极小连通子图,n 【解答】 因为 n 个顶点构成的环共有 n 条边, B。 去掉其中任意一条便是一棵生成树, 共有 n 种情况, 所以可以有 n 棵不同的生成树。 8. 【分析】 【单科书 P162】本题考查图的深度优先遍历。图的深度优先搜索算法尽可能“深”地搜索一个 【解答】D。仅 1 和 4 正确。以 2 为例,遍历到 c 之后,与 c 邻接且未被访问的结点为空集,所以 a 图,类似于树的先序遍历。 个顶点构成的环具有 n 条边,去掉任一条边后剩下的图依然的连通的。 这些二叉树转换为森林。为了简化思路,本类题可以直接将树看成二叉树。 开始,通过查找,将每个结点作为一个叶结点插入。

~ 37 ~

予人玫瑰 9.

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

的邻接点 b 或 e 入栈,显然 2 不符合这种情况。 【分析】 【单科书 P202】本题考查 B 树的形状与磁盘读取次数的关系。在 B 树上进行查找需比较的结 【解答】C。根据 B 树的定义,第一层(根结点)至少有 1 个结点;第二层至少有 2 个结点;除根结 点以外的每个非终端结点至少有 m/2 棵子树,则第三层至少有 2 m/2 个结点……第 h+1 层至少有 2 m/2
h?1

点数最多为 B 树的高度,B 树的高度与 B 树的阶 m 和关键字总数 n 有关。

个结点,注意到第 h+1 层是不包含任何信息的叶结点。对于关键字数为 n 的 B 树,叶结点即
h?1

查找不成功的结点为 n+1,由此有n + 1 ≥ 2 m/2

,即h ≤ log m /2 (( + 1)/2) + 1。

10. 【分析】 【单科书 P237】本题考查初始堆的建立。首先对以第 n/2 个结点为根的子树(也即最后一个 结点的父结点为根的子树)筛选,使该子树成为堆,之后向前依次对各结点为根的子树进行筛选,直到筛 选到根结点。 【解答】C。从 n/2 ~1 依次筛选堆的过程如下图所示:
30 20 10
筛选结点15

30 20 10

筛选结点10

30 20 1

15 5
筛选结点20

35

1

10 15

5

35

1

10 15

5

35

10

10

30 5 1

筛选结点30

1 5 10

15 20

35

10

10 20

15

35

30

10

11. 【分析】 【单科书 P240】本题考查归并排序的执行过程。第一趟归并时,将每个关键字看成一个有序 表,两两进行归并;第二趟归并时,将第一趟结果的 5 个长度为 2 的有序表归并,得到 2 个长度为 4 的有 序表和 1 个长度为 2 的有序表。 【解答】B。由于这里是采用 2-路归并,而且是第二趟排序,所以每 4 个元素放在一起归并,可将序 列划分为{25,50,15,35},{80,85,20,40}和{36,70},分别对它们进行排序为{15,25,35,50},{20,40,80,85}和 {36,70}。 12. 【分析】 【单科书 P14】本题考查部件的“透明性”。在计算机中,客观存在的事物或属性从某个角度看 不到,就称之为“透明”。这与日常生活中的“透明”正好相反,日常生活中的透明就是要公开,然大家看得 到。所谓透明实际上指那些不属于自己管的部分,在计算机系统中,下层机器级的概念性结构功能特性, 对上层机器语言的程序员来说就是透明的。 【解答】C。汇编程序员在编程时,不需要考虑指令缓冲器、移位器、乘法器和先行进位链等部件。 移位器、乘法器和先行进位链属于运算器的设计。 13. 【分析】 【单科书 P21 等】本题考查进制数的转换以及各种运算操作。 【解答】B。将寄存器 R 的前后内容转为二进制:1001 1110 和 1100 1111。XOR 指令,和 0101 0001 异或即可,A 正确;SAR 指令,算术右移一位可以得到结果,C 正确;ADD 指令,加上 31H 即可,D 正 确。有符号乘法指令则找不到可以相乘的整数,B 错误。 14. 【分析】 【单科书 P21 等】考查不同进制数之间的转换与算术移位运算。对于本类题型,应先将-1088 转换为 16 位的补码表示,执行算术右移之后,再转换为十六进制数。算术右移的规则为:保持最高的符 号位不变,符号位为 1 时,补码右移空位补 0;符号位为 1 时,右移空位补 1(逻辑左/右移都是补 0) 。 【解答】 R1的内容首先为[-1088]补=1111 1011 1100 0000B=FBC0H。 B。 算术右移4位的结果为1111 1111 1011 1100B=FFBCH,则此时R1中的内容为FFBCH。15. 【分析】 【单科书P79】本题考查SRAM和DRAM的区

~ 38 ~

予人玫瑰 别。

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

【解答】D。SRAM和DRAM都属于易失性存储器,掉电就会丢失,I错误。SRAM的集成度虽然更低, 但速度更快, 因此通常用于高速缓存Cache, II错误。 主存可以用SRAM实现, 只是成本高, III错误。 和SRAM 相比,DRAM成本低、功耗低、但需要刷新,IV错误。 16. 【分析】 【单科书P94】本题考查Cache命中率的相关计算。 【解答】D。设Cache命中率为a,则(1000+100)(1-a)+100a≤115,解得a≥0.985,故至少为99%。 【注意】虽然也可以采用同时访问Cache和主存的方式,此时不命中的访问时间为1000ns,但若题设 中没有说明,默认Cache不命中的时间为访问Cache和主存的时间之和。 17. 【分析】 【单科书 P130】本题考查相对寻址的原理。相对寻址的形式地址中存放的是相对位移量。有 效地址是将 PC 的内容加上指令格式中的形式地址 A 的结果。 【解答】D。由于转移指令占两个字节,当 PC 的内容为 2008H 时,执行完转移指令后 PC 的内容为 200AH,所以有 2001H-200AH=-9H,用补码表示为 F7H。 18. 【分析】 【单科书 P148】本题考查控制器的组成。控制器由程序计数器、指令寄存器、存储器地址寄 存器、存储器数据寄存器、指令译码器、时序电路和微操作信号发生器等组成。 【解答】C。程序状态字(PSW)寄存器属于运算器的组成部分。 19. 【分析】 【单科书 P10】本题考查根据时钟频率、指令条数和 CPI 来计算程序执行时间。 【解答】B。程序的执行时间 1.2× 109/2GHz=2.4s,所占百分比为(2.4/4)× 4× 100%=60%。 20. 【分析】 【单科书 P210】本题考查典型的总线标准。 【解答】B。PCI、EISA、ISA 均是并行总线标准,USB 是通用串行总线标准。 21. 【分析】 【单科书 P231】本题考查中断屏蔽字的设置。屏蔽字可以改变中断处理优先级,利用中断屏 蔽字可以不改变中断响应次序的情况下改变中断处理的次序。 【解答】B。在屏蔽字中,1 表示屏蔽该中断,0 表示响应该中断。1 级中断的屏蔽字为 1101,表示屏 蔽 1 级、 级和 4 级中断; 级中断的屏蔽字为 0100, 2 2 表示屏蔽 2 级中断 (即其自身, 故可知优先级最低) ; 3 级中断的屏蔽字为 1111,表示能屏蔽所有级中断(优先级最高) 级中断的屏蔽字为 0101,表示能屏蔽 ;4 2 级和 4 级中断。此外,还有一个简单方法:1 越多优先级就越高,因为屏蔽其他中断源数就越多。 22. 【分析】 【单科书 P234】本题考查各类通道的特点。字节多路通道用于连接多台低速设备;选择通道 又称高速设备,物理上可连接多个设备,但在一段时间内只能选择一台设备;数组多路通道结合了前两种 通道的特点,具有较高的传输速率和通道利用率。 【解答】B。打印机属于低速设备,它适合于连接到字节多路通道上,一个字节多路通道上运行连接 多台相同或不同的低速设备,以字节交叉方式传送信息。 23. 【分析】 【单科书 P35】本题考查并发执行的特点。根据进程的一次执行和并发执行的区别来分析影响 进程推进速度的因素。 在进程的一次运行过程中其代码的执行序列是确定的, 即使有循环、 转移、 或等待, 对于进程来讲,其运行的轨迹也是确定的。 【解答】C。当进程存在于一个并发系统中时,这种确定性就被打破了。由于系统中存在大量的可运 行的进程, 操作系统为了提高计算机的效率, 会根据用户的需求和系统资源的数量来进行进程调度和切换。 此时,进程由于被调度,打破了原来的固执执行速度,因此,进程的相对速度就不受进程自己的控制,而 是取决于进程调度的策略。 24. 【分析】 【单科书 P37】本题考查各种调度算法的特点。 【解答】B。FCFS 调度算法比较有利于长作业,而不利于短作业。所谓 CPU 繁忙型的作业,是指该 类作业需要大量的 CPU 时间进行计算,而很少请求 I/O 操作,I/O 繁忙型的作业是指 CPU 处理时,需频繁 的请求 I/O 操作,所以 CPU 繁忙型作业更接近于长作业。 25. 【分析】 【单科书 P50】本题考查互斥信号量的性质。 【解答】B。mutex 初值为 1,表示允许一个进程进入临界区,当由一个进程进入临界区且没有进程等 待进入时,mutex 减 1,变为 0。|mutex|为等待进入的进程数。 26. 【分析】 【单科书 P72】本题考查银行家算法。 【解答】B。安全性检查一般要用到进程所需的最大资源数,减去进程占用的资源数,得到进程为满

~ 39 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

足进程运行尚需要的可能最大资源数,而系统拥有的最大资源数减去已分配掉的资源数得到剩余的资源数, 比较剩余的资源数是否满足进程运行尚需要的可能最大资源数就可以得到当前状态是否安全的结论。而满 足系统安全的最少资源数并没有这么一个说法。 27. 【分析】 【单科书 P154】本题考查系统抖动。要通过对存储分配的理解来推断系统是否会发生抖动, 所以本题同时也需要了解不同的存储分配方案的内容。 【解答】D。抖动现象是指刚刚被换出的页很快又要被访问,为此,又要换出其他页,而该页又很快 被访问,如此频繁地置换页面,以致大部分时间都花在页面置换上。对换的信息量过大,内存容量不足不 是引起系统抖动现象的原因,而选择的置换算法不当才是引起抖动的根本原因,例如,先进先出算法就可 能会产生抖动现象。本题中只有虚拟页式和虚拟段式才存在换入换出的操作,简单页式和简单段式因已经 全部将程序调入内存,因此不需要置换,也就没有了抖动现象。 28. 【分析】 【单科书 P134】本题考查虚拟页式存储管理中多级页表的计算。 【解答】B。由题中所给的条件,虚拟地址空间是 248,即没有完全使用 64 位地址。页面大小为 213, 即 8KB,则用于分页的地址线的位数为 48-13=35。下面计算每一级页表能容纳的最多数量。由题意,每个 页面为 8KB,每个页表项为 8 字节,那么一页中能容纳的页表项为 8KB/8B=1K,即 1024 个页表项,可以 占用 10 位地址线来寻址,故剩余的 35 位地址线可以分为 35/10=3.5,向上取整为 4,因此至少 4 级页表才 能完成此虚拟存储的页面映射。 29. 【分析】 【单科书 P128】本题考查覆盖和交换的作用。内存管理是为了提高内存利用率,引入覆盖和 交换技术,就是为了在较小的内存空间中用重复使用的方法来节省存储空间。 【解答】D。覆盖和交换技术付出的代价是,需要消耗更多的处理机时间,它实际上是一种以时间换 空间的技术。为此,从节省处理机时间来讲,换入、换出速度越快,付出的时间代价就越小,反之就越大, 当时间代价大到一定程度时,覆盖和交换技术就没有意义了。 30. 【分析】 【单科书 P203】本题考查文件的物理结构。 【解答】C。第 22 个逻辑记录存放在第 5 个物理块中(22× 100/512=4,余 152) ,由于文件采用的物 理结构是链接文件,因此需要从第一个物理块开始读取,共需启动磁盘 5 次。 31. 【分析】本题考查目录检索的原理。实现用户对文件的按名存取,系统先利用用户提供的文件名形成 检索路径,对目录进行检索。在顺序检索中,路径名的一个分量未找到,说明路径名中的某个目录或文件 不存在,就不需要继续再检索了。 【解答】C。目录的查询方式有两种:顺序检索法和 Hash 法,通常还是采用顺序检索法,A 错误。在 树型目录中, 为了加快文件检索速度, 可设置当前目录, 于是文件路径可以从当前目录开始查找, 错误。 B 在顺序检索法查找完成后,得到的是文件的逻辑地址,D 错误。 32. 【分析】 【单科书 P239】本题考查通道控制方式。应结合组成中的知识点来解答。 【解答】C。CPU 启动通道时不管启动成功与否,通道都要回答 CPU,通道在执行通道程序时,CPU 与通道并行,当通道完成通道程序的执行,便产生 I/O 中断向 CPU 报告。 33. 【分析】 【单科书 P11】本题考查网络协议中的基本概念。协议、服务、对等层等基本概念是 OSI 参 考模型的重要内容,与分层体系结构的思想相互渗透。 【解答】 对等层是指计算机网络协议层次中, 将数据“直接”传递给对方的任何两个同样的层次, 因此, 对等层之间的通信必须有对等层之间的协议。选项 A 是相邻层之间通信所必需的,选项 C 和 D 是物理层 的内容。本题答案为 B。 34. 【分析】 【单科书 P29】考查数据的调制。波特率和比特率是一对容易混淆的概念,其联系也是考查的 重点,也常与奈奎斯特定理和香农定理结合起来考查。 【解答】B。若一个码元携带 n bit 的信息量,则 M Baud 的码元传输速率所对应的信息传输速率为 M*n bit/s。“四种相位变化和两种幅度变化”可得 1 码元对应的信息量为 log(4*2)=3bit,因而数据率为 600*3=1800 bps。 35. 【分析】 【单科书 P6】本题考查计算机网络的性能指标。计算机网络的各种性能指标(尤其是时延、 吞吐率)是重要考点,时延主要包括发送时延(也叫传输时延)和传播时延。 【解答】B。电路交换首先建立连接,然后再进行数据传输,因此传送所有数据所需的时间是连接建

~ 40 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

立时间,链路延迟,发送时间的和,即 S+hD+L/B。 36. 【分析】【单科书 P71】本题考查 CSMA/CD 协议的碰撞检测原理。最短帧长等于在争用期时间内发 送出的比特数。站点在发送帧后至多经过 2τ(争用期)就可以知道所发送的帧是否遭到了碰撞。因此,最 小帧长=总线传播时延× 数据传输速率× 2。 【解答】B。当传输速率提高时,为了有效地检测冲突,可采用减少电缆介质的长度,使争用期时间 减少(即以太网端到端的时延增小) ,保持最小帧长不变;或增加最短帧长。 37. 【分析】 【单科书 P112】本题考查对 IP 协议的理解。在因特网中,当一个路由器接收到一个 IP 分组 时,路由器根据 IP 分组头部中的目的 IP 地址进行路由选择,并不改变源 IP 地址和目的 IP 地址的值。需 要提醒的一点是:MAC 帧在不同的网络上传送时,其 MAC 帧首部中的源地址和目的地址都要发生变化。 【解答】A。即使在 IP 分组被分片时,源 IP 分组的源 IP 地址和目的 IP 地址也将复制到每个分片的头 部中。因此,在整个传输过程中,IP 分组中的源 IP 地址和目的 IP 地址都不发生变化。 38. 【分析】 【单科书 P159】本题考查传输层端口号。端口号只具有本地意义,即端口号只是为了标识本 计算机应用层中各进程。在因特网中不同计算机的相同端口号是没有联系的。 【解答】A。不论是 TCP 还是 UDP,它们都提供了对给定的主机上的多个进程进行区分的能力,端口 就是 TCP 和 UDP 为了识别一个主机上的多个进程而设计的。 TCP 和 UDP 分别拥有自己的端口号, 它们互 不干扰,是可以共存于同一台主机的。 39. 【分析】 【单科书 P113】本题考查以太网中 IP 数据报的分片。因为 IP 数据报被封装在链路层数据报 中,故链路层的 MTU(最大传输单元)严格地限制着 IP 数据报的长度。 【解答】B。以太网帧的 MTU 是 1500B,IP 头部长度为 20B,因此以太网的最大数据载荷是 1480B, 因此 3000B 的数据必须进行分片,3000=1480+1480+40 共 3 片。 40. 【分析】本题考查 WWW 高速缓存。 【解答】C。WWW 高速缓存将最近的一些请求和响应暂存在本地磁盘中,当与暂存的请求相同的新 请求到达时,WWW 高速缓存就将暂存的响应发送出去,从而降低了广域网的带宽。

二、综合应用题
41. 【分析】本题考查最小生成树的定义和性质。连通图的生成树包括图中的全部 n 个顶点和足以使图连 通的 n-1 条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大 到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。 若仍连通,继续向下删;直到剩 n-1 条边为止。 【解答】 这种方法是正确的。 由于经过“破圈法”之后, 最终没有回路, 故一定可以构造出一棵生成树。 下面证明这棵生成树是最小生成树。记“破圈法”生成的树为 T,假设 T 不是最小生成树,则必然存在最小 生成树 T0, 使得它与 T 的公共边尽可能地多, 则将 T0 与 T 取并集, 得到一个图, 此图中必然将存在回路, 由于破圈法的定义就是从回路中去除权最大的边,此时生成的 T 的权必然是最小的,这与原假设 T 不是最 小生成树矛盾。从而 T 是最小生成树。下面通过实例来说明“破圈法”的过程:

42. 【分析】本题考查顺序表的应用。本题最直接的做法就是用排序算法对数组先进行从小到大的排序, 然后直接提取 L(k)便得到了第 k 小元素,但其平均时间复杂度将达到O(nlog 2 n)以上。此外,还可以采用小

~ 41 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

顶堆的方法, 每次堆顶元素都是最小值元素, 时间复杂度为O(n + klog 2 n)。 下面介绍一个更为巧妙的算法, 它是基于快速排序的划分操作的。 【解答】 (1)算法的主要设计思想: 从数组 L[1…n]中选择枢轴 pivot(随机地或者直接取第一个)进行和快速排序一样的划分操作后,表 L[1…n]被划分为 L[1…m-1]和 L[m+1…n],其中 L(m)=pivot。 讨论 m 与 k 的大小关系: ①当 m=k 时,显然 pivot 就是所要寻找的元素,直接返回 pivot 即可。 ②当 m<k 时,则所要寻找的元素一定落在 L[m+1…n]中,从而可以对 L[m+1…n]递归地查找第 k 小的 元素。 ③当 m>k 时,则所要寻找的元素一定落在 L[1…m-1]中,从而可以对 L[1…m-1]递归地查找第 k 小的 元素。 (2)算法的实现如下:
int kth_elem(int a[],int low,int high,int k){ int pivot=a[low]; int low_temp=low; while(low<high){ while(low<high&&a[high]>pivot) --high; a[low]=a[high]; while(low<high&&a[low]<pivot) ++low; a[high]=a[low]; } a[low]=pivot; //上面即为快速排序中的划分算法 //以下就是本算法思想中所述的内容 if(low==k) else if(low>k) else } //由于与 k 相同,直接返回 pivot 元素 //在前一部分表中递归寻找 //在后一部分表中递归寻找 return a[low]; return kth_elem(a,low_temp,low-1,k); return kth_elem(a,low+1,high_temp,k); //由于下面会修改 low 与 high,在递归时又要用到它们 int high_temp=high;

算法的时间复杂度在平均情况下可以达到 O(n)。而所占空间复杂度则取决于划分的方法。 【说明】本题当然可以采用其他方法,这里仅仅提供一个巧妙的方法,供读者参考。 43. 【分析】本题考查补码的机内表示、补码的运算和溢出判断。 【解答】 (1)因 x=-68=-(100 0100)2,则[-68]补=1011 1100=BCH;因 y=-80=-(101 0000)2,则[-80]补=1011 0000=B0H,所以寄存器 A 和 B 中的内容分别是 BCH、B0H。 (2)[x+y]补=[x]补+[y]补=1011 1100+1011 0000=1 0110 1100=6CH,所以寄存器 C 中的内容是 6CH,其 真值为 108。此时,溢出标志位 OF 为 1,表示溢出,即说明寄存器 C 中的内容不是真正的结果;符号标 志位 SF 为 0,表示结果为正数(溢出标志为 1,说明符号标志有错) ;进位标志位 CF 为 1,仅表示加法器 最高位有进位,对运算结果不说明什么。 (3) [x-y]补=[x]补+[-y]补=1011 1100+0101 0000=1 0000 1100=0CH,最高位前面的一位被丢弃 (取模运算) , 结果为 12,所以寄存器 D 中的内容是 0CH,其真值为 12。此时,溢出标志位 OF 为 0,表示不溢出,即: 寄存器 D 中的内容是真正的结果;符号标志位 SF 为 0,表示结果为正数;进位标志位 CF 为 1,仅表示加

~ 42 ~

予人玫瑰

手留余香

王道 2012 年最后 6 套模拟试题

第 4~6 套

法器最高位有进位,对运算结果不说明什么。 44. 【分析】本题考查存储器的扩展。根据各个存储区所要求的容量和选定的存储芯片的容量,就可以计 算出各种芯片的数目,即:总片数=总容量/每片的容量。 将多个芯片组合起来常采用位扩展法、字扩展法、字和位同时扩展法。位扩展是指只在位数方向扩展 (加大字长) ,而芯片的字数和存储器的字数是一致的;字扩展是指仅在字数方向扩展,而位数不变,字 扩展将芯片的地址线、数据线、读写线并联,由片选信号来区分各个芯片。本题需采用字和位同时扩展, 即在字数方向和位数方向上同时扩展。 【解答】 (1)已知数据总线为 8 位,ROM 区为 3000H~4FFFFH,故 ROM 的容量为 8K× 8B;ROM 芯 片数=8K× 8B/4K× 2B=8 片(分为 2 组,每组 4 片) 。RAM 区为 5000H~67FFH,故 RAM 的容量为 6K× 8B; SRAM 芯片数=6K× 8B/2K× 4B=6 片(分为 3 组,每组 2 片) 。 (2)ROM 芯片的容量为 4K× 2,具有 12 根地址线、2 根数据线,因此 ROM 芯片的地址线连接 CPU 地址线的低 12 位 A11~A0,每组 ROM 内的 4 片芯片分别连接 CPU 数据线的 D7D6、D5D4、D3D2、D1D0。 SRAM 芯片的容量为 2K× 4,具有 11 根地址线、4 根数据线,因此 SRAM 芯片的地址线连接 CPU 地址线 的低 11 位 A10~A0,每组 SRAM 内的 2 片芯片分别连接 CPU 数据线的 D7D6D5D4、D3D2D1D0。 (3)ROM 区有 2 个片选信号,RAM 区有 3 个片选信号,共需 5 个片选信号,根据地址分配的要求, 各片选信号的逻辑表达式如下: CS0 = A15 A14 A13 A12 , CS1 = A15 A14 A13 A12 , CS2 = A15 A14 A13 A12 A11 CS3 = A15 A14 A13 A12 A11 , CS4 = A15 A14 A14 A12 A11 45. 【分析】本题考查各种调度算法的执行以及性能分析。 【解答】(1)采用先来先服务调度时,执行作业的次序为P1、P2、P3、P4、P5,如下表所示。 作业号 P1 P2 P3 P4 P5 就绪时刻 0 2 4 6 8 服务时间 3 6 4 5 2 平 作业号 P1 P2 P5 P3 P4 就绪时刻 0 2 8 4 6 服务时间 3 6 2 4 5 平 等待时间 0 1 5 7 10 均 等待时间 0 1 1 7 9 均 开始时刻 0 3 9 11 15 结束时刻 3 9 11 15 20 开始时刻 0 3 9 13 18 结束时刻 3 9 13 18 20 周期时间 3 7 9 12 12 8.6 周期时间 3 7 3 11 14 7.6 带权周转时间 3/3=1.0 7/6=1.17 9/4=2.25 12/5=2.4 12/2=6.0 2.56 带权周转时间 3/3=1.0 7/6=1.17 3/2=1.5 11/4=2.75 14/5=2.8 1.84

(2)采用短作业优先调度时,执行作业的次序为P1、P2、P5、P3、P4,如下表所示。

(3)采用高响应比优先调度时,响应比=响应时间/运行时间。在时刻0,只有进程P1就绪,执行P1, 在时刻3结束。此时只有P2就绪,执行P2,在时刻9结束。此时P3、P4、P5均就绪,计算它们的响应比分别为 2.25、1.6、1.5,则选择执行P3,在时刻13结束。此时P4、P5均就绪,计算它们的响应比分别为2.4、3.5,则 选择执行P5,在时刻15结束。此时只有P4就绪,执行P4,在时刻20结束。整个执行作业的次序为P1、P2、 P3、P5、P4,如下表所示。 作业号 P1 P2 P3 P5 就绪时刻 0 2 4 8 服务时间 3 6 4 2 等待时间 0 1 5 5 开始时刻 0 3 9 13 结束时刻 3 9 13 15 周期时间 3 7 9 7 带权周转时间 3/3=1.0 7/6=1.17 9/4=2.25 7/2=3.5

~ 43 ~

予人玫瑰 P4

手留余香 6

王道 2012 年最后 6 套模拟试题 5 平 9 均 15

第 4~6 套

20

14 8.0

14/5=2.8 2.14

46. 【分析】本题考查文件目录的结构。 【解答】 (1)因为磁盘块大小为 512B,所以索引块大小也为 512B,每个磁盘地址大小为 2B。因此, 一个一级索引表可容纳 256 个磁盘地址。同样地,一个二级索引表可容纳 256 个一级索引表地址,一个三 级 索 引 表 可 容 纳 256 个 二 级 索 引 表 地 址 。 这 样 , 一 个 普 通 文 件 最 多 可 有 文 件 页 数 为 10+256+256× 256+256× 256× 256=16843018 页。 (2) 由图可知, 目录文件 A 和 D 中的目录项都只有两个, 因此这两个目录文件都只占用一个物理块。 要读文件 J 中的某一页, 先从内存的根目录中找到目录文件 A 的磁盘地址, 将其读入内存 (已访盘 1 次) 。 然后从目录 A 中找出目录文件 D 的磁盘地址读入内存(已访盘 2 次) 。再从目录 D 中找出文件 J 的文件 控制块地址读入内存(已访盘 3 次) 。在最坏情况下,该访问页存放在三级索引下,此时需要一级一级地 读三级索引块才能得到文件 J 的地址(已访盘 6 次) 。最后读入文件 J 中的相应页(共访盘 7 次) 。所以, 若要读文件 J 中的某一页,最多启动磁盘 7 次。 (3)由图可知,目录文件 C 和 U 的目录项较多,可能存放在多个链接在一起的磁盘块中。在最好情 况下,所需的目录项都在目录文件的第一个磁盘块中。先从内存的根目录中找到目录文件 C 的磁盘地址读 入内存(已访盘 1 次) 。在 C 中找出目录文件 I 的磁盘地址读入内存(已访盘 2 次) 。在 I 中找出目录文件 P 的磁盘地址读入内存(已访盘 3 次) 。从 P 中找到目录文件 U 的磁盘地址读入内存(已访盘 4 次) 。从 U 的第一个磁盘块中找出文件 W 的文件控制块地址读入内存(已访盘 5 次) 。在最好情况下,要访问的页在 文件控制块的前 10 个直接块中,按照直接块指示的地址读文件 W 的相应页(已访盘 6 次) 。所以,若要 读文件 W 中的某一页,最少启动磁盘 6 次。 (4)为了减少启动磁盘的次数,可以将需要访问的 W 文件挂在根目录的最前面的目录项中。此时, 只需读内存中的根目录就可以找到 W 的文件控制块, 将文件控制块读入内存 (已访盘 1 次) 最差情况下, , 需要的 W 文件的那个页挂在文件控制块的三级索引下,那么读 3 个索引块需要访问磁盘 3 次(已访盘 4 次)得到该页的物理地址,再去读这个页即可(已访盘 5 次) 。此时,磁盘最多启动 5 次。 47. 【分析】本题考查CIDR编址和路由转发。 【解答】 (1)在使用 CIDR 时会有多个匹配结果,应从匹配结果选择具有最长网络前缀的路由。首先 142.150.0.0/16 和 142.150.71.132 是相匹配的,前面 16 位相同,下面分析其他项: ①142.150.64.0/24 和 142.150.71.132 不匹配,因为前 24 位不相同。 ②142.150.71.128/28 和 142.150.71.132 的前 24 位是匹配的,只需看后面 4 位是否一样,128 的二进制 为 1000 0000,132 的二进制为 1000 0100,前 4 位相同,故匹配了 28 位。 ③142.150.71.128/30 和 142.150.71.132 的前 24 位是匹配的, 但后面的 6 位中第 6 位不一样, 故不匹配。 因此,根据最长网络前缀的匹配原则,应根据第 2 个路由表项转发,下一跳路由为 B。 (2)欲达到题目的要求,只需构造一个网络前缀和该地址匹配 32 位就行了,即针对 142.150.71.132 的特定主机路由,增加的表项为:网络前缀 142.150.71.132/32、下一跳 A。 (3)增加 1 条默认路由:网络前缀 0.0.0.0/0、下一跳 E。 (4)要划分成 4 个规模尽可能大的子网,则需要从主机位中划出 2 位作为子网位(22=4,CIDR 广泛 使用之后允许子网位可以全 0 和全 1) 。 各子网地址分别为: 142.150.64.0000 0000; 142.150.64.0100 0000; 142.150.64.1000 0000; 142.150.64.1100 0000。子网掩码应该为 255.255.255.192。可分配地址范围需将主机号中全 0 和全 1 的都去掉。因此各子网 的地址分配方案如下: 子网地址:142.150.64.0/26 子网地址:142.150.64.64/26 子网地址:142.150.64.128/26 子网地址:142.150.64.192/26 地址范围:142.150.64.1~142.150.64.62 地址范围:142.150.64.65~142.150.64.126 地址范围:142.150.64.129~142.150.64.190 地址范围:142.150.64.193~142.150.64.254

~ 44 ~



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com