[考研类试卷]计算机专业（基础综合）模拟试卷97及答案与解析.doc

《[考研类试卷]计算机专业（基础综合）模拟试卷97及答案与解析.doc》由会员分享，可在线阅读，更多相关《[考研类试卷]计算机专业（基础综合）模拟试卷97及答案与解析.doc（44页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业（基础综合）模拟试卷 97 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列说法中，正确的是( )。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n 和 m 个元素的有序表（递增）归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n1。（A）仅、（B） 、（C）仅 、（D）仅、2 下列关于栈的说法中，正确的是( )。若进栈顺序为 a、b、 c，则通过出栈操

2、作可能得到 5 个 a、b、c 的不同排列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少了存取时间（A）仅（B）仅 、（C）仅 （D）仅、3 若将 n 阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)/21中，第一个非零元素 a(1，1)存于 BO中，则存放到 Bk中的非零元素a(i，j)(1in，1jn)的下标 i、j 与 k 的对应关系是 ( )。（A）k=i(i+1)/2+j（B） k=j(i1)/2+j1（C） k=j(j+1)/2+i（D）k=j(j 1)/2+i14 知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则

3、原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序： C_BHGJI_（A）CBEDAHGFIJ（B） CHEDABGFIJ（C） CBEDAJGFIH（D）CJEDAHGFIB5 设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对( )个字符编码。（A）3（B） 4（C） 5（D）66 下列说法中，正确的是( )。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n22e 若邻接表中有奇数个边表结点，则该图一定是有向图 对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历 使用队列实现广度优先遍

4、历算法，则每个顶点进队列的次数可能大于 1（A）仅、（B）仅 、（C）仅 、（D）仅、7 下列关于生成树的说法中，正确的是( )。（A）最小生成树是指权值之和为最小的生成树，且唯一（B）某图的广度优先生成树的高度一定大于等于深度优先生成树的高度（C） Prime 算法和 Kruskual 算法构造的最小生成树一定一样（D）Prime 算法适用于求边稠密的图的最小生成树8 下列关于 m 阶 B+树的说法中，正确的是 ( )。具有 n 个关键字的结点至少含有 n+1 棵子树所有叶子结点包含全部关键字B+树支持随机索引B+树可用于文件的索引结构（A）仅、（B）仅 、（C）仅 、（D）仅、9 利用逐点

5、插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行( )次元素间的比较。（A）4（B） 5（C） 6（D）710 对以下关键字序列用快速排序算法进行排序，速度最慢的是( )。（A）1，4，7，10，15，24（B） 2，5，3，20，15，18（C） 4，5，7，13，10，9（D）4，7，8，5，19，1611 在外部排序算法中，最佳归并树主要的作用是( )。（A）产生初始归并段（B）完成归并排序（C）对归并排序进行优化（D）增大归并路树12 下列说法中，错误的是( )。时钟频率和 CPI 成反比关系数据字长等于 MDR

6、的位数A 主机的 CPU 主频高于 B 主机的 CPU 主频，则前者运算能力将会高于后者（A）仅、（B）仅 、（C）仅 、（D）、13 假定采用 IEEE 754 单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（A）(+1125)2 10（B） (+1125)2 11（C） (+0125)2 11（D）(+0125)2 1014 个 8 位的二进制整数，若采用补码表示，且由 3 个“1”和 5 个“0” 组成，则最小值为( ) 。（A）127（B） 32（C） 125（D）一 315 台 8 位微机的地址总线为 16 条，其 RAM 存储器容量为 32KB，首地址为40

7、00H，且地址是连续的，可用的最高地址为( )。（A）BFFFH（B） CFFFH（C） DFFFH（D）EFFFH16 有效容量为 128KB 的 Cache，每块 16B，8 路组相联。字节地址为 1234567H的单元调入该 Cache，其 Tag 应为( )。（A）1234H（B） 2468H（C） 048DH（D）12345H17 在单发射、按序流动的普通流水线中，可能出现下列( )数据相关问题。写后读相关 RAW读后写相关 WAR写后写相关 WAW（A）仅（B）仅 、（C）仅 （D）仅、18 在按字节编址的计算机中，一条指令长 16 位，当前分支转移指令（采用相对寻址）地址为 30

8、00，指令地址的偏移量为5，当执行完此转移指令后，PC 的值为( )。（A）2996（B） 2997（C） 3001（D）300219 以下给出的事件中，无须异常处理程序进行中断处理的是( )。（A）缺页故障（B）访问 Cache 缺失（C）地址越界（D）除数为 020 假定一台计算机的显示存储器用 DRAM 芯片实现，若要求显示分辨率为16001200，颜色深度为 24 位，帧频为 85Hz，显存总带宽的 50用来刷新屏幕，则需要的显存总带宽至少约为( )。（A）245Mbit/s（B） 979Mbit/s（C） 1958Mbit/s（D）7834Mbit/s21 总线宽度只与下列( )选项

9、有关。控制线根数地址线根数数据线根数（A）仅（B）仅 、（C）仅 （D）、22 在主机和外设的信息传送中，( )没有使用程序控制方式。（A）程序查询方式（B）程序中断方式（C） DMA 方式（D）通道方式23 下列关于操作系统结构说法中，正确的是( )。当前广泛使用的 Windows XP 操作系统，采用的是分层式 OS 结构模块化的 OS 结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易由于微内核结构能有效支持多处理机运行，故非常合适于分布式系统环境采用微内核结构设计和实现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等（A）

10、仅、（B）仅 、（C）仅 （D）仅、24 在有一个 CPU 和两台外设 D1 和 D2，且能够实现抢占式优先级调度算法的多道程序环境中，同时进入优先级由高到低的 P1， P2 ， P3 的 3 个作业，每个作业的处理程序和使用资源的时间如下：P1: D2 (30ms)，CPU (10ms)，D1 (30ms)，CPU (10ms)P2: D1 (20ms)，CPU (20ms)，D2 (40ms)P3: CPU (30ms)，D1 (20ms)假设对于其他辅助操作时间忽略不计，CPU 的利用率是( )。（A）478（B） 578（C） 678（D）77825 设有如下两个优先级相同的进程 P1

11、 和 P2。信号量 S1 和 S2 的初值均为 0，试问P1、P2 并发执行结束后， z 的值可能是( )。（A）4、8、11（B） 4、6（C） 6、8（D）4、826 系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是( )。出现了环路没有环路每种资源只有一个，并出现环路每个进程结点至少有一条请求边（A）、（B）仅 、（C）仅 、（D）都能判断27 下列存储管理方式中，会产生内部碎片的是( )。分段虚拟存储管理分页虚拟存储管理段页式分区管理固定式区区管理（A）仅、（B）仅 、（C）仅 （D）仅、28 下列程序设计技术和数据结构中，适合虚拟页式存储系统的有( )。堆栈Hash 函数索

12、引的符号表顺序搜索二分法查找纯代码矢量操作间接寻址矩阵操作（A）、（B） 、（C） 、（D）、29 下面关于文件的叙述中，错误的是( )。打开文件的主要操作是把指定文件复制到内存指定的区域对一个文件的访问，常由用户访问权限和用户优先级共同限制文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件（A）仅（B）仅 、（C）仅 、（D）、30 在 PCDOS 中，某磁盘文件 A 与 B，它们所占用的磁盘空间如下所示。试问A、B 文件在磁盘上各占( )簇。（A）3，3（B） 4，5（C） 5，3（D）5，431 某磁盘盘组共有

13、 10 个盘面，每个盘面上有 100 个磁道，每个磁道有 32 个扇区，假定物理块的大小为 2 个扇区，分配以物理块为单位。若使用位图( bitmap)管理磁盘空间，则位图需要占用的空间大小是( )。（A）2000B（B） 12000B（C） 6000B（D）16000B32 关于 SPOOLing 技术的说法，以下正确的是( )。SPOOLing 系统中不需要独占设备SPOOLing 系统加快了作业完成的速度当输入设备忙时，SPOOLing 系统中的用户程序暂停执行，待 I/O 空闲时再被唤醒执行输出操作在采用 SPOOLing 技术的系统中，用户的打印结果首先被送到内存固定区域（A）仅、（

14、B）仅 （C）仅 、（D）仅、33 如图 71 所示的是某 IP 网络连接拓扑结构，共有 ( )。（A）5 个冲突域，1 个广播域（B） 3 个冲突域，3 个广播域（C） 4 个冲突域2 个广播域（D）6 个冲突域，2 个广播域34 长度为 1km，数据传输率为 10Mbit/s 以太网，电信号在网上的传播速度是200m/s。假设以太网数据帧的长度为 256bit，其中包括 64bit 帧头、检验和及其他开销。数据帧发送成功后的第一个时间片保留给接收方，用于发送一个 64bit 的确认帧。假设网络负载非常轻（即不考虑冲突的任何情形），则该以太网的有效数据传输速率为( ) 。（A）421Mbit

15、/s（B） 117Mbit/s（C） 609Mbit/s（D）519Mbit/s35 下面技术无法使 10Mbit/s 的以太网升级到 100Mbit/s 的是( )。（A）帧长保持不变，网络跨距增加（B）采用帧扩展技术（C）传输介质使用高速光纤（D）使用以太网交换机，引入全双工流量控制协议36 某端口的 IP 地址为 172167131/26，则该 IP 地址所在网络的广播地址是( )。（A）172167255（B） 172167129（C） 172167191（D）17216725237 下列关于 ARP 的说法中，错误的是( )。ARP 的请求报文是单播的ARP 的响应报文是单播的如果局

16、域网 A 的主机 1 想和局域网 B 的主机 2 通信，但是主机 1 不知道主机2 的物理地址，主机 1 通过发送 ARP 报文就可以解决（A）仅（B）仅 （C）仅 、（D）仅、38 个网段的网络号为 19890100/27，子网掩码固定为255255255224，最多可以分成( )个子块，而每个子块最多具有( )个有效的 IP 地址。（A）8，30（B） 6，30（C） 16，14（D）32，639 A 和 B 建立 TCP 连接， MSS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个 RTT 内，A 向 B 发送了 4KB 的数据（TCP 的数据部分）

17、，并且得到了 B 的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT 中，A 最多能向 B 发送( )数据。（A）2KB（B） 4KB（C） SKB（D）8KB40 在进行域名解析的过程中，由( )获取的解析结果耗时最短。（A）主域名服务器（B）辅域名服务器（C）缓存域名服务器（D）转发域名服务器二、综合应用题41-47 小题，共 70 分。40 设哈希函数为：H(key)=key mod 13，其中 key 为关键字，mod 为取模运算，试用关键字序列3925，15 ，54，26，24，14，21，37，38 构造哈希表。41 用链地址法处理冲突，画出该哈希表的存储结构图

18、，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。42 设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。42 输入一整数数组5，7 ，6，9，1 1，10，8 ，该整数序列为图 22 所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。要求：43 给出算法的基本设计思想。44 根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出

19、注释。45 说明你所设计算法的时间复杂度。45 某字长为 8 位的计算机中，带符号整数采用补码表示，x=68，y=80，x 和y 分别存放在寄存器 A 和 B 中，请回答下列问题（最终要求用十六进制表示二进制序列）。46 寄存器 A 和 B 中的内容分别是什么？47 若 x 和 y 相加后的结果存放在寄存器 C 中，则寄存器 C 中的内容是什么？运算结果是否正确？此时，溢出标志 OF、符号标志 SF 和零标志 ZF 各是什么？加法器最高位的进位 Cn 是什么？48 若 x 和 y 相减后的结果存放在寄存器 D 中，则寄存器 D 中的内容是什么？运算结果是否正确？此时，溢出标志 OF、符号标志

20、SF 和零标志 ZF 各是什么？加法器最高位的进位 Cn 是什么？49 若将加法器最高位的进位 Cn 作为进位标志 CF，能否直接根据 CF 的值对两个带符号整数的大小进行比较？49 假定一个计算机系统中有一个 TLB 和一个 L1 Data Cache。该系统按字节编址，虚拟地址 16 位，物理地址 12 位，页大小为 128B，TLB 为 4 路组相连，共有 16个页表项，Ll Data Cache 采用直接映射方式，块大小为 4B，共 16 行。在系统运行到某一时刻时，TLB、页表和 L1 Data Cache 中的部分内容如图 23 所示。试回答下列问题：50 虚拟地址中哪几位表示虚拟

21、页号？哪几位表示页内偏移量？虚拟页号中哪几位表示 TLB 标记？哪几位表示 TLB 索引？51 物理地址中哪几位表示物理页号？哪几位表示页内偏移量？52 主存（物理）地址如何划分成标记字段、行索引字段和块内地址字段？53 CPU 从地址 067AH 中取出的值为多少？说明 CPU 读取地址 067AH 中内容的过程。53 在单 CPU 和两台输入/输出设备(I1，I2)的多道程序设计环境下，同时投入 3 个作业 J1、J2 和 J3 运行。这 3 个作业对 CPU 和输入/ 输出设备的使用顺序和时间如下所示。J1: 12 (30ms)； CPU (10ms)； 11 (30ms)； CPU (

22、10ms)； 12 (20ms)J2: 11 (20ms)； CPU (20ms)； 12 (40ms)J3: CPU (30ms)； 11 (20ms)； CPU (10ms)； I0 (10ms)假定 CPU、I1 、I2 都能并行工作，J1 优先级最高， J2 次之，J3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 I1 和 I2。试求：54 3 个作业从投入到完成分别需要的时间。55 从投入到完成的 CPU 利用率。56 110 设备利用率。56 下列程序实现了矩阵乘法。int A100 150 ，int B150 200 ；int C100200l；for

23、(i=0；i 100；i+)for j=0； j200； j+)for (k=0； k150； k+)Cij+=Aik*Bkj；假设矩阵 A 和矩阵 B 的初值已经初始化过，矩阵 C 初始化为 0，各矩阵均以页为单位连续存放（且假定是行优先存储）。又假定一个整数占用 1 个字，代码以及变量 i、j 和 k 存放在其他页面里，并且存取变量 i、j 和 k 时不存在缺页问题。主存初始为空，在请求分页存储管理中，页面淘汰算法为 FIFO。57 作业分配 10 个页面，每个页面为 100 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少？当执行完程序时，留在内存的 10 个页面各属

24、于哪些矩阵？58 当作业分配两个页面，每个页面为 500 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少？当执行完程序时，留在内存的 10 个页面各属于哪些矩阵？（注： c+=c+a*b 的执行顺序为：读 a、读 b、计算 ab、读 c、计算 c+ab、写 c）58 假设主机 1（在图 24 中网络 1 以太网上）是可以运行 IE 浏览器的某客户机，主机 4（在图 24 中网络 3 以太网上）为天勤论坛 Web 服务器（IP 地址为202197115），主机 5（在图 24 中网络 2 的 FDDI 主干网上）为天勤论坛DNS 服务器，该 DNS 服务器上有天勤论坛 We

25、b 站点的域名地址到 IP 地址解析。其中，路由器 1 以太网端口（a 端口）的 MAC 地址是 E3，IP 地址是20219712，3，子网掩码是 2552552550；路由器 1 的 FDDI 端口（c 端口）的 MAC 地址是 Fl， IP 地址是 202197101，子网掩码是2552552550。路由器 2 的以太网端口（b 端口）的 MAC 地址是 E4，IP 地址是 20219 7114，子网掩码是 2552552550；路由器 2 的 FDDI 端口（c 端口）的 MAC 地址是 F3，IP 地址是 20219710，2，子网掩码是2552552550，其他站点的 IP 地址和

26、 MAC 地址如图 24 所示。试问：59 为了使主机 1 能够通过域名访问天勤论坛 Web 服务器，主机 1 上的 IP 地址、子网掩码、默认网关 IP 地址、DNS 服务器地址应该如何配置？60 假设主机 1 使用的 1234 的 UDP 端口与 DNS 服务器通信，使用的 1235 的 TCP端口与 Web 服务器通信，请写出主机 1 发给 DNS 服务器和 Web 服务器的 UDP 报文和 TCP 报文中的源端口号和目的端口号、IP 报文中的源 lP 地址和目的 IP 地址以及在 3 个物理网络中发送的 MAC 帧中的源 MAC 地址和目的 MAC 地址。61 从(2)的分析中，得出了

27、什么结论？请阐述。注：FDDI 为光纤分布式数据接口。计算机专业（基础综合）模拟试卷 97 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：有序表插入的时候是不能指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思想是：先通过元素比较找到插入的位置，再在该位置上插入，故 I 错误。:从单链表插入和删除的语句描述中可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故正确。:删除双链表中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故正确。：当一

28、个较短的有序表中所有元素均小于另一个较长的有序表中所有的元素，所需比较次数最少。假如一个有序表为 1、3、4，另一个有序表为 5、6、7、8、12，这样只需比较 3 次即可，故答案应该是 n 和 m 中较小者，即 min(n，m)，故错误。2 【正确答案】 A【试题解析】 ：该选项旨在让考生知道一个公式。对于 n 个不同元素进栈，出栈序列的个数为 可以马上得出，当 n=3 时，出栈序列个数为故正确。：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈顶指针，链空即栈空( top=NULL)，故错误。m: 由于栈中数据的操作只有入栈和出栈，且时间复杂度均为 O(1

29、)，因此并没有减少存取时间，故错误。补充知识点：共享栈解析：两个栈共享一个数组 AOMaxSize1的空间，从而构成共享栈。数组 A 的两端是固定的，而栈底也是固定的，为此将下标为 0 的一端作为栈 l 的栈底，其栈顶指针为 topl，将下标为 MaxSize1 的一端作为栈 2 的栈底，其栈顶指针为 top2，如图74 所示。栈 1的四要素如下：栈空条件： top1=1。栈满条件：top1=top2 1。元素x 进栈：top1+；将元素 x 插入 Atop1处。出栈元素：弹出 Atopl元素；topl-。栈 2 的四要素如下：栈空条件：top2=MaxSize 。 栈满条件：top2=top

30、 1+1。元素 x 进栈：top2-；将元素 x 插入 Atop2处。 出栈元素：弹出Atop2元素；top2+。注：以上都默认指针指向当前元素的下一个位置。3 【正确答案】 D【试题解析】 对于元素 a(i，j)而言，前面有 j1 列，第 1 列到第 j1 列的元素个数分别为 1j1 个，由等差数列求和公式可算得一共有 jx(j1)/2 个元素，故k=j(j1)/2+i1（注意 B 数组是从 0 开始存元素，因此要减去 1）。4 【正确答案】 A【试题解析】 对于一棵二叉树（包括子树），它的遍历序列对应的结构应该是：先序遍历：|根 |左子树|右子树|，中序遍历：| 左子树|根|右子树|，后序

31、遍历：| 左子树|右子树| 根|，由题目中给出的先序序列的第一个结点我们找到树的根 A，然后在中序序列中找到 A，并以 A 为分界将中序序列划分为|C_ED|A|_GFI_|，所以 C_ED为左子树，GFI 为右子树，再对应到后序遍历序列上，这里左子树结点的个数等于中序遍历序列中左子树结点的个数，因此 C_B 为左子树，HGJI_ 为右子树，这样把中序序列和后续序列中的左右子树一对比，则 CBED 为左子树，FGHIJ 为右子树。答案选 A。总结：根据树的遍历结果来还原二叉树，或者根据其中的两个遍历序列来求第三个遍历序列这是历年考试的热点，考生需要记住的是无论怎样的序列，要想构建二叉树必须有中

32、序序列。这是很显然的，这里说明一下原因：我们知道二叉树的定义是递归的，那么我们在构建二叉树的时候势必也会用到递归这种方法，而这种形式的递归我们把它称之为分治（从中间分开来治理）法，而在三种遍历序列中只有中序遍历的结构才体现了这种思想。5 【正确答案】 B【试题解析】 首先，赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如 1 和 10 就不行，因为 1 是 10 的前缀。既然 1 和 01 已经使用了，所以1 和 01 开头的码字不能再使用。又由于赫夫曼树的高度为 5，故赫夫曼编码的长度不能超过 4，只剩下 0000、0001、0010、O011 等 4 种编码（这种编码方式可得

33、到最多），故选 B 选项。 注意：本题选的是最多还可以对多少个字符编码，所以不能选取 001、000 等编码。例如选取 001，就意味着 0010 和 0011 不能使用，这样可编码的字符就少了 1 个。 总结： (1)有 n 个叶子结点的赫夫曼树的结点总数为2n1。 (2)高度为 h 的赫夫曼树中，至少有 2h1 个结点，至多有 2hl 个结点。 (3)赫夫曼树中一定没有度为 1 的结点。 (4) 赫夫曼树中两个权值最小的结点一定是兄弟结点。 (5)树中任一非叶子结点的权值一定不小于下一层任一结点的权值。 补充例题：一棵赫夫曼树共有 215 个结点，对其进行赫夫曼编码，共能得到多少个码字？

34、解析：求多少个码字就是求有多少个叶结点，从(1)可以得到，叶结点的个数为 108 个，故可以得到 108 个码字。6 【正确答案】 D【试题解析】 ：总结如下： 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 n2。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，非零元素的个数为 2e。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n22e， 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，非零元素的个数为 e。 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，零元素的个数为n2e。 根据，故 I 正确。 :无向图采用邻接表表示时，每条边存储

35、两次，所以其边表结点个数为偶数，故边表结点为奇数只能是有向图，故正确。 :深度优先遍历算法是先访问一个顶点 v，然后是离开顶点越远越优先访问，即相当于二叉树的先序遍历，故错误。 ：采用广度优先遍历算法遍历一个图时，每个顶点仅遍历一次，所以最多只能进队 1 次，故错误。7 【正确答案】 D【试题解析】 A:最小生成树是指权值之和为最小的生成树，但是不唯一，故 A 选项错误。 B:由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的生成树的树高大于等于广度优先算法构造的生成树的树高，故 B 选项错误。 C:当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故 C 选项错误。

36、 D：Prime 算法的时间复杂度为 O(n2)，适合稠密图；Kruskual 算法的时间复杂度为 O(elog2e)，适合稀疏图，故 D 选项正确。8 【正确答案】 B【试题解析】 一棵 m 阶 B+树满足下列条件：每个分支结点至多有 m 棵子树。根结点或者没有子树，或者至少有两棵子树。除根结点外，其他每个分支结点至少有m/2 棵子树。具有 n 个关键字的结点含有 n 棵子树。所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字的大小顺序链接。所有分支结点中仅包含它的各个子结点中最大关键字及指向子结点的指针。B+树中，所有非终端结点可以看成是索引部分，故可用于文件的索引结构。

37、注意：由于 B+树为链式存储结构，所以不支持随机检索。综上所述，可知、正确，、错误，故选 B 选项。补充知识点：很多考生被 B+树和 B树的基本概念弄混，下面做一个小结。解析：m 阶 B+树和 m 阶 B树的主要差异如下：在 B+树中，具有 n 个关键字的结点含有 n 棵子树；而在 B树中，具有 n 个关键字的结点至少含有(n+1)棵子树。在 B+树中，每个结点（除根结点外）中的关键字个数 n 的取值范围是m/2nm，根结点 n 的取值范围是 2nm；而在 B树中，除根结点外，其他所有非叶子结点的关键字个数 n 的取值范围是m/21nm1，根结点 n 的取值范围是1nm1。记忆方式：“B”中有

38、个“一”号，自然关键字个数相对于 B+减掉了 1。在 B+树中，所有叶子结点包含了全部关键字，即其他非叶子结点中的关键字包含在叶子结点中；而在 B树中，关键字是不重复的。在 B+树中，所有非叶子结点仅仅是起到了索引的作用，即结点中的每个索引项只含有对应子树的最大关键字和指向子树的指针，不含有该关键字对应记录的存储地址。而在 B树中，每个关键字对应一个记录的存储地址。在 B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点，所有叶子结点链接成一个链表；而在 B树中，叶子结点并不会有指针相连。9 【正确答案】 B【试题解析】 由题可以建立出如图 75 所示的一棵二叉排序树。查找元素

39、 30 次经过比较的元素为50，43，20，35，30，共有 5 次元素间的比较，因此本题选 B 选项。10 【正确答案】 A【试题解析】 首先需要知道快速排序的一个特性，即元素越无序，快速排序越快；元素越有序，快速排序越慢。但是一般情况下，有序的元素序列比较少，大部分情况都是杂乱无章的一堆数，所以说快速排序是所有排序中性能最好的排序方法。有些同学可能会有疑问，快速排序最差的时间复杂度是 O(n2)，而有不少排序算法最坏的时间复杂度是 O(nlog2n)，比如堆排序。为什么快速排序的性能是最好的呢？因为快速排序出现最坏性能的情况实在是太少发生了，所以要看综合的性能，不能只看最坏的（记住就好，在

40、此不举例子了）。本题 A 选项是一个有序序列，所以速度肯定最慢。 总结：如果元素基本有序，使用直接插入排序效果最好；如果元素完全没序，使用快速排序效果最好。11 【正确答案】 C【试题解析】 A:产生初始归并段的工作应该由置换一选择排序完成，故 A 选项错误。 设输入的关键字满足 k1k 2k m，缓冲区大小为 m，用置换选择排序方法可产生n/n 个初始归并段。 B:因为最佳归并树是针对排序之后的初始归并段操作，所以归并排序不可能由最佳归并树完成，故 B 选项错误。 C ：最佳归并树仿造赫夫曼树的构造过程，以初始归并段的长度为权值，构造具有最小带权路径长度的赫夫曼树，可以有效地减少归并过程中的

41、读写记录数，以加快外部排序的速度，故 C 选项正确。 D:增大归并路数应该是由败者树来完成的，故 D 选项错误。12 【正确答案】 D【试题解析】 ：时钟频率和 CPI 并无关系。时钟频率的提高仅仅是将时钟周期缩短，并没有改变执行一条指令所需要的时钟周期数，故错误。: 般来讲，MDR 的位数和存储字长相等，而数据字长是一次存取数据的长度，可以和 MDR 不相等，故 错误。：CPU 的主频是表示在 CPU 内数字脉冲信号震荡的次数，是衡量 CPU 运算速度的重要参数，但不是唯一的参数。故不能直接根据主频来比较运算能力，故错误。13 【正确答案】 B【试题解析】 45100000H 的二进制数为

42、0100 0101 0001 0000 0000 0000 0000 0000，第 1 位为符号位，表示正数，随后 8 位 1000 1010 为用移码表示的阶码，减去 127 得到十进制数 11，而 IEEE 754 中单精度数在阶码不为 0 时隐含 1，所以尾数为(1.0010) 2=1.125。14 【正确答案】 C【试题解析】 8 位补码最小时必为负数，所以第一位（符号位）必须为 1。而负数的数值位绝对值越大，则此负数越小。又负数的补码表示的高位 0 相当于原码表示的 1，故当剩下的 2 个“1”在最低位，5 个“0”在数值位的最高位时此负数最小。该负数的补码为 10000011，则原

43、码为 11111101转换成十进制为125。15 【正确答案】 A【试题解析】 32KB 存储空间共占用 15 条地址线，若 32KB 的存储地址起始单元为 OOOOH，其范围应为 00007FFFH，但现在的首地址为 4000H，即首地址后移了，因此最高地址也应该相应后移。故最高地址为 4000H+7FFFH=BFFFH。归纳总结：32KB 的存储空间是连续的，由于首地址发生变化，末地址也会跟着发生变化。16 【正确答案】 C【试题解析】 因为块的大小为 16B，所以块内地址字段为 4 位；又因为 Cache 容量为 128KB，8 路组相联，所以可以分为 1 024 组(128KB/(81

44、6B)=1 024)，对应的组号字段 10 位；剩下为标记字段。1234567H=OO01001000110100010101100111，标记字段为高 14 位，00010010001101=048DH，故选 C 选项。归纳总结：组相联映像对应的主存地址应包括 3 个部分，即标记(Tag)、组号(Index)和块内地址(Offset)。解题技巧：首先将主存地址由十六进制变成二进制，其中块内地址字段为最后 4 位，组号字段为中间 10 位，剩下的就是标记字段，将标记字段二进制转换为十六进制，即可得出结果。17 【正确答案】 A【试题解析】 指令取操作数的动作一定在写回结果之前，故在按序流动的单

45、发射（普通标量）普通流水线中，先进入流水线的指令的取操作数和写回结果的动作一定位于后续指令写回结果的动作之前，故不可能出现 WAR 和 WAW。唯一可能出现的数据相关问题是后续指令在前一指令写回结果之前读相关的操作数，即RAW。注：而在非按序流动的流水线中，允许后进入流水线的指令超过先进入流水线的指令先流出流水线，故 3 种数据相关都可能出现。提醒：直接按照中文翻译的比如“读后写”容易理解为“先读后写”，事实上根据英文的意思，应该是“先写后读”，容易绕晕，注意理顺思路，要反着读。18 【正确答案】 B【试题解析】 首先给出解答步骤，当前指令地址为 3000，取完这条指令后，PC的值增加一个指令

46、字长度，即 3002，加上偏移量5，所以执行完这条指令后，目标地址为 2997，然后将这个值覆盖到 PC 当中。总结：这里面存在两个问题：1）PC 值到底如何计算？2)得出的目标地址到底放哪里？这是一个当年困扰笔者和很多考生的一个很典型的问题，PC 到底是多少呢？“然后 PC=PC+1”，老师经常这么说。可是这里的“1”到底怎么理解？一个字节？一个指令字？你先别急着回答，笔者翻阅了很多书籍，也参考了各大院校的自主命题以及 408 统考真题，发现理解各不一样，拿北京理工大学 2005 年的一个选择题为例（在按字节编址的计算机中，一条指令长 16 位，然后取完指令后，PC 的值是多少？），这里参考

47、答案把加 1 理解成了 1 个字节。在 2009 年 408 真题当中同样类型的题目（指令字长 16 位，按字节编址），题于给出的却是每取出一个字节，PC+1，那么取完这条指令时，PC 的值便自增了 2，也就是说在我们熟悉的那句话“当取出一条指令后，PC 的值就+1”中，这里的 1 便是 1 个指令字的长度。在考试当中我们怎么理解？当然是按真题的讲解，一切以得分为目标，也就是说以后遇到这样的题，就把这里的 1 理解为一个指令字。得到的目标地址后不要以为就拿这个地址去寻址去了，记住，所有的取指令的地址都是从 PC 传到 MAR 中然后去寻址的，也就是说得到目标地址后还要把这个地址覆盖到 PC 当

48、中。终于讲解完毕了，对于考试来说也就够了，可是你真的觉得这就算完了吗？远不是这样，以上的理解都是片面的。(1) PC 自增 1 的情况指出现在无流水(nonpipeline)的情况下，这个时候取指，译码，执指都是顺序执行的。而在有流水的情况下就比较复杂了，这里用 arm7 的三级流水线为例。流水线使用三个阶段，因此指令分为三个阶段执行：1）取指（从存储器装载一条指令）；2)译码（识别将要被执行的指令）；3）执行（处理指令并将结果写回寄存器）。而 R15 (PC)总是指向“正在取指 ”的指令，而不是指向“正在执行”的指令或正在“译码”的指令。一般来说，人们习惯性约定将“正在执行的指令作为参考点”，称之为当前