1、考研计算机学科专业基础综合-13 及答案解析(总分：150.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.下列二叉树排序中，满足平衡二又树定义的是_。（分数：2.00）A.B.C.D.2.会使分时系统中响应时间变大的是_。（分数：2.00）A.进程调度和对换的时间减少B.分时用户的数目减少C.时间片增大D.内存容量增大3.为进程进行有序分配是一种_方法，它能使系统不发生死锁。（分数：2.00）A.死锁预防B.死锁检测C.死锁避免D.死锁解除4.有 4 个站进行码分复用 cDMA 通信。接收端收到这样的码片序列为(0 02+2 02 0+2)，下列发送的数据为比
2、特 0 的站点是_。（分数：2.00）A.(111+1+11+1+1)B.(1+11111+11)C.(1+11+1+1+111)D.(11+11+1+1+11)5.虚拟设备的是采用_技术实现的。（分数：2.00）A.缓冲技术B.覆盖技术C.SPOOLing 技术D.通道技术6.PPP 是 Internet 中使用的点到点协议，其功能对应于 OSI 参考模型的层次是_。（分数：2.00）A.数据链路层B.网络层C.传输层D.应用层7.将森林转换为对应的二叉树，若在二叉树中结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u和 v 可能具有的关系是_。父子关系 兄弟关系 u 的父结点与
3、v 的父结点是兄弟关系（分数：2.00）A.只有B.和C.和D.、8.外部打印机适合于连接到_。（分数：2.00）A.字节多路通道B.数组多路通道C.选择通道D.任意一种通道9.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数 边数大于顶点个数减 1至少有一个顶点的度为 1（分数：2.00）A.只有B.只有C.和D.和10.某计算机的指令系统定长为 16 位，采用扩展操作码，操作数地址需 4 位，该指令系统已有三地址指令12 条，二地址指令 30 条，没有零地址指令，则最多有一地址指令_。（分数：2.00）A.272 条B.352 条C.448 条D.544 条11.进程控制
4、块是描述进程状态和特性的数据结构，一个进程_。（分数：2.00）A.可以有多个进程控制块B.可以和其他进程共用一个进程控制块C.可以没有进程控制块D.只能有惟一的进程控制块12.已知一颗完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则完全二叉树的结点个数最多是_。（分数：2.00）A.39B.52C.111D.11913.设栈 s 和队列 Qde 初始状态均为空，元素 abcdefg 依次进入栈 s。若每个元素出栈后立即进入队列 Q，且 7 个元素的出队顺序是 bdcfeag，则栈 S 的容量至少是_。（分数：2.00）A.1B.2C.3D.414.系统的通道数量较少时，可能会产
5、生瓶颈现象。下面_不是解决此问题的有效方法。（分数：2.00）A.提高 CPU 的速度B.增加设备与通道之间的通路C.采用虚拟设备技术D.在设备上增加一些硬件缓冲区15.一个 TCP 连接下面使用 256Kb/s 的链路，其端到端时延为 128ms。经测试，发现吞吐量只有 120kb/s，则发送窗口大约是_。（分数：2.00）A.3614 字节B.7228 字节C.57826 字节D.120k 比特16.在 4 位有效信息上增加 3 位校验位后得到码长为 7 位的海明校验码，它的检、纠错能力为_。（分数：2.00）A.只有检错能力，没有纠错能力B.纠一位错且检两位错C.纠一位错或检两位错D.只
6、有纠错能力，没有检错能力17.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是_。（分数：2.00）_18.只能适用顺序存取但存储空间可以不连续的文件结构是_。（分数：2.00）A.顺序文件B.链接文件C.索引文件D.链接文件和索引文件19.在 Cache 和主存构成的两级存储体系中，Cache 的存取时间是 100ns，主存的存取时间是 1000ns，如果希望有效(平均)存取时间不超过 Cache 存取时间的 110%，则 Cache 的命中率至少应为_。（分数：2.00）A.90%B.98%C.95%D.99%20.在短期繁
7、重负荷情况下，决定应将哪个进程挂起，由哪一级调度程序负责_?（分数：2.00）A.高级调度B.中级调度C.作业调度D.进程调度21.下列不是电子邮件系统的主要组成部分的是_。（分数：2.00）A.用户代理B.邮件服务器C.SMTPD.HTTP22.某工作站采用的时钟频率 f 为 15MHz，处理速率为 10MIPS 的处理机来执行一个已知混合程序。假定每次存储器存储为 1 周期延迟，试问此计算机的有效 CPI 是_?（分数：2.00）A.2B.2.5C.1.5D.123.在组播路由选择算法中最浪费网络带宽的是_。（分数：2.00）A.反向路径广播B.支撑树C.泛洪法D.Steiner 树24.
8、下列叙述中，不符合 m 阶 B 树定义要求的是_。（分数：2.00）A.根结点最多有 m 棵子树B.所有叶结点都在同一层上C.各结点内关键字均为升序或降序排列D.叶结点之间通过指针连接25.给定二叉树图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，56，2，4，则其遍历方式是_。（分数：2.00）A.B.C.D.26.设机器数字长为 16 位(含一位符号位)，若一次移位需要 1s，一次加法需要 1s，则原码一位乘和原码加、减交替法最多各需要_时间。（分数：2.00）A.32s、33sB.30s、31sC.32s、32sD.30s
9、30s27.网桥进行转发决策时使用的 PDU 地址是_。（分数：2.00）A.目的物理地址B.目的 IP 地址C.源物理地址D.源 IP 地址28.为解决计算机与打印机之间速度不匹配的问题通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是_。（分数：2.00）A.栈B.队列C.树D.图29.动态存储器 DRAM 的存储位元是基于电容器上的电荷量存储信息，这个电荷量随着时间和温度而减少，因此必须定期地以_为单位进行刷新。（分数：2.00）A.存储单元B.行C.字节D.块30.一条双字长直接寻址的子程序调用指令其第一个字为
10、操作码和寻址特征，第二个字为地址码5000H。假设该指令所在主存地址为 2000H，SP 的内容为 0100H，栈顶内容为 2746H，存储器按字节编址，而且进栈操作是先执行(SP)SP，后存入数据。假定取指令时，每取一个字节 PC 自动加 1。该指令执行后的栈顶地址和内容为_。（分数：2.00）A.00FEH 2004HB.00FDH 2004HC.00FEH 2002 HD.00FDH 2002 H31.在三种集中式总线仲裁控制中，_方式响应速度最快，_方式对电路故障最为敏感。（分数：2.00）A.计数器定时查询、链式查询B.独立请求、计数器定时查询C.独立请求、链式查询D.计数器定时查询
11、独立请求32.微程序存放在_。（分数：2.00）A.主存储器的 ROM 中B.Cache 中C.堆栈中D.CPU 中的控制存储器中33.通常划分计算机的发展时代是以_为标准的。（分数：2.00）A.运算速度B.计算机结构C.所用语言D.所用的电子器件34.下列关于信息和速率的说法中，不正确的是_。（分数：2.00）A.比特是信息量的单位，波特是调制速率的单位B.信道的信息速率单位是比特/秒，码元传送速率是波特/秒C.信道的信息速率和码元速率存在一定的对应关系，在数值上可以换算D.一般来说，对于给定的信道，码元速率不大于信息速率35.下列算法中能避免磁臂粘着现象的是_。（分数：2.00）A.S
12、STFB.SCANC.CSCAND.N 步 SCAN36.在 OSI 参考模型中，自下而上第一个提供不相邻主机间通信服务的层次是_。（分数：2.00）A.数据链路层B.网络层C.传输层D.应用层37.在动态分区式内存管理中，尽可能不留下碎片空间的算法是_。（分数：2.00）A.最佳适应算法B.最坏适应算法C.循环适应算法D.最先适应算法38.中断的概念是指_。（分数：2.00）A.暂停正在运行的程序B.暂停对内存的访问C.暂停 CPU 运行D.暂停 I/O 设备的输入或输出39.文件被打开后，对文件的访问通常采用_。（分数：2.00）A.文件符号名B.文件路径名C.内存索引结点的指针D.文件描
13、述符40.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_。（分数：2.00）A.气泡排序B.插入排序C.选择排序D.二路归并排序二、综合应用题(总题数：7，分数：70.00)41.带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之存在路径，现有一种解决该问题的方法：(1)设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点。(2)选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v。(3)重
14、复步骤(2)，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。（分数：10.00）_42.已知一个带有表头结构的单链表，节点结构为date link假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 值，并返回 1；否则，只返回 0。要求：(1)描述算法的基本设计思想(2)描述算法的详细实现步骤(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用 C 或 C+或 Java 语言实现)，关键之处请给出简要注释。
15、分数：15.00）_43.某微机的寻址范围为 64KB，CPU 外接 8 片 8KB 的 RAM 芯片，存储芯片的片选信号为，试回答下列问题：(1)写出各片选信号的逻辑表达式或画出片选电路的逻辑图(允许使用译码器)。(2)写出每片 RAM 的地址范围；(3)如果运行时发现不论往哪片 RAM 芯片上写入 8KB 数据，以 6000H 为起始地址的 RAM 芯片上都会写入相同的数据，分析故障原因；(4)若发现 1.3.5.7 片 RAM 始终不被选中，试分析故障原因。（分数：11.00）_44.假定在设计机器的指令系统时，对条件转移指令的设计有以下两种不同的选择：(1)CPUA 采用一条比较指令
16、来设置相应的条件码，然后测试条件码进行转移。(2)CPUB 在转移指令中包含比较过程。在两种 CPU 中，条件转移指令需要 2 个时钟周期，而其他的指令只需 1 个时钟周期。又假设在 CPUA 上，要执行的指令中只有 20%是条件转移指令，由于每条条件指令都需要一条比较指令，因此，比较指令也占用 20%。由于 CPUA 在转移时不需要比较，因此假设它的时钟周期时间比 CPUB 快 1.25 倍。问：i哪一个 CPU 更快?ii如果 CPUA 的时钟周期时间仅仅比 CPUB 快 1.1 倍哪个 CPU 更快?（分数：10.00）_45.请用信号量解决以下的“晕独木桥”问题：同一方向的行人可连续过
17、桥，当某一方向有人过桥时，另一方向的行人必须等待，当某一方向无人过桥时，另一方向的行人可以过桥。（分数：8.00）_46.一个进程分配到四个物理页面，如下表所示，记录了，上一次装入的时间，及上一次访问的时间，及每一页的访问位和修改位的情况。(所有数字均为十进制)虚拟页号 物理块号 装入时间 访问时间 R 位 W 位2 10 60 161 0 11 11 130 160 1 00 12 26 162 1 03 13 30 163 1 1现需调用虚拟页面 4，发生缺页中断，假设下面页访问顺序为 4，0，0，0，2，4，2，1，0，3，2，使用下列置换算法，哪一个页面将用于置换，说明原因，并计算出前
18、三种置换算法产生的缺页次数各是多少。FIFO 算法LRU 算法最佳算法Colck 算法（分数：7.00）_47.主机 A 和 B 通过 TCP 连接进行通信。主机 B 已经收到了来自 A 的序号为 144 及以前的所有字节。假设A 然后向 B 发送了两个连续的报文段，其中第一个包含 20 字节的数据，第 2 个包含 40 字节的数据。第一个报文段的序号为 145，源端口号为 303，目的端口号为 80。主机 B 在收到 A 发送的报文段后发送确认。(1)A 向 B 发送的第二个报文段的序号、源端口号、目的端口号分别是多少?(2)如果第一个报文段在第二个报文段之前到达，则在第一个到达报文段的确认
19、中，源端口、目的端口和确认号分别为多少?(3)如果第二个报文段在第一个之前到达，则在第一个到达报文段的确认中，确认号是多少?(4)假设 A 发送的两个报文段按顺序到达 B。第一个确认丢失，但第二个确认在第一个超时间隔后到达 A，并且在第一个超时间隔后 A 重发了相应的报文段，如下图所示。给出所有报文段(包括重传的报文段)的序号、数据长度以及每个确认(包括重传报文段所对应的确认，即图中的第三个 ACK)的确认号。（分数：9.00）_考研计算机学科专业基础综合-13 答案解析(总分：150.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.下列二叉树排序中，满足平衡二
20、又树定义的是_。（分数：2.00）A.B. C.D.解析：平衡二叉树的特点为：左、右子树深度之差的绝对值不大于 1。2.会使分时系统中响应时间变大的是_。（分数：2.00）A.进程调度和对换的时间减少B.分时用户的数目减少C.时间片增大 D.内存容量增大解析：影响响应时间的几个因素是：用户数目，时间片及程序切换时内、外存需对换的信息量。用户数目减少，进程调度和对换的时间减少，有可能会导致响应时间变小。内存容量增大与响应时间无直接关系。3.为进程进行有序分配是一种_方法，它能使系统不发生死锁。（分数：2.00）A.死锁预防 B.死锁检测C.死锁避免D.死锁解除解析：预防死锁是破坏产生死锁的四个必
21、要条件之一来预防发生死锁，包括的方法有：(1)摒弃“请求与保持”条件，所有进程都必需一次性申请其在运行过程中所需的全部资源。(2)摒弃“不剥夺”条件，一个已经保持了某些资源的进程，在提出新的资源请求而不能立即得到满足时，必须释放它已获得的所有资源。(3)摒弃“环路等待”条件，将系统中的资源按类型赋予不同的序号，并规定所有的进程必须严格按照资源序号递增的顺序申请资源。有序分配法正是这种预防死锁的方法。4.有 4 个站进行码分复用 cDMA 通信。接收端收到这样的码片序列为(0 02+2 02 0+2)，下列发送的数据为比特 0 的站点是_。（分数：2.00）A.(111+1+11+1+1)B.(
22、1+11111+11)C.(1+11+1+1+111)D.(11+11+1+1+11) 解析：本题目主要考查“CDMA 码分多址原理”这一知识点。在 CDMA 码分多址通信中，每一个用户在同样的时间使用同样的频带进行通信但对发送的码型进行特殊处理。具体实现是：一个码被指派为 mbit 码片序列。一个站要发送比特 1，则发送 mbit 码片序列，如果要发送比特 0 码，就发送该 mbit 码片序列的反码。每一个站分配的码片序列不仅必须各不相同，而且还必须互相正交，即内积为 0。并且码片序列和各站的码片序列的反码的向量的内积也为 0，并且码片向量和码片向量自己的规格化内积是 1，码片向量和该码片反
23、码向量的规格化内积是-1。在每个比特时间间隔内，任何站点可以发送表示比特 1 的码元序列以及表示比特 0 的码元序列反码，或者保持沉默什么也不干。接收站接收到的信号是各个站发送的码片序列之和。由正交码和反码之间的乘积关系，当接收信号与发送端信号内积结果为 1 时，发送的是发送端的码片序列，即码元 1；当内积结果为-1 时，发送的是发送端码片的反码向量，即码元 0；当内积的结果为 0 是，没有数据发送。本题中，m=8。计算接收到的码片序列与 4 个发端 A。BCD 的内积如下：(0 02+2 02 0+2)(111+1+11+1+1)/8=1(0 02+2 02 0+2)(1+11111+11)
24、/8=0(0 02+2 02 0+2)(1+11+1+1+111)/8=0(0 02+2 02 0+2)(11+1l+1+1+11)/8=-1由内积知道，A 发送的比特为 1，B 和 C 未发送数据。D 发送的比特为 0。5.虚拟设备的是采用_技术实现的。（分数：2.00）A.缓冲技术B.覆盖技术C.SPOOLing 技术 D.通道技术解析：虚拟设备是指通过 SPOOLing 技术将一台独占设备变换为若干台逻辑设备，供若干个用户(进程)同时使用。6.PPP 是 Internet 中使用的点到点协议，其功能对应于 OSI 参考模型的层次是_。（分数：2.00）A.数据链路层 B.网络层C.传输层
25、D.应用层解析：本题目主要考查了“广域网”中的“PPP 协议”。数据链路层主要协议有 PPP、HDLC.Ethernet、Token Ring 等，其中前两个是广域网协议，后两个是局域网协议。网络层主要协议有 IP、ICMP、IGMP、ARP 等。传输层主要协议有 TCP、UDP 等。应用层主要协议有 HTTP、FTP、DNS、Telnet 等。7.将森林转换为对应的二叉树，若在二叉树中结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u和 v 可能具有的关系是_。父子关系 兄弟关系 u 的父结点与 v 的父结点是兄弟关系（分数：2.00）A.只有B.和 C.和D.、解析：基本原理是树
26、的孩子兄弟表示法。我们可以采用如下方法进行转化。步骤：将树中结点的所有兄弟结点用水平线连接起来；除保留当前结点同其最左子结点的连接之外，将所有同其余子结点的连接线全部删除；同时将当前结点同其最左子结点的连接线修改为垂直连接；将得到的图形顺时针旋转 45 度，即得二叉树。(或将当前纸面逆时针旋转 45 度，即得)：将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依次转换。转化步骤为：将森林中所有的树都转化为二叉树；第一棵树 T1的根结点作为 T 的根结点，T 1的根结点的子树转化为 T 的左子树，森林的其它树 T2，T 3，T n转
27、化为 T 的右子树。8.外部打印机适合于连接到_。（分数：2.00）A.字节多路通道 B.数组多路通道C.选择通道D.任意一种通道解析：数组多路通道适合高速设备并且能分时传送数据。字节多路通道适合低速设备，打印机属于低速设备，所以选择这种通道。选择通道又称为高速通道，适合于速度很高的设备，并且一次只能选择一个设备进行传输。9.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数 边数大于顶点个数减 1至少有一个顶点的度为 1（分数：2.00）A.只有 B.只有C.和D.和解析：图的连通性：如果从顶点 v 到 u 有路径，则称为 v 和 u 是连通的。连通图：对图 G 中任何两个顶
28、点，如果是连通的，则称 G 为连通图。对有向图来说，如果每对顶点之间 v 到 u，u 到 v 都是连通的，则称该有向图为强连通图。连通分量和极大连通子图：虽然无向图 G 本身不连通，但是 G 一般都有极大连通子图(也是连通的)，称为 G 的连通分量。10.某计算机的指令系统定长为 16 位，采用扩展操作码，操作数地址需 4 位，该指令系统已有三地址指令12 条，二地址指令 30 条，没有零地址指令，则最多有一地址指令_。（分数：2.00）A.272 条B.352 条C.448 条 D.544 条解析：一地址指令最多还有(24-12)24)-30)24=544 条。11.进程控制块是描述进程状态
29、和特性的数据结构，一个进程_。（分数：2.00）A.可以有多个进程控制块B.可以和其他进程共用一个进程控制块C.可以没有进程控制块D.只能有惟一的进程控制块 解析：一个进程只能有唯一的一个进程控制块与其对应，进程控制块是进程存在的唯一标志，是系统感知进程存在的依据。12.已知一颗完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则完全二叉树的结点个数最多是_。（分数：2.00）A.39B.52C.111 D.119解析：完全二叉树：深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树一一对应时，称为完全二叉树。深度为 k 的完全二叉树结点个数范围：最小结
30、点数：2 k-1，最大结点数 2k-1。13.设栈 s 和队列 Qde 初始状态均为空，元素 abcdefg 依次进入栈 s。若每个元素出栈后立即进入队列 Q，且 7 个元素的出队顺序是 bdcfeag，则栈 S 的容量至少是_。（分数：2.00）A.1B.2C.3 D.4解析：堆栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。习惯上称插入结点为入栈(压栈，进栈)，删除结点成为出栈(弹栈)。最先进栈的结点必定最后出栈，最后进栈的结点必定最先出栈，因此，栈是一种具有后进先出特性的数据结构。队列也是一种特殊类型的线性表，按照先进先出的原则对其中的元素进行操作。排在队首的先出队，然后后面的元素
31、依次前移。进入队列必须在队尾进行，删除必须在队首进行。14.系统的通道数量较少时，可能会产生瓶颈现象。下面_不是解决此问题的有效方法。（分数：2.00）A.提高 CPU 的速度 B.增加设备与通道之间的通路C.采用虚拟设备技术D.在设备上增加一些硬件缓冲区解析：提高 CPU 的速度不能改变瓶颈问题。15.一个 TCP 连接下面使用 256Kb/s 的链路，其端到端时延为 128ms。经测试，发现吞吐量只有 120kb/s，则发送窗口大约是_。（分数：2.00）A.3614 字节B.7228 字节 C.57826 字节D.120k 比特解析：本题目主要考查的是“TCP 流量控制”。为了提高报文段
32、的传输效率，TCP 采用大小可变的滑动窗口进行流量控制。窗口大小的单位为字节。发送窗口在连接建立时由双方商定。但在通信的过程中，接收端可根据自己的资源情况，随时动态地调整对方的发送窗口上限值。发送端利用发送窗口调节向网络注入分组的速率不仅是为了使接收端来得及接收，而且还是为了对网络进行拥塞控制。在每一个运输连接上报文段是断续发送的，这样就有了两种速率。一种是链路层的数据率，另一种是从运输层看到的数据注入速率。题目中给出端到端时延为 128ms，则在一个传输周期里，从发送第一个报文段到收到所有确认时间为：W/R+2*T，其中 w 为发送窗口的大小，R 为链路速率，T 为端到端时延。因此吞吐量 T
33、P=W/(W/R+2*T)，将题目中的具体数据代入，即可求得 W=7228 字节。16.在 4 位有效信息上增加 3 位校验位后得到码长为 7 位的海明校验码，它的检、纠错能力为_。（分数：2.00）A.只有检错能力，没有纠错能力B.纠一位错且检两位错 C.纠一位错或检两位错D.只有纠错能力，没有检错能力解析：有效信息位数为 4 位校验位数为 3，整个码长为 7，则满足不等式：N=7=4+32 3-1，所以可纠一位错检两位错。17.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是_。（分数：2.00）_解析：堆排序是另一种基于选
34、择的排序方法。n 个元素的序列k1，k2，k3，kn18.只能适用顺序存取但存储空间可以不连续的文件结构是_。（分数：2.00）A.顺序文件B.链接文件 C.索引文件D.链接文件和索引文件解析：文件物理结构就是文件的存储结构，与采用的外存分配方式有关，相应不同的分配方式，文件的物理结构分为：连续结构，链式结构，索引结构。连续结构实现简单，顺序存取速度快，但必须连续存放；链式结构允许不连续存放，但只适用于顺序存取；索引文件即允许不连续存放，而且可以随机存取。19.在 Cache 和主存构成的两级存储体系中，Cache 的存取时间是 100ns，主存的存取时间是 1000ns，如果希望有效(平均)
35、存取时间不超过 Cache 存取时间的 110%，则 Cache 的命中率至少应为_。（分数：2.00）A.90%B.98%C.95%D.99% 解析：平均存取时间 ta=tch+tM(1-h)，式中，tc 为 Cache 的存取时间，tM 为主存的存取时间。代入数值，即 100h+1000(1-h)1.11.0，故，h99%。20.在短期繁重负荷情况下，决定应将哪个进程挂起，由哪一级调度程序负责_?（分数：2.00）A.高级调度B.中级调度 C.作业调度D.进程调度解析：在短期繁重负荷情况下，应将哪个进程挂起由中级调度程序负责。21.下列不是电子邮件系统的主要组成部分的是_。（分数：2.00
36、A.用户代理B.邮件服务器C.SMTPD.HTTP 解析：本题目主要考查了“电子邮件”。电子邮件系统的 3 个主要组成部分：用户代理、邮件服务器、简单邮件传输协议(SMTP)。用户代理 UA(Use Agent)：是用户与电子邮件系统的接口。用户代理使用户能够通过一个很友好的接口来发送和接收邮件。邮件服务器：是电子邮件系统的核心部件，邮件服务器的功能就是发送和接收邮件，同时还要向发信人报告邮件传送的情况。SMTP 是因特网电子邮件中主要的应用层协议，它使用 TCP 可靠数据传输服务，从发送方的邮件服务器向接收方的邮件服务器发送邮件，默认使用 TCP 端口为 25。PCP3(Post Offi
37、ce Protocol Version 3，邮局协议，版本 3)，是电子邮件接收方向电子邮局发出接收邮件请求时使用的单向传输协议，默认使用 TCP 端口为 110。IMAP(Internet Message Access Protocol，Internet 报文存取协议)，是一个用于客户机对邮件服务器上的邮件可以进行远程管理的协议，默认使用 TCP 端口为 143。IMAP 与 POP 的工作区别：对于 POP，从网上收到的邮件是根据收信人的邮件地址交付给目的 ISP 邮件服务器，而收信人客户机不定期地连接到这个邮件服务器以便将发送给他的邮件下载到其客户机上。然后，所有对邮件的处理都在用户的客
38、户机上进行。在使用 IMAP 时，所有收到的邮件同样是先送到 ISP 的邮件服务器的 IMAP 服务器。而在用户的客户机上运行 IMAP 客户程序，然后与 ISP 的邮件服务器上的 IMAP 服务器程序建立 TCP 连接。用户在自己的 PC 机上就可以操纵 ISP 的邮件服务器的邮箱，就像在本地操纵一样。22.某工作站采用的时钟频率 f 为 15MHz，处理速率为 10MIPS 的处理机来执行一个已知混合程序。假定每次存储器存储为 1 周期延迟，试问此计算机的有效 CPI 是_?（分数：2.00）A.2B.2.5C.1.5 D.1解析：指令的平均时钟周期数 CPI(Cycles Per Ins
39、truction)=时钟周期数/程序执行的指令数。已知处理机的时钟频率 f 为 15MHz，即每秒有 15M 个时钟周期。处理速率为 10MIPS，即每秒处理 10M 条指令。所以，此计算机的有效 CPI=15M/10M=1.5。23.在组播路由选择算法中最浪费网络带宽的是_。（分数：2.00）A.反向路径广播B.支撑树C.泛洪法 D.Steiner 树解析：本题目主要考查了“IP 组播”中的“组播路由算法”。在组播模型中，组播源向某一组地址传递数据包，而这一地址却代表一个主机组。常见的组播路由选择算法有：泛洪法、支撑树、反向路径广播、修剪的反向路径广播、Steiner 树、核心树。泛洪法(F
40、looding)是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下：当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包，如果是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收者；如果不是首次收到，则抛弃该数据包。泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数据包列表，但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误，只要还存在一条到接收者的链路，则所有接收者都能接收到组播数据包。然而，洪泛法不适合用于 Internet，因为它不考虑链路状态，并产生大量的拷贝数据包。支撑树(spanning t
41、ree)算法选择成本最小的链路。为了向所有接收者传递数据，一般采用组播分布树描述 IP 组播在网络里经过的路径。组播分布树有两种基本类型：有源树和共享树。有源树也称为基于信源的树或最短路径树(Shortest Path Tree：SPT)。它是以组播源为根构造的从根到所有接收者路径都最短的分布树。如果组中有多个组播源，则必须为每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树上，因此采用 SPT 有利于网络中数据流量的均衡。共享树(Shared Distribution Tree)也称 RP 树，是指为每个组播组选定一个共用根(Rerldezvous Point，汇合
42、点)，以 RP 为根建立的组播树。同一组播组的组播源将所要组播的数据单播到 RP，再由 RP向其它成员转发。目前，讨论最多同时也是最具代表性的两种共享树是 Steiner 树和有核树(CBT)。Steiner 树是总代价最小的分布树，它使连接特定图(graph)中的特定组成员所需的链路数最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生拥塞的风险。Steiner 树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型网络缺少通用的解决方案。所以 Steiner 树只是一种理论模型，而非实用工具。目前，出现了许多 Steiner 树的次优启发式生成算法。有核树是由根到
43、所有组成员的最短路径合并而成的树。单播只关心下一跳在那里，而组播只关心数据从那里来的所以 router 用 RPF(Revetse Path Forward)对数据进行查看是否进行转发，如果 router 的接收数据端口是数据源到该端口的最短路径，则转发该数据；如果不是则丢掉。24.下列叙述中，不符合 m 阶 B 树定义要求的是_。（分数：2.00）A.根结点最多有 m 棵子树B.所有叶结点都在同一层上C.各结点内关键字均为升序或降序排列D.叶结点之间通过指针连接 解析：B树是一种平衡的多路查找树，其特点如下：1在 m 阶的 B树上，每个非终端结点可能含有：n 个关键字 Ki(1in)nm；n
44、 个指向记录的指针 Di(1in)，以及 n+1 个指向子树的指针Ai(0in)；2非叶结点中的多个关键字均自小至大有序排列，即：K1K2Kn；且 Ai-1 所指子树上所有关键字均小于 Ki；Ai 所指子树上所有关键字均大于 Ki；3树中所有叶子结点均不带信息，且在树中的同一层次上；根结点或为叶子结点，或至少有两棵子树；其余非叶结点至少有*棵子树，至多有m 棵子树。25.给定二叉树图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，56，2，4，则其遍历方式是_。（分数：2.00）A.B.C.D. 解析：有如下三种遍历方式：先序遍历
45、访问根结点，访问左子树、访问右子树；中序遍历：访问左子树，访问根结点、访问右子树；后序遍历：访问左子树，访问右子树，访问根结点。26.设机器数字长为 16 位(含一位符号位)，若一次移位需要 1s，一次加法需要 1s，则原码一位乘和原码加、减交替法最多各需要_时间。（分数：2.00）A.32s、33sB.30s、31s C.32s、32sD.30s、30s解析：n 位数值位的原码一位乘最多需要 n 次加法和 n 次移位，而补码比较法中需 n+1 次加和 n 次移位。除法中的原码加、减交替法最多需要 n+1 次加和 n 次移位，补码加、减交替法若采用末位商恒置 1 法，则需加 n 次、移 n 次。字长 16 位的机器数运算，数值位是 15 位，所以原码一位乘需要 15 次加和 15 次移位，即 30gs，原码加、减交替法需要 16 次加和 15 次移位，即 31s。27.网桥进行转发决策时使用的 PDU 地址是_。（分数：2.00）A
