1、考研计算机学科专业基础综合-7-2 及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在 OSI 参考模型中，会话层使用( )层的服务来完成自己的功能。（分数：2.00）A.物理层B.数据链路层C.网络层D.传输层2.如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的先序就是 T2 中结点的( )。（分数：2.00）A.先序B.中序C.后序D.层次序3.某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为 RAM 区，按字节编址。现要用 2K8 位的 ROM 芯片和 4K4 位的 RAM 芯片来设
2、计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是( )。（分数：2.00）A.1、15B.2、15C.1、30D.2、304.某机字长 32 位，其主存储器容量为 64MB，按字节编址，则该计算机的主存地址寄存器和主存数据寄存器的位数分别为( )。（分数：2.00）A.26，32B.26，8C.22，32D.无法确定5.下列关于进程的叙述，( )是最不符合操作系统对进程的理解。（分数：2.00）A.进程是在多程序并行环境中的完整的程序B.进程可以由程序、数据和进程控制块描述C.线程(THREAD)是一种特殊的进程D.进程是程序在一个数据集合上运行的过程，是系统进行资源管理的
3、一个独立单位6.浮点加减运算结果满足( )时，应作“机器零”处理。（分数：2.00）A.尾数为“全 0”B.阶码上溢C.阶码下溢D.A 或者 C7.指令系统中设置多种不同的寻址方式，可以( )。（分数：2.00）A.缩短指令字长B.扩大寻址空间C.提高编程灵活性D.以上都包括8.下列关于并行微程序控制器的说法正确的是( )。（分数：2.00）A.现行微指令的执行与取下一条微指令的操作并行B.现行微指令的执行与取下一条微指令的操作串行C.两条或更多微指令的执行在时间上并行D.两条或更多微指令的取微指令操作在时间上并行9.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（
4、分数：2.00）A.堆排序B.冒泡排序C.快速排序D.直接插入排序10.操作系统为了管理文件，设计了文件控制块(FCB)。FCB 是执行系统调用( )时建立的。（分数：2.00）A.createB.openC.readD.write11.某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为 06H，则该转移指令成功转移以后的目标地址是( )。（分数：2.00）A.2006HB.2007HC.2008HD.2009H1
5、2.页面置换算法( )可能会产生 Belady 异常现象。（分数：2.00）A.先进先出算法 FIFOB.最近最少使用算法 LRUC.利用 reference bit 的近似的 LRUD.最优算法 Optimal13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点在 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则应进行( )型调整以使其平衡。（分数：2.00）A.LLB.LRC.RLD.RR14.指出在顺序表 F=2，5，7，10，14，15，18，23，35，41，52中，用二分查找法查找 12 需要进行多少次比较( )。（分数：2.00）A.2B.3C.
6、4D.515.为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，( )不是一定需要。（分数：2.00）A.向操作系统预定运行时间B.将程序装入内存C.确定起始地址，并从这个地址开始执行指令D.用控制台监控程序执行过程16.要发送的数据是 1101 0110 11，采用 CRC 校验，生成多项式是 10011，那么最终发送的数据应该是( )。（分数：2.00）A.1101 0110 1110 10B.1101 0110 1101 10C.1101 0110 1111 10D.1111 0011 0111 0017.CPU 响应中断时需要保护断点，断点指的是( )。（分数：2
7、.00）A.中断服务程序的入口地址B.程序计数器 PC 的内容C.CPU 内各寄存器的内容D.指令寄存器 IR 的内容18.在 TELNET 协议中，用户发送的命令采用 TCP 传输到服务器，在 TCP 的数据包中，需要把( )符号位置移位，从而使服务器尽快响应命令。（分数：2.00）A.SYNB.URGC.PSHD.RST19.现在可以使用( )来编写 Web 页面。（分数：2.00）A.HTTPB.HTMLC.MIME：D.XML20.我们知道，有些 CPU 指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，( )可以不必具有此种特权。（分数：2.00）A.设置定时
8、器初值B.触发 trap 指令C.内存单元复位D.关闭中断允许位21.在一个双链表中，删除 p 结点之后的一个结点的操作是( )。（分数：2.00）A.p-next=p-next-next；p-next-next-prior=p；B.p-next-prior=p；p-next=p-next-next；C.p-next=p-next-next；p-next-prior=p；D.p-next-next=p-next；p-next-prior=p；22.一个以太网的帧数据长度为 20 字节，那么它的填充域长度是( )。（分数：2.00）A.0 字节B.23 字节C.45 字节D.26 字节23.两个
9、站点之间的距离是 10000km，信号在媒体上的传播速率为 2108m/s，线路的带宽是 10kbps，现在发送一个 3KB 的数据包，那么需要( )时间使得接收方收到数据。（分数：2.00）A.0.35sB.0.45sC.0.85sD.1.35s24.一个网络的物理线路上抓到 011001 位串的波形如下： 请问该线路采用了( )编码方式。（分数：2.00）A.二进制编码B.曼彻斯特编码C.差分曼彻斯特编码D.归零编码25.两个合作进程无法利用( )交换数据。（分数：2.00）A.数据库B.消息传递系统C.共享内存D.高级语言程序设计中的全局变量26.8 位二进制无符号整数可表示的数值范围是
10、( )。（分数：2.00）A.0255B.-128+127C.-127+127D.125627.冯诺依曼计算机的最根本特征是( )。（分数：2.00）A.以存储器为中心B.采用存储程序原理C.存储器按地址访问D.数据以二进制编码，并采用二进制运算28.下面关于虚拟存储管理的论述中，正确的是( )。（分数：2.00）A.为了能让更多的进程同时运行，可以只装入 10%30%的进程映像，即启动运行B.最佳页面置换算法是实现页式虚拟存储管理的常用算法C.即使在多用户环境下，用户也可以运用机器指令访问任一合法的物理地址D.为了提高内存保护的灵活性，内存保护通常由软件完成29.主机甲和主机乙间已建立一个
11、TCP 连接，主机甲向主机乙发送了两个连续的 TCP 段，分别包含 300 字节和 500 字节的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是( )。（分数：2.00）A.500B.700C.800D.100030.一个文件的绝对路径名是从( )开始，逐步沿着每一级目录向下追溯，最好到指定文件的整个通路上所有子目录组成的一个有序组合。（分数：2.00）A.当前目录B.根目录C.家目录(home directory)D.磁盘驱动器编号31.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为 30，10，20，5，当把森林转换成二
12、叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（分数：2.00）A.20B.29C.30D.3532.下列 4 组含 C1C7 的结点序列中，( )是下图所示的有向图的拓扑序列。（分数：2.00）A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，Cl，C2，C6，C733.下列文件物理结构中，适合随机访问且易于文件扩展的是( )。（分数：2.00）A.连续结构B.索引结构C.链式结构且磁盘块定长D.链式结构且磁盘块变长34.微程序存放在 CPU 的哪个部件中( )。（分数：2.00
13、）A.主存储器B.存储器控制器C.控制存储器D.辅助存储器35.动态 ROM 的刷新以( )为单位。（分数：2.00）A.位B.字节C.行D.整个 ROM36.高度为 5(除叶子层之外)的三阶 B-树至少有( )个结点。（分数：2.00）A.30B.31C.32D.3337.设二维数组 A610，每个数组元素占用 4 个存储单元，若按行优先顺序存放的数组元素，a00的存储地址为 860，则 a35的存储地址为( )。（分数：2.00）A.1000B.860C.1140D.120038.下列排序算法中，时间复杂度不受数据初始状态影响恒为 O(nlog n)的是( )。（分数：2.00）A.堆排序
14、B.冒泡排序C.快速排序D.直接插入排序39.对某一给定的程序，具有最高命中率的 Cache 替换算法是( )。（分数：2.00）A.先进先出替换算法B.最近最少使用替换算法C.随机替换算法D.无法确定40.下面关于设备属性的论述中，正确的是( )。（分数：2.00）A.字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址B.共享设备必须是可寻址和可随机访问的设备C.共享设备是同一时间内允许多个进程同时访问的设备D.在分配共享设备和独占设备时都可能引起进程死锁二、B综合应用题/B(总题数：2，分数：70.00)41.某汽车轮渡口，过江渡船每次能载 10 辆车过江。过江车辆分为
15、客车类和汽车类，上渡船有如下规定：同类车先到先上船，客车先于货车上船，且每上 4 辆客车，才允许上一辆货车，若等待客不足 4 辆，则以货车代替，若无货车等待允许客车都上船。写一算法模拟渡口管理。（分数：10.00）_某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：（分数：60.00）(1).可用什么数据结构来表示城镇和道路；（分数：4.00）_(2).请用伪代码描述效率最高的解法。（分数：4.00）_
16、(3).画出主存地址空间分配示意图；（分数：4.00）_(4).说明使用存储芯片的种类及数量；（分数：4.00）_(5).使用所给门电路画出存储芯片片选逻辑图(片选信号低电平有效)。 （分数：4.00）_(6).该流水线的加速比为多少?（分数：4.00）_(7).若四个过程段的执行所需时间都为 85ns，则加速比又为多少?（分数：4.00）_(8).开始运行后，CPU 有无空闲等待?若有，在哪段时间等待?计算 CPU 的利用率。（分数：4.00）_(9).进程 A 运行时有无等待现象?若有，在什么时候发生等待现象?（分数：4.00）_(10).进程 B 运行时有无等待现象?若有，在什么时候发生
17、等待现象?（分数：4.00）_(11).请说明系统处于不安全状态；（分数：4.00）_(12).请说明系统并不一定死锁。（分数：4.00）_(13).如果这时候该主机和其他主机通信，对端需要把数据发给什么地址?（分数：4.00）_(14).80.40.20 到达 160.80.0.0/16 网络后，会有主机响应该 ARP 请求吗?（分数：4.00）_(15).本地代理需要将发送给移动主机的分组发送到哪个地址? （分数：4.00）_考研计算机学科专业基础综合-7-2 答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在 OSI 参考模型
18、中，会话层使用( )层的服务来完成自己的功能。（分数：2.00）A.物理层B.数据链路层C.网络层D.传输层 解析：在 OSI 参考模型中，每一层使用它下层的服务来完成自己的功能，在会话层下面是传输层，所以会话层采用传输层的服务来完成自己的功能。2.如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的先序就是 T2 中结点的( )。（分数：2.00）A.先序 B.中序C.后序D.层次序解析：一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为 A。3.某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为
19、 RAM 区，按字节编址。现要用 2K8 位的 ROM 芯片和 4K4 位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是( )。（分数：2.00）A.1、15B.2、15C.1、30D.2、30 解析：根据题意可知，该机主存由 4K8 位 ROM 和 60K8 位 RAM 组成；又现有 ROM 芯片为 2K8 位，故ROM 需进行字扩展，用 2 片 2K8 位 ROM 串联组成 4K8 位 ROM；RAM 芯片为 4K4 位，故 RAM 需进行位字扩展，用 2 片 4K4 位 RAM 并联构成 4K8 位 RAM，再用 15 片 4K8 位 RAM 串
20、联组成 60K8 位 RAM，即共需 215=30 片 4K4 位的 RAM 芯片。4.某机字长 32 位，其主存储器容量为 64MB，按字节编址，则该计算机的主存地址寄存器和主存数据寄存器的位数分别为( )。（分数：2.00）A.26，32B.26，8 C.22，32D.无法确定解析：主存按字节编址，64MB=2 268 位，故主存地址寄存器为 26 位，主存数据寄存器为 8 位。5.下列关于进程的叙述，( )是最不符合操作系统对进程的理解。（分数：2.00）A.进程是在多程序并行环境中的完整的程序 B.进程可以由程序、数据和进程控制块描述C.线程(THREAD)是一种特殊的进程D.进程是程
21、序在一个数据集合上运行的过程，是系统进行资源管理的一个独立单位解析：A 的说法片面。6.浮点加减运算结果满足( )时，应作“机器零”处理。（分数：2.00）A.尾数为“全 0”B.阶码上溢C.阶码下溢D.A 或者 C 解析：当尾数为“全 0”时，不论阶码为何值，该浮点数真值都为 0，应作“机器零”处理；当阶码下溢时，说明浮点数的真值小于该机可以表示的最小值，也应作“机器零”处理，故选 D。7.指令系统中设置多种不同的寻址方式，可以( )。（分数：2.00）A.缩短指令字长B.扩大寻址空间C.提高编程灵活性D.以上都包括 解析：指令中设置多种寻址方式可以使程序员编程更加灵活，采用寄存器寻址等方式
22、可以缩短指令字长，采用间址寻址等可以扩大指令寻址空间，故 A、B、C 选项的内容都正确，选 D。8.下列关于并行微程序控制器的说法正确的是( )。（分数：2.00）A.现行微指令的执行与取下一条微指令的操作并行 B.现行微指令的执行与取下一条微指令的操作串行C.两条或更多微指令的执行在时间上并行D.两条或更多微指令的取微指令操作在时间上并行解析：并行微程序控制器中，在执行现行微指令的同时，取下一条微指令，A 选项的描述正确。9.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.00）A.堆排序B.冒泡排序C.快速排序D.直接插入排序 解析：直接插入排序在已经
23、排序好的序列的适当位置上插入关键字，因此可能需要移动元素。10.操作系统为了管理文件，设计了文件控制块(FCB)。FCB 是执行系统调用( )时建立的。（分数：2.00）A.createB.open C.readD.write解析：文件控制块是调用 OPEN 时建立的。11.某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为 06H，则该转移指令成功转移以后的目标地址是( )。（分数：2.00）A.2006HB.2
24、007HC.2008H D.2009H解析：相对寻址通过将形式地址与程序计数器 PC 的内容相加得到有效地址，即 EA=(PC)+A；又机器字长16 位，主存按字节编址，故该转移指令取出后的 PC 值为 2000H+2=2002H；所以该转移指令成功后的目标地址为 06H+2002H=2008H，选 C。12.页面置换算法( )可能会产生 Belady 异常现象。（分数：2.00）A.先进先出算法 FIFO B.最近最少使用算法 LRUC.利用 reference bit 的近似的 LRUD.最优算法 Optimal解析：先进先出算法会出现 Belady 异常。13.在平衡二叉树中插入一个结点
25、后造成了不平衡，设最低的不平衡结点在 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则应进行( )型调整以使其平衡。（分数：2.00）A.LLB.LR C.RLD.RR解析：由题意可知，A 的平衡因子为 1，又由于 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，由此可知，A 的左孩子上仅有右孩子，A 的右孩子上无左右孩子，在平衡二叉树中插入一个结点后造成不平衡，说明插入结点只能插在 A 的左孩子的右孩子上，这种情形属于在左子树的右子树上插入结点的情形，即 LR 型。14.指出在顺序表 F=2，5，7，10，14，15，18，23，35，41，52中，用二分查找法查找
26、 12 需要进行多少次比较( )。（分数：2.00）A.2B.3C.4 D.5解析：参考二分查找法。15.为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，( )不是一定需要。（分数：2.00）A.向操作系统预定运行时间 B.将程序装入内存C.确定起始地址，并从这个地址开始执行指令D.用控制台监控程序执行过程解析：实时系统才需要预定 CPU 时间。16.要发送的数据是 1101 0110 11，采用 CRC 校验，生成多项式是 10011，那么最终发送的数据应该是( )。（分数：2.00）A.1101 0110 1110 10B.1101 0110 1101 10C.11
27、01 0110 1111 10 D.1111 0011 0111 00解析：根据给出的除数，用 1101 0110 1100 00 除以 10011，得到的冗余码为 1110，添加在原来数据的最后发送出去。17.CPU 响应中断时需要保护断点，断点指的是( )。（分数：2.00）A.中断服务程序的入口地址B.程序计数器 PC 的内容 C.CPU 内各寄存器的内容D.指令寄存器 IR 的内容解析：CPU 在一条指令执行结束时响应中断，断点指的是程序计数器 PC 的内容，也就是现行程序下一条将要执行指令的地址。18.在 TELNET 协议中，用户发送的命令采用 TCP 传输到服务器，在 TCP 的
28、数据包中，需要把( )符号位置移位，从而使服务器尽快响应命令。（分数：2.00）A.SYNB.URGC.PSH D.RST解析：PSH 位表示带有 PUSH 标志的数据，接收方在收到数据后应该立即请求将数据递交给应用程序，而不是将它缓存起来。19.现在可以使用( )来编写 Web 页面。（分数：2.00）A.HTTPB.HTML C.MIME：D.XML解析：HTML(超文本标记语言)是用来描述格式化文档的语言，用来编写 Web 页面。20.我们知道，有些 CPU 指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，( )可以不必具有此种特权。（分数：2.00）A.设置定
29、时器初值B.触发 trap 指令 C.内存单元复位D.关闭中断允许位解析：trap 命令的一种常见用途是在脚本程序被中断时完成清理工作。21.在一个双链表中，删除 p 结点之后的一个结点的操作是( )。（分数：2.00）A.p-next=p-next-next；p-next-next-prior=p；B.p-next-prior=p；p-next=p-next-next；C.p-next=p-next-next；p-next-prior=p； D.p-next-next=p-next；p-next-prior=p；解析：(1)p 结点的后继结点指向 p 结点原来后继结点的后继结点，(2) 更新
30、后的 p 结点的后继结点的前驱结点指向 p。22.一个以太网的帧数据长度为 20 字节，那么它的填充域长度是( )。（分数：2.00）A.0 字节B.23 字节C.45 字节D.26 字节 解析：以太网要求帧的最小长度是 64 字节，源地址、目标地址、类型和校验及域占用了 18 个字节，那么一个有 20 字节数据的以太网帧的长度就是 38 字节，还需要填充 26 字节。23.两个站点之间的距离是 10000km，信号在媒体上的传播速率为 2108m/s，线路的带宽是 10kbps，现在发送一个 3KB 的数据包，那么需要( )时间使得接收方收到数据。（分数：2.00）A.0.35s B.0.4
31、5sC.0.85sD.1.35s解析：数据发送分为发送延时和传输延时。在题目中发送延时为 3000/10000=0.3s。传播延时为10000/200000000=0.05s，所以总共需要 0.35s 来传输该数据包。24.一个网络的物理线路上抓到 011001 位串的波形如下： 请问该线路采用了( )编码方式。（分数：2.00）A.二进制编码B.曼彻斯特编码 C.差分曼彻斯特编码D.归零编码解析：曼彻斯特编码每一周期分为两个相等的间隔。二进制“1”位在发送时，在第一个间隔中为高电压，在第二个间隔中为低电压。二进制“0”正好相反。25.两个合作进程无法利用( )交换数据。（分数：2.00）A.
32、数据库B.消息传递系统C.共享内存D.高级语言程序设计中的全局变量 解析：两个进程各自拥有自己的程序段和数据段，即有各自的全局变量，所以不可能通过全局变量交换数据。26.8 位二进制无符号整数可表示的数值范围是( )。（分数：2.00）A.0255 B.-128+127C.-127+127D.1256解析：8 位二进制无符号整数可表示的数值范围为 02 8-1，即 0255。27.冯诺依曼计算机的最根本特征是( )。（分数：2.00）A.以存储器为中心B.采用存储程序原理 C.存储器按地址访问D.数据以二进制编码，并采用二进制运算解析：存储程序原理是冯诺依曼计算机的基础，也是最根本特征。28.
33、下面关于虚拟存储管理的论述中，正确的是( )。（分数：2.00）A.为了能让更多的进程同时运行，可以只装入 10%30%的进程映像，即启动运行 B.最佳页面置换算法是实现页式虚拟存储管理的常用算法C.即使在多用户环境下，用户也可以运用机器指令访问任一合法的物理地址D.为了提高内存保护的灵活性，内存保护通常由软件完成解析：B：最佳页面置换不是页式虚拟存储管理的常用算法，实现的代价较大； C：在多用户环境下，系统应该对用户各自的数据和指令加以保护； D：内存保护通常由硬件完成，基址寄存器和界限寄存器等。29.主机甲和主机乙间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的 TCP 段，分别
34、包含 300 字节和 500 字节的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是( )。（分数：2.00）A.500B.700C.800D.1000 解析：总共发送了 1000 个字节，所以主机乙发送给主机甲的确认序号应该是 1000。30.一个文件的绝对路径名是从( )开始，逐步沿着每一级目录向下追溯，最好到指定文件的整个通路上所有子目录组成的一个有序组合。（分数：2.00）A.当前目录B.根目录 C.家目录(home directory)D.磁盘驱动器编号解析：本题考查文件路径的概念。31.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树
35、中的结点个数分别为 30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（分数：2.00）A.20B.29 C.30D.35解析：32.下列 4 组含 C1C7 的结点序列中，( )是下图所示的有向图的拓扑序列。（分数：2.00）A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，Cl，C2，C6，C7 解析：参考拓扑排序的算法。33.下列文件物理结构中，适合随机访问且易于文件扩展的是( )。（分数：2.00）A.连续结构B.索引结构 C.链式结构且磁
36、盘块定长D.链式结构且磁盘块变长解析：索引结构适合随机访问且易于文件扩展。34.微程序存放在 CPU 的哪个部件中( )。（分数：2.00）A.主存储器B.存储器控制器C.控制存储器 D.辅助存储器解析：微程序存放在控制存储器中，选 C。注意区别存控与控存的区别，控存用来存放微程序，而存控是用来管理协调 CPU、DMA 控制器等对主存储器访问的部件。35.动态 ROM 的刷新以( )为单位。（分数：2.00）A.位B.字节C.行 D.整个 ROM解析：动态 ROM 的刷新以行为单位。36.高度为 5(除叶子层之外)的三阶 B-树至少有( )个结点。（分数：2.00）A.30B.31 C.32D
37、.33解析：由 m 阶 B-树性质可知，根结点至少有两棵子树，根结点之外的所有非终端结点至少有 m/2 棵子树：则三阶 B-树的形状至少类似于一棵满二叉树，也即高度为 5 的三阶 B-树至少有(2 5-1=)31 个结点。37.设二维数组 A610，每个数组元素占用 4 个存储单元，若按行优先顺序存放的数组元素，a00的存储地址为 860，则 a35的存储地址为( )。（分数：2.00）A.1000 B.860C.1140D.1200解析：860+(3*10+5)*4=1000。38.下列排序算法中，时间复杂度不受数据初始状态影响恒为 O(nlog n)的是( )。（分数：2.00）A.堆排序
38、 B.冒泡排序C.快速排序D.直接插入排序解析：只有 A 和 C 是 O(nlog n)的复杂度，但是快速排序在“最坏”的情况下蜕化为冒泡排序，其时间复杂度为O(n2)。39.对某一给定的程序，具有最高命中率的 Cache 替换算法是( )。（分数：2.00）A.先进先出替换算法B.最近最少使用替换算法C.随机替换算法D.无法确定 解析：选项中三种替换算法，平均来说 LRU 替换算法命中率最高，但对于某一个特定的程序，无法确定哪种替换算法命中率最高。40.下面关于设备属性的论述中，正确的是( )。（分数：2.00）A.字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址B.共
39、享设备必须是可寻址和可随机访问的设备 C.共享设备是同一时间内允许多个进程同时访问的设备D.在分配共享设备和独占设备时都可能引起进程死锁解析：可寻址是块设备的基本特征，故 A 不对。共享设备是指一段时间内允许多个进程同时访问的设备，在同一时间内，即对某一时刻共享设备仍然只允许一个进程访问，故 C 不正确。分配共享设备是不会引起进程死锁的，故 D 不正确。二、B综合应用题/B(总题数：2，分数：70.00)41.某汽车轮渡口，过江渡船每次能载 10 辆车过江。过江车辆分为客车类和汽车类，上渡船有如下规定：同类车先到先上船，客车先于货车上船，且每上 4 辆客车，才允许上一辆货车，若等待客不足 4
40、辆，则以货车代替，若无货车等待允许客车都上船。写一算法模拟渡口管理。（分数：10.00）_正确答案：()解析：假设 q 数组的最大下标为 10，恰好是每次渡载的最大量。假设客车的队列是 q1，货车的队列是q2。算法如下： void Manager(Sqqueue* q，Squeue * q1，Squeue * q2) elemtype x； intj=0，i=0； while(j10) if(!empty(q1)i4) x=q1-dataq1-front； q1-front=q1-front+1； q-rear=q-rear+1； q-dataq-rear=x： i+； j+； if(i=4)
41、 !empty(q2) x=q2-dataq2-front； q2-front=q2-front+1； q-rear=q-rear+1； q-dataq-rear=x： j+； i=0： if(empty(q2)!empty(q1) i=0： 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：（分数：60.00）(1).可用什么数据结构来表示城镇和道路；（分数：4.00）_正确答案：()解析：用图结构表
42、示，其中顶点表示城镇，顶点之间路径表示道路。(2).请用伪代码描述效率最高的解法。（分数：4.00）_正确答案：()解析：这个应该是特殊(道路权重为 1)的 prim 算法。 采用邻接表结构，顶点结构包括：known 表示时候已经加入，dist 表示到起点的道路条数，path 表示相连的城镇。算法如下： void unweight(Table T) Queue Q； Vertex v，w； Q=CreateQueue(NumVertex)；MakeEmpty(Q)； Enqueue(S，Q)；/s 表示起点，可为任一城镇。 While(!IsEmpty(Q) V=Dequeue(Q)； TV.
43、Known=True； For each w adaicent to v If(T-w.Dist=Infinity) Tw.dist=Tv.dist+1；Tw.path=v；Enqueue(w，Q) DisposeQueue(Q)； dfstravrese(G，visit(int v) boolean VisitedMAX； initstack(S)； for(v=0；v=G.maxvexnum；v+)Visitedv=FLASE： for(v=0；v=G.maxvexnum；v+) if(Visitedv=FLASE) push(s，v)； DFS(G，v)； while(!Stackempty(S) printf(“%d“，v)； DFS(G，w) Visitedw=TRUE： for(firstadjvex(G，w)；w-0；w=nextadjvex(G，w) Visitedw=TRUE： ； (3).画出主存地址空
