&&&华职教育自学考试&自考试卷&04747&Java语言程序设计（一）&阶梯式突破试卷&附历年...
邀请好友参加吧
版 次：1页 数：字 数：印刷时间：日开 本：16开纸 张：胶版纸包 装：平装是否套装：是国际标准书号ISBN：6所属分类：&&
下载免费当当读书APP
品味海量优质电子书，尊享优雅的阅读体验，只差手机下载一个当当读书APP
本商品暂无详情。
当当价：为商品的销售价，具体的成交价可能因会员使用优惠券、积分等发生变化，最终以订单结算页价格为准。
划线价：划线价格可能是图书封底定价、商品吊牌价、品牌专柜价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品曾经展示过的销售价等，由于地区、时间的差异化和市场行情波动，商品吊牌价、品牌专柜价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：折扣指在划线价（图书定价、商品吊牌价、品牌专柜价、厂商指导价等）某一价格基础上计算出的优惠比例或优惠金额。如有疑问，您可在购买前联系客服咨询。
异常问题：如您发现活动商品销售价或促销信息有异常，请立即联系我们补正，以便您能顺利购物。
当当购物客户端手机端1元秒
当当读书客户端万本电子书免费读(window.slotbydup = window.slotbydup || []).push({
id: '4540180',
container: s,
size: '250,200',
display: 'inlay-fix'
热门资料排行
添加成功至
资料评价：
所需积分：0当前位置： >>
王道模拟试题(前3套,正式版)
予人玫瑰手留余香王道计算机统考模拟试题1第1套一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选 项最符合试题要求。1. 6 个元素以 6、5、4、3、2、1 的顺序进栈，下列不合法的出栈序列是（ A. 5、4、3、6、1、2 C. 3、4、6、5、2、1 2. B. 4、5、3、1、2、6 D. 2、3、4、1、5、6 ） 。利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN 只有两个存储单元，则在下列表达式中， 不会发生溢出的是（ ） 。 A. A-B*(C-D) B. (A-B)*C-D C. (A-B*C)-D D. (A-B)*(C-D) 在一棵三叉树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（ A. 4 ）个。 B. 5 C. 6 B. ABDCEF D. 7 ）。 C. DBACEF ）个。 D. DABECF3.4. 5.已知某二叉树的中序、层序序列为 DBAFCE、FDEBCA，则该二叉树的后序序列为（ A. BCDEAF I. II. 以下关于二叉排序树的说法中，错误的有（对一棵二叉排序树按前序遍历得出的结点序列是从小到大的序列 每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树就是二叉排序 树III. 在二叉排序树中，新插入的关键字总是处于最底层 IV. 删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同 A. 1 6. B. 2 C. 3 D. 4 ）。B E A C D如右图所示为一棵平衡二叉树（字母不是关键字），在结点 D 的右子树上插入结 点 F 后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树应为（7. 8.若 G 是一个具有 36 条边的非连通无向图（不含自回路和多重边） ，则图 G 的结点数至少是（ A. 11 B. 10 C. 9 D. 8 ） 。） 。已知有向图 G=(V，A)，其中 V={a,b,c,d,e}，A={&a,b&，&a,c&，&d,c&，&d,e&，&b,e&，&c,e&}，对该 图进行拓扑排序，下面序列中不是拓扑排序的是（ A. a,d,c,b,e B. d,a,b,c,e C. a,b,d,c,e D. a,b,c,d,e ）9.折半查找有序表（2,10,25,35,40,65,70,75,81,82,88,100 ），若查找元素 75，需依次与表中元素（ 进行比较。 A. 65,82,75 B. 70,82,75 C. 65,81,75 D. 65,81,70,7510. 对一组数据（84,47,15,21,25）排序，数据在排序的过程中的变化如下： （1） 84 47 15 21 25 （3） 21 25 15 47 84 则所采用的排序方法是（ A. 堆排序 A. 2 B. 3 （2） 25 47 15 21 84 （4） 15 21 25 47 84 ）。 C. 快速排序 D. 插入排序 ） 。B. 冒泡排序 C. 4 D. 511. 若对 29 个记录只进行三趟多路平衡归并，则选取的归并路数至少是（1题中的疑问请在王道论坛答疑专区提出，并注明：模拟试题/第 x 套/第 x 题-1-予人玫瑰手留余香 ） 。 B. 该机器的地址总线宽度为 32 位 D. 以上说法均不正确 B. x1 必须为 1，x2x3x4 任意 D. x1 必须为 0，x2x3x4 任意12. 下列关于配备 32 位微处理器的计算机说法正确的是（ A. 该机器的通用寄存器一般为 32 位 C. 该机器能支持 64 位操作系统 13. 设[x]补=1.x1x2x3x4，当满足（ A. x1 必须为 1，x2x3x4 至少有一个为 1 C. x1 必须为 0，x2x3x4 至少有一个为 1int n=0xA1B6; unsigned int m=n; m=m&&1; //m 右移一位）时，x&-1/2 成立。14. 设机器数字长 16 位，有一个 C 语言程序段如下：则在执行完该段程序后，m 的值为（ A. 50DBH B. FFB6H） D. D0DBH ） 。 （假设不考虑一致维护位） D. 64× 13 bit ） 。C. A1B6H15. 某存储系统中，主存容量是 Cache 容量的 4096 倍，Cache 被分为 64 个块，当主存地址和 Cache 地址 采用直接映像方式时，地址映射表的大小应为（ A. 6× 4097 bit B. 64× 12 bit 16. 下列关于 Cache 和虚拟存储器的说法中，错误的有（ C. 6× 4096 bitI.当Cache失效（即不命中）时，处理器将会切换进程，以更新Cache中的内容 II.当虚拟存储器失效（如缺页）时，处理器将会切换进程，以更新主存中的内容 III.Cache和虚拟存储器由硬件和OS共同实现，对应用程序员均是透明的 IV.虚拟存储器的容量等于主存和辅存的容量之和 A. I和IV B. III和IV C. I、II和III D. I、III和IV ） 。 17. 在通用计算机指令系统的二地址指令中，操作数的物理位置可安排在（ I.一个主存单元和缓冲存储器 III.一个主存单元和一个数据寄存器 V.一个主存单元和一个外存单元 A. II、III 和 IV 18. 指令（ B. II、III C. I、II 和 III D. I、II、III 和 V ）从主存中读出。 B. 有时根据 PC，有时根据转移指令 D. 有时根据 PC，有时根据地址寄存器 ） 。 II.两个数据寄存器 IV.一个数据寄存器和一个控制存储器A. 总是根据程序计数器 PC C. 根据地址寄存器 ADD ADD19. 流水线计算机中，下列语句发生的数据相关类型是（ R1, R2, R3; (R2) + (R3) -& R1 R4, R1, R5; (R1) + (R5) -& R4 B. 读后写 C. 写后读 D. 读后读A. 写后些 A. 数据总线 时间是（ A. 34.82s I. 外部事件20. 间址寻址第一次访问内存所得到信息经系统总线的（ B. 地址总线 ） 。 B. 42.86s II. Cache C. 85.71s D. 87.77s C. 控制总线）传送到 CPU。 D. 总线控制器21. 传输一幅分辨率为 640X480，6.5 万色的照片（图像） ，假设采用数据传输速度为 56kb/s，大约需要的22. 当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断的是（ III. 虚拟存储器失效 D. I、III 和 V IV. 浮点运算下溢 A. I、III 和 IV 的优势。 A. 使系统更高效 C. 使系统更安全 B. 想添加新任务时，不必修改内核 D. 使系统更可靠 V. 浮点运算上溢 B. I 和 V C. I、II 和 III） 。23. 相对采用单一内核结构，采用微内核结构设计和实现操作系统有诸多好处，但是（）不是微内核-2-予人玫瑰手留余香 ） 。24. 支持多道程序设计的操作系统在运行过程中，会不断选择新进程来运行，共享 CPU 资源，但是下面 哪个不是操作系统选择新进程的直接原因， （ A. 运行进程的时间片用完 C. 运行进程等待某个事件的发生 B. 运行进程出错 D. 有新的进程被创建进入就绪队列 ） 。25. 设有 3 个作业，它们的到达时间和运行时间如下表所示，并在一台处理机上按单道方式运行。如按高 响应比优先算法，则作业执行的次序和平均周转时间依次为（ 作业提交时间和运行时间表 作业号 1 2 3 A. J1,J2,J3、1.73 C. J1,J3,J2、2.08int counter=6; P1: counter=counter+1; P2: counter=counter-2;提交时间 8:00 8:30 9:30 B. J1,J3,J2、1.83 D. J1,J2,J3、1.83运行时间（小时） 2 1 0.2526. 设有两个进程 P1 和 P2，counter 为共享变量，描述如下：两个进程并发执行，运行完成后，counter 的值不可能为（ A. 4 B. 5 C. 6 D. 7 ） 。） 。27. 设 m 为同类资源数，n 为系统中并发进程数。当 n 个进程共享 m 个互斥资源时，每个进程的最大需求 是 w，则下列情况会出现系统死锁的是（ A. m=2,n=1,w=2 C. m=4,n=3,w=2 B. m=2,n=2,w=1 D. m=4,n=2,w=328. 有一请求分页式存储管理系统，页面大小为每页 100 字节，有一个 50× 50 的整型数组按行为主序连续 存放，每个整数占两个字节，将数组初始化为 0 的程序描述如下：int A[50][50]; for(int i=0;i&50;i++) for(int j=0;j&50;j++) A[i][j]=0;若在程序执行时内存只有一个存储块用来存放数组信息，则该程序执行时产生（ A. 1 B. 50 C. 100 D. 2500 ） 。）次缺页中断。29. 若存储单元长度为 n，存放在该存储单元的程序长度为 m，则剩下长度为 n-m 的空间称为该单元的内 部碎片。下面存储分配方法中，哪种存在内部碎片（ I. 固定式分区 II. 动态分区 IV. 段式管理 A. I 和 II B. I、III 和 V III. 页式管理 VI.请求段式管理 D. III 和 V ） 。 C. IV、V 和 VI V. 段页式管理30. 下列关于文件系统的说法中，正确的是（A. 文件系统负责文件存储空间的管理但不能实现文件名到物理地址的转换 B. 在多级目录结构中对文件的访问是通过路径名和用户目录名进行的 C. 文件可以被划分成大小相等的若干物理块且物理块大小也可任意指定 D. 逻辑记录是对文件进行存取操作的基本单位-3-予人玫瑰手留余香 ） 。 ） 。 ） 。31. 某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为 1024B，每个盘块索引号占用 4 字节，请问在该文件系统中，最大的文件大小为（ A. 16GB A. 并行技术 B. 32GB C. 8GB D. 以上均不对 C. 缓冲技术 D. 虚存技术32. CPU 输出数据的速度远高于打印机的打印速度，为解决这一矛盾，可采用的技术是（ B. 通道技术33. 传输层的作用是向源主机和目的主机之间提供D端对端‖的逻辑通信，其中D端对端‖的含义是（ A. 源主机网卡到目的主机网卡之间 B. 操作源主机的用户和操作目的主机的用户之间 C. 源主机和目的主机的进程之间 D. 源主机所在网络和目的主机所在网络之间34. 在一种网络中，超过一定长度，传输介质中的数据就会衰减。如果需要比较长的传输距离，就需要安 装（ ）设备。 B. 中继器 ） 。 C.6 D. 7 C. 路由器 D. 网桥 A. 放大器 少需要的位数是（ A. 4 是（ ） 。 B. 535. 数据链路层采用后退 N 帧协议，如果发送窗口的大小是 16，那么为了保证协议不会出错，序列号至36. CSMA 协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的 I. 非坚持型监听算法有利于减少网络空闲时间 II. 1-坚持型监听算法有利于减少冲突的概率 III. P 坚持型监听算法无法减少网络的空闲时间 IV. 1-坚持型监听算法能够及时抢占信道 A. I、II 和 III A. 129.23.191.21 B. II 和 III C. I、II 和 IV D. II 和 IV ） 。 D. 129.23.148.127 ）的 ICMP 报文。 37. 若子网掩码是 255.255.192.0， 那么下列主机必须通过路由器才能与主机 129.23.144.16 通信的是 （ B. 129.23.127.222 C. 129.23.130.33 B. 继续转发，改变路由 D.本地提交，终点不可达 ） 。 38. 路由器中发现 TTL 值为 0 的分组，将进行（ A. 返回发送方，源点抑制 C. 丢弃，时间超过 ）处理，并向源主机返回（39. 设 TCP 的拥塞窗口的慢启动门限初始值为 8（单位为报文段） ，当拥塞窗口上升到 12 时，网络发生超 时，TCP 开始慢启动和拥塞避免，那么第 12 次传输时拥塞窗口大小为（ A. 5 I. II. B. 6 C. 7 ） 。 D. 8 40. 下列关于客户/服务器模型的描述中，错误的是（客户端和服务器必须都事先知道对方的地址，以提供请求和服务 HTTP 基于客户/服务器模型，客户端和服务器端的默认端口号都是 80III. 浏览器显示的内容来自服务器 IV. 客户端是请求方，即使连接建立后，服务器也不能主动发送数据 A. I 和 IV B. II 和 IV C. I、II 和 IV D. 只有 IV二、综合应用题：第 41～47 小题，共 70 分。41. （10 分） 设有五个数据 do， for， if， repeat， while， 它们排在一个有序表中， 其查找概率分别为 p1=0.2， p2=0.15， p3=0.1， p4=0.03， p5=0.01。 而查找它们之间不存在数据的概率分别为 q0=0.2， q1=0.15， q2=0.1， q3=0.03，q4=0.02，q5=0.01。 do for if repeat while q0 p1 q1 p2 q2 p3 q3 p4 q4 p5 （1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。 功的平均查找长度。 q5（2）分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成-4-予人玫瑰手留余香（3）判定是顺序查找好？还是折半查找好？ 42. （13 分）设一个长度为 n(n&1)的单链表 L，从第一个结点开始计数，当计数到 m(m&1)时，将这第 m 个结点从单链表上摘除，然后从被摘除的下一个结点开始重新计数；当计数到表尾时，接着表的第一 个结点继续计数。试设计一个在时间和空间两方面都尽可能高效的算法，完成上述过程，要求： （1） 给出算法的基本设计思想。 （2） 根据设计思想，采用 C 或 C++或 Java 语言描述算法，关键之处给出注释。 （3） 说明你所设计算法的时间复杂度和空间复杂度。 43. （11 分）已知两个实数 x=-68，y=-8.25，它们在 C 语言中定义为 float 型变量，分别存放在寄存器 A 和 B 中。另外，还有两个寄存器 C 和 D。A、B、C、D 都是 32 位的寄存器。请问下列问题（要求用 十六进制表示二进制序列） ： （1）寄存器 A 和 B 中的内容分别是什么？ （2）x 和 y 相加后的结果存放在 C 寄存器中，寄存器 C 中的内容是什么？ （3）x 和 y 相减后的结果存放在 D 寄存器中，寄存器 D 中的内容是什么？ 44. （12 分）某 16 位机器所使用的指令格式和寻址方式如下所示，该机有四个 20 位基址寄存器，十六个 16 位通用寄存器（可用做变址寄存器） 。指令汇编格式中的 S（源） ，D（目标）都是通用寄存器，M 是主存的一个单元。三种指令的操作码分别是 MOV(OP)=(A)H，STA(OP)=(1B)H，LDA(OP)=(3C)H。 MOV 是传送指令，STA 为写数指令，LDA 为读数指令。（1） 分析三种指令的指令格式和寻址方式特点。 （2） 处理机完成哪一种操作所花时间最短？哪一种最长？第二种指令的执行时间有时会等于第三种 指令的执行时间吗？ （3） 下列情况中，每个十六进制指令字分别代表什么操作？若有指令编码不正确，如何改正才能成 为合法指令？ ① (F0F1)H (3CD2)H ② (2856)H ③ (6DC6)H ④ (1C2)H 45. （7 分）有三个进程 PA、PB 和 PC 合作解决文件打印问题：PA 将文件记录从磁盘读入主存的缓冲区 1，每执行一次读一个记录；PB 将缓冲区 1 的内容复制到缓冲区 2，每执行一次复制一个记录；PC 将 缓冲区 2 的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录的大小。请用 P、 V 操作来保证文件的正确打印。 46. （8 分）某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如 下所示，所有的数字均为十进制，每一项的起始编号是 0，并且所有的地址均按字节编址，每页的大 小为 1024 字节。 逻辑页号 0 1 2 3 4 5 存在位 1 1 0 1 0 1 引用位 1 1 0 0 0 0 修改位 0 1 0 0 0 1 页框号 4 3 -1 -5（1）将下列逻辑地址转换为物理地址，写出计算过程，对不能计算的说明为什么？-5-予人玫瑰手留余香，， （2）假设程序欲访问第 2 页，页面置换算法为改进的 CLOCK 算法，请问该淘汰哪页？页表如何修 改？上述地址的转换结果是否改变？变成多少？ 47. （9 分）TCP 的拥塞窗口 cwnd 大小与传输轮次 n 的关系如下所示： cwnd n cwnd n 1 1 40 14 2 2 41 15 4 3 42 16 8 4 21 17 16 5 22 18 32 6 23 19 33 7 24 20 34 8 25 21 35 9 26 22 36 10 1 23 37 11 2 24 38 12 4 25 39 13 8 26（1）画出 TCP 的拥塞窗口与传输轮次的关系曲线。 （2）分别指明 TCP 工作在慢开始阶段和拥塞避免阶段的时间间隔。 （3）在第 16 轮次和第 22 轮次之后发送方是通过收到三个重复的确认还是通过超时检测到丢失了报 文段？ （4）在第 1 轮次，第 18 轮次和第 24 轮次发送时，门限 ssthresh 分别被设置为多大？ （5）在第几轮次发送出第 70 个报文段？ （6）假定在第 26 轮次之后收到了三个重复的确认， 因而检测出了报文段的丢失， 那么拥塞窗口 cwnd 和门限 ssthresh 应设置为多大？-6-予人玫瑰手留余香第1套 答案与解析一、 单项选择题 1 C 11 C 21 D 31 A 1. 2 B 12 A 22 D 32 C 3 C 13 D 23 A 33 C 4 B 14 A 24 D 34 B 5 D 15 D 25 B 35 B 6 B 16 D 26 C 36 A 7 B 17 B 27 D 37 B 8 D 18 A 28 B 38 C 9 D 19 C 29 B 39 B 10 A 20 A 30 D 40 C【分析】 【单科书2P53】本题考查出栈序列的合法性。这类题通常采用手动模拟法。 【解答】A 选项：6 入,5 入,5 出,4 入,4 出,3 入,3 出,6 出,2 入,1 入,1 出,2 出；B 选项：6 入,5 入,4 入,4出,5 出,3 入,3 出,2 入,1 入,1 出,2 出,6 出； D 选项： 6 入,5 入,4 入,3 入,2 入,2 出,3 出,4 出,1 入,1 出,5 出,6 出； C 选项：无对应的合法出栈顺序。 【另解】对于已入栈且尚未出栈的序列，要保证先入栈的一定不能在后入栈的前面出栈，C 选项中的 6 在 5 前入栈，5 没有出栈，6 却出栈了，所以不合法，其他都符合规律。 2. 【分析】 【单科书 P64】本题考查栈在表达式求值中的应用。栈通常可以解决括号匹配、表示式求值、 【解答】利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，但其原理不变。选项 B 中 A 入栈，B 入栈，计算得 R1，C 入栈，计算得 R2，D 入栈，计算得 R3，由此得栈深为 2。A、C、D 依次计 算得栈深为 4、3、3。 3. 【分析】【单科书 P90】本题考查树的度与结点数的关系。将二叉树的相关性质推广到树。 【解答】设 B 为分支数， N 为结点总数，则 B=N-1 ， N=n0+n1+n2+n3 ，已知 n3+n2+n1=2+1+2=5 ， B=3× 2+2× 1+1× 2=10，所以 n0=11-5=6。 【另解】画草图。画出一个满足题设条件的特定树，然后计算其中叶结点的数量。 4. 【分析】 【单科书 P96】本题考查由遍历序列确定二叉树。二叉树的先序、中序和后序遍历，访问左、 右子树的顺序不变的。层序遍历先访问第 1 层的结点（树根），然后从左到右依次访问第 2 层上的结点， 依次类推，自上而下、自左向右逐层访问各层上的结点。 【解答】 由层序序列可得： F 是树根结点， 结合中序序列 DBA 构成 F 的左子树， CE 构成 F 的右子树， D、E 是第 2 层结点；进一步有 C 是 E 的左孩子、E 无右孩子；这样 A 是第 4 层结点，据 DBA 序列有 B 是 D 的右孩子，A 是 B 的右孩子。易知后序序列为 ABDCEF。 【提示】本类题型建议画出草图求快速解。根据左、右子树的遍历顺序不变，递归地根据根结点划分 出左、右子树，直到得到序列的整个树形结构。然后再根据图形代入验证。 5. 【分析】 【单科书 P109】 本题考查二叉排序树的性质。 二叉排序树的定义及性质、 二叉排序树的建立、 【解答】 二叉排序树的中序序列才是从小到大有序的， I 错误。 左子树上所有的值均小于根结点的值； 右子树上所有的值均大于根结点的值，而不仅仅是与左、右孩子的值进行比较，II 错误。新插入的关键字 总是作为叶结点来插入，但叶结点不一定总是处于最底层，III 错误。当删除的是非叶结点时，根据 III 的 解释，显然重新得到的二叉排序树和原来的不同；只有当删除的是叶结点时，才能得到和原来一样的二叉 排序树，IV 错误。 6. 【分析】 【单科书 P113】本题考查平衡二叉树的旋转。平衡二叉树的插入过程前半程和二叉排序树相 二叉排序树的删除、二叉排序树的查找效率分析等都是考查的重点。二叉排序树是递归定义的。 迷宫问题、递归等应用。2单科书指对应科目的王道考研系列单科复习指导书-7-予人玫瑰手留余香同，但新插入结点可能会导致不平衡，因此需要进行旋转调整。 【解答】由于在结点 A 的右孩子（R）的右子树（R）上插入新结点 F，A 的平衡因子由-1 减至-2，导 致以 A 为根的子树失去平衡，需要进行 RR 旋转（左单旋） 。A B E-1A0-2C-10CB ECA-10D-1DD FBEFRR 旋转的过程如上图所示，将 A 的右孩子 C 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转 成为 C 的左子树的根结点，而 C 的原来的左子树 E 则作为 A 的右子树。 【注意】平衡旋转的操作都是在插入操作后，引起不平衡的最小不平衡子树上进行的，只要将这个最 小不平衡子树调整平衡，则其上级结点也将恢复平衡。 7. 【分析】 【单科书 P150】本题考查无向完全图的性质。n 个结点的无向完全图共有 n(n-1)/2 条边。对 于 n+1 个结点和 n(n-1)/2 边构成的非连通图，仅当 n 个顶点构成完全图、第 n+1 个顶点构成一个孤立顶点 的图；若再增加一条边，则在任何情况下都是连通的。 【解答】 n 个顶点构成的无向图中， 边数≤n(n-1)/2， 将 e=36 代入， 有 n≥9， 现已知无向图是非连通的， 则 n 至少为 10。 8. 【分析】 【单科书 P171】本题考查拓扑排序。拓扑排序的方法：1）从 AOV 网中选择一个没有前驱的 顶点（入度为 0） ，并输出它；2）从 AOV 网中删去该顶点，以及从该顶点发出的全部有向边；3）重复上 述两步，直到剩余的网中不再存在没有前驱的顶点为止。 【解答】选项 D 中，删去 a、b 及其对应的出边后，c 的入度不为 0，此有边&d,c&，故不是拓扑序列。 选项 A、B、D 均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。 9. 【分析】 【单科书 P197】本题考查折半查找的查找过程。此类题应结合元素下标求解。 【解答】有序表长 12，依据折半查找的思想，第一次查找第 ?(1+12)/2?=6 个元素，即 65；第二次查 找第 ?[(6+1)+12]/2?=9 个元素，即 81 ；第三次查找第 ?[7+(9-1)]/2?=7 个元素，即 70 ；第四次查找第 ?[(7+1)+8]/2?=8 个元素，即 75。比较的元素依次为 65,81,70,75。 10. 【分析】 【单科书 P237】本题考查堆排序的排序过程。堆排序的过程首先是构造初始堆，然后将堆顶 元素（最大值或最小值）与最后一个元素交换，此时堆的性质会被破坏，需要从根结点开始进行向下调整 操作。如此反复，直到堆只有一个元素为止。 【解答】经过观察发现，每趟排序都是从未排序序列中选择一个最大元素放到其最终位置，符合大顶 堆的性质，初始序列本身就是一个大顶堆，将每趟数据代入验证正确。冒泡排序虽然也可以形成全局有序 序列，但是题中的排序过程显然不满足冒泡排序的过程。 【注意】堆存储在一个连续的数组单元中，它是一棵完全二叉树。 11. 【分析】 【2012 补充文件】本题考查多路平衡归并。 【解答】m 路平衡归并就是将 m 个有序表组合成一个新的有序表。每经过一趟归并后，剩下的记录数 是原来的 1/m，则经过 3 趟归并后 29/m3 =1，4 为最小满足条件的数。 【注意】本题中 4 和 5 均能满足，但 6 不满足，若 m=6，则只需 2 趟归并便可排好序。因此，还需要 满足 m2&29，也即只有 4 和 5 才能满足。 【另解】此类题，建议大家画出 ABC 选项对应的满树的草图，然后计算结点数是否能达到或超过 29 个，如果 C 能到达，则 D 就不必画了，否则就必然选 D 了。 12. 【分析】 【单科书 P10】本题考查计算机的性能指标。微处理器的位数是指该 CPU 一次能够处理的数 据长度，称为机器字长。通常机器字长等于通用寄存器的长度。 【解答】64 位操作系统（通常向下兼容）需要 64 位 CPU 的支持，64 位操作系统不仅是寻址范围增 加到 264，同时要求机器字长 64 位。 13. 【分析】 【单科书 P31】本题考查小数的补码表示法。真值 0 的补码表示是唯一的，补码比原码多表示 -1。负数[x]补和[x]原的转换规则：符号位不变，数值部分取反，末位加 1。-8-予人玫瑰手留余香【解答】[-1/2]补为 1.1000，采用补码表示时，如果符号位相同，则数值位越大，码值越大。所以要使 x&-1/2 成立，x1 必须为 0，而 x2~x4 任意。 【另解】因为 [-1]补为 1.0000，直接排除 A、B、C，只可能选 D。解答此类题时，应有意识到联想到 几个特殊值的表示，以迅速得出答案，或检验答案的正确性。 14. 【分析】 【单科书 P33】本题考查无符号数的逻辑移位运算。无符号数的移位方式为逻辑移位，不管是 左移还是右移，都是添 0。 【解答】 A1B6H 作为无符号数， 使用逻辑右移。 11 0110 右移一位得 01 1011， 即 50DBH。 15. 【分析】 【单科书 P96】本题考查 Cache 与主存的映射原理。主存-Cache 地址映射表（标记阵列）中 内容：映射的 Cache 地址（直接映射不需要因为 Cache 地址唯一，组相联只需要组号） 、主存标记（命中 判断） 、有效位。如下图所示：【解答】由于 Cache 被分为 64 个块，那么 Cache 有 64 行，采用直接映射，一行相当于一组。故而该 标记阵列每行存储 1 个标记项，其中主存标记项为 12bit（212=4096，是 Cache 容量的 4096 倍，那么就是 地址长度比 Cache 长 12 位） ，加上 1 位有效位，故而为 64× 13bit。 16. 【分析】 【单科书 P93 等】本题考查 Cache 和虚拟存储器的特性。Cache 和虚拟存储器和原理都是基于 程序访问的局部性原理，但他们实现的方法和作用均不太相同。 【解答】Cache失效与虚拟存储器失效的处理方法不同，Cache完全由硬件实现，不涉及到软件端；虚 拟存储器由硬件和OS共同完成，缺页时才会发出缺页中断，故I错误、II正确、III错误。在虚拟存储器中， 主存的内容只是辅存的一部分内容，IV错误。 17. 【分析】 【单科书 P124】 本题考查指令的地址码字段。 对于二地址指令， 若两个操作数都在寄存器中， 称为 RR 型指令；若一个操作数在寄存器中另一个操作数在存储器中，称为 RS 型指令；若两个操作数都 在存储器中，则称为 SS 型指令。 【解答】缓冲存储器（如 Cache） ，用来存放最近使用的数据，其内容和调度是由硬件或操作系统完成 的，因此不能作为指令的地址码。控制存储器采用 ROM 结构，存放的是微程序，它对软件开发人员是透 明的，显然不能作为指令的地址码。CPU 不能直接访问外存，如果所需的数据存放在外存，则需要先调入 主存，而指令中只能使用主存地址。 18. 【分析】 【单科书 P153】本题考查指令的执行特点。不论是中断返回指令、还是无条件转移指令等， 指令总是根据程序计数器 PC 中的内容来执行下一条指令。 【解答】考生可能会想到无条件转移指令，认为不一定总是根据 PC 读出。实际上，当前指令正在执 行时，其实 PC 已经是下一条指令的地址了。若遇到无条件转移指令，只需简单地将跳转地址覆盖原 PC 的内容即可，最终的结果还是指令需要根据 PC 从主存读出。 19. 【分析】 【单科书 P178】本题考查流水线的数据相关。数据相关包括 RAW(写后读)、WAW(写后写)、 WAR(读后写)。设有 i 和 j 两条指令，i 指令在前，j 指令在后，则三种相关的含义： ●RAW（写后读） ：指令 j 试图在指令 i 写入寄存器前旧读出该寄存器的内容，这样指令 j 就会错误地 读出该寄存器旧的内容。 ●WAR（读后写） ：指令 j 试图在指令 i 读出该寄存器前就写入该寄存器，这样指令 i 就会错误地读出-9-予人玫瑰手留余香该寄存器的新内容。 ●WAW （写后写） ： 指令 j 试图在指令 i 写入寄存器前就写入该寄存器， 这样两次写的先后次序被颠倒， 就会错误地使由指令 i 写入的值称为该寄存器的内容。 【解答】在这两条指令中，都对 R1 进行操作，其中前面对 R1 写操作，后面对 R1 读操作，因此发生 写后读相关。 20. 【分析】 【单科书 P153】 本题考查间址周期的数据流。 系统总线按传送内容的不同可分为： 地址总线、 数据总线和控制总线。地址总线由单向多根信号线组成，可用于 CPU 向主存、外设传送地址信息；数据 总线由双向的多根信号线组成，CPU 可以沿着这些线从主存或外设读入数据，也可发送数据；控制总线上 传输控制信息，包括控制命令和反馈信号等。 【解答】间址寻址第一次访问内存所得到的信息是操作数的有效地址，该地址通过数据线传送至 CPU 而不是地址线。地址线是单向总线，只能由 CPU 向主存和外设传送。 21. 【分析】 【单科书 P219】本题考查图像存储空间的计算。首先计算出每幅图的存储空间，然后除以数 据传输率， 就可以得出传输一幅图的时间。 图片的容量不仅与分辨率有关， 还与颜色数有关， 分辨率越高、 颜色数越多，图像所占的容量就越大。 【解答】图像的颜色数为 65 536 色，意味着颜色深度为 log（即用 16 位的二进制数表示 65 536 种颜色） ，则一幅图所占据的存储空间为 640X480X16=4915200b。数据传输速度为 56kb/s，则传输时 间=4915200b/(56X103b/s)=87.77s。 22. 【分析】 【单科书 P227】本题考查中断请求。中断请求是指中断源向 CPU 发送中断请求信号，分为外 中断和内中断。外中断指来自处理器和内存外部的中断，如 I/O 设备发出的、外部事件等；内中断指在处 理器和内存内部产生的中断。 【解答】外部事件如按&Esc&键以退出运行的程序等，属于外中断，I 正确。Cache 完全是由硬件实现 的，不会涉及到中断层面，II 错误。虚拟存储器失效如缺页等，会发出缺页中断，属于内中断，III 正确。 浮点运算下溢，直接当做机器零处理，而不会引发中断，IV 错误。浮点数上溢，表示超过了浮点数的表示 范围，属于内中断，V 正确。 23. 【分析】 【补充文档】本题考查微内核结构的特点。微内核结构将内核中最基本的功能（如进程管理、 虚存管理等）保留在内核，而将那些不需要在核心态执行的部分移到用户态执行。 【解答】微内核结构需要频繁地在管态和目态之间进行切换，操作系统的执行开销相对偏大；而且在 微内核结构中，那些移出内核的操作系统代码根据分层的原则被划分成若干服务程序，它们的执行相互独 立，交互则都借助于微内核进行通信，影响了系统的效率，因此 A 不是优势。由微内核的定义和特点，不 难得出 B、C 和 D 均是微内核结构的优势。 24. 【分析】 【单科书 P35】本题考查进程调度的时机。读者应掌握不能进行进程调度与切换的情况（处理 中断的过程、访问临界区、原子操作） ；及应该进行进程调度与切换的情况。 【解答】运行着的进程由于时间片用完、或者运行结束、或者需要等待事件的发生（例如等待键盘响 应） 、或者出错、或者自我阻塞等均可以激活调度程序进行重新调度，选择一个新的就绪进程投入运行。 新进程加入到就绪队列不是引起调度的直接原因，当 CPU 正在运行其它进程时，该进程仍需等待。即使 在采用高优先级优先调度算法的系统中， 一个最高优先级的进程进入就绪队列， 仍需要考虑是否允许抢占， 当不允许抢占时仍需等待。 25. 【分析】 【单科书 P39】本题考查高响应比优先调度和平均周转时间。高响应比优先调度算法综合考虑 了进程的等待时间和执行时间，响应比=(等待时间+执行时间)/执行时间。 【解答】J1 第一个提交，也第一个执行，J1 在 10:00 执行完毕，这时 J2、J3 都已到达。J2 的响应比= (1.5+1)/1 =2.5，J3 的响应比= (0.5+0.25)/0.25 =3，故第二个执行 J3；第三个执行 J2。平均周转时间=(J1 的 周转时间+J2 的周转时间+J3 的周转时间)/3=[2+(1.75+1)+(0.5+0.25)]/3=5.5/3=1.83 。 26. 【分析】 【单科书 P22】本题考查程序的并发执行。在并发环境下，程序的执行是间断的，由于失去了 封闭性，也将导致失去了结果的可再现性。 【解答】本题需要考虑赋值表达式左值和右值（或理解为分解成 2 条指令） ，如下： 计算右值 1. counter+1 3. counter-2-10-予人玫瑰手留余香 4. counter=左值赋值 2. counter=初始时 counter 为 6，考虑到进程并发执行的特点，当执行顺序为 1,2,3,4 或 3,4,1,2 时，counter 的结果 为 5。当执行顺序为 1,3,2,4 或 3,1,2,4 时，counter 的结果为 4。当执行顺序为 1,3,4,2 或 3,1,4,2 时，counter 的结果为 7。故而无法得到 6。 27. 【分析】 【单科书 P75】本题考查死锁的检测。 【解答】A 不会发生死锁，只有一个进程怎么也不会发生死锁。B 不会发生死锁，两个进程各需要一 个资源，而系统中刚好有 2 个资源。C 不会发生死锁，3 个进程需要的最多资源数都是 2，系统总资源数是 4，所以总会有一个进程得到 2 个资源，运行完毕后释放资源。D 可能会发生死锁，当 2 个进程各自都占 有了 2 个资源后，系统再无可分配资源。由此可得出结论：当满足 m&=n(w-1)+1 时，不会产生死锁。 28. 【分析】 【单科书 P149】本题考查缺页中断的计算。对于整个程序，都会遇到每个页面的第一个整数 不在内存中，其他欲访问的整数都在内存的页面中。 【解答】一个页面可以容纳 100/2=50 个整数，50× 50 整型数组以行序为主序存储，则每行（刚好 50 个整数）占用一个页面，共需要 50 个页面。在数组中刚好每行占用一个内存页面，代码是按行访问的， 故每访问一行的第一个整数时产生一次缺页中断。 【提示】本题若将语句DA[i][j]=0‖改为DA[j][i]=0‖，则应该如何计算？ 29. 【分析】 【单科书 P129 等】本题考查各存储分配方法的特点。当程序小于固定分区大小时，也占用了 一个完整的内存分区空间，导致分区内部有空间浪费，这种现象称内部碎片。 【解答】固定分区存在内部碎片。凡涉及到页的存储分配管理，每个页的长度都一样（对应固定） ， 所以会产生内部碎片，虽然页的碎片比较小，每个进程平均产生半个块大小的内部碎片。段式管理中每个 段的长度都不一样（对应不固定） ，所以只会产生外部碎片。 30. 【分析】 【单科书 P188 等】本题考查文件系统的多个知识点。 【解答】文件系统使用文件名进行管理，也实现了文件名到物理地址的转换，A 错误。多级目录结构 中，对文件的访问通过路径名和文件名进行，B 错误。文件被划分的物理块的大小是固定的，通常和内存 管理中的页面大小一致，C 错误。 逻辑记录是文件中按信息在逻辑上的独立含义来划分的信息单位，它是 对文件进行存取操作的基本单位，D 正确。 31. 【分析】 【单科书 P205】本题考查多级索引下文件的存放方式。本题是一个简化的多级索引题，根据 题意，它采用的是三级索引，那么索引表就应该具有三重。 【解答】 依题意， 每个盘块为 1024B， 每个索引号占 4 字节， 因此每个索引块可以存放 256 条索引号， 三级索引共可以管理文件的大小为 256×256×256×1024B≈16GB。 32. 【分析】 【单科书 P243 等】本题考查各种输入/输出技术。并行技术主要是为了提高整机的运行效率 和吞吐率；通道技术是为了减少 CPU 对 I/O 操作的控制，提高 CPU 的效率；缓冲技术是为了解决 CPU 和 外设的速度不匹配；虚存技术是为了解决存储系统的容量问题。 【解答】缓冲技术的引入主要解决 CPU 速度和外设速度不匹配的问题，它同时减少了通道数量上的 占用，提高了 CPU、I/O 和通道的并发性，减少了中断的次数，放宽了 CPU 对中断响应的时间要求，例如 打印、文件访问、网络收发等场合，均要用到缓冲技术。 33. 【分析】 【单科书 P14】本题考查传输层的功能。在 OSI/RM 中，数据链路层提供结点到结点的通信； 网络层提供主机到主机的通信；传输层提供端到端（进程到进程）的通信。 【解答】传输层的作用是提供源主机到目的主机进程之间的逻辑通信，称为 D端到端‖。这里的D端‖是 指用户程序的端口，端口号标识了不同的进程（分用） 。 34. 【分析】 【单科书 P42】本题考查物理层设备。电磁信号在网络传输媒体中进行传递时会衰减而使信号 变得越来越弱， 还会由于电磁噪声和干扰使信号发生畸变， 因此需要在一定的传输媒体距离中使用中继器， 来对传输的数据信号整形放大后再传递。 【解答】放大器常用于远距离模拟信号的传输，它同时也会使噪声放大，引起失真。网桥用来连接两 个网段以扩展物理网络的覆盖范围。路由器是网络层的互连设备，可以实现不同网络的互连。中继器的工 作原理是信号再生（不是简单的放大） ，从而延长网络的长度。 35. 【分析】 【单科书 P62】 本题考查后退 N 帧协议的原理。 数据链路层的停止-等待协议、 后退 N 帧协议、-11-予人玫瑰手留余香选择重传协议，以及 TCP 协议对发送窗口和接收窗口的要求，是理解协议工作原理精髓所在。 【解答】后退 N 帧协议的最大发送窗口为 2n-1（其中 n 为帧号的位数） ，题目中已经说明发送窗口的 大小为 16，也就是说如果要使得协议不出错，必须满足 16≤2n-1，所以 n 至少要等于 5。 36. 【分析】 【单科书 P69】本题考查 CSMA 协议的各种监听。CSMA 有三种类型：①非坚持 CSMA：一 个站点在发送数据帧之前，先对媒体进行检测。如果没有其它站点在发送数据，则该站点开始发送数据。 如果媒体被占用，则该站点不会持续监听媒体而等待一个随机的延迟时间后再监听。②1-坚持 CSMA：当 一个站点要发送数据帧时， 它就监听媒体， 判断当前时刻是否有其他站点正在传输数据。 如果媒体忙的话， 该站点等待直至媒体空闲。一旦该站点检测到媒体空闲，就立即发送数据帧，故 IV 正确。如果产生冲突， 则等待一个随机时间再监听。之所以叫D1-坚持‖，是因为当一个站点发现媒体空闲的时候，它传输数据帧 的概率是 1。③P-坚持 CSMA：当一个站点要发送数据帧时，它先检测媒体。若媒体空闲，则该站点以概 率 P 的可能性发送数据，而有 1-P 的概率会把发送数据帧的任务延迟到下一个时槽。P-坚持 CSMA 是非坚 持 CSMA 和 1-坚持 CSMA 的折中。 【解答】采用随机的监听延迟时间可以减少冲突的可能性但其缺点也是很明显的：即使有多个站点有 数据要发送，因为此时所有站点可能都在等待各自的随机延迟时间，而媒体仍然可能处于空闲状态，这样 就使得媒体的利用率较为低下，故 I 错误。1-坚持 CSMA 的优点是：只要媒体空闲，站点就立即发送；它 的缺点在于： 假如有两个或两个以上的站点有数据要发送， 冲突就不可避免， 故 II 错误。 按照 P-坚持 CSMA 的规则，若下一个时槽也是空闲的，则站点同样按照概率 P 的可能性发送数据，所以说如果处理得当 P 坚 持型监听算法还是可以减少网络的空闲时间的，故 III 错误。 37. 【分析】 【单科书 P116】本题考查子网划分与子网掩码。不同子网之间需通过路由器相连，子网内的 通信则无需经过路由器转发，因此比较各主机的子网号即可。 【解答】将子网掩码 255.255.192.0 与主机 129.23.144.16 进行 D 与 ‖ 操作，得到该主机网络地址为 129.23.128.0，再将该子网掩码分别与四个候选答案的地址进行D与‖操作，只有 129.23.127.222 的网络地址 不为 129.23.128.0。因此该主机与 129.23.144.16 不在一个子网中，需要通过路由器转发信息。 38. 【分析】 【单科书 P113、P120】本题考查 IP 报头字段的功能和 ICMP 报文。ICMP 报文作为 IP 分组的 数据字段，用它来使得主机或路由器可以报告差错和异常情况。 【解答】路由器对 TTL 值为零的数据分组进行丢弃处理，并向源主机返回时间超时的 ICMP 报文。 39. 【分析】 【单科书 P171】本题考查 TCP 的拥塞控制。此类题往往综合四种拥塞控制算法，解题时或画 出拥塞窗口变化曲线图，或列出拥塞窗口大小变化序列，尤其要注意在拐点处的变化情况。 【解答】在慢启动和拥塞避免算法中，拥塞窗口初始值为 1，窗口大小开始按指数增长。当拥塞窗口 大于慢启动门限后，停止使用慢启动算法，改用拥塞避免算法。此时，慢启动的门限值初始为 8，当拥塞 窗口增大到 8 时改用拥塞避免算法，窗口大小按线性增长，每次增长 1 个报文段。当增加到 12 时，出现 超时，重新设置门限值为 6（12 的一半） ，拥塞窗口再重新设为 1，执行慢启动算法，到门限值为 6 时执行 拥塞避免算法。按照上面的算法，拥塞窗口的变化为：1、2、4、8、9、10、11、12、1、2、4、6、7、8、 9.....，从该序列可以看出，第 12 次传输时拥塞窗口大小为 6。 【注意】很多考生误选 D 选项，原因是直接在以上的序列中从 4 增加到 8。拥塞窗口的大小是和门限 值有关的，在慢开始算法中不能直接变化为大于门限值，所以 4 只能最多增加到 6，之后再执行拥塞避免 算法。 40. 【分析】 【单科书 P185】本题考查客户/服务器模式的概念。客户端是服务请求方，服务器是服务提供 方，二者的交互由客户端发起。 【解答】客户端是连接的请求方，在连接未建立之前，服务器在端口 80 上监听。这时客户端必须要知 道服务器的地址才能发出请求，很明显服务器事先不需要知道客户端的地址。一旦连接建立后，服务器就 能主动发送数据给客户端（即浏览器显示的内容来自服务器） ，用于一些消息的通知（例如一些错误的通 知） 。在客户/服务器模型中，默认端口号通常都是指服务器端，而客户端的端口号通常都是动态分配。 二、 综合应用题：第 41～47 小题，共 70 分。 41. 【分析】本题考查顺序查找和折半查找的判定树、及对应的平均查找长度。本题的难点在于各个数据 的查找概率，以及查找失败的概率是不同的，在这种情况下折半查找的效率未必比顺序查找的效率好。本-12-予人玫瑰手留余香题应特别注意如何计算折半查找失败的比较次数。 【解答】 （1）采用顺序查找的判定树如下：do&(-∞,do)=& &for=& &if(do,for)=& &(for,if)repe at=& &whi le(if,repeat)=&(while, ∞)(repeat, while)题 41 图(1) 顺序查找判定树 采用折半查找的判定树如下：&do if&repe at&&=&=&whi le(-∞,do)= &(if,repeat)for&(for,if)&(repeat, while)=(do,for)=&(while, ∞)题 41 图(1) 折半查找判定树 （2）根据各数据查找所需的比较次数，以及查找概率可得到平均查找长度为： ASL 顺序成功 =（1p1+2p2+3p3+4p4+5p5)=0.97 ASL 折半成功 =（1p3+2(p1+p4)+3(p2+p5)=1.04 ASL 折半失败 =（2q0+3q1+3q2+2q3+3q4+3q5)=1.30 ASL 顺序失败 =（1q0+2q1+3q2+4q3+5q4+5q5)=1.07 （3）由上题的计算结果可知，本题采用顺序查找更好。 42. 【分析】本题考查单链表的应用。 【解答】 （1）从逻辑上可以把题中的单链表看成是一个循环单链表，因此在第一趟遍历时，可以将单 链表改造成循环单链表。算法的基本设计思想如下： ①设置一个计数变量 i，初始时工作指针 p 指向第一个结点，故初始置 i 为 1。 ②第一趟访问时，令尾结点的指针（初始为 NULL）指向头指针 L（注意：未改造前，单链表中仅有 尾结点的 next 域为 NULL，且改造后表中不存在 next 域为 NULL 的结点） 。 ③如果 i 等于 m：则摘下、输出并删除这个计数值等于 m 的结点，工作指针 p 指向被删除的下一 个结点，计数变量重新置为 1。 ④如果 i 不等于 m：继续访问单链表的下一个结点，计数值加 1。 重复过程③④，直到单链表中所有的结点均已删除，即 L 指针等于 NULL 为止。 （2）算法的实现如下：typedef struct LNode{ ElemT struct LNode * } *LinkL void Loop_Del(LinkList &L,int n,int m){ int i=1; LNode *pre,*p=L,*pD while(L){ if(i==m){ //计数，初始 p 指向第 1 个元素 //p 工作指针，pDel 指向待删除结点 //L 不空则循环 //计数到第 m 个结点 //链表结点的结构定义 //结点数据 //结点链接指针if(p-&next==NULL) p-&next=L;//第一趟，将尾结点指向 L-13-予人玫瑰手留余香pDel=p; pre-&next=p-& p=p-& Output(pDel-&data);free(pDel);//输出并销毁 i=1; } else{ pre=p; p=p-& i++; } //计数值加 1 //非第 m 个结点，则继续计数 //逐链访问 //重新开始计数 //摘下这个结点 //断链}//while(L) }（3）在单链表中共有 n 个结点，每删除一个结点需要遍历 m 次，故总的时间复杂度为 O(m*n)。若 m 为常量，则时间复杂度为 O(n)。算法的空间复杂度为 O(1) 【注意】解答中的单链表是不带头结点的，若采用带头结点的单链表，则算法要进行一定的改造，留 给读者思考。本题的思想若采用顺序存储结构，则应该如何设计算法？ 43. 【分析】本题考查浮点数的表示与运算。 【解答】 （1） float 型变量在计算机中都被表示成 IEEE754 单精度格式。 X=-68=-( =-1.0001× 26， 符号位为 1， 阶码为 127+6=128+5=(， 尾数为 1.0001， 所以小数部分为： 000 00 ， 合起来整个浮点数表示为： 1 0 00
， 写成十六进制为： C2880000H。 Y=-8.25=-(=-1.00001× 23，符号位为 1，阶码为 127+3=128+2=(，尾数为 1.00001， 所以小数部分为： 000 00
， 合起来整个浮点数表示为： 1 0 00
写成十六进制为 C1040000H。 因此，寄存器 A 和 B 的内容分别为 C2880000H、C1040000H。 （2）两个浮点数相加的步骤如下： ① 对阶：Ex=，Ey=，则： [Ex-Ey]补=[Ex]补+[-Ey]补=11。 Ex 大于 Ey，所以对 y 进行对阶。对阶后，y=-0.× 26。 ② 尾数相加： x 的尾数为-1.000 00 ， y 的尾数为-0.001 00 ， 用原码加法运算实现，两数符号相同，做加法，结果为-1.001 00
。 即 x 加 y 的结果为-1.001 1000 1× 26，所以符号位为 1，尾数为：001 00
，阶码 为 127+6=128+5，即：。合起来为：1 1 00
，转换为十六进制 形式为：C2988000H。 所以 C 寄存器中的内容是 C2988000H （3）两个浮点数相减的步骤同加法，对阶的结果也一样，只是尾数相减。 尾数相减：x 的尾数为-1.000 00 ，y 的尾数为-0.001 00
。 用原码减法运算实现，两数符号相同，做减法：符号位：取大数的符号，负数，所以为 1。数值部分： 大数加小数负数的补码： 1. + 000 11 00 00 00 00 1. 110 0. 111X 减 y 的结果为-0.× 26=-1.1101111× 25，所以： 符号位为 1，尾数为 110 00 ，阶码为 127+5=128+4，即 。 合起来为：1 0 00
，转换为十六进制形式为：C26F0000H。所以寄 存器 D 中的内容是 C26F0000H。-14-予人玫瑰手留余香【注意】 如果是对于选择题， 第 2 问可不采用这么严格的计算， 可以采用偷懒的方法， 先将十进制的 x+y， x-y 计算之后的结果再转成 IEEE754。对于大题，也可以采用这种方法验证结果的正确性。44. 【分析】本题考查指令的格式与编码。 【解答】 （1）第一种指令是单字长二地址指令，RR 型；第二种指令是双字长二地址指令，RS 型，其 中 S 采用基址寻址或变址寻址，R 由源寄存器决定；第三种也是双字长二地址指令，RS 型，其中 R 由目 标寄存器决定，S 由 20 位地址（直接寻址）决定。 （2）处理机完成第一种指令所花的时间最短，因为是 RR 型指令，不需要访问存储器。第二种指令 所花的时间最长，因为 RS 型指令，需要访问存储器，同时要进行寻址方式的变换运算（基址或变址） ，这 也要时间。第二种指令的执行时间不会等于第三种指令，因为第三种指令虽然也访问存储器，但节省了求 有效地址运算的时间开销。 （3）根据已知条件：MOV(OP)=001010，STA(OP)=011011，LDA(OP)=111100，将指令的十六进制格 式转换为二进制代码且比较后可知： 1 (F0F1)H (3CD2)H 指令代表 LDA 指令，编码正确，其含义是把主存(13CD2)H 地址单元的内容取至 15 ○ 号寄存器。 2 (2856)H 指令代表 MOV 指令，编码正确，含义是把 6 号源寄存器的内容传送至 5 号目标寄存器。 ○ 3 (6DC6)H 是单字长指令，一定是 MOV 指令，但编码错误，可改正为(29C6)H。 ○ 4 (1C2)H 是单字长指令，代表 MOV 指令，但编码错误，可改正为(29C2)H。 ○ 45. 【分析】本题考查用 PV 操作解决进程的同步互斥问题。 【解答】进程 PA 、 PB 、 PC 之间的关系为： PA 与 PB 共用一个单缓冲区， PB 又与 PC 共用一个单缓冲 区，其合作方式如下图所示。当缓冲区 1 为空时，进程 PA 可将一个记录读入其中；若缓冲区 1 中有数 据且缓冲区 2 为空，则进程 PB 可将记录从缓冲区 1 复制到缓冲区 2 中；若缓冲区 2 中有数据，则进程 PC 可以打印记录。在其他条件下，相应进程必须等待。事实上，这是一个生产者 - 消费者问题。题 45 图 进程间的合作方式 为遵循这一同步规则。应设置 4 个信号量 emptyl 、 empty2 、 full1 、 full2 ，信号量 emptyl 及 empty2 分别表示缓冲区 1 及缓冲区 2 是否为空，其初值为 1; 信号量 full1 及 full2 分别表示缓冲 区 1 及缓冲区 2 是否有记录可供处理，其初值为 0 。相应的进程描述如下：semaphore empty1=1; semaphore full1=0; semaphore empty2=1; semaphore full2=0; cobegin{ process PA(){ while(TRUE){ 从磁盘读入一条记录; P(empty1); 将记录存入缓冲区1; V(full1); } } process PB(){ while(TRUE){ P(full1); 从缓冲区1中取出一条记录; //缓冲区 1 是否为空 //缓冲区 1 是否有记录可供处理 //缓冲区 2 是否为空 //缓冲区 2 是否有记录可供处理-15-予人玫瑰手留余香V(empty1); P(empty2); 将取出的记录存入缓冲区2; V(full2); }} process PC(){ while(TRUE){ P(full2); 从缓冲区2中取出一条记录; V(empty2); 将取出的记录打印出来; } } } coend46. 【分析】 本题考查逻辑地址到物理地址的转换、 页面置换等。 地址转换过程一般是先将逻辑页号取出， 然后查找页表，得到页框号，将页框号与页内偏移量相加，即可获得物理地址，若取不到页框号，那么该 页不在内存，于是产生缺页中断，开始请求调页。若内存有足够的物理页面，那么可以再分配一个新的页 面，若没有页面了，就必须在现有的页面之中找到一个页，将新的页与之置换，这个页可以是系统中的任 意一页，也可以是本进程中的一页，若是系统中的一页，则这种置换方式称为全局置换，若是本进程的页 面，则称为局部置换。置换时为尽可能地减少缺页中断次数，可以有多种算法来应用，本题使用的是改进 的 CLOCK 算法，这种算法必须使用页表中的引用位和修改位，由这 2 位组成 4 种级别，没被引用和没修 改的页面最先淘汰，没引用但修改了的页面其次，再者淘汰引用了但是没修改的页面，最后淘汰既引用又 修改的页面，当页面的引用位和修改位相同时，随机淘汰一页。 【解答】 （1）根据题意，每页1024字节，地址又是按字节编址，计算逻辑地址的页号和页内偏移量， 合成物理地址如下表所示。 逻辑地址 99 32 逻辑页号 0 1 2 3 4 5 页内偏移量 793 173 51 248 92 212 页框号 4 3 -1 -5 物理地址
缺页中断 1272 缺页中断 5332（2）第2页不在内存，产生缺页中断，根据改进CLOCK算法，第3页为没被引用和没修改的页面，故 淘汰。新页面进入，页表修改如下： 逻辑页号 0 1 2 3 4 5 地址转换变为如下表： 逻辑地址 逻辑页号 页内偏移量 页框号 物理地址 存在位 1 1 0→1 1→0 0 1 引用位 1 1 0-&1 0 0 0 修改位 0 1 0 0 0 1 页框号 4 3 -- →1 1→--5 调入 淘汰因为页面2调入是为了使用，所以页面2的引用位必须改为1。-16-予人玫瑰手留余香 99 32 0 1 2 3 4 5 793 173 51 248 92 212 4 3 1 --5 75 缺页中断 缺页中断 533247. 【分析】本题考查 TCP 的拥塞控制算法。在画出拥塞窗口与传输轮次的曲线后，根据四种拥塞控制 算法的特点，以图像的拐点进行分段分析。初始时，拥塞窗口置为 1，即 cwnd=1，慢开始门限置为 32， 即 ssthresh=32。慢开始阶段，cwnd 初值为 1，以后发送方每收到一个确认 ACK，cwnd 值加 1，也即经过 每个传输轮次 （RTT） ， cwnd 呈指数规律增长。 当拥塞窗口 cwnd 增长到慢开始门限 ssthresh 时 （即当 cwnd=32 时） ，就改用拥塞避免算法，cwnd 按线性规律加性增长。当 cwnd=42 时，收到三个重复的确认，启用快恢 复算法，更新 ssthresh 值为 21（即变为超时时 cwnd 值 42 的一半） 。cwnd 重置 ssthresh 减半后的值，并执 行拥塞避免算法。当 cwnd=26 时，网络出现拥塞，改用慢开始算法，ssthresh 置为拥塞时窗口值得一半， 即 13，cwnd 置为 1。 【解答】 （1）拥塞窗口与传输轮次的关系曲线如图所示：（2）慢开始的时间间隔：[1, 6]和[23, 26]。拥塞避免的时间间隔：[6, 16]和[17, 22]。 （3）在第 16 轮次之后发送方通过收到三个重复的确认检测到丢失的报文段。在第 22 轮次之后发送 方是通过超时检测到丢失的报文段。 （4）在第 1 轮次发送时，门限 ssthresh 被设置为 32。 在第 18 轮次发送时，门限 ssthresh 被设置为发生拥塞时的一半，即 21。 在第 24 轮次发送时，门限 ssthresh 是第 22 轮次发生拥塞时的一半，即 13。 （5）第 70 报文段在第 7 轮次发送出。 （6）拥塞窗口 cwnd 和门限 ssthresh 应设置为 8 的一半，即 4。-17-予人玫瑰手留余香王道计算机统考模拟试题第2套一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选 项最符合试题要求。1. 用 I 表示进栈操作，用 O 表示出栈操作，若元素的进栈顺序是 1234，为了得到 1342 的出栈顺序，相 应的 I 和 O 的操作序列为（ A. IOIOIIOO 2. ）。 C. IOIIOOIO D. IOIIOIOO B. IIIOOIOO若循环队列以数组 Q[0..m-1]作为其存储结构， 变量 rear 表示循环队列中的队尾元素的实际位置， 其移 动按 rear=(rear+1) MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元 素的实际位置是（ A. rear-length C. (1+rear+m-length) MOD m ） 。 B. (rear-length+m) MOD m C. m-length ）。 B. 一棵二叉树的度可以小于 2 D. 二叉树就是度为 2 的有序树3.有关二叉树下列说法正确的是（ A. 二叉树的度为 2C. 二叉树中至少有一个结点的度为 2 4. 可能是（ A. 30,36 5. 6. A. 107 最多有（ A. 11 7. ）。 B. 38,48,28 B. 108 ）个顶点。 B. 12在含有 15 个结点的平衡二叉树上，查找关键字为 28（存在该结点）的结点，则依次比较的关键字有 C. 48,18,38,28 C. 214 D. 215 D. 60,30,50,40,38,36 ）个不同的码字。一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G C. 15 ） 。 D. 16下列关于 AOE 网的叙述中，正确的是（A. 关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短 B. 关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少 C. 关键路径上任一关键活动改变后，都必然会影响关键路径的改变 D. 若所有的关键路径一同延长或缩短，则不会引起关键路径的改变 8. 下列关于 m 阶 B-树的说法中，正确的有（ I. 每个结点至少有两棵非空子树 ） 。II. 非叶结点仅其索引作用，每次查找一定会查找到某个叶结点 III.所有叶子在同一层上 IV.当插入一个数据项引起 B 树结点分裂后，树长高一层 A. I、II 9. B. II、III C. III、IV D. III ） 。 D. 平衡二叉树 D.插入排序 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（ A. 二叉排序树 A. 快速排序 B. 大顶堆 B. 冒泡排序 C. 小顶堆 ）排序的两趟排序后的结果。 C.选择排序10. 数据序列（2,1,4,9,8,10,6,20）只能是（11. 设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种 要求的排序方法是（ ） 。 A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序 B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序 C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序 D. 先按 k2 进行简单选择排序，再按 k1 进行直接插入排序-18-予人玫瑰 A. 总线手留余香 ） D. 运算器 B. 控制器 C. 控制存储器 ） 。12. 冯? 诺伊曼机可以区分指令和数据的部件是（ 13. 下列关于浮点数的说法中，正确的是（I. 最简单的浮点数舍入处理方法是恒置D1‖法 II. IEEE754 标准的浮点数进行乘法运算的结果肯定不需要做D左规‖处理 III. 浮点数加减运算的步骤中，对阶的处理原则是小阶向大阶对齐 IV. 当补码表示的尾数的最高位与尾数的符号位（数符）相同时表示规格化 V. 在浮点运算过程中如果尾数发生溢出，则应进入相应的中断处理 A. II、III 和 V I. B. II 和 III C. I、II 和 III ） 。 D. II、III、IV 和 V 14. 下列关于 ROM 和 RAM 的说法中，错误的是（ CD-ROM是ROM的一种，因此只能写入一次II. Flash快闪存储器属于随机存取存储器，具有随机存取的功能 III. RAM的读出方式是破坏性读出，因此读后需要再生 IV. SRAM读后不需要刷新，而DRAM读后需要刷新 A. I和II B. I、III和IV C. II和III D. I、II和III 15. 设有一主存-Cache 层次的存储器，其主存容量 1MB，Cache 容量 16KB，每字块有 8 个字，每字 32 位，采用直接地址映像方式，若主存地址为 35301H，且 CPU 访问 Cache 命中，则该主存块在 Cache 的第（ A. 152 I. ）字块中（Cache 起始字块为第 0 字块） 。 B. 153 C. 154 D. 151 ） 。16. 下列关于指令字长、机器字长和存储字长的说法中，正确的是（ 指令字长等于机器字长的前提下，取指周期等于机器周期 II. 指令字长等于存储字长的前提下，取指周期等于机器周期 III.指令字长和机器字长的长度没有必然联系 IV.为了硬件设计方便，指令字长都和存储字长一样大 A. I、III 和 IV I. B. II、III 和 IV C. II 和 III D. I 和 IV ） 。 17. 下列关于基址寻址和变址寻址的说法中，正确的是（ 两者都扩大指令的寻址范围 II. 变址寻址适合于编制循环程序III.基址寻址适合于多道程序设计IV.基址寄存器的内容由操作系统确定，在执行的过程中可变 V.变址寄存器的内容由用户确定，在执行的过程中不可变 A. I、II 和 III A. 状态寄存器 I. B. I、II 和 V ） 。 C. ALU ） 。 D. 数据高速缓存 B. 通用寄存器 C. II 和 III D. II、III、IV 和 V 18. 下列部件不属于运算器的是（19. 在微程序控制方式中，以下说法正确的是（ 采用微程序控制器的处理器称为微处理器 II. 每一条机器指令由一个微程序来解释执行III.在微指令的编码中，执行效率最低的是直接编码方式 IV.水平型微指令能充分利用数据通路的并行结构 A. I 和 II A. 机器字长 A. PC 和 PSW B.II 和 IV C. I 和 III D. II、III 和 IV ）相关。 C. 存储字长 ） 。 D. AR 和 PSW ） 。 C. AR 和 IR D. 存储器地址寄存器 20. 在系统总线中，地址总线的位数与（ B. 实际存储单元个数 B. PC 和 IR21. CPU 响应中断时，保护两个关键的硬件状态是（22. 在 DMA 方式下，数据从内存传送到外设经过的路径是（ A. 内存-&数据总线-&外设 C. 内存-&CPU-&数据总线-&外设 D. 外设-&内存B. 内存-&DMAC-&外设-19-予人玫瑰手留余香 ） 。 B. 寄存器清零 C. 系统调用 ） 。 D. 取数23. 在操作系统中，以下只能在核心态下执行的指令是（ A. 读时钟 I. 24. 下列关于进程状态的说法中，正确的是（从运行态到阻塞态的转换是进程的D自主‖行为II. 从阻塞态到就绪态的转换是由协作进程决定的 III.当进程被调度程序选中时，它就从阻塞态变为就绪态 IV.在进程状态转换中，D就绪-&阻塞‖是不可能发生的 A. I、III 和 IV 量 S 的初值为（ A. m B. n B. I、II 和 IV ） 。 C. m-n ） 。 B. 系统资源不足 D. 进程竞争使用共享资源 ） 。 II. 固定分区分配 IV. 段页式分配 C.III、IV 和 V ） 。 C. 矢量运算 D. 二分搜索 ） 。 V. 分段式分配 D. II、IV 和 V D. Cm C. I 和 II D. I 和 IV 25. 设有 n 个进程共用一个相同的程序段，假设每次最多允许 m 个进程（m≤n）同时进入临界区，则信号26. 系统产生死锁的可能原因是（ A. 一个进程进入死循环 C. 共享资源分配不当 I. 动态分区分配 III. 分页式分配 A. I 和 II27. 支持程序存放在不连续内存中的存储管理方法有（B.III 和 IV28. 总体上说，D按需调页‖（Demand-paging）是一个很好的虚拟内存管理策略。但是，有些程序设计技 术并不适合于这种环境。例如， （ A. 堆栈 B. 线性搜索29. 在一个请求分页系统中， 采用 LRU 页面置换算法时， 假如一个作业的页面走向为 1,3,2,1,1,3,5,1,3,2,1,5。 当分配给该作业的物理块数分别为 3 和 4 时，则在访问过程中所发生的缺页率分别为（ A. 50%、33% B. 25%、100% C. 25%、33% D. 50%、75%30. 现代操作系统中， 文件系统都有效地解决了文件重名 （即允许不同用户的文件可以具有相同的文件名） 问题，系统是通过（ A. 重名翻译机构 I. ）来实现这一功能的。 B. 建立索引表 C. 树型目录结构 ） 。 D. 建立指针31. 下列关于文件系统的说法中，错误的是（一个文件在同一系统中、不同的存储介质上的拷贝，应采用同一种物理结构II. 对一个文件的访问，常由用户访问权限和用户优先级共同限制 III.文件系统采用树型目录结构后，对于不同用户的文件，其文件名应该不同 IV.为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件 A．I、II 和 III B．I、III C．I、III、IV ） 。 D．I、II、III 和 IV 32. 下列有关虚拟设备的论述中，正确的是（A. 虚拟设备是指将独占设备转变成了共享设备 B. 虚拟设备是指允许用户以标准化方式来使用物理设备 C. 虚拟设备是把一个物理设备变换成了多个对应的逻辑设备 D. 虚拟设备是指允许用户程序不必全部装入多个对应的逻辑设备 33. 关于 OSI 参考模型和 TCP/IP 模型在网络层和传输层提供的服务，正确的说法是（ A. OSI 模型在网络层提供无连接和面向连接服务，在传输层提供面向连接服务 B. TCP/IP 模型在网络层提供无连接服务，在传输层提供面向连接服务 C. OSI 模型在网络层和传输层均可提供无连接和面向连接服务 D. TCP/IP 模型在网络层提供无连接和面向连接服务，在传输层提供面向连接服务 34. 以下各项中，不是数据报服务特点的是（ B. 在整个传送过程中，不需要建立虚电路 ） 。 A. 每个分组自身携带有足够多的信息，它的传送被单独处理 ） 。-20-予人玫瑰手留余香C. 使所有分组按顺序到达目的端系统 D. 网络结点要为每个分组做出路由选择 35. 以下滑动窗口协议中，一定按序接收到达的分组的有（ I. 停止－等待协议 A. I 和 II A. 172.16.7.191 II. 后退 N 帧协议 C. II 和 III B. I 和 III ） 。 III. 选择重传协议 D. I、II 和 III ） 。 D. 172.16.7.25236. 某端口的 IP 地址为 172.16.7.131/26，则该 IP 地址所在网络的广播地址（ B. 172.16.7.129 C. 172.16.7.255 ） 。 37. 以下关于路由器的路由表说法正确的是（ B. 必须包含子网掩码 C. 必须包含目的网络和到达该目的网络路径上的下一个路由器的 IP 地址A. 必须包含目的网络和到达该网络的完整路径D. 必须包含目的网络和到达该目的网络路径上的下一个路由器的 MAC 地址 38. TCP 的通信双方，有一方发送了带有 FIN 标志的数据段后表示（ A. 将断开通信双方的 TCP 连接 B. 单方面释放连接，表示本方已经无数据发送，但是可以接受对方的数据 C. 中止数据发送，双方都不能发送数据 D. 连接被重新建立 39. 假设在没有发生拥塞的情况下，在一条往返时间 RTT 为 10ms 的线路上采用慢开始控制策略。如果接 收窗口的大小为 24KB，最大报文段 MSS 为 2KB。那么发送方能发送出一个完全窗口（也就是发送窗 口达到 24KB）需要的时间是（ A. 30ms I. 域名空间 III. 域名服务器 A. I 和 II B. I、II 和 III B. 60ms ） 。 II. 分布式数据库 IV. 从内部 IP 地址到外部 IP 地址的翻译程序 C. II 和 III D. I、II、III 和 IV 40. 域名系统 DNS 的组成包括（ ） 。 C. 50ms D. 40ms ） 。二、综合应用题：第 41～47 小题，共 70 分。41. （8 分）下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的 另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：(顶 点 边 ) 1 V1 2 V2 3 V3 ? 4 V4 5 V5 6 V6 ? 2 30 1 10 3 38 6 18 ? 5 42 ? 2 33 3 36 ? （出边表） 4 29 6 25 ?（1）该带权有向图的图形。 （2）从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树。 （3）以顶点 V1 为起点的深度优先搜索生成树。 （4）由顶点 V1 到顶点 V3 的最短路径。 42. （15 分）已知线性表（a1, a2,a3,…,an）存放在一维数组 A 中。试设计一个在时间和空间两方面都尽可 能高效的算法，将所有奇数号元素移到所有偶数号元素前，并且不得改变奇数号（或偶数号）元素之 间的相对顺序，要求： （1） 给出算法的基本设计思想。 （2）根据设计思想，采用 C 或 C++或 Java 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。 43. （11 分）某机按字节编制，主存容量为 1MB，采用两路组相联方式（每组仅有两块）的 Cache 容量-21-予人玫瑰手留余香为 64KB， 每个数据块为 256B。 已知访问开始前第 2 组 （组号为 1） 的地址阵列内容如下图所示。 Cache 采用 LRU 替换策略。 0 1 00100（二进制） 01011（二进制）（1） 分别说明主存地址中标记(Tag)、组号和块内地址三部分的位置和位数。 （2）若 CPU 要顺序访问地址为 20124H、58100H、60140H 和 60138H 等 4 个主存单元。上述 4 个数 能否直接从 Cache 中读取，若能，请给出实际访问的 Cache 地址。第 4 个数访问结束时，上图 中的内容将如何变化。 （3）若 Cache 完成存取的次数为 5000 次， 主存完成存取的次数为 200 次。 已知 Cache 存取周期为 40ns， 主存存取周期为 160ns，求该 Cache/主存系统的访问效率。 44. （12 分）假定硬盘传输数据以 32 位的字为单位，传输速率为 1MB/s。CPU 的时钟频率为 50MHz。 （1）采用程序查询的输入输出方式，假设查询操作需要 100 个时钟周期，求 CPU 为 I/O 查询所花费 的时间比率，假定进行足够的查询以避免数据丢失。 （2）采用中断方法进行控制，每次传输的开销（包括中断处理）为 100 个时钟周期。求 CPU 为传输 硬盘数据花费的时间比重。 （3）采用 DMA 控制器进行输入输出操作， 假定 DMA 的启动操作需要 1000 个时钟周期， DMA 完成 时处理中断需要 500 个时钟周期。如果平均传输的数据长度为 4KB，问在硬盘工作时处理器将 用多少时间比重进行输入输出操作，忽略 DMA 申请使用总线的影响。 45. （8 分）在某段式存储管理系统中，逻辑地址为 32 位，其中高 16 位为段号，低 16 位为段内偏移量， 以下是段表（其中的数据均为 16 进制）：以下是代码段的内容（代码前数字表示存放代码的十六进制逻辑地址）： main 240 244 248 试问： （1）x 的逻辑地址为 10108H，它的物理地址是多少？要求给出具体的计算过程。 （2）若栈指针 SP 的当前值为 70FF0H，push x 指令的执行过程：先将 SP 减 4，然后存储 x 的值。试 问存储 x 的物理地址是多少？ （3）call sin 指令的执行过程：先将当前 PC 值入栈，然后在 PC 内装入目标 PC 值。请问：哪个值被 压入栈了？新的 SP 指针的值是多少？新的 PC 值是多少？ （4）Dmov 4+(sp), r2‖的功能是什么？ 46. （7 分）一个磁盘机有 19,456 个柱面，16 个读写磁头，并且每个磁道有 63 个扇区。磁盘以 5400rpm 的速度旋转。试问： push x[10108] call sin ? sin 360 364 366 488 mov 4+(sp), r2 push r2 ? ret-22-予人玫瑰手留余香（1） 如果磁盘的平均寻道时间是 10ms，那么读一个扇区的平均时间是多少？ （2）在一个请求分页系统中，若将该磁盘用作交换设备，而且页面大小和扇区的大小相同。读入一 个换出页的平均时间和上面计算的相同。假设如果一个页必须被换出，则寻找换入页的时间将 只有 1ms，那么传输这两个页的平均时间是多少？ （3）如果在该系统中打开的文件数目远远多于驱动器的数目时，对磁盘机有什么影响？ 47. （9 分）设 A、B 两站相距 4km，使用 CSMA/CD 协议，信号在网络上的传播速度为 200 000km/s，两 站发送速率为 100Mbps，A 站先发送数据，如果发送碰撞，则： （1） 最先发送数据的 A 站最晚经过多长时间才检测到发生了碰撞？最快又是多少？ （2）检测到碰撞后，A 站已发送数据长度的范围是多少（设 A 要发送的帧足够长）？ （3）若距离减少到 2km，为了保证网络正常工作，则最小帧长度是多少？ （4）若发送速率提高，最小帧长不变，为了保证网络正常工作应采取什么解决方案？-23-予人玫瑰手留余香第2套 答案与解析一、 单项选择题 1 D 11 D 21 A 31 D 1. 2 C 12 B 22 B 32 C 3 B 13 B 23 C 33 A 4 C 14 D 24 B 34 C 5 B 15 A 25 A 35 A 6 D 16 C 26 C 36 A 7 B 17 A 27 C 37 C 8 D 18 D 28 D 38 B 9 C 19 B 29 A 39 D 10 A 20 D 30 C 40 B【分析】【单科书 P53】本题考查出入栈序列。 【解答】出栈序列 1342 由 1 入,1 出,2 入,3 入,3 出,4 入,4 出,2 出得到。采用排除法，选项 A、B、C 得到的出栈序列分别为 、1324，只有选项 D 的出栈序列为 1342。 2. 【分析】 【单科书 P59】本题考查循环队列的性质。区分循环队列队空还是队满有 3 种方法：①牺牲一 【解答】因为元素移动按 rear = (rear+1) MOD m 进行，则当数组 Q[m-1]存放了元素之后，下一个入队 的元素将存放到 Q[0]中，因此队首元素的实际位置是(rear-length+1+m) MOD m。 【另解】特殊值代入法：对于循环队列，A 和 D 无取 MOD 操作，显然错误，直接排除。设 length 等 于 1，rear 等于 0，代入 BC 两项，显然仅有 C 符合。 3. 【分析】【单科书 P89】本题考查二叉树的定义和性质。需要注意的是，尽管二叉树与树有许多相似 【解答】 二叉树的度至多为 2， 也可以小于 2。 当二叉树只有一个结点时， 度为 0。 在度为 2 有序树中： ①至少有一个结点的度为 2；②孩子结点的左右顺序是相对于其兄弟结点而言的，如果仅有一个孩子结点 就无所谓左右孩子了。而二叉树的左右顺序是相对于根结点的，即使只有一个孩子结点也要指明是左孩子 还是右孩子。由①②可知，D 错误。 4. 【分析】 【单科书 P114】本题考查平衡二叉树的性质与查找操作。平衡二叉树在结点最多的情况下为 满二叉树，在结点最少的情况下也满足一定的条件。二叉排序树的查找路径是否合法，应从查找的原理， 根据结点与待查结点之间的大小（决定分支方向）进行判断。 【解答】设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，有： N0=0 ， N1=1 ， N2=2 ， … ， Nh=Nh-1+Nh-2+1，N3=4，N4=7，N5=12，N6=20&15。也就是说，高度为 6 的平衡二叉树最少有 20 个结点， 因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。而 A 和 B 的查 找过程不能构成二叉排序树，因此 A、B 错误。 5. 【分析】【单科书 P115】本题考查哈夫曼树的性质。哈夫曼树中只有度为 2 和度为 0 的结点，哈夫曼 编码是对哈夫曼树中的叶子结点编码。 由于左、 右结点的顺序是任意的， 所以构造出的哈夫曼树并不唯一， 但各哈夫曼树的带权路径长度是相同且最优的。 【解答】 根据树的性质 N0=N2+1， 故 N0=(N2+N0+1)/2=(215+1)/2=108， 哈夫曼树共有 108 个叶子结点， 所以共能得到 108 个不同的码字。 6. 【分析】 【单科书 P151】本题考查图的性质。在无向图中，一条边连接两个顶点，故所有顶点的度之 【解答】由于在具有 n 个顶点 e 条边的无向图中，有 个，从而最多有 16 个顶点。 7. 【分析】 【单科书 P173】本题考查关键路径的性质。关键路径是从源点到汇点最长的路径，关键路径 可能并不唯一，当然各关键路径的路径长度一定是相等的。n i=1 TD个存储单元；②增设表示元素个数的变量；③设标记法。之处，但二叉树不是树的特殊情形。和等于边数的 2 倍。 vi = 2e，故可求得度为 2 的顶点数为 7-24-予人玫瑰手留余香【解答】只有为各关键路径所共有的关键活动，且减少它尚不能改变关键路径的前提下，才可缩短工 期，A 错误。根据关键路径的定义，关键路径上活动的时间延长多少，整个工程的时间也就必然随之延长 多少，B 正确。如果是改变所有关键路径上共有的一个关键活动，则不一定会影响关键路径的改变， C 错 误。若所有的关键路径一同延长，则关键路径不会改变；但若一同缩短到一定的程度，则有可能引起关键 路径的改变，D 错误。 8. 【分析】 【单科书 P202】本题考查 B 树的性质。B 树是考查的重点，此类题通常会将 B+树的性质说 【解答】m 阶 B 树根结点至少有两棵子树，且这两棵子树可以是空树，其他非叶结点至少有 m/2 棵 子树，I 错误。II 为 B+树的性质。B 树又称多路平衡查找树，叶结点都在同一层次上，可以看出是查找失 败结点。结点的分裂不一定会使树高增 1，如图 1 所示，只有当结点的分裂传到根结点，并使根结点也分 裂，才会导致树高度增 1，如图 2 所示。30插入60后，溢出成是 B 树的性质，因此读者一定要掌握它们之间的差异。30结点分裂30 522050 522050 52 60205060图 1 结点分裂不导致树高增 1（3 阶 B 树）52 30 52 20 50插入7030 52 20 50结点分裂30 52 68 50 60再分裂30 20 50 6068 7060 6860 68 702070图 2 结点分裂导致树高增 1（3 阶 B 树） 9. 【分析】 【单科书 P108 等】本题考查几种特殊二叉树的比较。 【解答】二叉排序树中的任一结点 x 大于其左孩子，小于其右孩子，从二叉排序树的任一结点出发到 根结点，只要路径中存在左子树关系则必不满足题中降序的条件。同理，平衡二叉树也不满足。小顶堆中 的任一结点 x 均小于左右孩子， 因此从任一结点到根的路径上的结点序列必然是降序的。 大顶堆刚好相反。 【另解】这类题建议大家画几个简单的草图，就很容易得出答案了。 10. 【分析】 【单科书 P232 等】本题考查各种排序算法的特点。读者应从原理上理解掌握哪些排序算法能 形成全局有序序列，或局部有序序列，而不应是死记硬背。 【解答】冒泡排序和选择排序经过两趟排序之后，应该有两个元素放在其最终位置；插入排序经过两 趟排序之后，前 3 个元素应该是局部有序的；只有可能是快速排序。 11. 【分析】本题综合考查基数排序的特性、排序算法的稳定性。由题意，数据项的先后顺序是 k1，k2， 联想到基数排序的过程，应先对 k2 排序，再对 k1 排序。在最后对 k1 排序时，若采用不稳定的排序方法， 可能会导致D在 k1 相同的情况下：k2 小的在前，大的在后‖。 【解答】首先应确定 k1，k2 的排序顺序，若先排 k1 再排 k2，则排序结果不符合题意，排除 AC。再 考虑算法的稳定性， 当 k2 排好序后， 再对 k1 排序， 若对 k1 排序采用的算法是不稳定的， 则对于 k1 相同， 而 k2 不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序算法是稳定的，而简 单选择排序算法是不稳定的。 12. 【分析】 【单科书 P152】本题考查控制器的功能。在控制器的控制下，计算机在不同的阶段对存储器 进行读写操作时， 取出的代码也就有不同的用处。 同一串代码， 在取指阶段读出的二进制代码则作为指令， 在执行阶段读出的二进制代码则就有可能作为数据。 【解答】通过总线无法区分指令和数据，而主存能通过总线和指令周期区分地址和非地址数据。运算 器是对数据进行算逻运算的部件。 控制存储器器是存放微指令的部件。 这二者均无区分指令和数据的功能。 13. 【分析】 【单科书 P47】本题考查浮点数的运算。浮点数运算的过程为对阶、尾数求和、规格化、舍入 和溢出判断，本题的 5 个选项涉及到了这 5 个过程。 【解答】最简单的舍入处理方法是直接截断，不进行任何其他处理（截断法） ，I 错误。IEEE 754 标准 的浮点数的尾数都是大于等于 1 的，所以乘法运算的结果也是大于等于 1，故不需要D左规‖，II 正确；对 阶的原则是小阶向大阶看齐，III 正确。当补码表示的尾数的最高位与尾数的符号位（数符）相异时表示规-25-予人玫瑰手留余香格化，IV 错误。浮点运算过程中，尾数出现溢出并不表示真正的溢出，只有将此数右归后，再根据阶码判 断是否溢出，V 错误。 14. 【分析】 【单科书 P80 等】本题考查 ROM 和 RAM 的相关性质。 【解答】CD-ROM属于光盘存储器，是一种机械式的存储器，和ROM有本质的区别，I错误。Flash存 储器是E2PROM的改进产品，虽然它也可以实现随机存取，但从原理上讲仍属于ROM，而且RAM是易失性 存储器，II错误。DRAM的读出方式并不是破坏性的，读出后不需再生，III错误。SRAM采用双稳态触发 器来记忆信息，因此不需要再生；而 DRAM采用电容存储电荷的原理来存储信息，只能维持很短的时间， 因此需要再生，IV正确。 15. 【分析】 【单科书 P95】本题考查 Cache 和主存的地址映射方式。对于此类题，先写出主存地址的二进 制形式，然后分析 Cache 块内地址、Cache 字块地址和主存字块标记。 【解答】主存地址35301H对应的二进制为11 ，现在要分析该地址中哪些位是 Cache块内地址、主存字块标记和Cache字块地址。低位是块内地址，每个字块8个字=25B（每字32位） ，所 以低5位表示字块内地址；主存字块标记为高6位（1MB÷ 16KB=64 =26） ，其余01 即为Cache字块地 址，对应的十进制数为152。 16. 【分析】 【单科书 P14】本题考查指令字长、机器字长和存储字长的区别与联系。指令字长是指指令中 包含二进制代码的位数；机器字长是 CPU 一次能处理的数据长度，通常等于内部寄存器的位数；存储字 长是一个存储单元存储的二进制代码（存储字）的长度。 【解答】指令字长通常取存储字长的整数倍，如果指令字长等于存储字长的 2 倍，则需要 2 次访存， 取指周期等于机器周期的 2 倍， 如果指令字长等于存储字长， 取指周期等于机器周期， 故 I 错误、 II 正确。 指令字长取决于操作码的长度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系，但 为了硬件设计方便，指令字长一般取字节或存储字长的整数倍，III 正确。指令字长一般取字节或存储字长 的整数倍，IV 错误。 17. 【分析】 【单科书 P131】本题考查基址寻址和变址寻址的区别。理解基址寻址和变址寻址各自的特点 和区别，它们的真实地址 EA 都是形式地址 A 加上一个寄存器中的内容。 【解答】两者的有效地址都加上了对应寄存器的内容，都扩大了指令的寻址范围， I 正确。变址寻址 适合处理数组、编制循环程序，II 正确。基址寻址有利于多道程序设计，III 正确。基址寄存器的内容由操 作系统或管理程序确定，在执行过程中其内容不变，而变址寄存器的内容由用户确定，在执行过程中其内 容可变，故 IV 和 V 错误。 18. 【分析】 【单科书 P148】本题考查运算器的组成。运算器应包括算术逻辑单元、暂存寄存器、累加器、 通用寄存器组、程序状态字寄存器、移位器等。控制器应包括指令部件、时序部件、微操作信号发生器(控 制单元)、中断控制逻辑等，指令部件包括程序计数器(PC)、指令寄存器(IR)和指令译码器(ID)。 【解答】数据高速缓存是专门存放数据的 Cache，不属于运算器。 19. 【分析】 【单科书 P167】本题考查微程序控制器的相关概念。再考查微程序的相关概念时，可以联系 到程序的相关内容，但是要注意区分。 【解答】微处理器是相对于大型机的处理器而言的，和微程序控制器没有必然联系，I 错误。微程序 的设计思想就是将每一条机器指令编写成一个微程序，每一个微程序包含若干条微指令，每一条微指令对 应一个或几个微操作命令，II 正确。直接编码方式中每一位代表一个微命令，不需要译码，因此执行效率 最高，III 错误。一条水平型微指令能定义并执行几种并行的基本操作，因此能更充分利用数据通路的并行 结构，IV 正确。 20. 【分析】 【单科书 P200】本题考查地址总线。地址总线的位数和最大存储单元个数相关，也和 MAR 的位数相关。地址总线的宽度决定了 CPU 可以访存的最大物理地址空间。如 32 位的地址线，按字节寻址 的可寻址的最大容量为 232bit=4GB。 【解答】 地址总线的位数和实际存储单元个数是无关的， 如 32 位的地址线， 可以仅仅用 2GB 的内存。 而 MAR 的位数和其是相关的，一般这二者是相等的。 21. 【分析】 【单科书 P229】本题考查中断的处理过程及 CPU 中的各类寄存器。程序计数器 PC，指令寄 存器 IR，PSW 程序状态字，AR 地址寄存器。-26-予人玫瑰手留余香【解答】PC 的内容是被中断程序尚未执行的指令地址，PSW 保存各种状态信息。CPU 响应中断后， 需要保护中断的 CPU 现场，将 PC 和 PSW 压入堆栈，这样等到中断结束后，可以将压入堆栈的原 PC 和 PSW 的内容返回相应的寄存器，原程序从断点开始继续执行。 22. 【分析】 【单科书 P232】 本题考查 DMA 的数据传送方式。 在 DMA 方式下， 数据传送不需要经过 CPU， 但需要经过 DMA 控制器中的数据缓冲寄存器。 【解答】DMA 控制器中的数据缓冲寄存器用来暂存每次传送的数据。输入时，数据由外设（如磁盘） 先送往数据缓冲寄存器，再通过数据总线送到主存。反之，输出时，数据由主存通过数据总线送到数据缓 冲寄存器，然后再送到外设。 23. 【分析】 【单科书 P11】本题考查操作系统的运行机制。通常将 CPU 执行的程序分为操作系统内核程 序和用户自编程序，它们分别运行在核心态和用户态。 【解答】大多数计算机操作系统内核包括四个方面的内容，即时钟管理、中断机制、原语和系统控制 的数据结构及处理，其中第 4 部分实际上是系统调用类的指令（广义指令） 。而 A、B 和 D 三项均可以在 汇编语言中涉及，因此都可以运行在用户态。 24. 【分析】 【单科书 P23】本题考查进程的状态与转换。从运行态到阻塞态的转换是由进程自身决定的， 它是由于进程的时间片用完，D主动‖调用程序转入就绪态。 【解答】进程的阻塞和唤醒是由 block 和 wakeup 原语实现的，block 原语是由被阻塞进程自我调用实 现的，而 wakeup 原语则是由一个与被唤醒进程相合作或其他相关的进程调用实现的，故 I 和 II 正确。进 程调度只可能是从就绪队列中选择进程到 CPU 上执行，因此只可能是从就绪态到执行态，III 错误。只有 在运行中的进程当请求某一资源或等待某一事件时，才会转入到阻塞态，因此不可能直接从就绪态转到阻 塞态，IV 错误。 25. 【分析】 【单科书 P51】本题考查互斥信号量的设置。 【解答】互斥信号量的初值应为可用资源数，在本题中为可同时进入临界区的资源数。每当一个进程 进入临界区，S 减 1，减到-(n-m)为止，此时共有|S|个进程在等待进入。 26. 【分析】 【单科书 P69】本题考查死锁的原因。死锁的可能原因包括时间和空间上的。时间上由于进程 运行中推进顺序不当，即调度时机不合适，不该切换进程时进行了切换，可能会造成死锁；空间上是对共 享资源分配不当，互斥资源部分分配又不剥夺，易造成死锁。 【解答】系统资源不足只会对进程造成饥饿，如某系统只有 3 台打印机，若进程运行中要申请 4 台， 显然不能满足，该进程会一直等待下去。如果该进程在创建时便声明要 4 台打印机，那么操作系统将不会 创建该进程。一般的，系统由于部分分配，剩余资源不足时，可能会造成死锁，这实际上是资源分配不当 的一种表现，不能以系统资源不足来描述剩余资源不足的情形，B 错误。进程自己进入死循环只能产生饥 饿， 并不涉及别的进程，A 错误。 共享型资源允许多个进程申请使用，故也不是造成死锁的原因，D 错误。 27. 【分析】 【单科书 P131】本题考查非连续分配管理方式。非连续分配允许一个程序分散地装入不相邻 的内存分区中。 【解答】动态分区分配和固定