1、计算机专业（基础综合）模拟试卷 30 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式最节省时间的是( )。（A）单链表 （B）双链表（C）单循环链表 （D）顺序表2 在非空双循环链表中 q 所指的结点前插入一个由 p 所指结点的过程依次为：pnextq；P priorqprior；qprior p；下一条语句是( )。（A）qnextp； （B） qpriornextp；（C） ppriornextp；（D）pnextpriorp；3 在一
2、个长度为 n 的顺序存储线性表中，删除第 i 个元素(1in1)时，需要从前向后依次前移的元素个数是( )。（A）ni （B） ni1 （C） ni1 （D）i4 将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较次数是( ) 。（A）1（B） n1 （C） n （D）2n5 已知一算术表达式的中缀形式为 AB*CDE ，后缀形式为 ABC DE，其前缀形式为( )。（A）AB*CD/E（B） -A+B*CD/E（C） *ABC/DE（D）A*BCDE6 一个循环队列 Q 最多可存储 m 个元素，已知其头尾指针分别是 front 和 rear，则判定该循
3、环队列为满的条件是( )。（A）Qrear Qfront m （B） Qrear!Qfront（C） Qfront(Q rear1)m （D）Qfront Qrearm17 某二叉树的先序和后序序列正好相反，则该二叉树一定是( )。（A）空或只有一个结点 （B）高度等于其结点数（C）任一结点无左孩子 （D）任一结点无右孩子8 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，为实现编号可采用的遍历是( ) 。（A）先序 （B）中序（C）后序 （D）从根开始按层次遍历9 一棵哈夫曼树共有 9 个结点，则其叶子
4、结点的个数为( )。（A）4（B） 5（C） 6（D）710 下列有关散列查找的叙述正确的是( )。（A）散列存储法只能存储数据元素的值，不能存储数据元素之间的关系（B）散列冲突是指同一个关键字对应多个不同的散列地址（C）用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续的存储单元中（D）若散列表的装填因子 a1，则可避免冲突的产生11 以下排序方法中，不需要进行关键字的比较的是( )。（A）快速排序 （B）归并排序 （C）基数排序 （D）堆排序12 “容量为 640KB 的存储器”是指( )。（A）64010 4 字节的存储器 （B） 640103 位的存储器（C） 6
5、40210 位的存储器 （D）6402 10 字节的存储器13 在微程序控制的计算机中，若要修改指令系统，只要( )。（A）改变时序控制方式 （B）改变微指令格式（C）增加微命令个数 （D）改变控制存储器的内容14 生成多项式为 x3x1，则数据信息 10101 的 CRC 编码是( )。（A）1.00101e+007（B） 1.00001e+007（C） 1.01011e+007（D）1110100l15 判断加减法溢出时，可采用判断进位的方式，如果符号位的进位为 CO，最高数值位为 Cl，产生溢出的条件是( )。IC0 产生进位； C1 产生进位；C0 、C1 都产生进位； C0 、C1
6、都不产生进位；VC0 产生进位，C1 不产生进位； C0 不产生进位，C1 产生进位（A）I 和 （B） （C） IV （D）V 和16 内存按字节编址，地址从 90000H 到 CFFFFH，若用存储容量为 16K8bit 芯片构成该内存，至少需要的芯片数是( )。（A）2（B） 4（C） 8（D）1617 某计算机指令字长为 16 位，指令有双操作数、单操作数和无操作数 3 种格式，每个操作数字段均有 6 位二进制表示，该指令系统共有 m 条(mnextq； ppriorqprior； qpriorp； ppriornextp； 显然，题目中需要补充的语句为第条语句，答案为C。3 【正确答
7、案】 A【试题解析】 顺序表的删除运算的时间主要消耗在了移动表中元素上，删除第 i个元素时，其后面的元素 ai1 a n 都要向上移动一个位置，共移动了 ni 个元素。4 【正确答案】 C【试题解析】 假设有两个有序表 A 和 B 都递增有序，当有序表 A 所有元素均小于 B 的元素时，只需将 A 的所有元素与 B 的第一个元素比较即可，其比较 n 次。5 【正确答案】 D【试题解析】 将算术表达式的中缀形式作为一棵二叉树的中序遍历序列，将后缀形式作为这棵二叉树的后序遍历序列，再由二又树的中序遍历序列和后序遍历序列唯一的确定这棵二叉树，在对其进行先序遍历，就可得出算术表达式的前缀形式。6 【正
8、确答案】 C【试题解析】 少用一个元素空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满，这种情况下队满的条件是：(Qrear1)MAXsIZEQfront，能和空队区别开。7 【正确答案】 B【试题解析】 由于先序遍历是“根左子树右子树”，而后序遍历是“左子树右子树根”，若某二叉树的先序和后序序列正好相反，则该二叉树每层左、右子树只能有 1 个，即则该二叉树一定是高度等于其结点数。8 【正确答案】 C【试题解析】 根据题意和先序、中序、后序遍历规则，可简单地判断出正确答案。9 【正确答案】 B【试题解析】 哈夫曼树中没有度为 1 的结点，用 n 个权值(对应，z 个叶子结
9、点)构造哈夫曼树，共需要 n1 次合并，即哈夫曼树中非叶子结点的总数为 n1，总结点个数为 2n1。10 【正确答案】 A【试题解析】 在散列表中，每个元素的存储位置通过散列函数和解决冲突的方法得到，散列存储法只存储数据元素的值，不能存储数据元素之间的关系，所以选项A 正确；散列冲突是指多个不同关键字对应相同的散列地址，选项 B 错误；用线性探测法解决冲突的散列表中，散列函数值相同的关键字不一定总是存放在一片连续的存储单元中，选项 C 错误；装填因子 a 越小，发生冲突的概率越小，但仍有可能发生冲突。11 【正确答案】 C【试题解析】 基数排序是采用分配和收集实现的，不需要进行关键字的比较，而
10、其他几种排序方法都是通过关键字的比较实现的。12 【正确答案】 D【试题解析】 通常，以字节数来表示存储容量，这样的计算机称为字节编址的计算机。“容量 640KB”是指 6401KB，即 640210B。归纳总结在表示存储器容量大小时，经常用到 K，M，G，T，P 之类的字符，它们与通常意义下的K，M，G，T，P 有些差异，见下表。 每1024 个字节称为 1K 字节，每 1024K 字节称为 1M 字节，每 1024M 字节称为 1G字节计算机的主存容量越大，存放的信息就越多，处理问题的能力就越强。解题技巧 选项 B、C 的单位是位而不是字节，选项 A 与实际的存储单元数有误差。13 【正确
11、答案】 D【试题解析】 在微程序控制的计算机中，若要修改指令系统，只需修改相应指令的微程序即可。这些微程序都存放在控制存储器中，所以只需改变控制存储器的内容。归纳总结 微程序控制器的设计思想和组合逻辑控制器的设计思想截然不同。它具有设计规整、调试、维修以及更改、扩充指令方便的优点，易于实现自动化设计，已成为当前控制器的主流。但是，由于它增加了一级控制存储器，所以指令执行速度比组合逻辑控制器慢。14 【正确答案】 C【试题解析】 CRC 编码由数据信息和校验位共同组成，前 5 位为数据位，后 3 位为检验位。101010001011，余数为 101，将余数 101(检验位)拼接在数据位的后面，就
12、得到 CRC 码。 归纳总结循环冗余校验码是通过除法运算来建立有效信息位和校验位之问的约定关系的。假设，待编码的有效信息以多项式 M(X)表示，将它左移若干位后，用另一个约定的多项式 G(x)去除，所产生的余数 R(X)就是检验位。有效信息和检验位相拼接就构成了 CRC 码。当整个 CRC 码被接收后，仍用约定的多项式 G(X)去除，若余数为 0 表明该代码是正确的；若余数不为 0 表明某一位出错，再进一步由余数值确定出错的位置，以便进行纠正。 现生成多项式为x3x1，表示除数为 1011。 解题技巧在四个选项中，只有选项 C 的前 5 位与数据位相同，所以实际上并不需要真得做除法运算，就可以
13、立即得出正确答案。15 【正确答案】 D【试题解析】 采用进位位来判断溢出时，当最高有效位和符号位的值不相同时才会产生溢出。归纳总结 两正数相加，当最高有效位产生进位(C 11)而符号位不产生进位(C s0)时，发生正溢；两负数相加，当最高有效位不产生进位(C 10) 而符号位产生进位(C s1)时，发生负溢。故溢出条件为：溢出 。16 【正确答案】 D【试题解析】 CFFFF90000140000，即 256KB，若用存储容量为 16K8bit芯片则需芯片数(256K8)(16K8)16(片)。归纳总结 采用字扩展的方法，用若干存储芯片构成一个存储器。 解题技巧 用地址范围的末地址减去首地址
14、再加 1，就可以方便的计算出存储空间的大小。17 【正确答案】 B【试题解析】 双操作数指令操作码字段占 4 位，单操作数指令操作码字段占 10 位，无操作数指令操作码字段占 16 位。现指令系统中有 m 条双操作数指令，则给单操作数和无操作数指令留下了(2 4m)个扩展窗口。因为存在着无操作数指令，所以单操作数指令必须要给无操作数指令留下一个扩展窗口，最终最多可以设计出单操作数指令的数目为(2 4m)2 61。 归纳总结 因为如果指令长度一定，则地址码与操作码字段的长度是相互制约的。采用扩展操作码法是让操作数地址个数多的指令(三地址指令) 的操作码字段短些，操作数地址个数少的指令(一或零地址
15、指令)的操作码字段长些，这样既能充分地利用指令的各个字段，又能在不增加指令长度的情况下扩展操作码的位数，使它能表示更多的指令。 解题技巧选项 C 没有给无操作数指令留下扩展窗口，不完全符合题意。18 【正确答案】 B【试题解析】 在第 18 题图中，第 3 个流水段的执行时间没有给出，显然这是一个瓶颈段，设它的执行时间为 X。通过列方程(3X)t49XAt153t，可以求得X3。 归纳总结 对于包含瓶颈段的指令流水线，完成 n 个任务的解释共需时间T （n 1）maxt i，其中 k 为流水线段数。 解题技巧首先要列方程，然后才能求出瓶颈段的执行时间。19 【正确答案】 B【试题解析】 程序计
16、数器 PC 又称指令计数器，用来存放正在执行的指令地址或接着要执行的下一条指令地址，不能用于临时存储算术逻辑运算结果。归纳总结 控制器中应包括指令部件、时序部件、微操作信号发生器(控制单元)、中断控制逻辑等。指令部件中包括程序计数器、指令寄存器和指令译码器。解题技巧 程序计数器归属于控制器，而与运算器没有关系。20 【正确答案】 B【试题解析】 地址总线的位数与存储单元个数有关，地址总线的位数越长，可访问的存储单元个数就越多。 归纳总结系统总线按传送信息的不同可以细分为：地址总线、数据总线和控制总线。地址总线由单方向的多根信号线组成，用于 CPU向主存、外设传输地址信息；数据总线由双方向的多根
17、信号线组成，CPU 可以沿这些线从主存或外设读入数据，也可以沿这些线向主存或外设送出数据；控制总线上传输的是控制信息，包括 CPU 送出的控制命令和主存(或外设)返回 CPU 的反馈信号。 地址总线宽度决定了 CPU 可以访问的最大的物理地址空间，简单地说就是CPU 到底能够使用多大容量的主存。例如，32 位地址线，可寻址的最大容量为2324096MB(4GB)。 解题技巧 地址总线的位数与选项 A、C、D 均无：关，采用排除法。21 【正确答案】 D【试题解析】 格式化容量计算中根据扇区数和扇区容量计算出每条磁道上的信息量，然后再乘以总磁道数。而总磁道数计算时，首先求出每面磁道数(柱面数)，
18、再乘以记录面数。归纳总结 磁盘的容量有格式化容量与非格式化容量之分，磁盘上标称的容量为格式化容量。计算磁盘容量公式中的总磁道数是指记录面数与圆柱面数的乘积。其中柱面数的计算公式为：柱面数(外半径内半径)道密度格式化容量是磁盘实际可以使用的容量。新的磁盘在使用之前需要先进行格式化，格式化实际上就是在磁盘上划分记录区，写入各种标志信息和地址信息。这些信息占用了磁盘的存储空间，故格式化之后的有效存储容量要小于非格式化容量。它的计算公式为：格式化容量每道扇区数扇区容量总磁道数解题技巧 计算格式化容量时只与道密度有关，而与位密度没有关系，所以选项 A和 C 都是错误的，而选项 B 扩大了一个 10 倍。
19、22 【正确答案】 B【试题解析】 在 4 个选项中，唯有选项 B 为正确答案，因为并非每条指令执行完毕都会产生中断请求。归纳总结DMA 操作结束必须产生中断请求以进行后处理；机器出现故障将产生故障中断请求对故障进行处理；当执行“软中断”(INT)指令时也将产生中断请求进行相应的处理。23 【正确答案】 A【试题解析】 本题考查操作系统的接口。操作系统的接口有命令输入和系统调用。编写程序所使用的是系统调用，例如 read()。系统调用会给用户提供一个简单的使用计算机的接口，而将复杂的对硬件(例如磁盘)，和文件操作(例如查找和访问)的细节屏蔽起来，为用户提供一种高效使用计算机的途径。24 【正确
20、答案】 A【试题解析】 本题考查进程间的通信，进程间的通信主要有管道，命名管道，消息传递，共享内存，文件映射和套接字等。数据库不能用于进程间的通信。25 【正确答案】 A【试题解析】 本题考查进程的时间片轮转调度算法。时间片轮转的主要目的是使得多个交互的用户能够及时得到响应，使得用户以为“独占”计算机在使用。因此它并没有偏好，也不会对特殊进程特殊服务。时间片轮转增加了系统开销，所以不会使得系统高效运转，吞吐量和周转时间均不如批处理优。但是其较快速的响应时间使得用户能够与计算机进行交互，改善了人机环境，满足用户需求。26 【正确答案】 B【试题解析】 发生死锁的四个必要条件如下：互斥条件、占有并
21、请求资源、非剥夺条件和循环等待条件。一次分配所有资源的方法是当进程需要资源时，一次性提出所有的请求，若请求的所有资源均满足则分配，只要有一项不满足，那么不分配任何资源，该进程阻塞，直到所有的资源空闲后，满足了进程的所有需求时再分配。这种分配方法不会部分占有资源，所以就打破了死锁的四个必要条件之一，实现了对死锁的预防。但是，这种分配方式需要凑齐所有资源，所以，当一个进程所需的资源比较多时，资源的利用率会比较低，甚至会造成进程的饥饿。正确答案为 B。27 【正确答案】 B【试题解析】 本题考查多级存储层次下的平均访问时间的计算。根据题意，处理机执行指令的时间与存储器的平均存取周期成正比，因此只要计
22、算出存储器的平均存取周期，即可比较出两者的优劣。对于处理机 P1，存储器的平均存取周期为：4007(100040)(107)340ns对于处理机 P2，存储器的平均存取周期为：5007(90050)(107)320ns因此可以看出，处理机 P1 需要更多的处理机时间，处理机 P1 比处理机 P2 更慢。28 【正确答案】 C【试题解析】 本题考查页式存储管理的基本概念。页式存储管理的基本点是解决程序在内存中离散存放的问题，其寻址方式是借鉴于动态重定位的技术，在动态重定位技术中，通过设置基址寄存器，将程序的逻辑地址通过基址寄存器和地址加法器，动态地实现了地址转换(即每一条都是自动转换的)，操作系
23、统在装载程序时可以不用像静态重定位那样计算程序代码的地址定位，使得地址转换快捷又简单。页式存储管理将动态重定位中的基址寄存器用一组页表来替代，当访问不同的页面时，在基址寄存器中只要存放该页面的页框号便可以快速地实现地址转换。所以说，页表项实际上是实现了动态重定位。29 【正确答案】 D【试题解析】 文件的逻辑结构和物理结构是从两个：不同观点组织文件的结构而形成的概念。用户根据自己的需要确定文件的逻辑结构，而文件物理结构则是系统设计者根据文件存储器的特性和用户对文件的使用情况来确定的，一旦确定，就由操作系统管理。故正确答案为 D。30 【正确答案】 D【试题解析】 FCB 的存放是不能分开的，所
24、以 1KB 大小的盘块能存放的 FCB 数为：10246416，要注意单位的统一，约定俗成的 KB 一般指 1024B，kB 指1000B。31 【正确答案】 B【试题解析】 本题考查文件路径名的概念。文件的路径名是从根目录到目标文件所经历的路径上各符号名的集合。路径名有二种形式，第一种是绝对路径名，它由根目录出发，沿着目录的路径直到文件，绝对路径名总是从根目：录出发，并且是唯一的。第二种是相对路径名，它与工作目录(也称当前目录)一起使用，用户一般预先指定一个目录为当前目录，这时，所有的路径名均从当前目录出发，这样的路径名，只要不是从根目录出发的，都称为相对路径名。32 【正确答案】 C【试题
25、解析】 本题考查对通道和 DMA 的理解。对于 CPU 干预的 IO 操作，程序查询和中断技术都是必要的，而可以解放 CPU 且能控制数据交换的 10 操作只能是通道技术和 DMA 方式。经过分析这两种方式，我们发现，DMA 方式需要将 10设备的数据口地址映射到内存中，通道是不需要的，所以采用通道控制方式来作此传送是最佳的。33 【正确答案】 C【试题解析】 协议是控制两个对等层实体之间通信的规则的集合，网络协议的三要素是语法、语义和同步，其中语法和语义规定了对等层实体之间所交换的信息的格式和含义，但第 N 层协议要为第 N1 层提供服务，因此选项 C 的论述是错误的，答案是 C。34 【正
26、确答案】 A【试题解析】 本题考查奈奎斯特定理的直接应用，注意这里采用 8 种不同的状态，因此离散个数为 8，由 C2Hlog 2N26log 2836Mbps，因此答案为 A。35 【正确答案】 B【试题解析】 本题考查局域网的体系结构，局域网的数据链路层分为逻辑链路控制即 LLC 和媒体接入控制，即 MAC，因此 MAC 子层还是属于链路层，数据传输单元就是 MAC 帧，答案为 B。归纳总结IEEE 802 标准将数据链路层划分成两个子层：LLC 和 MAC 子层。凡与网络拓扑结构，通信介质，访问方式无关的部分集中在 LLC 子层，换句话说，无论是以太网，令牌环网或令牌总线网，它的 LLC
27、 子层都是相同的。LLC 子层为上层用户提供三种类型的服务可供选择。它们是无确认连接，有确认无连接和面相连接三种服务。一般提供三种可选功能。MAC 子层的任务：将 LLC 帧包装成 MAC 帧，并将 MAC 帧从源站点传输到目的站点。IEEE802 标准分别规定了三种 MAC 协议，每种协议对应一种特定的介质访问方法，拓扑结构和物理层技术规范。这三种协议分别是：8023、8024和 8025。36 【正确答案】 A【试题解析】 本题考查 CSMACD 协议的基本原理，这里 a 代表单程端到端的传播延时，因此 2a21000210810 微秒。在 1Gbps 速率下，每位的时间为1 纳秒，所以最
28、小帧长为 1010 310000 位1250 字节，因此答案为 A。37 【正确答案】 B【试题解析】 本题考查信道复用的几种方式，题意指明这种复用是通过划分时间片，因此是时分多路复用，答案为 B。归纳总结 频分多路复用 (FDM)将一条物理线路的总带宽分割成若干个较小带宽的子信道，每个子信道传输一路信号。时分多路复用(TDM)将一条高速物理线路的传输时间划分成若干相等的时间片，轮流的为多路信号使用。统计 TDM：采用动态分配时间策略，即有数据要传输的线路才分配时间片。38 【正确答案】 B【试题解析】 本题考查 TCP 流量控制，TCP 采用滑动窗口机制来实现流量控制，并通过接收端来控制发送
29、端的窗口大小，因此这是一种大小可变的滑动窗口协议，因此答案是 B。39 【正确答案】 B【试题解析】 本题考查网络设备中路由器的作用结构和工作原理，路由器是网络互连的关键设备，其任务是转发分组。每个路由器都维护着一个路由表以决定分组的传输路径。当目的主机与源主机不在同一个网络中，则应将数据报发送给源主机所在网络上的某个路由器，由该路由器按照转发表(由路由表构造的)指出的路由将数据报转发给下一个路由器，这种交付方式称为间接交付。I：为了提高路由器的查询效率和减少路由表的内容，路由表只保留到达目的主机的下一个路由器的地址，而不是保留通向目的主机的传输路径上的所有路由信息，故 I 错误。：路由表并不
30、一定包含子网掩码，一般只在划分了子网的网络中，路由器的路由表才使用子网掩码，如果不使用就根本不能得到网络号。而没有划分子网的网络，使用默认的就可以，不需要在路由表上显示，故错误。：路由器的路由表的表项通常包含目的网络和到达该目的网络的下一个路由器的 IP 地址，因为路由器是工作在网络层，网络层使用的是 IP 地址，故正确，：路由器是工作在网络层的设备，对数据链路层是透明的，故 IV 错误。综上，只有正确，因此答案是 B。 40 【正确答案】 B【试题解析】 本题考查 FTP 的基本原理，FTP 客户与服务器之间一般要建立两个连接，一个是控制连接，一个是数据连接，控制连接在整个会话期间一直保持打
31、开，FTP 客户发出的传送请求通过控制连接发送给服务器端的控制进程，但控制连接不用来传送文件。实际用于传输文件的是“数据连接”。服务器端的控制进程在接收到 FTP 客户发送来的文件传输请求后就创建“数据传送进程”和“数据连接”，用来连接客户端和服务器端的数据传送进程。数据传送进程实际完成文件的传送，在传送完毕后关闭“数据传送连接”并结束运行。因此答案是 B。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 可以。原因：后序遍历的顺序是“左子树一右子树一根结点” 。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。if(p
32、! NuLL)while(plchild!NuLL prchild!NuLL)while(plchild! NULL)pplchild；if(prchild! NULL)pprchild ；return(p)； 返回后序序列第一个结点的指针【试题解析】 本题主要考查后序遍历过程及特点。42 【正确答案】 void delall(LinkList&L)LNode * p，*pre，* minp，* minpre；while(Lnext!：L) 循环单链表不空时循环pLnext ；preL；minpp；mijnprepre；while(p!L) 从头开始查找最小值的结点if(pdat：adata)
33、minpp；minpre pre；prep； p、pre 同步后移ppnext；printf(”c”，minpdata)； 输出最小值结点minprenextminp 一next ； 删除最小值结点free(minp)；free(L)；【试题解析】 对于循环单链表 L，在不空时循环：每循环一次查找一个最小结点(由 minp 指向最小结点，minpre 指向其前趋结点)并删除它。最后释放头结点。43 【正确答案】 单重分组即组内并行、组间串行的进位方式；双重分组即组内并行，组间也并行。双重分组跳跃进位链中一个按 3，5，3，5 分组，大组中产生的进位输出是 C4、C 7、C 12 和 C15；而
34、一个按 4，4，4，4 分组，大组中产生的进位输出是 C3、C 7、 C11 和 C15 虽然这两种方式小组内的位数不同，但产生全部进位的时间是一致的。因为两种方式都被分成 4 个小组，假定一级“与门” 、“或门”的延迟时间定为 ty，则每一级进位的延迟时间为 2ty。C 1 经过 2ty 产生第 1 小组的进位及所有组进位产生函数 Gi*和组进位传递函数 Pi*；再经过 2ty，由大组产生相应的进位；再经过 2ty 后，才能产生第 2、3、4 小组内的其余的进位，所以最长的进位延迟时间都为 6ty。【试题解析】 假设最低位为第 0 位，16 位并行加法器均分为 4 组，最低位的进位输入为 c
35、1 ，最高位的进位输出为 C15。 归纳总结n 位并行加法器按进位信号的传递方式，可分为串行进位方式、并行进位方式和分组并行进位方式。串行进位方式的每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的；并行进位方式所有各位的进位不依赖于其低位的进位，而只依赖于最低位的进位 C1 ，各位的进位是同时产生的，随着加法器位数的增加，完全采用并行进位是不现实的。 真正实用的进位方式是分组先行进位方式，分组先行进位方式又有单级和多级之分。 单级先行进位方式(单重分组)又称为组内并行、组间串行方式。多级先行进位方式(双重或多重分组) 又称组内并行、组间并行方式。 解题技巧首先要搞清楚单重分组和双重分组
36、跳跃进位链的特点。然后利用双重分组跳跃进位链构成两种 16 位并行加法器，两种方式的区别在于其小组的位数不同。44 【正确答案】 (1)将各部件间的主要连接线补充完后，数据通路下图所示。(2)指令 SUB(R1)，(R 2)的含义为 (R2)1R 2 (R1)(R 2)(R 2) 指令的执行流程如下： (Pc)MAR ；取指令 Read M(MAR)MDRIR (PC)1PC (R 1)MAR ；取被减数 Read M(MAR)MDRC (R 2)1R 2 ；修改目的地址 (R2)MAR ；取减数 Read M(MAR)MDRD (C)(D)MDR ；求差并保存结果 Write MDRMM【试
37、题解析】 第 44 题的图中只给出了计算机的主要部件，但各部件之间的连接线没有给出，由于 LA 和 LB 分别为输入选择器，所以特将数据通路设计为简单的单总线结构形式。 归纳总结指令执行流程中的前 4 步是完成去主存中取指令的操作，这是公操作，与具体指令无关；接下来的 3 步是去主存中取被减数，把取出的被减数放在暂存器 C 中；然后的 4 步是去主存中取减数，并把取出的减数放在暂存器D 中，由于目的操作数寻址方式为自减型寄存器间接寻址，所以先要修改目的地址；最后的 3 步是完成减法运算，并将结果保存在主存中。 自减寻址是先对寄存器R。的内容自动减量修改，修改之后的内容才是操作数的有效地址，据此
38、可到主存中取出操作数。寻址操作的含义为：R i(R i)1， EA(Ri)，通常记作(R i)，减号在括号之前，形象地表示先修改后操作。而自增寻址时，寄存器 Ri 的内容是有效地址，按照这个有效地址从主存中取数以后，寄存器的内容自动增量修改。寻址操作的含义为：EA(R i)，R i(R i)1，通常记作 (Ri)，加号在括号之后，形象地表示先操作后修改。 解题技巧根据数据通路，写出指令执行的微操作序列。使用寄存器传送语句(如 PCMAR)，比较直观。45 【正确答案】 第一部分：假设临界区能容纳的最大读者数量为 n。则：typedef int semaphore； 定义信号量semaphore
39、 mutex1； 读写的互斥量semaphore readersn； 读者的资源最void Readers(viod) 读者进程 while(TRUE) 调度P(mutex)； 读写互斥P(readers)； 读者资源量减一，为负时等待V(mutex)； 释放读写互斥readdata(void)； 读者读取数据V(readers)； 离开时释放读者数量，加一Void writers(void) 写者进程 while(TRUE)P(mutex)； 获取读写互斥量for(int i1；i ：n ；i)P(readers)；将许可读者进入的资源量消耗光write_data(V0id)； 写入数据fo
40、r(int i1 ；i n；i)V(readers)；释放读者的资源量V(mutex)；) 释放读写互斥量第二部分：若对读者的数量不加以限制，那么应该如下书写程序。typedef int semaphore； 定义信号量semaphore rwmutex1； 读写的互斥量semaphore rcmutex1； 访问读者计数器的互斥量semaphore nrmutexl； 写者等待读者退出的互斥最int readerscount0； 渎者计数器void Readers(viod) 读者进程 while(IIIRUE) 调度P(rwmutex)； 读写互斥P(rcmutex)； 进入修改读者计数器
41、互斥readerscount； 读者数量加一if(readerscount1)P(nrmutex) ；若是第一个读者，互斥写者V(rcmutex)； 释放读者计数器互斥量V(rwmutex)； 及时释放读写互斥量，允许其它进程申请readdata(void)； 读者读取数据P(rcmutex)； 离开临界区时读者计数器互斥readerscount； 读者数量减一if(readerscount0)V(nrmutex)；所有读者退出临界区V(rcmutex)；) 离开时释放读者计数器互斥量Void writers(void) 写者进程 while(TRUE)P(rwmutex)； 获取读写互斥量P
42、(nrmutex)； 若临界区有读者，等待其退出writedata(void)； 写入数据V(nrmutex)； 允许后续第一个读者进入临界区V(rwmutex)； 允许新的读者和写者排队上述程序不能保证在等待队列中写者更优一点，因为上述约束条件只能将读者无限制地进入临界区的情况给屏蔽了，而在临界区外，读者和写者还是按照先来先服务的方式排队。第三部分给出的方法使得访问队列中只要有写者出现，它必然优先进入临界区。typedef int semaphore； 定义信号量semaphore rwmutex1； 读写的互斥量semaphore remutex1； 访问读者计数器的互斥量semaphor
43、e wcmutexl ； 访问排队写者计数器的互斥量semaphore nrmutex1； 写者等待读者退出的互斥量int readerscount0； 读者计数器int writerscount0； 写者计数器void Readers(viod) 读者进程 while(TRUE) 调度P(rwmutex)； 读写互斥P(rcmutex)； 进入修改读者计数器互斥readerscount； 读者数量加一if(readerscount1)P(nrmutex) ；若是第一个读者，互斥写者v(rcmutex)； 释放读者计数器互斥量V(rwmutex)； 及时释放读写互斥量，允许其它进程申请read dat|a(void)； 读者读取数据P(rcmutex)； 离开临界区时读者计数器互斥readerscount； 读者数量减一if(readerscount0)V(nrmutex)；所有读者退出临界区v(rcmutex)； 离开时释放读者计数器互斥量void writers(void) 写者进程
