1、考研计算机学科专业基础综合-19 及答案解析(总分：119.98，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.若二叉树的前序序列为 DABCEFG，中序序列为 BACDFGE，则其层次序列为( )。 ABCAGFED BDAEBCFG CABCDEFG DBCAEFGD（分数：2.00）A.B.C.D.2.页面置换算法( )可能会产生 Belady 异常现象。 A先进先出算法 FIFO B最近最少使用算法 LRU C利用 reference bit 的近似的 LRU D最优算法 Optimal（分数：2.00）A.B.C.D.3.如果一个没有内存映射的 IO 设备
2、与主存之间交换数据，希望这种数据交换不经过 CPU 来完成，那么，可以采用的方法是( )。A程序查询方式 B中断技术 C通道技术 DDMA 方式（分数：2.00）A.B.C.D.4.MIPS(每秒百万次指令数)和 MFLOPS(每秒百万次浮点运算数)是衡量 CPU 性能的两个指标，其中( )。AMIPS 适合衡量向量处理机的性能，MFLOPS 适合衡量标量处理机的性能BMIPS 适合衡量标量处理机的性能，MFLOPS 适合衡量向量处理机的性能CMIPS 反映计算机系统的峰值性能，MFLOPS 反映计算机系统的持续性能DMIPS 反映计算机系统的持续性能，MFLOPS 反映计算机系统的峰值性能（
3、分数：2.00）A.B.C.D.5.进行 P0 和 P1 的共享变量定义及其初值为boolean flag2; int turn=0; flag0=faulse; flag1=faulse; 若进行 P0 和 P1 访问临界资源的类 C 代码实现如下：Void P0( )/进程 p0 Voicl P1( )/进程 p1while(TuRE) while(TURE)Flag0=TURE； Flag1=TuRE；turn=1； turn=0；While(flag1 int turn=0; flag0=faulse; flag1=faulse; 若进行 P0 和 P1 访问临界资源的类 C 代码实现
4、如下：Void P0( )/进程 p0 Voicl P1( )/进程 p1while(TuRE) while(TURE)Flag0=TURE； Flag1=TuRE；turn=1； turn=0；While(flag1&(turn=1) While(flag0%&(turn=0)； ；临界区； 临界区；Flag0=FALSE； Flag1=FALSE；则并发执行进程 P0 和 P1 时产生的情况是：A不能保证进程互斥进入临界区，会出现“饥饿”现象B不能保证进程互斥进入临界区，不会出现“饥饿”现象C能保证进程互斥进入临界区，会出现“饥饿”现象D能保证进程互斥进入临界区，不会出现“饥饿”现象（分数
5、：2.00）A.B.C.D. 解析：解析 考查进程间通信与 Peterson 算法。算法实现互斥的主要思想在于设置了一个 turn 变量，用于进程间的互相谦让。如果进程 P0 试图访问临界资源，flag0=true，表示希望访问。此时如果进程 P1 还未试图访问临界资源，则 flag1在进程上一次访问完临界资源退出临界区后已设置为 false。所以进程 P0 在执行循环判断条件时，第一个条件不满足，进程 P0 可以正常进入临界区，且满足互斥条件。我们需要考虑的是两个进程同时试图访问临界资源的情况。注意 turn 变量的含义：进程在试图访问时，首先设置自己的 flag 变量为 true，表示希望
6、访问；但又设置 turn 变量为对方的进程编号，表示谦让，因为在循环判断条件中 turn 变量不是自己编号时就循环等待。这时两个进程就会互相“谦让”一番，但是这不会造成“饥饿”的局面，因为 turn 变量会有一个最终值，所以必定有进程可以结束循环进入临界区。实际的情况是，先作出“谦让”的进程先进入临界区，后作出“谦让”的进程则需要循环等待。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“您走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。6.有四个用户 Li，
7、zhang，sun 和 wang，对应的用户组分别为 system，staff，stLldent，stuation。下列五个文件的访问控制列表和访问控制权限如下：File0:(Li,*,rwx),(*,staff,rw-)File1:(*,system,rwx)File2:(Li,*,rw-),(wang,staff,rw-),(sun,*,rw-)File3:(*,student,rw-)File4:(zhang,*,-x),(*,stuation,rwx)那么，只能够读写其中二个文件的用户是( )。ALi Bzhang Csun Dwang（分数：2.00）A.B.C. D.解析：解析 本
8、题考查学生对文件保护中访问控制权限的理解。操作系统在对文件的保护中，可以采取用户口令认证、域保护和访问控制列表及访问控制权限表等方式。将访问矩阵按列进行划分，每一列建立一个控制表，即可得到各个对象的访问控制丧。将矩阵按行进行划分，每一行建立一个访问权限表，即可得到各个域的访问权限表，域在不同操作系统中可以按不同方式出现，例如可以是进程，也可以是用户等。当某个进程或用户需要访问某个文件时，先检查对象的访问控制表，检杏是否有访问权限，若有，则为其建立访问权限表，并链接到该进程或用户，以后，该进程或用户可以直接利用该用户权限表进行访问。本题中，Li 可以读写的文件有三个 File0、1 和 2,zh
9、ang 可以访问的文件有二个 Filc0 和 4,但是其中 File4只能运行不能读写，sun 可以读写的文件为 File2 和 3，wang 可以读写文件 File4，但是 wang 不是 staff组员，所以不能读写 File2。因此，满足条件的答案只有 C。7.电路交换的优点是( )。传输时延小 分组按序到达 无需建立连接 线路利用率高A和 B和 C和 D和（分数：2.00）A. B.C.D.解析：解析 本题考查电路交换、分组交换、报文交换的特点和优缺点，主要有两种考查方式：一、直接考查某一种(或多种)交换方式的特点，是非选择判断题目；二、给定应用背景，交换方式的选择问题，这种方式比较灵
10、活，间接性考查三种交换的优缺点，难度大。这里是针对第一种考查，电路交换是面向连接的，一旦连接建立，数据便可以通过连接好的物理通路到达接收端，因此传输时延小；由电路交换面向连接的特性，可知传送的分组必定是按序到达的；但在电路交换中，通信双方始终独自占用带宽，线路利用率很低，因此答案是 A。8.设指令由取指、分析、执行 3 个子部件完成，并且每个子部件的时间均为 t，若采用常规标量流水线处理机，连续执行 8 条指令，则该流水线的加速比为( )。A3 B2 C3.4 D2.4（分数：2.00）A.B.C.D. 解析：解析 当采用流水线时，第一条指令完成的时间是 3t，以后每 t 都有一条指令完成，8
11、 条指令总共需要的时间为 3t+(8-1)t=10t，若不采用流水线，完成 8 条指令总共需要的时间为 83t=24t，所以加速比=24t/10t=2.4。归纳总结 设-m 段流水线的各段经过时间均为t 0，则需要 T0=mt。的流水建立时间，之后每隔t 0就可流出一条指令，完成 n 个任务的解释共需时间 T=mt 0+(n-1)t 0。流水线的加速比 Sp表示流水方式相对于非流水顺序方式速度提高的比值。9.若处理器有 32 位地址，则它的虚拟地址空间为_字节。A2G B4G C100K D640K（分数：2.00）A.B. C.D.解析：处理器有 32 位，则其虚地址空间为 232 字节，即
12、为 4*230=4G 字节。10.操作系统中，某进程从一个临界区离开，有可能发生进程状态改变的是( )。A该进程本身 B输入输出进程C等待使用该临界区的进程 D调度器进程（分数：2.00）A.B.C. D.解析：解析 本题考查进程状态的转换和临界区的概念。进程有三个基本状态，处于阻塞状态的进程是由于某个事件不满足需求而等待。这样的事件一般是 IO 操作，例如键盘，磁盘等。或者是因互斥或同步数据引起的等待，例如等待信号或等待进入互斥临界区等。仔细分析进程访问临界区的操作，例如 P、V操作，在进程离开临界区时，例如 V 操作时，若有其它进程等待进入该临界区，则离开临界区的进程必须将等待进入临界区的
13、进程唤醒，唤醒的过程也是改变等待进入临界区进程的状态的过程，这个进程由原来的阻塞状态变为就绪，等待调度而可以进入临界区。离开临界区的进程若没有阻塞或用时完毕，可以继续处于运行状态，同样地，调度器也不必激活，输入输出进程更与其无关。11.为解决计算机与打印机之间速度不匹配的问题通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是_。A栈 B队列 C树 D图（分数：2.00）A.B. C.D.解析：队列的主要应用为：汽车加油站、模拟打印机缓冲区、CPU 分时系统等方面。12.如下图所示，若低位地址(A0A11)接在内存芯片地址
14、引脚上，高位地址(A12A19)进行片选译码(其中，A14 和 A16 没有参加译码)，且片选信号低电平有效，则对下图所示的译码电路，不属于此译码空间的地址是( )。（分数：2.00）A.B.C.D. 解析：解析 这是一个部分译码的片选信号，高 8 位地址中有 2 位(A14 和 A16)没有参与译码，根据泽码器电路，译码输出的逻辑表达式应为：13.用户程序在用户态下使用陷入指令而引起的中断是( )。A故障中断 B外部中断 C不可屏蔽中断 D访管中断（分数：2.00）A.B.C.D. 解析：解析 本题考查用户态和内核态及其转换的概念。在操作系统管理下的计算机中，为保护系统的安全，对一部分处理机
15、的指令限定使用对象，即只有操作系统才可以执行。而当用户需要使用这些特权指令时，必须调用特定的访管指令，也称陷入指令，顾名思义由用户态陷入到内核态，从而从用户态转入内核态，继而可以执行特权指令；访管指令引起的中断称为访管中断，它是用户使用特权指令的唯一入口。14.已知有向图 G=(V，A)，其中V=a，b，c，d，e，A=a，b，a，c，d，c，d，e，b，e，c，e，对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。Aa，d，c，b，e Bd，a，b，c，e Ca，b，d，c，e Da，b，c，d，e（分数：2.00）A.B.C.D. 解析：解析 对 AOV 网进行拓扑排序的方法和步骤是：
16、(1)从 AOV 网中选择一个没有前驱的顶点(该顶点的入度为 0)，并且输出它；(2)从网中删去该顶点，并且删去从该顶点发出的全部有向边；(3)重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。本题按照拓扑排序方法对该图进行拓扑排序便可得到结果。15.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为_。A13 B33 C18 D40（分数：2.00）A.B. C.D.解析：n 阶对称矩阵 A 中的元素满足下述条件：a ija，。(1=i，j=n)。对称矩阵中的每一对数据元素可以共用一个存
17、储空间，因此可以将 n2个元素压缩存储到 n(n+1)/2 个元的空间中，即可以一维数组保存。假设用一维数组 sn(n+1)/2作为对称矩阵 A 的存储结构，则 sk和矩阵元素 aij 的下标 i、j 的对应关系为：当 i=j 时，k=i(i-1)/2+j；当 ij 时，k=j(j-1)/2+i；16.一个正处于得不到所申请的资源而暂时停止下来的进程由于终端用户的请求被挂起，这时，它所申请的资源得到满足，则它的状态应转变为_状态。A静止阻塞 B活动阻塞 C静止就绪 D活动就绪（分数：2.00）A.B.C. D.解析：此题为五状态的进程转换问题，原来三状态中的就绪，阻塞在此分为了两部分活动就绪与
18、静止就绪，活动阻塞与静止阻塞，实际上，原三状态中的就绪与阻塞与五状态中的活动就绪和活动阻塞基本一致，其转换原因也与三状态中相同。只有通过挂起才有了静止就绪与静止阻塞，而引起挂起的原因之一就是用户的请求。而由静止转为活动只有一个原因激活，还有一个比较特别的就是当处于静止阻塞的进程所请求的I/O 事件得到满足后转为静止就绪。17.假设某硬盘由 5 个盘片构成(共有 8 个记录面)，盘面有效记录区域的外直径为 30cm，内直径为 10cm，记录位密度为 250 位/mm，磁道密度为 16 道/mm，每磁道分 16 个扇区，每扇区 512 字节，则该硬盘的格式化容量约是( )。（分数：2.00）A.B
19、. C.D.解析：解析 格式化容量计算中根据扇区数和扇区容量计算出每条磁道上的信息量，然后再乘以总磁道数。而总磁道数计算时，首先求出每面磁道数(柱面数)，再乘以记录面数。归纳总结 磁盘的容量有格式化容量与非格式化容量之分，磁盘上标称的容量为格式化容量。计算磁盘容量公式中的总磁道数是指记录面数与圆柱面数的乘积。其中柱面数的计算公式为：柱面数=(外半径-内半径)道密度格式化容量是磁盘实际可以使用的容量。新的磁盘在使用之前需要先进行格式化，格式化实际上就是在磁盘上划分记录区，写入各种标志信息和地址信息。这些信息占用了磁盘的存储空间，故格式化之后的有效存储容量要小于非格式化容量。它的计算公式为：格式化
20、容量=每道扇区数扇区容量总磁道数解题技巧 计算格式化容量时只与道密度有关，而与位密度没有关系，所以选项 A 和 C 都是错误的，而选项 D 没有注意到直径的单位是 cm，而道密度的单位是 mm，因此相差了 10 倍。18.一个 C 类网络的子网掩码为 255.255.252.252，则该 C 类网络的主机数目是( )。A2046 B1022 C510 D128（分数：2.00）A.B.C.D. 解析：解析 本题考查 IPv4 子网划分，首先明确 C 类网络的掩码是 255.255.0.255，而 252 的二进制是1111 1100，由此可知可划分 26=64 个子网，每个子网的主机数为 22
21、-2=2，因此该 C 类网络的主机数目是642=128，因此答案是 D。19.一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树的结点数是( )。A2 k-1-1 B2 k-1 C2 k-1+1 D2 k-1（分数：2.00）A.B.C.D. 解析：解析 一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，也就是说每个非终端结点都有左子树和右子树且高度相等。因此，这样的平衡二叉树即为满二叉树，而高度为 k 的满二叉树的结点数是 2k-1。20.某机字长 32 位，主存容量 1MB，按字编址，块长 512B，Cache 共可存放 16 个块，采用直接映射方式，
22、则 Cache 地址长度为( )。 A11 位 B13 位 C18 位 D20 位（分数：2.00）A. B.C.D.解析：主存地址中除去 tag(主存字块标记)的部分就是 Cache 地址；其中，块长 512B，主存按字编址，512B/(4B/W)=128w=27W，即块内字地址 7 位；Cache 共可存放 16 个块，采用直接映射方式，2 4=16，即Cache 字块地址 4 位；故 Cache 地址共 4+7=11 位，选 A。21.设指令中的地址码为 A，变址寄存器为 X，程序计数器为 PC，则变址间址寻址方式的操作数有效地址EA 是( )。A(PC)+A) B(X)+A) C(X)
23、+(A) D(X)+A（分数：2.00）A.B. C.D.解析：解析 变址间址寻址方式就是先变址后间址，在 4 个选项中，选项 A 为相对寻址，选项 C 为间址变址寻址，选项 D 为变址寻址。归纳总结 把变址和间址两种寻址方式结合起来，按寻址方式操作的先后顺序，有前变址和后变址两种形式。前变址方式即变址间址方式，先进行变址运算，其运算结果作为间接地址，间接地址指出的单元的内容才是有效地址，EA=(X)+A)。后变址方式即间址变址方式，将指令中的地址码先进行一次间接寻址，然后再与变址值进行运算，从而得到一个有效地址，有效地址 EA=(X)+(A)。22.给定二叉树如右图所示。设 N 代表二叉树的
24、根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是( )（分数：2.00）A.B.C.D. 解析：解析 考查二叉树的遍历。分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是 RNL。23.在 IP 数据报报头中有两个有关长度的字段，一个为报头长度(IHL)字段，一个为总长度(total length)字段，下面说法正确的是( )。A报头长度字段和总长度字段都以 8 比特为计数单位B报头长度字段以 8 比特为计数单位，总长度字段以 32 比特为计数单位C报头长度字段以 32 比特为计数
25、单位，总长度字段以 8 比特为计数单位D报头长度字段和总长度字段都以 32 比特为计数单位（分数：2.00）A.B.C. D.解析：解析 本题考查 IPv4 分组头结构，报文长度也就是首部长度，占 4 个 bit，以 4 字节为单位，必须是 4 字节的整数倍，而总长度是首部和数据之和的长度，单位是字节，因此答案是 C。24.在缺页处理过程中，操作系统执行的操作可能是( )修改页表磁盘 I/O分配页框A仅， B仅 C仅 D，和（分数：2.00）A.B.C.D. 解析：解析 缺页中断机制：突然有一个页面没有在内存中，发生中断，将进程放到阻塞队列中。因此，缺页中断需要调入新页面到内存中。要将新的页面
26、调入内存，则需要修改页表项并为新的页面分配页框。同时内存中没有页面，需要从外存读入，会发生磁盘 I/O。因此，和都是操作系统要执行的操作。25.下列关于无向连通图特性的叙述中，正确的是( )所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1A只有 B只有 C和 D和（分数：2.00）A. B.C.D.解析：解析 考查无向连通图的特性。每条边都连接了两个结点，则在计算顶点的度之时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。边数大于顶点个数减 1，如果定点数为 3，则边数为 2，边数=定点个数减 1；在顶点数 n3 的完全有向图中，没有度为 1 的节点，
27、如下图所示：26.一个支持并发的操作系统在运行过程中，调度模块会不断地选择新进程运行。在非抢先式操作系统中，下面不是引起操作系统重新选择新进程的直接原因是( )。A分配的时间片用完 B运行着的进程要等待某一信号到来C正在运行的进程出错 D有新进程进入就绪队列（分数：2.00）A.B.C.D. 解析：解析 本题考查进程调度的时机。在所列出的四个选项中，A、B 和 C 的情况一旦发生，处理机空闲，操作系统必须立即调度其他进程，而 D 选项有新的进程进入就绪状态，如果操作系统采用的是抢先式调度，则立即激活调度模块，进行进程调度，进程调度的结果可能引起进程切换，也可能维持当前进程运行而不切换；而当操作
28、系统采用非抢先式调度方式时，当新进程进入就绪状态，若此时处理机正在忙于处理当前运行进程的请求，则不会激活调度模块。这里需要了解进程调度的细节问题。27.假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10MHz，则总线带宽是( )。 A10MB/s B20MB/s C40MB/s D80MB/s（分数：2.00）A.B. C.D.解析：总线时钟频率为 10MHz，一个总线周期占用 2 个时钟周期，故 1s 内共有 5M 个总线周期；每个周期并行传输 4 字节信息，故总线带宽为 5M/s4B=20.MB/s。28.给定二叉树图所示。设 N
29、代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，7，5，6，1，2，4，则其遍历方式是( )。 * ALRN BNRL CRLN DRNL（分数：2.00）A.B.C.D. 解析：29.下列计算机总线属于串行总线的是( )。APCI B1394 CEISA DISA（分数：2.00）A.B. C.D.解析：解析 1394 是高性能的串行总线。归纳总结 IEEE-1394 是由 TEEE 标准委员会发布的，它的最初版本传输速率为 200Mbps，高版本有望支持 1600Mbps 的传输速率，甚至可达到 3200Mbps。IEEE-1394 构建在菊花链或
30、树状的拓扑结构上的，它支持 63 个节点，每个节点可以支持多达 16 台设备的菊花链。最新的高性能外部总线设计的趋势是使用串行结构，这样可以通过一根导线一次发送一位数据，而无须担心数据的到达时间，如 IEEE-1394 端口(使用高速串行技术)支持的传输速率高达 400Mbps(约 50MB/s)，USB 2.0 支持的传输速率可以为 480Mbps(约 60MB/s)。解题技巧 选项 A、C、D 均属于并行总线。30.关于以太网交换机，下面的论述中不正确的是( )。A交换机工作在数据链路层 B交换机的每个端口形成一个冲突域C交换机支持多端口同时收发数据 D交换机是一种多端口中继器（分数：2.
31、00）A.B.C.D. 解析：解析 本题考查交换机的工作原理和特性，交换机是工作在数据链路层的网络设备，每个端口是独立的冲突域，交换机的交换结构保证了多端口同时进行数据交换，多端口的中继器可以认为是集线器，其所有端口处于同一个冲突域内，因此答案为 D。31.操作系统的主要功能是管理计算机系统中的_。A程序和数据 B硬件 C资源 D中断（分数：2.00）A.B.C. D.解析：操作系统的定义就提到操作系统是控制和管理计算机硬件和软件资源的，硬件和软件资源统称为资源。D 项不属于操作系统所管理的资源，选其它任何一个选项都不全面。32.利用逐点插入建立序列(50，72，43，85，75，20，35，
32、45，65，30)对应的二叉排序树以后，要查找元素 30 要进行元素间的比较次数是( )。A4 B5 C6 D7（分数：2.00）A.B. C.D.解析：解析 利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素 30 的比较次数为 5 次。33.下列可能引起 Belady 异常的页面置换算法是( )。ALRU BClock CLFU DFIFO（分数：2.00）A.B.C.D. 解析：解析 本题考查对 Belady 现象的理解。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，
33、即页面数量由小到大，则发生缺页的次数会由高至低。但是使用 FIFO算法时，在未给进程或作业分配它所要求的页面数时，有时会出现分配的页面数增大，缺页次数反而增高的现象。这称为 Belady 异常。这种异常只在 FIFO 算法中出现，因为 FIFO 算法忽略了一种现象的存在，就是在内存中停留时间最长的页往往也是经常被访问的页。将这些页淘汰，很可能刚置换出去，又请求调用该页，致使缺页中断较高，严重降低内存的利用率。34.假设按低下标优先存储整型数组 A-3:8，3:5，-4:0，0:7时，第一个元素的字节存储地址是 100，每个整数占 4 个字节，问 A0，4，-2，5的存储地址是_。A1783 B
34、1784 C1985 D1984（分数：2.00）A.B. C.D.解析：公式：Loc(Aijkl)=100+(i-cl)v2v3v4+(j-c2)v3v4+(k-c3)v4+(1-c4)*4。35.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的_的两趟排序后的结果。A选择排序 B冒泡排序 C插入排序 D堆排序（分数：2.00）A.B.C. D.解析：直接插入排序是一种最基本的排序算法，基本操作为：将一个记录插入到一个已经排好序的有序表中，从而得到一个新的、长度增 1 的有序表。一般情况下，第 i 趟的操作为：在含有 i-1 个记录的有序子序列 r1i-1中插入一个新
35、记录 ri，变成含有 i 个记录的有序序列 r1i。设置 r0为空值，从 r1开始保存信息，可首先将待插入的记录 ri复制到 r0中，如下所示：36.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是_。A3，5，12，8，28，20，15，22，19B3，5，12，19，20，15，22，8，28C3，8，12，5，20，1 5，22，28，19D3，12，5，8，28，20，15，22，19（分数：2.00）A. B.C.D.解析：堆排序是另一种基于选择的排序方法。n 个元素的序列k1，k2，k3，kn，当且仅当满足以下关系时
36、，称之为堆：37.某 DRAM 芯片内部存储元排列成 10241024 的矩阵，且已知其存取周期为 0.1s，最大刷新间隔为2ms。当采用异步刷新方式时，死时间( )。 A=2ms B0.1ms C-0.2s D-0.1s（分数：2.00）A.B.C.D. 解析：当采用异步刷新方式时，将对 DRAM 芯片内 1024 行的刷新均匀分布在 2ms 内的不同时间，每次刷新一行；这样每次刷新只需停止一个存取周期，即“死时间”为一个存取周期0.1s，故选 D。38.8 位二进制无符号整数可表示的数值范围是( )。 A0255 B-128+127 C-127+127 D1256（分数：2.00）A. B
37、.C.D.解析：8 位二进制无符号整数可表示的数值范围为 02 8-1，即 0255。39.假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是( )。Ak-1 Bk Ck+1 Dk(k+1)/2（分数：2.00）A.B.C.D. 解析：解析 假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，探查次数最少的情况是第 1 个关键字通过 1 次比较后插入，第 2 个关键字通过 2 次比较后插入，第 k 个关键字通过 k 次比较后插入。总的比较次数=1+2+k=k(k+1)/2。40.完整的计算机系统由( )组成。 A运算器和控制器 BCP
38、U 和主存储器 C主机和外部设备 D硬件系统和软件系统（分数：2.00）A.B.C.D. 解析：完整的计算机系统由配套的硬件系统和软件系统组成。二、综合应用题(总题数：4，分数：40.00)41.已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子 a=0.75，散列函数的形式为 H(K)=K MOD P，回答下列问题：(1)构造散列函数；(2)画出散列表；(3)计算出等概率情况下查找成功的平均查找长度；(4)计算出等概率情况下查找不成功的平均查找长度。（分数：10.00）_正确答案：(解答 由 =0.75，得表长 m=11/0.
39、7515。(1)在一般情况下，H(K)=K MOD P 中，P 取质数或者不包含小于 20 的质因数的和数，因此选择 P=13。散列函数 H(K)=K MOD13。(2)散列表：)解析：解析 本题是对散列表的一种常见考查方式，题目的难点是求查找成功和不成功的平均查找长度。用链地址法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下：归纳总结 散列表的查找效率(比较次数)取决于：散列函数、处理冲突的方法和散列表的装填因子。当具体给出散列表的长度 m、元素个数 n，以及散列函数和解决冲突方式后，可以在求出散列表的基础上计算查找成功时的平均查找长度和查找不成功的平均查找长度。查找成功时的平均
40、查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列到的位置上要插入新元素时为找到空位置的探查次数的平均值。某机字长 32 位，采用定长操作码，单字长指令，共有机器指令 100 条，CPU 内部有通用寄存器 32 个，可作变址寄存器用，存储器按字节编址，指令拟用直接寻址、间接寻址、变址寻址和相对寻址等 4 种寻址方式。（分数：9.99）(1).分别画出寻址方式由操作码指出和寻址方式由专用字段指出时的指令格式。（分数：3.33）_正确答案：(100 条指
41、令需 7 位操作码，当寻址方式由操作码指出时，指令格式如下： 操作码(7 位) 形式地址 A(25 位)当寻址方式由专用字段指出时，指令格式如下： 操作码(7 位) 寻址方式(2 位) 形式地址(23 位)解析：(2).当指令寻址方式由操作码指出时，直接和间接寻址可寻址的主存空间大小为多少?（分数：3.33）_正确答案：(当指令方式由操作码指出时，形式地址 A 为 25 位，又存储器按字节编址，故直接寻址可寻址的主存空间大小为 225B=32MB；由于机器字长为 32 位，间接寻址可寻址的主存空间大小为 232B=4GB。)解析：(3).写出 4 种寻址方式下，有效地址 EA 的表达式。（分数
42、：3.33）_正确答案：(四种寻址方式下有效地址 EA 的表达式为 直接寻址 EA=A； 间接寻址 EA=(A)；变址寻址 EA=(IX)+A，其中 IX 为变址寄存器； 相对寻址 EA=(PC)+A，其中 PC 为程序计数器。)解析：42.对有五个结点 A，B，C，D，E 的图的邻接矩阵，（分数：10.00）_正确答案：( )解析：某计算机的主存地址空间为 256MB，按字节编址，指令 Cache 分离均有 8 个 Cache 行，每个 Cache 行的大小为 64B，数据 Cache：采用直接映射方式，现有两个功能相同的程序 A 和 B，其伪代码如下页所示：（分数：9.99）(1).若不考
43、虑用于 Cache 一致性维护和替换算法的控制位，则数据 Cache 的总容量是多少?（分数：3.33）_正确答案：(64B8=512B；)解析：(2).要组元素 a031和 a11各自所在的主存块对应的 Cache 行号分别是多少(Cache 行号从 0 开始)?（分数：3.33）_正确答案：(主存地址与 cache 的地址格式如下图所示：aij占 32 位，共四个字节；a00的开始地址为：320；a031与 a00相距 314 个地址单位，即 320+314=444；444 换成二进制：110111100；a11与 a00相距 2574 个地址单位，即 320+2574=1348；1348
44、 换成二进制：10101000100；)解析：(3).程序 A 和 B 的数据访问命令中各是多少?那个程序的执行时间更短?（分数：3.33）_正确答案：(程序 A 按行优先访问数组 aij：总共需要访问：256256=216次a00a01a02a03a04a05a06 a07第 1 块 a08a09a010a011a012a013a014 a015a016a017a018a019a020a021a022 a023第 2 块a024a025a026a027a028a029a030 a031a032a033a034a035a036a037a038 a039第 3 块a040a041a042a043a044a045a046 a047行优先的情况下，a00未命中，但 a01，a02，a03，a04，a05，a06，a07，a08，a09，a010，a011，a012，a013，a014，a015均命中，则未命中的有 a00，a016，a032即每块的块首元素，共有 212个块，即未命中次数为 212； 故程序 A 的数据访问命中率为： )解析：
