1、计算机专业（基础综合）模拟试卷 94 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在双链表中 p 所指的结点之前插入一个结点 q 的操作为( )。（A）pprior=q；qnext=p；ppriornext=q； qprior=pprior；（B） qprior=pprior ； ppriornext=q；qnext=p；pprior=qnext；（C） qnext=p ；pnext=q；qpriornext=q；qnext=p ；（D）ppriornext=q；qnext=p ；qpriorprior；
2、pprior=q；2 下列关于链式栈的叙述中，错误的是( )。链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取因为链式栈没有栈满问题，所以进行进栈操作，不需要判断任何条件在链式队列的出队操作中，需要修改尾指针的情况发生在空队列的时候（A）仅（B）仅 、（C）仅 （D）、3 设有一个二维数组 Amn在存储中按行优先存放（数组的每一个元素占一个空间），假设 A00存放位置在 780clo)，A46存放位置在 1146(10)则 A620在( )位置(其中(10) 表明用十进制数表示）。（A）1342 (10)（B） 1336(10)（C） 1338(10)（D）1340 (10)4 棵二叉
3、树的前序遍历序列为 1234567，则它的中序遍历序列不可能是( )。3124567123456741356271436572（A）仅、（B）仅 、（C）仅 、（D）仅、5 宽度为 27，高度为 4 的满 N 叉树总共有( )个结点。（A）27（B） 40（C） 85（D）976 对于一棵具有 n 个结点、度为 4 的树来说（树的层数从 1 开始），以下说法正确的是( )。树的高度至多为 n3至少在某一层上正好有 4 个结点第 i 层上至多有 4（i 一 1）个结点（A）仅（B）仅 、（C）仅 （D）仅、7 以下有关拓扑排序的说法中，错误的是( )。如果某有向图存在环路，则该有向图一定不存在拓
4、扑排序在拓扑排序算法中，既可以使用栈，也可以使用队列若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1（A）仅、（B）仅 、（C）仅 （D）仅8 无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有( )个顶点。（A）11（B） 12（C） 15（D）169 图 81 是一棵( ) 。（A）4 阶 B树（B） 4 阶 B+树（C） 3 阶 B树（D）3 阶 B+树10 如果一台计算机具有多个可并行运行的 CPU，就可以同时执行相互独立的任务。归并排序的各个归并段的归并也可并行执行，因此称归并排序是可并行执行
5、的。那么以下的排序方法不可以并行执行的有( )。基数排序快速排序起泡排序堆排序（A）仅、（B）仅 、（C）仅 、（D）仅、11 在进行外部排序的 m 路平衡归并排序的过程中，需设置 ( )个输入缓冲区，才能实现输入、内部归并、输出等操作的并行。（A）2（B） m（C） 2m1（D）2m12 已知定点整数 x 的原码为 1Xn1Xn2Xn3X0，且 x2 n1，则必有( )。（A）X n1=0（B） Xn1=1（C） Xn1=0，且 X0X n2 不全为 0（D）X n1=1，且 x0X n2 不全为 013 在原码一位乘中，当乘数 Yi 为 1 时，( )。（A）被乘数连同符号位与原部分积相加
6、后，右移一位（B）被乘数绝对值与原部分积相加后，右移一位（C）被乘数连同符号位右移一位后，再与原部分积相加（D）被乘数绝对值右移一位后，再与原部分积相加14 假定主存按字节编址，Cache 共有 64 行，采用 4 路组相联映射方式，主存块大小为 32 字节，所有编号都从 O 开始，则主存第 3000 号单元所在主存块对应的Cache 组号是 ( )。（A）1（B） 5（C） 13（D）2915 如图 82 所示，若低位地址(A 0A 11)接在主存芯片地址引脚上，高位地址(A12 A19)进行片选译码（其中 A14 和 A16 没有参加译码），且片选信号低电平有效，则对图 82 所示的译码器
7、，不属于其译码空间的地址为( )。（A）ABOOOHABFFFH（B） BBOOOHBBFFFH（C） EFOOOHEFFFFH（D）FEOOOHFEFFFH16 在计算机体系结构中，CPU 内部包括程序计数器(PC)、存储器数据寄存器(MDR)、指令寄存器(IR) 和存储器地址寄存器(MAR)等。若 CPU 要执行的指令为MOV X，#10（即将数值 10 传送到寄存器 X 中），则 CPU 首先要完成的操作是( )。（A）100RO（B） 100MDR（C） PCMAR（D）PCIR17 假设某计算机的指令长度为 20 位，具有双操作数、单操作数和无操作数三种指令形式，每个操作数地址规定用
8、 6 位表示，若操作码字段不固定，现已给出 m 条双操作数指令，n 条无操作数指令。在此情况下，这台计算机最多可以设计出( )条单操作数指令。（A）2 8mn（B） 212mn（C） (28m)212n（D）(2 8m)212n/2618 流水线中有 3 类数据相关冲突：写后读相关、读后写相关、写后写相关。那么下列 3 组指令中存在读后写相关的是( )。I: I1 SUB R1，R2，R3； (R2)(R3)R112 ADD R4，R5，R1 ； (R5)+(R1)R4: I1 STA M，R2 ； (R2)M，M 为主存单元12 ADD R2，R4，R5 ； (R4)+(R5)R2: I1
9、MUL R3，R2，R1； (R2)(R1)R312 SUB R3，R4，R5 ； (R4)(R5)R3（A）仅、（B）仪 （C）仅 、（D）、19 某计算机采用 4 级中断，优先级从高到低分别为 1、2、3、4。若将优先级的顺序修改为 3、1、2、4，则此时 1、2、3、4 级的中断屏蔽字分别为( )。（A）1111、0111、0011、0001（B） 1101、0101、1111、0001（C） 1101、0101、1011、0001（D）1101、1010、1111、000120 下列属于微指令结构设计的目标是( )。提高微程序的执行速度.缩短微指令的长度.增大控制存储器的容量（A）仅、
10、（B）仅 、（C）仅 、（D）、21 下列说法中，正确的是( )。（A）CPU 通过控制单元 CU 来识别信息是地址还是数据（B）间接寻址第一次访问内存所得到的信息经过系统总线的地址总线传送到 CPU（C）单总线结构中，可以不使用 I/O 指令（D）在异步总线中，传送操作由设备控制器控制22 关于总线的叙述，以下正确的是( )。总线忙信号由总线控制器建立计数器定时查询方式不需要总线同意信号链式查询、计数器查询、独立请求方式所需控制线路由少到多排序是：链式查询、独立请求方式、计数器查询（A）仅、（B）仅 、（C）仅 （D）仅23 下列关于系统调用说法中，正确的是( )。当操作系统完成用户请求的“
11、系统调用” 功能后，应使 CPU 从内核态转到用户态工作.用户程序设计时，使用系统调用命令，该命令经过编译后，形成若干参数和屏蔽中断指令.用户在编写程序时计划读取某个数据文件中的 20 个数据块记录，需使用操作系统提供的系统调用接口用户程序创建一个新进程，需使用操作系统提供的系统调用接口（A）仅、（B）仅 、（C）仅 、（D）仅、24 下列关于线程的叙述中，正确的是( )。在采用轮转调度算法时，一进程拥有 10 个用户级线程，则在系统调度执行时间上占用 10 个时间片属于同一个进程的各个线程共享栈空间同一进程中的线程可以并发执行，但不同进程内的线程不可以并发执行线程的切换，不会引起进程的切换（
12、A）仅、（B）仅 、（C）仅 、（D）全错25 在一单道批处理系统中，一组作业的提交时间和运行时间见表 81。以下 3 种作业调度算法的平均周转时间分别是( )。 (1)先来先服务(2)短作业优先 (3)响应比高者优先（A）05、0875、0825（B） 085、0875、0625（C） 085、0675、0825（D）05、0675、062526 设有 10 个进程共享 n 个资源，每次允许 3 个进程同时使用该资源。试问：信号量的变化范围是( ) 。（A）3n 10，3n（B） n10，n（C） n10/3，n（D）3n 10，n27 如果对经典的分页式存储管理策略的页表做细微改造，允许不
13、同页表的页表项指向同一物理页帧，可能的结果有( )。实现对可重入代码的共享只需要修改页表项，就能实现内存“复制” 操作容易发生越界访问实现进程间通信（A）仅、（B）仅 、（C）仅 、（D）仅28 作业在执行中发生缺页中断，经操作系统处理后应让其执行的指令是( )。（A）被中断的前一条（B）被中断的那一条（C）被中断的后一条（D）启动时的第一条29 在一个请求分页系统中，采用 LRU 页面置换算法时，假如一个作业的页面走向为：1、3、2、1、1、3、5、1、3、2、1、5。当分配给该作业的物理块数分别为 3和 4 时，试计算在访问过程中所发生的缺页率是( )。（A）35，25（B） 35，50（
14、C） 50，33（D）50，2530 下面关于目录检索的论述中，正确的叙述是( )。（A）由于 Hash 法具有较快的检索速度，故现代操作系统中都用它来替代传统的顺序检索方法（B）在利用顺序检索法时，对树形目录应采用文件的路径名，且应从根目录开始逐级检索（C）在利用顺序检索法时，只要路径名的一个分量名未找到，便应停止查找（D）在顺序检索法时的查找完成后，即可得到文件的物理地址31 在磁盘文件系统中，对于下列文件物理结构，( )不具有直接读写文件任意一个记录的能力。（A）顺序结构（B）链接结构（C）索引结构（D）散列结构32 下列几种类型的系统中，适合采用忙等待 I/O 的有( )。专门用来控制
15、单 I/O 设备的系统运行一个多任务操作系统的个人计算机作为一个负载很大的网络服务器的工作站（A）仅（B）仅 、（C）仅 、（D）仅、33 个信道每 1/8s 采样一次，传输信号共有 8 种变化状态，则最大的数据传输率是( )。（A）16bit/s（B） 24bit/s（C） 32bit/s（D）48bit/s34 下列协议中，不会发生碰撞的是( )。TDMALOHACSMACDMA（A）仅（B）仅 、（C）仅 、（D）都有可能35 在二进制指数后退算法中，在 16 次碰撞之后，那么站点会在 0( )之间选择一个随机数。（A）1023（B） 2151（C） 2161（D）以上都错误36 个主机
16、有两个 IP 地址，一个地址是 192168 1125，另一个地址可能是( )。192168112192168122519216813251921681425（A）仅、（B）仅 、（C）仅 、（D）仅、37 个信道的数据率为 8000bit/s，单向传播时延为 20ms，要是停止一等待协议的信道利用率达到 50，则帧长至少是( )。（A）80bit（B） 160bit（C） 240bit（D）320bit38 IPv6 地址以 16 进制表示，每 4 个 16 进制数为一组，组之间用冒号分隔，下面的 IPv6 地址 ADBF:0000:FEEA:0000:0000:00EA:00AC:DEED
17、 的简化写法是( )。（A）ADBF:0:FEEA:00:EA:AC:DEED（B） ADBF:0:FEEA:EA:AC:DEED（C） ADBF:0:FEEA:EA:AC:DEED（D）ADBF:FEEA:EA:AC:DEED39 个 TCP 连接下面使用 128kbit/s 的链路，其端到端时延为 32ms。经测试，发现吞吐率只有 60kbit/s。则其发送窗口是( )。（A）904B（B） 906B（C） 452B（D）454B40 域名系统 DNS 的组成包括( )。域名空间分布式数据库域名服务器从内部 IP 地址到外部 IP 地址的翻译程序（A）仅、（B）仅 、（C）仅 、（D）、二
18、、综合应用题41-47 小题，共 70 分。40 设一个整形一维数组里有 n(n1)个整数，在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法，输出所有子数组的和的最大值。例如一维数组中的整数为 1，2，3，10，4，7，2，5，则和最大的子数组为3，10，4，7，2，该子数组的和为 18。要求：41 给出算法的基本设计思想。42 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。43 说明你所设计算法的时间复杂度和空间复杂度。43 已知一个带头结点单链表的结点类型 next
19、Node 定义为 struct nextNodeint data；int freq；struct nextNode *next； ；其中，data 为结点值域，freq 为该结点元素的访问计数，初始为 O；next 为指向链表中该结点后继结点的指针域，设该链表所有结点按照 freq 值从大到小链接。请设计一个时间和空间上尽可能高效的算法，编写一个查找函数 Search，从链表首结点开始查找结点 data 值与给定值相等的结点。如果找到，则将该结点的 freq 值加 1，然后把它前移到与结点 freq 值相等的结点的后面，使得所有结点仍然都保持按照 freq 值从大到小链接。44 给出算法的基本
20、设计思想。45 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。46 说明你所设计算法的时间复杂度与空间复杂度。46 在网络编程中，如果 URL 参数中含有特殊字符，如空格、“#”等，可能导致服务器端无法获得正确的参数值，需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在“ ” 后面跟上 ASC码的两位十六进制的表示。比如空格的ASC码是 32，即十六进制的 020，因此空格被替换为“20” 。再比如“#” 的ASC码为 35，即十六进制的 023，它在 URL 中被替换为“23” 。请设计一个时间和空间上尽可能高效的算法，把字符串中的每个空格替换为“2
21、0” 。例如输入“We are happy” ，则输出 “We20are 20happy ” 。要求：47 给出算法的基本设计思想。48 根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出注释。49 说明你所设计算法的时间复杂度和空间复杂度。注：要求考生在原来的字符串上做替换，即字符串后面有足够多的空余内存。50 抽象数据类型可以用三元组(D，S，P)，其中的 D，S，P 分别表示什么？你认为定义抽象数据类型的主要目的是什么？51 用类 C 语言写出求广义表深度以及复制广义表的算法。52 试写出连接两个顺序串以及判断两个顺序串是否相等的算法。计算机专业（基础综合）模拟试卷 9
22、4 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 这种题目其实大部分考生都见过，解题步骤都是固定的。先画图，将选项给出的代码一个个进行检查，看看是否存在断链或者赋值错误的情况。但是这种题型有一种万能的解法，可以应对算法题。如果此题是算法题，考生可将此题的答案按照下面所给的解题技巧轻松地写出，完全不必担心是否步骤会发生错误。解题技巧：这种题目的目的仅仅是需要把一个结点插进两个结点之间即可，答案肯定不唯一。但是我们应该从一些正确答案中挑选出一个万能的插入公式，只要遇到这种题目，就能迎
23、刃而解了。例题：假设在双链表中 p 所指的结点之后插入一个结点 s，其操作语句描述为 snext=p next ；sprior =p； p next=s；s next p rior=s；指针变化过程如图 85 所示。2 【正确答案】 D【试题解析】 ：栈要求只能在表的一端（栈顶）访问、插入和删除，这决定了栈无论采用何种存储方法表示，只能顺序访问，不能直接存取，故错误。：每创建新的栈结点时还要判断是否动态分配成功，若不成功，则进栈操作失败。故错误。StackNode *s=new StackNode，If(s=NULL) Print(“结点存储分配失败！n”)：首先要清楚链式队列需要两个指针，即
24、头指针和尾指针。当链队列需要插入元素时，在链式队列尾部插入一个新的结点，并且修改尾指针；当链队列需要删除元素时，在链式队列头部删除一个结点，并且修改头指针。所以当链式队列需要进行入队操作时，应该只需修改尾指针即可。但是有一种特殊情况（考生务必记住，因为不少考生在写链式队列出队的算法时，并没有考虑到去判断这种情况），就是当此时只有一个元素时，不妨设此时链式队列有头结点，那么当唯一一个元素出队时，应该将头指针指向头结点，并且此时尾指针也是指向该唯一的元素，所以此时需要修改尾指针，并且使尾指针指向头结点，故错误。3 【正确答案】 D【试题解析】 由 Loc(4， 6)=Loc(0，0)+(4n+6)
25、1=780+(4n+6)=1146， n=(11467806)/4=90，则可计算 Loc(6， 20)=Loc(0， 0)+(690+20)1=780+560=1340。4 【正确答案】 C【试题解析】 由二叉树的前序遍历为 1234567 可知，该二叉树的根为结点 1，并且2 为 1 的孩子结点。：假如 3124567 是该二叉树的中序遍历，那么 3 必然是 l 的左孩子，前序遍历的序列一定是 13，而前序遍历并没有以 13 开头，所以不可能是中序序列。:首先需要来证明一个知识点，什么情况下前序遍历和中序遍历是一样的。前序遍历是 tlr（根左右），中序遍历是 ltr（左根右），下面就从 t
26、lr 和ltr 着手。 (1) 当没有左子树时，前序遍历变成了 tr，中序遍历也变成了 tr，故前序遍历和中序遍历一样。(2)当没有右子树时，前序遍历变成 t1，中序遍历却变成了1t，故前序遍历和中序遍历不一样。综上分析，只要该二叉树没有左子树都能够满足前序遍历和中序遍历是一样的，故是可能的。:和的情况一样的分析，前序应该是以 14 开头，所以不可能是中序序列。：构造的二叉树如图 86 所示。因此，、不可能。总结：以下 3 种情况可以唯一确定一棵二叉树：先序序列和中序序列。 后序序列和中序序列。 层次序列和中序序列（重点，注意出题！）5 【正确答案】 B【试题解析】 宽度是指树中每一层结点个数
27、的最大值。满 N 叉树的宽度为 27，即最底层的叶结点有 27 个，该层结点最多。高度为 4，根据 N 叉树的性质，第 4 层有结点 N4I=27，N=3。该满 3 叉树的结点个数为 (341)/(31)=（811）/2=40。6 【正确答案】 A【试题解析】 ：树中各结点的度的最大值称为树的度，所以对于度为 4 的树，必须存在某个结点有 4 个分支结点。那么树最高的情况应该类似于图 87，故正确。 :这个不一定，比如图 88 所示，故错误。：就拿树的第三层来说，可以有 16 个结点，正确的答案应该是第 i 层上至多有4i1 个结点，故错误。7 【正确答案】 D【试题解析】 ：如果一个有向图存
28、在环路，则肯定不会存在拓扑排序，因为该环路找不到入度为 0 的结点，拓扑排序自然也就进行不下去了，故正确。:使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故正确。: 个反例如图 89 所示。该图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出 1，故错误。8 【正确答案】 D【试题解析】 顶点的度是指与此顶点相关联的边数，而每条边与两个顶点相关联。23 条边最多有 46 个顶点（不排除多条边共享一个顶点），设图 G 中有 n 个顶点，则有 45+34+(n54)2
29、232，解得 n16。9 【正确答案】 A【试题解析】 首先很明显不是 B+树，因为 B+树叶子结点本身依关键字的大小自小而大顺序链接，故排除 B、D 选项。另外，B树有一个性质为：m 阶 B树的结点关键字数量最多为 m1 个，但是图中有个结点有 3 个关键字，也就是说此 B树不可能是 3 阶，故选 A 选项。10 【正确答案】 C【试题解析】 此题解题的关键是要知道哪种内部排序算法在执行的过程中，不能划分出子序列来进行并行的排序，快速排序在一趟划分了两个子序列后，各子序列又可并行执行排序。而其他 3 种排序不能划分成子序列来并行执行排序，故 4 个选项中，只有快速排序可以并行执行，故选 C
30、选项。11 【正确答案】 D【试题解析】 为了在执行内部归并操作时，可以同时进行输入和输出操作，对于m 路平衡归并排序，需要设置 2m 个输入缓冲区和 2 个输出缓冲区。12 【正确答案】 A【试题解析】 由于 x 的符号位为 1，可知 x 为负数。又因为 x一 2n1，可以得到x 的绝对值必须小于 2n1，所以 xn1 必须为 0。13 【正确答案】 B【试题解析】 具体请参看表 84。14 【正确答案】 C【试题解析】 因为主存按字节编址，每块 32B，故第 3000 号单元（从 0 开始编制）所在的块号为 3000/32=93；又因为 Cache 采用四路组相连，一共 64 行（可看成
31、64 块），一共有 64/4=16 组，于是按照主存块号对应 Cache 组号，映射后第 93块在 Cache 中的组号为 9316=13。答案选 C。提示：求第多少号单元属于第几主存块的时候，很多同学可能有这样的错觉，只要不是整除，那么就一定在下一个主存块，其实这是不对的，因为块的编号是从 0 开始的，原则上从次序上来说，它确实是第 94 块，但计算机起始计数一般都是从 0开始的，这样它的序号就变成了 93，Cache 也是如此，因此当结果求得是 13 的时候，它确实是在次序上来说处于第 14 组，但是编号确实第 13 组；另外，题目不加说明我们默认主存块大小等于 Cache 块大小，Cac
32、he 一行等于一块。15 【正确答案】 D【试题解析】 这是一个部分译码的片选信号（因为高 8 位地址中有两位没有参与译码），根据译码器电路，译码输出的逻辑表达式应为 =A19(A18+A17)A15A13A12注意：1 表示只要有一个为 1 即可，所以形成 A17+A18。而译码器中间有一个&，所以 A19、A 17+A18、A 15、A 13、A 12 都必须为 1。换句话说， A19、A 15、A 13、A 12 必须为 1，而 A17、A 18 必须至少有 1 个为 1。由于 D 选项的 A12 为 0，所以不属于此译码空间。16 【正确答案】 C【试题解析】 取指周期完成的微操作序列
33、是公共的操作，与具体指令无关。CPU首先需要取指令，取指令阶段的第一个操作就是将指令地址（程序计数器中的内容）送往存储器地址寄存器。题干中虽然给出了一条具体的指令“MOV R0，#100”，实际上 CPU 首先要完成的操作是取指令，与具体指令是没有关系的。17 【正确答案】 D【试题解析】 操作码不固定，有 m 条双操作数指令，所以前 8 位还剩下 256m条。有 n 条无操作数指令，所以还剩下的空间只有(2 8m)212n，即可设计出(28m)212n/26 条，结果取整；当然这里也可以按照第三套当中讲的第二种方法，这里不做过多赘述。18 【正确答案】 B【试题解析】 : I1 指令运算结果
34、应先写入 R1，然后在指令 I2 中读出 R1 的内容。由于 I2 指令进入流水线，使得 I2 指令在 I1 指令写入 R1 前就读出 R1 的内容，发生“写后读相关”。：I1 指令应先读出 R2 的内容并存入存储单元 M 中，然后 I2 指令将运算结果写入 R2 中。但由于 I2 指令进入流水线，使得 I2 指令在 I1 指令读出 R2 之前就写入R2，发生“读后写相关”。：I2 指令应该在 I1 指令写入 R3 之后，再写入 R3。现由于 I2 指令进入流水线，如果 I2 指令减法运算在 I1 指令的乘法运算之前完成，使得 I2 指令在 I1 指令写入R3 之前就写入 R3，导致 R3 内
35、容错误，发生“写后写相关”。19 【正确答案】 B【试题解析】 修改之后的优先级是 3、1、2、4，表示 3 号的优先级最高，它可以抢占任何级别的中断处理，故 3 的屏蔽字是 1 1 1 1，1 号其次，表示除了 3 号我不能抢占它，其余的我都可以抢占，故 1 的屏蔽字为 1101，依次类推，2 号中断屏蔽字为 0101，4 号中断屏蔽字为 0001。20 【正确答案】 B【试题解析】 设计微指令结构时，所追求的目标如下：微指令结构要有利于缩短微指令字长度。有利于减小控制存储器的容量。有利于提高微程序的执行速度。有利于微指令的修改。有利于微程序设计的灵活性。21 【正确答案】 C【试题解析】
36、A: CPU 通过总线的类型来识别信息是地址还是数据，故 A 选项错误。B：间接寻址第一次访问内存所得到的信息是操作数的有效地址，该地址通过数据线传送至 CPU，而不是地址线，故 B 选项错误。C：在单总线结构中，CPU、主存和 I/O 设备（通过 I/O 接口）都挂在一组总线上，若 I/O 设备和主存统一编址，则可以很方便地使用访存指令访问 I/O 设备，故 c 选项正确。D：异步总线即采用异步通信方式的总线。在异步方式下，没有公共的时钟，完全依靠传送双方相互制约的“握手”信号来实现定时控制，故 D 选项错误。22 【正确答案】 D【试题解析】 ：在总线控制中，申请使用总线的设备向总线控制器
37、发出“总线请求”信号，由总线控制器进行裁决。如果经裁决允许该设备使用总线，就由总线控制器向该设备发出“总线允许”信号，该设备收到信号后发出“总线忙”信号，用于通知其他设备总线已被占用。当该设备使用完总线时，将“总线忙”信号撤销，释放总线。所以总线忙信号的建立者是获得总线控制权的设备，所以 I 错误。 ：计数器定时查询方式只需要总线忙信号线和总线请求信号线，而不需要总线同意信号线，所以正确。 ：链式查询仅用了 2 根线即可确定总线使用权属于哪个设备（BS总线忙信号线不参加使用权的确定，所以不是 3 根）；在计数器查询中需要使用log2n+1 根线（其中 n 表示允许接纳的最大设备数）；独立请求是
38、每一台设备均有一对总线请求线和一对总线同意线，所以独立请求方式需采用 2N 根线（其中 N表示允许接纳的最大设备数），所以错误。23 【正确答案】 C【试题解析】 正确，程序执行系统调用是通过中断机构来实现的，需要从用户态转到内核态，当系统调用返回后，继续执行用户程序，同时 CPU 状态也从核心态切换到用户态。错误，用户程序无法形成屏蔽中断指令。这里应该是形成若干参数和陷入(trap)指令。系统调用需要触发 trap 指令，如基于 x86 的 Linux 系统，该指令为 int Ox80 或 sysentero正确，编写程序所使用的是系统调用，例如 read()。系统调用会给用户提供一个简单的
39、使用计算机的接口，而将复杂的对硬件（例如磁盘）和文件操作（例如查找和访问）的细节屏蔽起来，为用户提供一种高效使用计算机的途径。正确，用户程序通过程序接口（即系统调用）进行进程控制。操作系统实现的所有系统调用所构成的集合，即程序接口或应用编程接口( Application Programminglnterface， API)，是应用程序同系统之间的接口。它包括进程控制、文件系统控制、系统控制、内存管理、网络管理、用户管理、进程间通、信等，所以几乎各个功能都需要用到系统调用。系统调用是操作系统提供给应用程序的唯一接口。综上分析，本题选 C 选项。24 【正确答案】 D【试题解析】 错误，由于用户级
40、线程不依赖于操作系统内核，因此，操作系统内核是不知道用户线程的存在的，由于操作系统不知道用户级线程的存在，所以，操作系统把 CPU 的时间片分配给用户进程，再由用户进程的管理器将时间片分配给用户线程。那么，用户进程能得到的时间片即为所有用户线程共享。所以该进程只占有 1 个时间片。若是内核级线程，由于内核级线程操作系统是知道的，它们与进程一样地分配处理机时间， 所以，有多少个内核级线程就可以获得多少个时间片。错误，各个线程拥有属于自己的栈空间，不允许共享。错误，同一进程内的多个线程可以并发执行，甚至不同进程内的多个线程也可以并发执行。错误，当从一个进程中的线程切换到另一个进程中的线程时，将会引
41、起进程的切换。知识点回顾：线程，也被称为轻量级进程，是一个基本的 CPU 执行单元。它包含了一个线程ID、一个程序计数器、一个寄存器组和一个堆栈。在多线程模型中，进程只作为除 CPU 以外系统资源的分配单位，线程则作为处理机的分配单位，甚至不同进程中的线程也能并发执行。25 【正确答案】 C【试题解析】 FCFS（先来先服务）和 SJF（短作业优先）算法大家应该都很熟悉，这里不多解释。高响应比优先算法的优先级=（等待时间+ 运行时间）/运行时间周转时间=结束时间一提交时间=等待时间+ 运行时间= 响应时间（仅在某些情况下成立，后面会讨论）(1) FCFS( 见表 85)过程说明：该算法最简单，
42、根据 FCFS 原则，作业执行顺序为1、2、3、4。T=(1.0+1.0+0，7+0.7) /4=0.85(2) SJF(见表 86)过程说明：作业 1 提交时，没有其他作业，故作业 1 马上开始运行，直到完成，此时有两个进程都在就绪队列，即作业 2 和作业 3。根据 SJF，选择作业 3 运行，直到完成，此时仍有两个进程在就绪队列，即作业 2 和作业 4。根据 SJF，选择作业4 运行，直到完成，最后作业 2 运行，完成。T=(1.0+1.3+0.2+0.2)/4=0.675(3)高响应比(见表 87)过程说明：作业 1 提交时，没有其他作业，故作业 1 马上开始运行，直到完成，此时有两个进
43、程都在就绪队列，即作业 2 和作业 3。此时作业 2 响应比为(0.5+0.5)/0.5=2，作业 3 响应比为(0+0.2)/0.2=1，根据响应比高者优先，选择作业 2 执行，直到完成，此时仍有两个进程在就绪队列中，即作业 3 和作业 4。作业 3 响应比为(0.5+0.2)/0.2=3.5，作业 4 响应比为(0.4+0.1)/0.1=5，根据响应比高者优先，选择作业 4 执行，直到完成，最后作业 3 运行，完成。T=(1.0+1.0+0.8+0.5) /4=0.825 关于响应时间和周转时间的关系如下：响应时间：从提交第一个请求到产生第一个响应所用时间。（这个定义不好理解）周转时间：从
44、作业提交到作业完成的时间间隔。如果大家多做几道这样的题会发现，这两个时间经常是相等的，即等待时间+运行时间。但既然有两个定义，就肯定有区别之处。之所以相等的原因是，这些题目太老了，这些题目中大都有个前提，“批处理系统中”，当产生第一次响应时，就是作业完成了。但在分时系统中，时间片结束后，就认为产生了第一个响应。下面举个例子，希望大家能对这两个概念区分开。比如回答：100+100+100+100100 等于多少？情况 A:我用 2s 回答了问题，等于 300。那么我要计算你这个问题是要时间的，我花了 1.8s 来运算就是周转时间。总共用了 2s 准确地回答了问题就是响应时间。计算过程是周转时间。
45、接到命令到提交完答案就是响应时间。情况 B：我用了0.5s 回答，“我现在很忙，待会儿再回答你”。0.5s 是响应时间，这就是“产生第一个响应”的意思。至于周转时间，肯定是大于 0.5s 的。所以，两者是没有谁大谁小的关系，只是在特殊题设条件下才相等的，大家要注意区分。26 【正确答案】 A【试题解析】 本题的关键在于，“每次允许 3 个进程同时使用一个资源”这个条件，即可以把该资源看成是 3 个独立的临界资源。那么临界资源的总个数为 3n，很显然，A 选项是正确答案。27 【正确答案】 A【试题解析】 地址在页式分配系统上是一个逻辑页号和一个偏移量。在逻辑页号的基础上产生一个物理页号，物理页
46、通过搜索表被找到。因为操作系统控制这张表的内容，只有在这些物理页被分配到进程中时，它可以限制一个进程的进入。一个进程想要分配一个它所不拥有的页是不可能的，因为这一页在页表中不存在。为了允许这样的进入，操作系统只简单地需要准许入口给无进程内存被加到进程页表中。正确，让同一页表的两个页表项指向同一物理页帧，用户可以利用此特点共享该页帧的代码或数据。如果代码是可重入的，如编辑软件、编译软件、数据库管理系统等，这种方法可节省大量的内存空间。正确，实现内存“复制”操作时，不需要将页面的内存逐字节复制，而只要在页表里，将指向该页面的指针复制到代表目的地址的页表项中。错误，是干扰项。正确，当两个或多个进程需
47、要交换数据时，这是十分有用的。它们只是读和写相同的物理地址（可能在多样的物理地址中）。在进程间通信时，这是十分高效的。28 【正确答案】 B【试题解析】 因为中断是由执行指令自己产生的，而且还没有执行完，故中断返回时，应重新执行被中断的那一条指令。知识点回顾：在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺之页调入内存。此时应将缺页的进程阻塞（调页完成后唤醒），如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应的页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回内存）。缺页中断与一般中断的相同点是：
48、缺页中断作为中断，同样需要经历诸如保护CPU 环境、分析中断原因、转入缺页中断处理程序进行处理、恢复 CPU 环境等几个步骤。但缺页中断是一种特殊的中断，与一般中断有明显区别：缺页中断是在指令执行期间产生和处理中断信号，另外一条指令在执行期间，可能产生多次缺页中断。29 【正确答案】 C【试题解析】 物理块数为 3 时，缺页情况如表 88 所示。缺页次数为 6，缺页率为 6/12=50。物理块数为 4 时，缺页情况如表 89 所示。缺页次数为 4，缺页率为 4/12=33。本题小技巧：当分配给作业的物理块数为 4时，注意到作业请求页面序列只有 4 个页面，可以直接得出缺页次数为 4，而不需要按表中列出缺页情况。30
