1、考研计算机学科专业基础综合-6-1 及答案解析(总分：149.96，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.下列叙述中，正确的是_。非空循环单链表 head 的尾结点 p 满足 pnext=head带头结点的循环单链表的头指针为 head，如果 headnextnextnext=head 成立，则该单链表的长度为 3静态链表中的指针表示的是下一个元素在数组中的位置将长度为 n 的单链表链接在长度为 m 的单链表之后的算法时间复杂度为 O(1) A.仅、 B.、 C.仅、 D.仅、（分数：2.00）A.B.C.D.2.利用栈求表达式的值时，设立运算数栈 s
2、。假设栈 S 只有两个存储单元，在下列表达式中，不发生溢出的是_。 A.A-B*(C-D) B.(A-B)*C-D C.(A-B*C)-D D.(A-B)*(C-D)（分数：2.00）A.B.C.D.3.设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B中，A11存放到 B1中(假定不用 0 下标)，那么 Bk存放的元素的行号是_。 A BC D （分数：2.00）A.B.C.D.4.某完全二叉树的结点个数为 4N+3，则该树的叶结点个数为_。 A.2N B.2N-1 C.2N-2 D.2N+2（分数：2.00）A.B.C.D.5.下列说法中，正确的
3、是_。具有 10 个叶子结点的二叉树中有 9 个度为 2 的结点设高度为 5 的二叉树上只有度为 0 和度为 2 的结点，则该二叉树中所包含的结点数至少为 9一棵完全二叉树上有 1001 个结点，则可知叶子结点的个数为 501 个高度为 h 的完全二叉树最少有 2h个结点 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.6.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则为使其平衡，应做_型调整。 A.LL B.RR C.RL D.LR（分数：2.00）A.B.C.D.7.下列关于无向图
4、的说法中，正确的是_。无向图中某个顶点的度是指图中与该顶点连通的项点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n-1 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分量 A.仅、 B.仅、 C.仅 D.、（分数：2.00）A.B.C.D.8.下列关于强连通图的说法中，正确的是_。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.9.假设初始为空的散列表的地址空间为(010)，散列函数为 H(key)=key rood 11，采
5、用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、48，则最后一个关键字值 48 的插入位置是_。 A.4 B.5 C.6 D.8（分数：2.00）A.B.C.D.10.设待排序元素序列所有元素的排序码都相等，则下列排序方法中排序速度最慢的是_。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.基数排序（分数：2.00）A.B.C.D.11.设线性表中每个元素有两个数据项 K1 和 K2，现对线性表按下列规则进行排序：先看数据项 K1，K1 值小的在前，大的在后；在 K1 值相同的情况下，再看数据项 K2，K2 值小的在前，大的在后满足这种要求的排序方法是_。 A.先
6、按 K1 值进行直接插入排序，再按 K2 值进行简单选择排序 B.先按 K2 值进行直接插入排序，再按 K1 值进行简单选择排序 C.先按 K1 值进行简单选择排序，再按 K2 值进行直接插入排序 D.先按 K2 值进行简单选择排序，再按 K1 值进行直接插入排序（分数：2.00）A.B.C.D.12.下列说法中，错误的是_。设浮点数的基数为 4，尾数用原码表示，则 0.000 010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次 A.仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.13.下列关于定点数原码一位乘法的
7、描述中，错误的是_。符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位在原码一位乘算法过程中，所有的移位均是算术移位操作假设两个 n 位数进行原码一位乘，部分积至少需要使用 n 位寄存器 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.14.某容量为 256MB 的存储器由若干 16M8bitDRAM 芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是_。 A.20 B.24 C.32 D.36（分数：2.00）A.B.C.D.15.现有一 64K2bit 的存储器芯片，欲设计具有同样存储容量的存储器，有_种方法可以合理地安排地址线和数据线引脚的数目，且使两者
8、之和最小。 A.2 B.3 C.4 D.5（分数：2.00）A.B.C.D.16.某计算机有 30 个通用寄存器，采用 32 位定长指令字，操作码字段(不含寻址方式)为 8 位，Add 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Add 指令中偏移量的取值范围是_。 A.-40964095 B.-20482047 C.-10231024 D.-30713072（分数：2.00）A.B.C.D.17.与本指令的地址有关的寻址方式是_。 A.寄存器寻址 B.直接寻址 C.相对寻址 D.间接寻址（分数：2.00）A.B.C
9、.D.18.假定执行最复杂的指令需要完成 6 个子功能，分别由对应的功能部件 AF 来完成，每个功能部件所花的时间分别为 80ns、40ns、50ns、70ns、20ns、30ns，流水线寄存器延时为 20ns，现把最后两个功能部件 E 和 F 合并，以产生一个五段流水线。该五段流水线的时钟周期至少是_。 A.70ns B.80ns C.90ns D.100ns（分数：2.00）A.B.C.D.19.微操作信号发生器的设计与下列因素中的_基本无关。 A.CPU 寄存器数量 B.指令系统 C.数据通路 D.机器字长（分数：2.00）A.B.C.D.20.微指令的组成部分不可能包含_。微操作控制字
10、段 外部条件字段操作码字段 下地址字段 A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.21.在计数器定时查询方式下，若每次计数从 （分数：2.00）A.B.C.D.22.以下 4 个步骤在通道过程中的正确顺序是_。组织 I/O 操作 向 CPU 发出中断请求编制通道程序 启动 I/O 通道 A. B. C. D.（分数：2.00）A.B.C.D.23.下列关于批处理技术和多道程序设计技术说法中，正确的是_。批处理系统的最主要缺点是不能并发执行所谓多道程序设计，是指每一个时刻有若干个进程在执行引入多道程序设计的前提条件之一是系统具有中断功能采用多道程序设计的系统中，系统的
11、程序道数越多，系统的效率越高 A.仅、 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.24.假设系统中所有进程是同时到达，则最不利于短作业的进程调度算法是_。 A.FCFS B.SPF C.RR D.高响应比优先（分数：2.00）A.B.C.D.25.Pi()Lock(m_mutex); /含义为获取互斥信号量a=new int100; /开辟一个大小为 100 的整型数组空间，/并用全局指针变量 a 保存空间地址UnLock(m_mutex);free(a); /释放数组空间，且 a 的值不改变有多个优先级相同的进程 Pi。试问下列同时运行多个进程 Pi，可能会出现的错误是_。
12、 A.内存泄露 B.内存越界访问 C.内存泄露和内存越界访问 D.无（分数：2.00）A.B.C.D.26.生产者进程和消费者进程代码如下。生产者进程有一个局部变量 nextProduced，以存储新产生的新项：while(1)/*produce an item in nextProduced*/while(in+1) % BUFFER SIZE=out); /*do nothing*/bufferin=nextProduced;in=(in+1) % BUFFER SIZE;消费者进程有一个局部变量 nextConsumed，以存储所要使用的项：while(1)while(in=out);
13、/*do nothing*/nextConsumed=bufferout;out=(out+1) % BUFFER SIZE;/*consume the item in nextConsumed*/当 in=out 和(in+1)%BUFFER_SIZE=out 条件成立的时候，缓冲区中 item 数目各是_。 A.0，BUFFER_SIZE B.0，BUFFER_SIZE-1 C.BUFFER_SIZE-1，0 D.BUFFER_SIZE，0（分数：2.00）A.B.C.D.27.某操作系统采用可变分区分配存储管理方法，操作系统占用低地址部分的 126KB。用户区大小为386KB，且用户区始
14、址为 126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址的方案，且初始时用户区的 386KB 空间空闲，对下述申请序列：作业 1 申请 80KB，作业 2 申请 56KB，作业 3 申请120KB，作业 1 完成并释放空间，作业 3 完成并释放空间，作业 4 申请 156KB，作业 5 申请 80KB。如果用首次适应算法处理上述序列，最后的空闲分区的首地址为_。 A.126 B.432 C.256 D.220（分数：2.00）A.B.C.D.28.某请求分页管理系统中，页表保存在内存中。若有一个可用的空闲或被置换的页未被修改，则它处理一个缺页中断需要 8ms(1ms=106ns
15、)，这种情况占缺页中断事件的 30%；若被置换的页已被修改，则处理一缺页中断因增加写回外存时间而需要 20ms，一次内存的存取时间为 1ns。为保证有效访问时间不超过12ns，可接受的最大缺页率是_。(结果保留两位有效数字) A.6.110-5 B.1.210-5 C.6.110-6 D.1.210-6（分数：2.00）A.B.C.D.29.在页式虚拟管理系统中，假定驻留集为 m 个页帧(初始所有页帧均为空)，在长为 P 的引用串中具有 n个不同页号(nm)，对于 FIFO、LRU 两种页面替换算法，其缺页中断的次数的范围分别为_。 A.m，p和n，P B.m，n和n，P C.n，p和m，n
16、D.n，p和n，P（分数：2.00）A.B.C.D.30.设有一个记录式文件，采用链接分配方式，逻辑记录的固定长度为 100B，记录类型是英文文本(例如：WelcOmE to TiaNqin!)，在磁盘上存储时采用成组分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存，用户现在需要规范第 22 个逻辑记录中的大小写格式，该操作共需启动硬盘的次数为_。 A.1 B.2 C.5 D.6（分数：2.00）A.B.C.D.31.考虑一个有如下参数的磁盘： 参数 值旋转速率Tavg seek每条磁道的平均扇区数7200r/min9ms400估计访问一个磁盘扇区的平均时间 Taccess约为_
17、。 A.4ms B.8ms C.13ms D.17ms（分数：2.00）A.B.C.D.32.下列关于设备驱动程序的叙述中，正确的是_。与设备相关的中断处理过程是由设备驱动程序完成的由于驱动程序与 I/O 设备(硬件)紧密相关，故必须全部用汇编语言书写磁盘的调度程序是在设备驱动程序中运行的一个计算机系统配置了 2 台同类绘图机和 3 台同类打印机，为了正确驱动这些设备，系统应该提供 5个设备驱动程序 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.33.透明网桥的 MAC 地址表要记录的信息有_。目的站 MAC 地址 源站 MAC 地址 端口号帧到达时间 帧转发标记 A.
18、仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.34.下列说法中，错误的是_。假设帧序号有 3 位，采用连续 ARQ 协议，发送窗口的最大值为 4对于窗口大小为 n 的滑动窗口，最多可以有 n 帧已发送但没有确认在后退 N 帧协议中，如果发送窗口的大小是 16，那么至少需要 4 位的序列号才能保证协议不出错 A.仅、 B.仅 C.仅、 D.、（分数：2.00）A.B.C.D.35.假设某网络最远的两个站点长度为 10km，数据传输率为 10Mbit/s 的 CSMA/CS 以太网，信号传播速度为 200m/s。那么该网络的最小帧长为_。 A.20bit B.200bit C
19、.100bit D.1000bit（分数：2.00）A.B.C.D.36.下图是网络地址转换 NAT 的一个实例，根据图中的信息，标号为的方格中的内容应为_。（分数：2.00）A.B.C.D.37.对于 193.100.60.0 网络，若子网掩码设置成 255.255.255.192，则每个子网最多可接入_台主机。 A.256 B.254 C.62 D.30（分数：2.00）A.B.C.D.38.在 IP 分组的传输过程中，以下 IP 分组首部中的字段保持不变的是_。总长度 头部检验和生存时间 源 IP 地址 A.仅、 B.仅 C.仅、 D.仅、（分数：2.00）A.B.C.D.39.有一个
20、TCP 连接，当其拥塞窗口为 64 个分组大小时超时。假设网络的 RTT 是固定的 3s，不考虑比特开销，即分组不丢失，则系统在超时后处于慢启动阶段的时间是_。 A.12s B.15s C.18s D.21s（分数：2.00）A.B.C.D.40.某网络允许的最大报文段的长度为 128B，序号用 8bit 表示，报文段在网络中的寿命为 30s，则每一条TCP 连接所能达到的最高数据率为_。 A.4.6kbit/s B.18.9kbit/s C.8.7kbit/s D.25.6kbit/s（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)已知一个长度为 12
21、的表Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec；（分数：9.99）(1).试按照表中元素的顺序依次插入一棵初始为空的二叉排序树(字符之间以字典序比较大小)，请画出最终对应的二叉排序树。（分数：3.33）_(2).若对表中的元素先进行排序构成有序表(字典序)，试求在等概率情况下对此有序表进行检索时检索成功的平均检索长度。（分数：3.33）_(3).按表中元素的顺序构造一棵平衡二叉树，试求在等概率情况下检索成功的平均检索长度。（分数：3.33）_设有向无环图 G 以邻接矩阵的方式存储，Gij中存放的是从结点 i 出发到结点 j 的边权，Gij
22、=0 代表从 i 到 J 没有直接的边，试编写程序，求 G 图中最长的路径长度。（分数：12.99）(1).给出算法的基本设计思想。（分数：4.33）_(2).根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。（分数：4.33）_(3).给出算法的时间复杂度。（分数：4.33）_设有一个直接映像方式的 Cache，其容量为 8KB，每块的大小为 16B，主存的容量为 512KB，试回答以下问题：（分数：10.98）(1).主存有多少个块?分为多少个区?（分数：1.83）_(2).该 Cache 可容纳多少个块?Cache 字地址有多少位?块号和块内地址各多少位?（分数：1.83）
23、_(3).主存字地址有多少位?区号、区内块号和块内地址各多少位?（分数：1.83）_(4).主存中的第 i 块映像到 Cache 中哪一个块?（分数：1.83）_(5).将主存中的第 513 块调入 Cache，则 Cache 的块号为多少?它的区号为多少?（分数：1.83）_(6).在上一步的基础上，假设送出的主存地址为 04011H，是否命中?（分数：1.83）_假定磁盘传输数据以 32 位的字为单位，传输速率为 1MB/s。CPU 的时钟频率为50MHz。（分数：12.00）(1).程序查询的输入输出方式，一个查询操作需要 100 个时钟周期，求 CPU 为 I/O 查询所花费的时间比率
24、，假定进行足够的查询以避免数据丢失。（分数：3.00）_(2).用中断方式进行控制，每次传输的开销(包括中断处理)为 100 个时钟周期。求 CPU 为传输磁盘数据花费的时间比率。（分数：3.00）_(3).采用 DMA 控制进行输入输出操作，假定 DMA 的启动操作需要 1000 个时钟周期，DMA 完成时处理中断需要 500 个时钟周期，如果平均传输的数据长度为 4KB，问在磁盘工作时处理器将用多少时间比率进行输入输出操作，忽略 DMA 申请使用总线的影响。（分数：3.00）_(4).根据以上计算，可得出什么结论?（分数：3.00）_在一个分页存储管理系统中，地址空间分页(每页 1K)，物
25、理空间分块，设主存总容量是 256KB，描述主存分配情况的位示图如图所示(0 表示未分配，1 表示已分配)，此时作业调度程序选中一个长为 5.2K 的作业投入内存。试问：（分数：8.01）(1).为该作业分配内存后(分配内存时，首先分配低地址的内存空间)，请填写该作业的页表内容。（分数：2.67）_(2).页式存储管理有无内存碎片存在，若有，会存在哪种内存碎片?为该作业分配内存后，会产生内存碎片吗?如果产生，大小为多少?（分数：2.67）_(3).假设一个 64MB 内存容量的计算机，其操作系统采用页式存储管理(页面大小为 4K)，内存分配采用位示图方式管理，请问位示图将占用多大的内存?（分数
26、：2.67）_现有 3 名学生 S1、S2 和 S3 上机实习，程序和数据都存放在同一磁盘上。若 3人编写的程序分别为 P1、P2 和 P3，要求这 3 个学生用自编的程序调用同一个数据文件 A 进行计算。试问：（分数：6.99）(1).若文件 A 作为共享文件，系统应采用何种目录结构?画出示意图。（分数：2.33）_(2).若学生 S1，S2，S3 都将自己的程序名起为 P，则上题答案中的目录结构能否满足要求?（分数：2.33）_(3).对于上题简要说明系统是如何使每个学生获得他的程序和数据的?（分数：2.33）_下图所示为一个局域网的连接图，每个计算机的 IP 地址和物理地址见下表。 B显
27、示计算机的 IP 地址和物理地址/B计算机名称 IP 地址 物理地址计算机 A 192.168.48.19EE.24.D3.D1.B4.A4计算机 B 192.168.48.12DD.45.A5.A1.CB.E4计算机 C 192.168.48.21CC.34.5F.90.E8.C1（分数：9.00）(1).假设该局域网采用了以太网，需要达到 100Mbit/s 的数据传输率，那么线路的带宽最小为多少?如果信号在网络中的传播速度是 200000km/s，那么该网络的最大长度应该为多少?（分数：3.00）_(2).一个 IP 数据包的源地址和目的地址分别是 192.168.48.19 和 192
28、.168.48.21，为了发送该 IP 包，源主机应该先发送什么帧?该分组的以太网帧的源地址、目的地址各是什么?（分数：3.00）_(3).假设计算机 B 是天勤论坛的 Web 服务器，计算机 A 分别在如下 4 个条件使用非持久连接模式和持久连接模式向计算机 B 访问天勤论坛中的一个 Web 页面。4 个条件如下： 条件一：测试的 RTT 平均值为150ms，一个 gif 对象的平均发送时延为 35ms。 条件二：一个 Web 页面中有 10 个 gif 图片，Web 页面的基本 HTML 文件、HTTP 请求报文、TCP 握手报文大小忽略不计。 条件三：TCP 三次握手的第三步中捎带一个
29、HTTP 请求。 条件四：使用非流水线方式。 试计算使用非持久连接模式和持久连接模式分别需要多少时间?（分数：3.00）_考研计算机学科专业基础综合-6-1 答案解析(总分：149.96，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.下列叙述中，正确的是_。非空循环单链表 head 的尾结点 p 满足 pnext=head带头结点的循环单链表的头指针为 head，如果 headnextnextnext=head 成立，则该单链表的长度为 3静态链表中的指针表示的是下一个元素在数组中的位置将长度为 n 的单链表链接在长度为 m 的单链表之后的算法时间复杂度为 O
30、(1) A.仅、 B.、 C.仅、 D.仅、（分数：2.00）A.B.C. D.解析：解析 ：非空循环单链表的尾结点指针应该指向链表头，即 pnext=head，故正确。 ：head 指向头结点，headnext 就指向第一个结点。既然 headnextnextnext=head，说明此循环链表共有 3 个结点(包含头结点)，而单链表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存储线性表的元素，故不能算为单链表结点，故此单链表的长度为 2，故错误。 ：静态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的位詈，即数组下标，故正确。 ：将链表连接起来只需 O(1)的
31、操作，但找到具有 m 个结点链表的尾结点需遍历该链表，所以时间复杂度应该为 O(m)，故错误。2.利用栈求表达式的值时，设立运算数栈 s。假设栈 S 只有两个存储单元，在下列表达式中，不发生溢出的是_。 A.A-B*(C-D) B.(A-B)*C-D C.(A-B*C)-D D.(A-B)*(C-D)（分数：2.00）A.B. C.D.解析：解析 利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一例。例如，求 2(5-3)+6/2 的过程如下表所示。 当前字符 运算符栈 运算数栈 说明2 2 * 2( *( 25 *( 2 5- *(- 2 53 *(- 2 5 3) 2 2 “-”
32、出栈+ + 4 “*”出栈6 + 4 6/ +/ 4 62 +/ 4 6 2+ 4 3 “/”出栈7 “+”出栈从上述的计算过程中，考生可以自行对 A、B、C、D 选项进行练习，运算数栈 S 的大小分别至少为4、2、3、3，只有 B 选项满足条件。3.设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B中，A11存放到 B1中(假定不用 0 下标)，那么 Bk存放的元素的行号是_。 A BC D （分数：2.00）A.B. C.D.解析：解析 这种题目最好采用特殊值法，推导过程可能比较繁琐，见下表。 B特殊值推导过程/Bk 1 2 3 4 5 6 7
33、8 9AijA11A12A21A22A23A32A33A34A43* 1 1 2 2 2 3 3 3 4从表中的规律可得出答案。4.某完全二叉树的结点个数为 4N+3，则该树的叶结点个数为_。 A.2N B.2N-1 C.2N-2 D.2N+2（分数：2.00）A.B.C.D. 解析：解析 首先，由于该二叉树的结点个数为 4N+3，所以该二叉树一共有 4N+2 个分支。其次，因为是完全二叉树，所以不可能同时有两个结点只有一个叶结点。故 4N+2 个分支就肯定是来自 2N+1 个非叶结点，总结点数是 4N+3，所以，叶结点有 2N+2 个。5.下列说法中，正确的是_。具有 10 个叶子结点的二叉
34、树中有 9 个度为 2 的结点设高度为 5 的二叉树上只有度为 0 和度为 2 的结点，则该二叉树中所包含的结点数至少为 9一棵完全二叉树上有 1001 个结点，则可知叶子结点的个数为 501 个高度为 h 的完全二叉树最少有 2h个结点 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D. 解析：解析 ：二叉树叶子结点的个数比度为 2 的结点的个数多 1，故正确。：最少结点的情况应该是除根结点层只有 1 个结点外，其余 4 层都有 2 个结点，因此结点总数为2(5-1)+1=9。如图所示，故正确。*：由二叉树的性质可知：n 0=n2+1，且完全二叉树度为 1 的结点个数要
35、么为 0，要么为 1。又因为二叉树的总结点个数 n=n0+n1+n2。将 n0=n2+1 代入，可得 n=2n0+n1-1；由于 n=1 001，得到 2n0=1 002+n1。当 n1=1 时，无解。当 n1=0 时，可解得 n0=501故正确。：高度为 h 的完全二叉树中，第 1 层第 h-1 层构成一个高度为 h-1 的满二叉树，结点个数为 2h-1-1。第 h 层至少有一个结点，所以最少的结点个数=(2 h-1-1)+1=2h-1，故错误。6.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则为使其平衡，
36、应做_型调整。 A.LL B.RR C.RL D.LR（分数：2.00）A.B.C.D. 解析：解析 既然最低不平衡结点是 A，则以 A 为根的子树不平衡的情况有 4 种，如图所示。 * 又因为 A 的左孩子的平衡因子为-1，右孩子的平衡因子是 0，只有第 2 个符合，所以应当做 LR 型调整。7.下列关于无向图的说法中，正确的是_。无向图中某个顶点的度是指图中与该顶点连通的项点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n-1 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分量 A.仅、 B.仅、 C.仅 D.、（分数：2.00）A.B. C.D.
37、解析：解析 ：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数(这样就会扩大范围，如图所示)，故错误。*顶点 V2的度应该是 1，而如果度是按照图中与该顶点连通的顶点数来定义，顶点 V2的度应该是 3，明显错误。：n 个顶点的无向图要连通的话只需每个顶点做一个结点，构成一棵树即可(解题关键)，并且此时是边最少的情况。对于树来说，顶点的个数比边要多 1，故正确。：显然，在无向图中，每条边(没有方向)对应于矩阵中与主对角线对称的两个“1”，因此无向图对应的邻接矩阵是对称的，故确。：无向图的连通分量最少只有一个，即其自身；最多有 n 个，即该
38、图没有边，则每个顶点构成一个连通分量，故正确。8.下列关于强连通图的说法中，正确的是_。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C. D.解析：解析 ：强连通图是相对于有向图而言的，即在有向图 G 中，任何两个顶点都存在路径。所以最少的情况应该是 n 个顶点构成一个首尾相连的环，共有 n 条边，故正确。 ：这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。有向图中顶点 A 和 B 之间存在边，不能说明 A 和 B 是互相连通的，所以说正确的表述应该是强连通图是任何顶点到其他所有顶点都有路径，故错误。 ：完全有向图肯定是任何顶点到其他所有顶点都有路径，故正确。9.假设初始为空的散列表的地址空间为(010)，散列函数为 H(key)=key rood 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、48，则最后一个关键字值 48 的插入位置是_。 A.4 B
