您的位置： &
TCP段乱序重排的硬件设计与实现
优质期刊推荐[特别说明]_豆搜网
[特别说明]
文档格式：PDF&&
更新时间：&&
下载次数：0&&
点击次数：1
予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~1~【特别说明】 本次编著《王道 6 套模拟题》的时间较为仓促,而且各科编者的时间也非常零散,因此在内容质 量上我们或许做得不够出色,在此对广大的道友表示诚挚的歉意!但不管怎么说,我们也已尽最大努 力来帮助大家冲刺 2012 年的专业课.希望道友们能抓住最后的 20 天,调整好心态,认真总结之前的 复习内容.考试结束后,也希望你们能偶尔上上王道论坛帮助未来考研的师弟师妹们. 真心地祝愿各位道友考研成功!予人玫瑰 手留余香 王道计算机统考模拟试题1 一、单项选择题:第1~40 小题,每小题 2 分,共80 分.下列每题给出的四个选项中,只有一个选 项最符合试题要求. 1. 设有一个 10 阶对称矩阵 A,采用压缩存储方式,以行序为主存储,a1,1 为第一个元素,其存储地址为 1,每个元素占一个地址空间,则a8,5 的地址是( ) . A.13 B.33 C.18 D.40 2. 循环队列用数组 A[0…m-1]存放其元素值,头尾指针分别为 front 和ont 指向队头元素,rear 指向队尾元素的下一个元素,则当前队列中的元素个数是( ). A.(ont+m)%m B.(ont+1)%m ont-1 ont 3. 若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点,则该二叉树共有( )个叶子结点. A.17 B.18 C.19 D.20 4. 某二叉树结点的中序序列为 BDAECF,后序序列为 DBEFCA,则该二叉树对应的森林包括( )棵树. A. 1 B. 2 C. 3 D. 4 5. 利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树后,要查找元素 30 要进行 元素间的比较次数是( ). A. 4 B. 5 C. 6 D. 7 6. 一个有 n 个顶点和 n 条边的无向图一定是( ) . A. 连通的 B. 不连通的 C. 无环的 D. 有环的 7. 一个含有 n 个顶点和 e 条边的简单无向图,其邻接矩阵存储中零元素的个数是( ). A. e B. 2e C. n2 -e D. n2 -2e 8. 散列表的地址范围为 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 欢迎各位道友在【计算机考研交流专区】交流模拟题中的疑问和问题. 第4套予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~2~第三趟:15,20,21,25,27,35,47,68,84 则所采用的排序方法是( ). A.选择排序 B.希尔排序 C.归并排序 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 B.2 C.1.5 D.1 13. 按IEEE754 标准规定的 32 位浮点数(单精度浮点数)41A4C000H 对应的十进制数是( ) . A.4.59375 B.-20.59375 C.-4.59375 D.20.59375 14. 设某按字节编址的计算机已配有00000H~07FFFH的ROM区,地址线为20位,现再用16K* 8位的RAM 芯片构成剩下的RAM区08000H~FFFFFH,则需要这样的RAM芯片( )片. A. 61 B. 62 C. 63 D. 64 15. 设存储器容量为32字,字长为64位.模块数m=4,采用低位交叉方式.存储周期T=200ns,数据总线 宽度为64位,总线传输周期r=50ns.该交叉存储器的带宽是( ) . A.32 * 107 bit/s B.8 * .73 * 107 bit/s D.18 * 107 bit/s 16. 虚拟存储器中的页表有快表和慢表之分,下面关于页表的叙述中正确的是( ) . A.快表与慢表都存储在主存中,但快表比慢表容量小 B.快表采用了优化的搜索算法,因此查找速度快 C.快表比慢表的命中率高,因此快表可以得到更多的搜索结果 D.快表采用高速存储器件组成,按照查找内容访问,因此比慢表查找速度快 17. 下列关于各种寻址方式获取操作数快慢的说法中,正确的是( ) . I.立即寻址快于堆栈寻址 II.堆栈寻址快于寄存器寻址 III.寄存器一次间接寻址快于变址寻址 IV.变址寻址快于一次间接寻址 A.I 和IV B.II 和III C.I、III 和IV D.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 19. 当微指令采用分段编码时,我们将互斥性微命令( ) . A.放在同一段中 B.用多级译码来区分 C.放在不同段中 D.任意存放 20. 在32 位总线系统中,若时钟频率为 500MHz,传送一个 32 位字需要 5 个时钟周期,则该总线系统的 数据传输速率是( ) . A. 200MB/s B. 400MB/s C. 600MB/s D. 800MB/s 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 指令来启动通道 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~3~D.通道程序是由通道来执行的 23. 在操作系统的以下功能中,不需要硬件支持的是( ) . I.中断系统 II.时钟管理 III.地址映射 IV.页面调度 A. III 和IV B. II、III 和IV C. I 和IV D. 只有 IV 24. 以下描述中,哪个不是多线程系统的特长, ( ) . A. 利用线程并行地执行矩阵乘法运算 B. Web 服务器利用线程请求 HTTP 服务 C. 键盘驱动程序为每一个正在运行的应用配备一个线程,用来响应相应的键盘输入 D. 基于 GUI 的debugger 用不同线程处理用户的输入、计算、跟踪等操作. 25. 如果系统中所有进程是同时到达的,则平均周转时间最短的调度算法是( ) . A. 先来先服务 B. 短进程优先 C. 优先级调度 D. 时间片轮转 26. 在使用信号量机制实现互斥和同步时,互斥信号量和同步信号量的初值分别为( ) . A. 0、1 B. 1、0 C. 1、1 D. 1、由用户确定 27. 有两个并发进程如下面所示,对于这段程序的运行,正确的说法是( ) . int x,y,z,t,u; P1(){ P2(){ while(1){ while(1){ x=1; x=0; y=0; t=0 if(x>=1) y=y+1; if(x1)的单链表,表头指针为 L,结点结构由 data 和next 两个域构成,其中 data 域为字符型.试设计一个在时间和空间两方面都尽可能高效的算法,判断该单链表是否中心对称 (例如 xyx、xxyyxx 都是中心对称的) ,要求: (1)给出算法的基本设计思想. (2)根据设计思想,采用 C 或C++或Java 语言描述算法,关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 43. (11 分)下图是一个简化的 CPU 与主存连接结构示意图(图中省略了所有多路选择器) .其中有一个 累加寄存器 AC、 一个状态寄存器和其他四个寄存器: 主存地址寄存器 MAR、 主存数据寄存器 MDR、 程序计数器 PC 和指令寄存器 IR,各部件及其之间的连线表示数据通路,箭头表示信息传送方向. 一个简化的 CPU 与主存连接结构示意图 要求: (1)请写出图中 a、b、c、d 四个寄存器的名称. (2)简述图中指令从主存取到控制器的过程. (3)说明数据从主存取出、运算、写回主存所经过的数据通路(假定数据地址已在 MAR 中) . 44. (11 分)设某计算机有 4 级中断 A、B、C、D,其硬件排队优先级次序为 A>B>C>D.如表所示列出 了执行每级中断服务程序所需的时间. 中断服务程序所需的时间 中断服务程序 所需时间 A 5us B 15us C 3us D 12us 如果以执行中断服务程序的时间作为确定中断优先级的尺度:时间越短优先级越高. (1)如何为各级中断服务程序设置屏蔽码? (2)如果 A、B、C、D 分别在 6us、8us、10us、0us 时刻发出中断请求,请画出 CPU 执行中断服务 程序的序列. (3)基于上题,请计算上述 4 个中断服务程序的平均执行时间. 45. (7分)兄弟俩共同使用一个账号,每次限存或取10元,存钱与取钱的进程分别如下所示: ount=0; SAVE(){ int m1; TAKE(){ int m2; m2=m2-10; amount=m2; } 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~6~m1=m1+10; amount=m1; } 由于兄弟俩可能同时存钱和取钱, 因此两个进程是并发的. 若哥哥先存了两次钱, 但在第三次存钱时, 弟弟在取钱.请问: (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 地址. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~7~第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.分ont 和ont 两种情况讨论:①当ont 时,队列中元素个数为 ont=(ont+m)%m;②当ont 时,队列中元素个数为 m-(front-rear) =(ont+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 的关系.此二叉树的形态如 下图右所示. 再根据二叉树与森林的对应关系.森林中树的棵数即为其对应二叉树(向右上旋转 45o 后)中根结点 A 及其"右兄弟"数.可知此森林中有 3 棵树,根结点分别为 A、C 和F. 【提示】由二叉树求森林中树的个数、或求各棵树形等,应将二叉树向右上旋转 45o ,然后再根据森 林和二叉树的转换规则来描绘出森林中的树形. 5. 【分析】 【单科书 P100】本题考查二叉排序树的构造和查找.利用逐点插入法建立二叉排序树是从空 树开始,通过查找,将每个结点作为一个叶结点插入. 【解答】 B. 按题中数据的输入次序, 建立的二叉排序树如下图所示. 查找元素 30 的比较次数为 5 次. 6. 【分析】 【单科书 P150】本题考查图的基本性质.n 个顶点构成连通图至少需要 n-1 条边(生成树) , 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~8~但若再增加 1 条边,则必然会构成环. 【解答】D.如果一个无向图有 n 个顶点和 n-1 条边,可以使它连通但没有环(即生成树) ,但再加一 条边,在不考虑重边的情形下,就必然会构成环. 7. 【分析】【单科书 P154】本题考查邻接矩阵存储的定义.无向图的邻接矩阵是对称的,即图中的任一 条边 ai,j 对应邻接矩阵中的两个非零元素 A[i][j]和A[j][i]. 【解答】D.一个含有 n 个顶点和 e 条边的简单无向图的邻接矩阵为 n* n 矩阵,共有 n2 个元素,其中 非零元素个数为 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* 106 = 1.5.这里的存储器延迟为迷惑项,与CPI 的计算无关. 13. 【分析】 【单科书 P46】 本题考查 IEEE754 标准的浮点数. 单精度浮点数 () 与双精度浮点数 (double) 都采用隐含尾数最高数位的方法, 故可多表示一位尾数.临时浮点数又称为扩展精度浮点数,无隐含位. 在单精度浮点数中, 最高位为数符位; 其后是 8 位阶码, 以2为底, 用移码表示, 阶码的偏置值为 127; 其后 23 位是尾数数值位.对于规格化的二进制浮点数,数值的最高位总是"1",为了能使尾数多表示一位 有效值,将这个"1"隐含,因此尾数数值实际上是 24 位.隐含的"1"是一位整数.在浮点格式中表示出来的 23 位尾数是纯小数,用原码表示. 【解答】 D. 41A4C000H 写成二进制为 10 00 , 第一位为符号位 0, 表示是正数.之后的 8 位 表示阶码,真值为(100)B,即4.剩下的是隐含了最高 1 的尾数,故而 为1.010 00 ,数值左移四位后整数部分 10100 表示为 20. 14. 【分析】 【单科书P87】本题考查存储芯片的扩展. 【解答】B.RAM区的地址范围为:00
~ 11 ,由此可知 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* 10-7 s.故带宽为:W=64* 4b/(3.5* 10-7 s)=73* 107 b/s. 16. 【分析】 【单科书 P103】本题考查快表和慢表的关系.快表又称 TLB,采用高速相联存储器来存储可 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~9~能需要使用的页的对应表项.而慢表存储在内存中. 【解答】 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.引入多线程是为了更好的并发执行,键盘属于慢速外设,它无法并发执行,因此仅用一 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~10 ~ 个线程来处理整个系统的键盘输入即可. 25. 【分析】 【单科书 P38】本题考查各调度算法的特点. 【解答】B.平均周转时间=各进程周转时间之和/进程数,因为每个进程的执行时间都是固定的,所 以变化的是等待时间,只有短进程优先算法能最小化等待时间. 26. 【分析】 【单科书 P51】本题考查信号量机制.注意互斥信号量和同步信号量的区别.信号量机制是每 年考题的重点,这就要求考生能在理解的基础上熟练应用和掌握信号量. 【解答】 D. 互斥信号量的初值为 1, P 操作成功则将其改成 0 , V 操作成功将其改成 1. 实现同步时, 信号量的初值应根据具体情况来确定,若期望的消息尚未产生,则对应的初值应为 0;若期望的消息已经 存在,则信号量的初值应设为一个非 0 的正整数. 27. 【分析】本题考查进程的并发执行.要求分析程序运行的结果,通常会涉及到同步、互斥、饥饿和死 锁.因此考生要理解同步和互斥、饥饿和死锁的区别,并能根据程序分析. 【解答】C.本题中两个进程不能正确地工作,运行结果的可能性,详见下面说明. 1. x=1; 5. x=0; 2. y=0; 6. t=0 3. if(x>=1) y=y+1; 7. if(x2->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 现象. 【解答】 B. I正确, 举例如下: 页面走向为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.网络体系结构是抽象的,它不包括各层协议及功能的具体实现细节.分层使得各层次之 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~11 ~ 间相对独立,各层仅需关注该层需要完成的功能,保持了网络的灵活性和封装性,但网络的体系结构并没 有规定层次的名称和功能必须一致. 34. 【分析】 【单科书 P30】本题考查几种交换技术.电路交换、分组交换、报文交换及数据报服务、虚电 路服务这些易混知识点容易出串联性选择题,要在对比中加深理解和记忆. 【解答】D.电路交换是真正的物理线路交换,例如电话线路;虚电路交换是多路复用技术,每一条 物理线路可以进行多条连接,是逻辑上的连接,因此 A 错误.虚电路不只是临时性的,它提供的服务包括 永久性虚电路(PVC)和交换型虚电路(SVC) .其中前者是一种提前定义好的,基本上不需要任何建立时 间的端点之间的连接,而后者是端点之间的一种临时性连接,这些连接只持续所需的时间,并且当会话结 束时就取消这种连接,因此 B 错误.数据报服务是无连接的,不提供可靠性保障,也不保证分组的有序到 达,虚电路服务提供可靠性,且保证分组的有序到达,因此 C 错误.数据报服务中,每个分组在传输过程 中都必须携带源地址和目的地址;而虚电路服务中,在建立连接后,分组只需携带虚电路标识,而不必带 有源地址和目的地址. 35. 【分析】 【单科书 P71】本题考查 CSMA/CD 协议的最小帧长.在发送的同时要进行冲突检测,这就要 求在能检测出冲突的最大时间内数据不能发送完毕,否则冲突检测不能有效地工作.所以,当发送的数据 帧太短时,必须进行填充.最小帧长=数据传输速率*争用期. 【解答】 A. 争用期=网络中两站点最大的往返传播时间 2τ=2*(1/200 000)=0.00 001; 最小帧长=* 0.00 001=10 000bit. 36. 【分析】 【单科书 P116】本题考查子网划分与子网掩码.一个子网中的所有主机的子网号应该相同, 因此若因 IP 地址分配不当,则应联想到可能 子网号分配错误. 【解答】A.这4个IP 地址都是 C 类地址,前3个字节是网络号,224 用二进制表示是 , 因此子网号长度为3. 这4 个IP 地址的最后一个字节的二进制表示分别是 , , , .考察子网号部分(第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错误;P 提供面向连接的可靠数据传输服务,故II 错误;III:IP 数据报不是由传输层来组织的,而 应该由网络层加上 IP 数据报的首部来形成 IP 数据报,故III 错误;IV:前面已经分析,正确.综上,I、 II 和III 都是错误的. 39. 【分析】 【单科书 P113、P169】本题考查 PDU 在对等层间的处理.PDU 中装载的是哪一层的数据, 就有哪一层来处理该数据,而PDU 所在的层只负责传输该数据. 【解答】是分组交换网络,每个分组的首部都包含了完整的源地址和目的地址,以便途经 的路由器为每个 IP 分组进行路由,即便是同一个源站点向同一个目的站点发出的多个 IP 分组也并不一定 走同一条路径, 亦即这些 IP 分组到达目的站点的顺序可能不一定按序到达, 目的站点的传输层必须进行排 序;而一个较大的 IP 分组在传输的过程中,由于途经物理网络的 MTU 可能比较小,一个 IP 分组可能将 分成若干个分组,每个分组都有完整的首部,与普通的 IP 分组没有区别地传输.按照网络对等层通信的原 则,接收站点的网络层收到的 IP 分组必须与发送站点发送的 IP 分组相同,所以接收站点的网络层必须把 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~12 ~ 沿途被分片的分组进行重组,还原成原来的 IP 分组.所以重组工作是由网络层完成的. 40. 【分析】 【单科书 P199】本题考查对 WWW 服务的理解.如果用户直接使用域名去访问一个 WWW 服务器,其过程是:域名解析、建立 TCP 连接、传输数据、释放连接. 【解答】B.只有获得服务器的 IP 地址后,WWW 浏览器才能与 WWW 服务器建立连接开始后续的 交互.因此从协议执行过程来说,访问 WWW 服务器的第一步是域名解析. 二、综合应用题 41. 【分析】本题考查图的邻接矩阵存储表示、拓扑排序、关键路径和最短路径.拓扑排序、关键路径和 最短路径是图应用中最重要的知识点(常考题型,综合题考图章节的概率也很大) ,特别是后两者也是难 点.读者应熟练掌握此类题的解法. 【解答】 (1)该图对应的邻接矩阵如下: ∞ 2 3 ∞ ∞ ∞ ∞ ∞ ∞
5 ∞ ∞ ∞ ∞ 3 10 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 6 1 ∞ (2)只有顶点 V1 的入度为 0,由此可以得到两个拓扑序列:V1,V2,V3,V4,V6,V5,V7,V8 和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 V3 V4 V5 V6 V7 V8 最早发生时间 0 2 3 7 13 11 16 17 最晚发生时间 0 2 3 7 13 11 16 17 活动 V1-V2 V1-V3 V2-V4 V3-V4 V3-V5 V4-V6 V6-V5 V5-V7 V6-V8 V7-V8 最早开始时间 0 0 2 3 3 7 11 13 11 16 最晚开始时间 0 0 2 4 3 7 11 13 11 16 时间余量 0 0 0 1 0 0 0 0 0 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)算法的实现如下: f { //链表结点的结构定义 ElemT //结点数据
* //结点链接指针 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~13 ~ } * int nkList L,int n){ //本算法判断带头结点的单链表是否是中心对称 Stack k(s); //初始化栈
*q,*p=L-> //q 指向出栈元素,p 工作指针 t i=1;i } if(n%2==1) p=p-> //若n为奇数,需要特殊处理 while(p!=null){ //后一半表依次和前一半表比较 q=pop(s); //出栈一个结点 if(q->data==p->data) p=p->//相等则继续比较下一个结点 //不等则跳出循环 } if(empty(s)) return 1; //栈空,则说明对称 else return 0; //否则不对称 } (3)算法的时间复杂度为 O(n),空间复杂度为 O(n). 43. 【分析】本题考查数据通路和指令执行过程.读者应牢固掌握指令的执行过程和原理,并能根据指令 的执行过程和特点了解控制器中各个寄存器的连接方式. 【解答】 (1)b 单向连接微控制器,由微控制器的作用不难得知 b 是指令寄存器(IR) ;a 和c直接连 接主存,只可能是 MDR 和MAR,c 到主存是单向连接,a 和主存双向连接,根据指令执行的特点,MAR 只单向给主存传送地址,而MDR 既存放从主存中取出的数据又要存放将要写入主存的数据,因此 c 为主 存地址寄存器(MAR) ,a 为主存数据寄存器(MDR) .d 具有自动加 1 的功能,且单向连接 MAR,不难 得出为程序计数器(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, ,R→M(MAR). 44. 【分析】本题考查中断处理次序.中断响应次序和中断处理次序是两个不同的概念.中断响应次序也 称为硬件排队次序,它是不可改变的.在不改变硬件排队电路的前提下,可以通过改变中断屏蔽字来改变 中断处理的优先级,使原来级别较低的中断源变成较高的级别. 【解答】 (1)由题意,可知中断处理的次序为 C>A>D>B.屏蔽码中的"1"表示屏蔽该中断源的中断请 求,"0"表示没有屏蔽,各中断服务程序的屏蔽码如下表所示. 中断源 中断屏蔽码 A B C D A 1 1 0 1 B 0 1 0 0 C 1 1 1 1 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~14 ~ D 0 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的值取决于ount=m2的执行先后次序,若前者先执行,则最后 amount的值为10, 若后者先执行, 则最后amount的值为30. 因此, 最后账号amount上面可能出现的值有10、 20、30. (2)在上述问题中,共享变量amount是一个临界资源,为了实现两并发进程对它的互斥访问,可为 它设置一初值为1的互斥信号量mutex,并将上述算法修改为: ount=0; tex=1; //互斥访问amount变量的信号量 { s SAVE(){ int m1; P(mutex); m1=m1+10; amount=m1; V(mutex); } s TAKE(){ int m2; P(mutex); m2=m2-10; amount=m2; V(mutex); } 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~15 ~ } coend 46. 【分析】本题考查磁盘的性能分析及优化. 【解答】(1)每分钟6000转,则旋转1周所需的时间为10ms,旋转1个记录需10/9ms. A B C D E F G H I 1 2 3 4 5 6 7 8 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 H F D B I G E C 1 2 3 4 5 6 7 8 9 此时,读出整个文件需要的时间为(4*10/9)*8+1.11+2.5=39.16ms. 47. 【分析】本题考查路由器地址分配的一般原则、路由表的结构、子网划分和子网掩码.首先应根据题 意给出局域网 A和局域网B 的子网, 这里局域网 A的编号为01, 也就是202.38.60., 即202.38.60.64, 一般选择该网络最小的地址分配给路由器的接口 a,即201.38.60.,即202.38.60.65,子网掩码为 255.255.255.192.同理局域网 B 的子网编号为 10,202.38.60.,即202.38.60.128,接口 b 的地址为 202.38.60.,即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., 即202.38.60.191, 对于局域网 C, 就是标准的 202.38.61.255. 【解答】 (1)路由器 a 202.38.60.65 255.255.255.192 路由器 b 202.38.60.129 255.255.255.192 路由器 c 202.38.61.1 255.255.255.0 路由器 d 61.60.21.80 255.0.0.0 可知,局域网 A 的子网掩码为 255.255.255.192;局域网 B 的子网掩码为 255.255.255.192;局域网 C 的子网掩码为 255.255.255.0. (2)路由器的路由表如下: 目的网络地址 子网掩码 下一跳地址 接口 202.38.60.64 255.255.255.192 直接 a 202.38.60.128 255.255.255.192 直接 b 202.38.61.0 255.255.255.0 直接 c 61.0.0.0 255.0.0.0 直接 d 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~16 ~ 0.0.0.0 0.0.0.0 61.60.21.80 d (3)202.38.60.191. (4)202.38.61.255. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~17 ~ 王道计算机统考模拟试题 一、单项选择题:第1~40 小题,每小题 2 分,共80 分.下列每题给出的四个选项中,只有一个选 项最符合试题要求. 1. 一个栈的输入序列为 1,2,3,…,n,输出序列的第一个元素是 i,则第 j 个输出元素是( ). A.i-j-1 B. i-j C.j-i+1 D.不确定 2. 执行( )操作时,需要使用队列作为辅助存储空间. A.查找哈希表 B.广度优先搜索图 C.前序(根)遍历二叉树 D.深度优先搜索图 3. 有n个结点,并且高度为 n 的二叉树的数目为( ). A.log2n B.2n C.n D.2n-1 4. 在常用的描述二叉排序树的存储结构中,关键字值最大的结点是( ). A. 左指针一定为空 B. 右指针一定为空 C. 左右指针均为空 D. 左右指针均不为空 5. 含有 20 个结点的平衡二叉树的最大深度为( ). A. 4 B. 5 C. 6 D. 7 6. 设无向图 G=(V,E)和G'=(V',E'),如果 G'是G的生成树,则下面说法错误的是( ) . A. G'是G的子图 B. G'是G的连通分量 C. G'是G的极小连通子图且 V=V' D. G'是G的一个无环子图 7. 在有向图 G 的拓扑序列中,若顶点 Vi 在顶点 Vj 之前,则下列情形不可能出现的是( ) . A.G 中有弧 B.G 中有一条从 Vi 到Vj 的路径 C.G 中没有弧 D.G 中有一条从 Vj 到Vi 的路径 8. 具有 12 个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的 平 均查找长度依次为( ) . A. 37/12,49/13 B. 35/12,39/13 C. 37/13,49/13 D. 37/12,49/12 9. 对关键字序列{23,17,72,60,25,8,68,71,52}进行堆排序,输出两个最小关键字后的剩余堆是 ( ) . A.{23,72,60,25,68,71,52} B.{23,25,52,60,71,72,68} C.{71,25,23,52,60,72,68} D.{23,25,68,52,60,72,71} 10. 对n个关键字进行快速排序,最大递归深度和最小递归深度分别为( ) . A. nlog2n、log2n B. n、log2n C. nlog2n、n D. n2 、log2n 11. 下列排序方法中,时间性能与待排序记录的初始状态无关的是( ) . A.插入排序和快速排序 B.归并排序和快速排序 C.选择排序和归并排序 D.插入排序和归并排序 12. 以下有关计算机运算速度衡量指标的描述中,正确的是( ) . A. MIPS 大的机器一定比 MIPS 小的机器快 B. CPU 的主频越高速度越快 C. 执行不同的程序,测得的同一台计算机的 CPI 可能不同 D. CPU 执行程序的时间就是观测到用户程序的执行时间 13. 对于相同位数(设为 N 位,且各包含 1 位符号位)的二进制补码小数和十进制小数,二进制小数 能表示的数的个数/十进制小数所能表示的个数为( ) . A.(0.2)N B. (0.2)N-1 C. (0.02)N D.(0.02)N-1 14. 下列关于机器零的说法,正确的是( ) . A. 发生"下溢"时,浮点数被当做机器零,机器将暂停运行,转去处理"下溢" B. 只有以移码表示的阶码时,才能用全 0 表示机器零的阶码 C. 机器零属于规格化的浮点数 第5套予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~18 ~ D. 定点数中的零也是机器零 15. 下列的说法中,正确的是( ) . I.双端口存储器可以同时访问同一区间、同一单元 II.双端口存储器当两个端口的地址码相同时,必然会发生冲突 III.高位多体交叉存储器的设计依据了程序的局部性原理 IV.高位四体交叉存储器可能在一个存储周期内连续访问四个模块 A. I和III B. II和III C.I和IV D.只有I 16. 假定用若干个8K* 8位的芯片组成一个32K* 32位的存储器,则地址41F0H所在芯片的最大地址是 ( ) . A. 0000H B. 4FFFH C. 5FFFH D. 7FFFH 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 的中断向量表(中断向量表存放中段向量)的指针是 H 单元中的值为 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 和VB. I 和IV C. I D. II 和III 23. 当中断发生后,进入中断处理的程序属于( ) . A.用户程序 B.可能是用户程序,也可能是 OS 程序 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~19 ~ C.OS 程序 D.单独的程序,即不是用户程序也不是 OS 程序 24. 下列关于进程和线程的叙述中,正确的是( ) . I. 一个进程可包含多个线程,各线程共享进程的虚拟地址空间 II. 一个进程可包含多个线程,各线程共享栈 III. 当一个多线程进程中某个线程被阻塞后,整个进程都将被阻塞 IV. 当一个多线程进程中某个线程被阻塞后,该阻塞进程将被撤销 A.I、II、III B.I、III C.II、III D.II、IV 25. 现有 4 个作业 J1,J2,J3,J4,它们的提交时间和运行时间如下表所示,系统按单道方式运行且采用短作 业优先算法,则平均周转时间是( ) . 作业号 提交时间 运行时间 J1 8 2 J2 8.4 1 J3 8.8 0.5 J4 9 0.2 A. 2.5 B. 2.1 C. 0.925 D. 2 26. 有两个优先级相同的并发程序 P1 和P2,它们的执行过程如下所示,假设,当前信号量 s1=0,s2=0. 当前的 z=2,进程运行结束后,x、y 和z的值分别是( ) . 进程 P1 进程 P2 … … y:=1; x:=1 y:=y+2; x:=x+1; z:=y+1; P(s1); V(s1); x:=x+y; P(s2); z:=x+z; y:=z+y; V(s2); … … … … A. 5,9,9 B. 5,9,4 C. 5,12,9 D. 5,12,4 27. 假设系统有 5 个进程,A、B、C 三类资源.某时刻进程和资源状态如下: n ble A B C A B C A B C P1 2 1 2 5 5 9 2 3 3 P2 4 0 2 5 3 6 P3 4 0 5 4 0 11 P4 2 0 4 4 2 5 P5 3 1 4 4 2 4 下面叙述正确的是( ) . A. 系统不安全 B. 该时刻,系统安全,安全序列为 C. 该时刻,系统安全,安全序列为 D. 该时刻,系统安全,安全序列为 28. 下列关于页式存储的说法中,正确的是( ) . I.在页式存储管理中,若关闭 TLB,则每访问一条数据都要访问 2 次内存. II.页式存储管理不会产生内部碎片 III.页式存储管理当中的页面是用户可以感知的 IV.页式存储方式可以采用静态重定位 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~20 ~ A.I、II 和IV B.I 和IV C.I D.I 和III 29. 在虚拟分页存储管理系统中,若进程访问的页面不在主存,且主存中没有可用的空闲帧时,系统 正确的处理顺序为( ) . A.决定淘汰页 -> 页面调出 -> 缺页中断 -> 页面调入 B.决定淘汰页 -> 页面调入 -> 缺页中断 -> 页面调出 C.缺页中断 -> 决定淘汰页 -> 页面调出 -> 页面调入 D.缺页中断 -> 决定淘汰页 -> 页面调入 -> 页面调出 30. 若用 8 个字(字长 32 位,且字号和位号都从 0 开始计数)组成的位示图管理内存,假定用户归 还一个块号为 100 的内存块时,它对应位示图的位置为( ) . A.字号为 3,位号为 5 B.字号为 4,位号为 4 C.字号为 3,位号为 4 D.字号为 4,位号为 5 31. 假如一个 FCB 块的大小是 64 字节.盘块的大小为 1KB,则在每个盘块中能存放的最大 FCB 数是 ( ) . A. 64 B. 1 C. 1000 D. 16 32. 下列关于设备独立性的论述中,正确的是( ) . A. 设备独立性是 I/O 设备具有独立执行 I/O 功能的一种特性 B. 设备独立性是指用户程序独立于具体使用的物理设备的一种特性 C. 设备独立性是指独立实现设备共享的一种特性 D. 设备独立性是指设备驱动独立于具体使用的物理设备的一种特性 33. 对于可靠服务和不可靠服务,正确的理解是( ) . A. 可靠服务是通过高质量的连接线路来保证数据可靠传输 B. 如果网络本身是不可靠的,那么用户只能尝试使用并无更好的办法 C. 可靠性是相对的,不可能完全保证数据准确传输到目的地 D. 对于不可靠的网络,可以通过应用或用户来保障数据传输的正确性 34. 一个传输数字信号的模拟信道的信号功率是0.62W, 噪音功率是0.02W, 频率范围是3.5-3.9MHz, 该信道的最高数据传输速率是( ) . A. 1Mbps B. 2Mbps C. 4Mbps D. 8Mbps 35. 在CSMA/CD 协议中,下列指标与冲突时间没有关系的是( ) . A.检测一次冲突所需要的最长时间 B.最小帧长度 C.最大帧长度 D.最大帧碎片长度 36. 用以太网交换机连接的一组工作站( ) . A.同属于一个冲突域,但不属于一个广播域 C.不属于一个冲突域,也不属于一个广播域 C.不属于一个冲突域,但同属于一个广播域 D.同属于一个冲突域,也同属于一个广播域 37. 一台主机的 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 38. 设有以下 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 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~21 ~ 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. 一台域名服务器希望解析域名 ,如果这台主机配置的 DNS 地址为
的 根域名服务器为 b,而存储域名
与其 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 23A0H 23A0H H 2400H 23BAH FH 2500H (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).试问: 进程 最大资源需求量 已分配资源数量 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 (1)系统是否处于安全状态?如安全,请给出一个安全序列. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~22 ~ (2)如果此时 P1 和P2 均发出资源请求向量 t(1,0,1),为了保证系统的安全性,应该如何分配 资源给这两个进程?说明你所采用策略的原因. (3)如果(2)中两个请求立即得到满足后,系统此刻是否处于死锁状态. 46. (7分)设一个没有设置快表的虚拟页式存储系统,页面大小为100字节.一个仅有460个字节的程序 有下述内存访问序列(下标从0开始):10、11、104、170、73、309、185、245、246、434、358、 364,为该程序分配有2个可用页帧(ame).试问: (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 的确认报文中的确认号应该是多少? 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~23 ~ 第5套 答案与解析 一、单项选择题 1. 【分析】 【单科书 P53】本题考查出栈序列的特征.若输出序列的第一个元素是 i,则只能说明前面 i-1 个元素均已入栈,而第 j 个出栈元素的序号却无法确定.若假设输出序列的第一个元素是 n,则能否确定 第j个输出元素的序号,请读者仔细思考. 【解答】D.当第 i 个元素第一个出栈时,则i之前的元素可以依次排在 i 之后出栈,但剩余的元素可 以在此时进栈并且也会排在 i 之前的元素出栈,所以第 j 个出栈的元素是不确定的. 2. 【分析】 【单科书 P66 等】本题考查队列的应用.队列通常应用在需要逐层或逐行的问题,以保存下 一步的处理顺序,以及应用于缓冲区、OS 调度等. 【解答】B.图的广度优先搜索类似于树的层序遍历(形象地想象成一个扇形,以搜索起点为中心, 逐层向相连的外圈搜索) ,同样需要借助于队列.前序遍历二叉树是一个递归的过程,通常可以借助于栈, 将递归算法转换为非递归算法.图的深度优先搜索类似于树的前序遍历,也是一个递归的过程,通常也可 以借助栈来实现. 3. 【分析】 【单科书 P89】考查二叉树的性质.若将二叉树的左、右子树颠倒,就成为另一棵不同的二叉 树.即使树中结点只有一棵子树,也要区分它是左子树还是右子树. 【解答】D.由题可得,每层有一个结点,从根结点往下,每个结点都有做左孩子右孩子两种情况, 由概率知识可得,二叉树共有 2n-1 种树形. 【另解】画草图.n 个结点且高度为 n 的二叉树中,相邻层(每层一个结点)之间有一条边,共有 n-1 条.每条边既可以指向左也可以指向右,共有 2n-1 种指法,对应 2n-1 种树形. 4. 【分析】 【单科书 P109】本题考查二叉排序树的性质.二叉排序树中关键字值大小关系为:左子树< 根结点决定淘汰页->页面调出->页面调入. 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 数为 . 32. 【分析】 【单科书 P247】本题考查设备独立性的定义. 【解答】B.设备独立性的定义就是指用户程序独立于具体物理设备的一种特性,引入设备的独立性 是为了提高设备分配的灵活性和设备的利用率等. 33. 【分析】 【单科书 P12】本题考查对可靠服务和不可靠服务的理解.在网络的传输过程中,数据出错是 很难避免的,只有通过检错、纠错、应答机制才能保证数据正确地传输,这种数据传输是可以准确地到目 的地的. 【解答】D.不可靠服务是出于速度、成本等原因的考虑,而忽略了应该有的数据传输的保证机制, 但是可以通过应用或用户判断数据的准确性, 再通知发送方采取措施, 从而把不可靠的服务变为可靠服务. 34. 【分析】 【单科书 P27】本题考查奈氏定理的应用.题干已说明是有噪声的信道,因此应联系到香农定 理,而对于无噪声的信道,则应联系到奈奎斯特定理.奈奎斯特就是在采样定理和无噪声的基础上,提出 了奈氏准则:Cmax=f 采样*log2N=2f*log2N,其中 f 表示带宽.而香农公式给出了有噪声信道的容量: 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~27 ~ Cmax=W* log2(1+S/N),其中 W 为信道的带宽.它指出,想提高信息的传输速率,应设法提高传输线路的带 宽或者设法提高所传信号的信噪比. 【解答】B.首先计算信噪比 S/N=0.62/0.02=31;带宽 W=3.9-3.5=0.4MHz,由香农公式可知最高数据 传输率 V=W* log2(1+S/N)=0.4* log2(1+31)=2Mbps. 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→→→→.显然,这四个数字只有前五位是完全 相同的,因此汇聚后的网络的第三个字节应该是 8.聚合后的网络的掩码中 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.链地址法构造的表如下: 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~28 ~ (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)算法的实现如下: t A[],int m,int n){ ElemT //辅助变量,暂存待插入元素 t i=m+1;i=1&&temp R1 SUB R4,R1,R5 # R1-R5 -> R4 两条指令在流水线中执行情况如下表所示: 时钟 指令 1 2 3 4 5 6 7 ADD 取指 指令译码 并取数 运算 写回 SUB 取指 指令译码 并取数 运算 写回 ADD 指令在时钟 4 时将结果写入寄存器堆(R1),但SUB 指令在时钟 3 时读寄存器堆(R1).本来 ADD 指令应先写入 R1,SUB 指令后读 R1,结果变成 SUB 指令先读 R1,ADD 指令后写 R1,因而发生两条指 令间数据相关.如果硬件上不采取措施,第2条指令 SUB 至少应推迟 2 个操作时钟周期(2* 100ns) ,即将 SUB 指令中的指令译码并取数阶段推迟到 ADD 指令的写回阶段之后才能保证不会出错.如下表所示: 时钟 指令 1 2 3 4 5 6 7 ADD 取指 指令译码 并取数 运算 写回 SUB 取指 指令译码 并取数 运算 写回 (3)如果硬件上加以改进,可只延迟 1 个操作时钟周期(100ns) .因为在 ADD 指令中,运算阶段就 已经得到结果了, 因此可以通过数据旁路技术在运算结果一得到的时候将结果快速送入寄存器 R1, 而不需 要等到写回阶段完成.流水线中执行情况如下图所示: 时钟 指令 1 2 3 4 5 6 7 ADD 取指 指令译码 并取数 运算 (并采用数据旁路技 术写入寄存器 R1) 写回 取指 SUB 取指 指令译码并 取数 运算 写回 45. 【分析】本题考查采用银行家算法避免死锁. 【解答】(1)利用安全性算法对时刻的资源分配情况进行分析,可得到如下表所示的安全性检测情 况.可以看出,此时存在一个安全序列{P2,P3,P4,P1},故该系统是完全的. 进程 Work n Work +
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P2 2 1 2 2 0 2 4 1 1 6 2 3 True P3 6 2 3 1 0 3 2 1 1 8 3 4 True P4 8 3 4 4 2 0 0 0 2 8 3 6 True 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~30 ~ P1 8 3 6 2 2 2 1 0 0 9 3 6 True (2)若此时P1发出资源请求t1(1,0,1),按银行家算法进行检查: t1(1,0,1) ≤ Need1(2,2,2) t1(1,0,1) ≤ ble(2,1,2) 试分配并修改相应的数据结构,由此形成的资源分配情况如下表所示: 进程 n ble R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 1 1 2 1 1 1 1 P2 4 1 1 2 0 2 P3 2 1 1 1 0 3 P4 0 0 2 4 2 0 再利用安全性算法检查系统是否安全,可用资源ble(1,1,1)已不能满足任何进程,系统进入不安 全状态,此时系统不能将资源分配给P1. 若此时P2发出资源请求t2(1,0,1),按银行家算法进行检查: t2(1,0,1) ≤ Need2(2,0,2) t2(1,0,1) ≤ ble(2,1,2) 试分配并修改相应的数据结构,由此形成的资源分配情况如下表所示: 进程 n ble R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 1 0 0 2 2 2 1 1 1 P2 5 1 2 1 0 1 P3 2 1 1 1 0 3 P4 0 0 2 4 2 0 再利用安全性算法检查系统是否安全,安全性检查情况如下表所示.可以看出,此时存在一个安全序 列{P2,P3,P4,P1},故该状态是完全的,可立即给P2申请的资源分配给它. 进程 Work n Work +
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P2 1 1 1 1 0 1 5 1 2 6 2 3 True P3 6 2 3 1 0 3 2 1 1 8 3 4 True P4 8 3 4 4 2 0 0 0 2 8 3 6 True P1 8 3 6 2 2 2 1 0 0 9 3 6 True (3)如果(2)中两个请求立即得到满足,此刻系统并没有立即进程死锁状态,因为这时所有进程没 有提出新的资源申请, 全部进程均没有因资源请求没得到满足而进入阻塞状态. 只有当进程提出资源请求, 且全部进程都进入阻塞状态时,系统才处于死锁状态. 46. 【分析】本题考查缺页中断和页面置换算法. 【解答】(1)缺页中断是一种特殊的中断,它与一般中断的区别是:①在指令执行期间产生和处理 中断信号.CPU通常在一条指令执行完后检查是否有中断请求,而缺页中断是在指令执行时间,发现所要 访问的指令或数据不在内存时产生和处理的;②一条指令在执行期间可能产生多次缺页中断.如一条读取 数据的多字节指令,指令本身跨越两个页面,若指令后一部分所在页面和数据所在页面均不在内存,则该 指令的执行至少产生两次缺页中断. (2)每个页面大小为100字节,则页面的访问顺序如下: 10 11 104 170 73 309 185 245 246 434 458 364 0 0 1 1 0 3 1 2 2 4 4 3 采用FIFO算法的页面置换情况如下表,共产生缺页中断6次. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~31 ~ 走向 0 0 1 1 0 3 1 2 2 4 4 3 块号1 0 0 1 1 1 3 3 2 2 4 4 3 块号2 0 0 0 1 1 3 3 2 2 4 淘汰 0 1 3 2 缺页
采用LRU算法的页面置换情况如下表,共产生缺页中断7次. 走向 0 0 1 1 0 3 1 2 2 4 4 3 块号1 0 0 1 1 0 3 1 2 2 4 4 3 块号2 0 0 1 0 3 1 1 2 2 4 淘汰 1 0 3 1 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. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~32 ~ 王道计算机统考模拟试题 一、单项选择题:第1~40 小题,每小题 2 分,共80 分.下列每题给出的四个选项中,只有一个选 项最符合试题要求. 1. 若已知一个栈的入栈序列是 1,2,3,4.其出栈序列为 p1,p2,p3,p4,则p2,p4 不可能是( ). A.2、 4 B.2、 1 C.4、 3 D.3、 4 2. 在链式队列的出队操作中,需要修改尾指针的情况发生在( ). A.队列为空队列时 B.变成满队列的时候 C.队列只剩一个元素的时候 D.任何时候 3. 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( ). A.250 B.500 C.254 D.501 4. 由某种序列可以唯一的确定一棵二叉树,不能唯一的确定一棵二叉树是( ). A.先序序列和中序序列 B.后序序列和中序序列 C.中序序列和层序序列 D.先序序列和层序序列 5. 分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ). A. (100,80, 90,60,120,110,130) B. (100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D. (100,80, 60, 90,120,130,110) 6. 由4棵树组成的森林中,第一、第二、第三和第四棵树中的结点数分别为 30、10、20、5,当把森林 转换成二叉树后,对应二叉树中根结点的右子树的左子树的结点数为( ). A. 29 B. 9 C. 25 D. 19 7. 如果具有 n 个顶点的图是一个环,则它有( )棵生成树. A.n2 B.n C.n-1 D.1 8. 如右图所示,在下面的 5 个序列中,符合深度优先遍历的序列有多少个( ) . 1. aebfdc 2. b 3. aedfcb 4. aefdbc 5. aecfdb A.5 B.4 C.3 D.2 9. 在一棵含有 n 个关键字的 m 阶B-树中进行查找,至多需要读盘( )次(假设 读一次盘就能将整个结点取出) . A.log2n B.1+log2n C.1+log m/2 [(n+1)/2] D. 1+log n/2 [(m+1)/2] 10. 一组数据(30,20,10,15,35,1,10,5),用堆排序(小顶堆)的筛选方法建立的初始堆为( ). A.1,5,15,20,35,10,30,10 B.1,10,30,10,5,15,35,20 C.1,5,10,15,35,30,10,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 B. 15,25,35,50,20,40,80,85,36,70 C. 15,25,50,35,80,85,20,36,40,70 D. 15,25,35,50,80,20,36,40,70,85 12. 对汇编语言程序员来说,以下部件中不透明的是( ) . I. 指令缓冲器 II. 移位器 III. 通用寄存器 IV. 中断字寄存器 V. 乘法器 VI. 先行进位链 A.I、II 和III B.IV、V 和VI C. III 和IV D. I、II、V 和VI 13. 在补码表示的机器中,若寄存器 R 中原存的数为 9EH,执行一条指令后现存的数为 CFH,则表明该 指令不可能是( ) A.XOR 异或运算指令 B.IMUL 有符号数乘法指令 C.SAR 算术右移指令 D.ADD 加法指令 14. 已知 C 程序中,某类型为 int 的变量 x 的值为-1088.程序执行时,x 先被存放在 16 位寄存器 R1 中, 第6套予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~33 ~ 然后被进行算术右移 4 位的操作.则此时 R1 中的内容(以十六进制表示)的是( ) . A. FBC0H B. FFBCH C. 0FBCH 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 D.F7H 18. 下列部件不属于控制器的是( ) . A.指令寄存器 B.程序计数器 C.程序状态字寄存器 D.时序电路 19. 已知一台时钟频率为 2GHz 的计算机的 CPI 为1.2.某程序 P 在该计算机上的指令条数为 4* 109 .若在 该计算机上,程序 P 从开始启动到执行结束所经历的时间是 4s,则运行 P 所用 CPU 时间占整个 CPU 时间的百分比大约是( ) . A. 40% B. 60% C. 80% D. 100% 20. 下列计算机总线是串行总线的是( ) . A.PCI B.USB C.EISA D.ISA 21. 某机有四级中断,优先级从高到低为 1→2→3→4.若将优先级顺序修改,改后 1 级中断的屏蔽字为 1101,2 级中断的屏蔽字为 0100,3 级中断的屏蔽字为 1111,4 级中断的屏蔽字为 0101,则修改后的 优先顺序从高到低为( ) . A.1→2→3→4 B.3→1→4→2 C.1→3→4→2 D.2→1→3→4 22. 外部设备打印机适合于连接的通道是( ) . A. 数组多路通道 B. 字节多路通道 C. 选择通道 D. 任意一种通道 23. 并发进程运行时,其推进的相对速度是( ) . A. 由进程的程序结构决定 B. 由进程自己的代码控制 C. 与进程调度策略有关 D. 在进程创建时确定的 24. ( )调度算法有利于 CPU 繁忙型的进程,而不利于 I/O 繁忙型的进程 A. 时间片轮转 B. 先来先服务 C. 短进程优先 D. 优先级调度 25. 对于两个并发进程,设互斥信号量为 mutex,若mutex=0,则表示( ) . A. 没有进程进入临界区 B. 有一个进程进入临界区 C. 有一个进程进入临界区,另一个进程等待进入 D. 有一个进程在等待进入 26. 利用银行家算法进行安全序列检查时,不需要的参数是( ) . A. 系统资源总数 B. 满足系统安全的最少资源数 C. 用户最大需求数 D. 用户已占有的资源数 27. 下列哪些存储分配方案可能使系统抖动, ( ) . I.动态分区分配 II.简单页式 III.虚拟页式 IV.简单段页式 V.简单段式 VI.虚拟段式 A. I、II 和VB. III 和IV C. 只有 III D.III 和VI 28. 一个 64 位的计算机系统中,地址线宽为 64 位,实际使用的虚拟地址空间的大小是 248 ,若采用虚拟 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~34 ~ 页式存储管理,每页的大小为 213 ,即8KB,页表表项长为 8 字节,采用多级页表进行管理,那么多 级页表的级次最小是( ) . A. 3 B. 4 C. 5 D. 6 29. 对外存对换区的管理应以( )为主要目标. A. 提高系统吞吐量 B. 提高存储空间的利用率 C. 降低存储费用 D. 提高换入、换出速度 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. 对等层协议 C. 服务原语 D. 电信号 34. 现采用调相和调幅相结合的调制方式,载波有四种相位变化和两种幅度变化,调制速率是 600 波特, 那么数据速率是( ) . A.1200 bps B. 1800 bps C. 2400 bps D. 3600 bps 35. 设待传送数据总长度为 L 位,分组长度为 P 位,其中头部开销长度为 H 位,源结点到目的结点之间的 链路数为 h, 每个链路上的延迟时间为 D 秒, 数据传输率为 B bps, 电路交换建立连接的时间为 S 秒, 则电路交换方式传送完所有数据需要的时间是( ) . A.hD+L/B 秒B. S+hD+L/B 秒C. S+hD+PL/((P-H)B)秒D. S+L/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 的端口没有本质区别,它们互不干扰,不能共存于同一台主机 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~35 ~ 39. 一个长度为 3000 字节的 UDP 数据报.在数据链路层使用以太网来进行传输,为了正确传输,则需要 将其拆分成( )个IP 数据片. A.2 B.3 C.4 D.不拆分 40. 下列哪种技术可以最有效地降低访问 WWW 服务器的时延( ) . A. 高速传输线路 B. 高性能 WWW 服务器 C. WWW 高速缓存 D. 本地域名服务器 二、综合应用题:第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* 2 的ROM 芯片; 5000H~67FFH 为RAM 区,选用 2K* 4 的SRAM 芯片.请问: (1)组成该存储器需要多少片 ROM 芯片和 SRAM 芯片? (2)ROM 芯片、SRAM 芯片各需连接 CPU 的哪几根地址线和数据线? (3)应如何设置片选信号,分别写出各片选信号的逻辑表达式. 45. (7分)系统有5个进程,其就绪时刻(指在该时刻已进入就绪队列)、服务时间如下表所示.分 别计算采用先来先服务、短作业优先、高响应比优先的平均周转时间和带权周转时间. 进程 就绪时刻 服务时间 P1 0 3 P2 2 6 P3 4 4 P4 6 5 P5 8 2 46. (8 分)有一文件系统如图 1 所示.根目录常驻内存,目录文件组织成链接文件,不设文件控制 块,普通文件组织成索引文件.目录表目指示下一级文件名及其磁盘地址(各占 2 个字节,共4个字节) .若下级文件是目录文件,指示其第一个磁盘块地址.若下级文件是普通文件,指示其 文件控制块的磁盘地址.每个目录文件磁盘块的最后 4 个字节供拉链使用.下级文件在上级目录 文件中的次序在图中为从左至右.每个磁盘块有 512 字节,与普通文件的一页等长. 予人玫瑰 手留余香 王道 2012 年最后 6 套模拟试题 第4~6 套~36 ~ 图1图2普通文件的文件控制块组织如图 2 所示,其中,每个磁盘地址占 2 个字节,前10 个地址直接指 示该文件前 10 页的地址.第11 个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文 件页地址;第12 个地址指示二级索引表地址,二级