1、计算机专业（基础综合）-试卷 100 及答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.在 n 个结点的线性表的数组表示中，以下算法的时间复杂度是 O(1)的操作是( )。访问第 i 个结点(1=i=n)和求第 i 个结点的直接前驱(2=i=n)在最后一个结点后插入一个新的结点删除第一个结点在第 i 个结点后插入一个结点(1=i=n)（分数：2.00）A.仅B.仅、C.仅、D.仅、3.中缀表达式 a * (b+c)一 d 的后缀表
2、达式是( )。（分数：2.00）A.abcd * +B.abc+ * dC.abc * +dD.+ * abcd4.设线性表有 n 个元素，以下操作中，( )在顺序表上实现比链表上实现效率更高。（分数：2.00）A.输出第 i(1in)个元素值B.交换第 1 个元素与第 2 个元素的值C.顺序输出这 n 个元素的值D.输出与给定值 x 相等的元素在线性表中的序号5.设 k 是中序线索二叉树中一个有左子女的结点，且 k 不是根结点，则 k 在中序序列下的直接前驱结点是( )。（分数：2.00）A.k 的左线索（指示中序前驱）所指示的结点B.从 k 父结点的左子女开始沿右子女链走到底的结点C.从
3、k 的左子女开始沿右子女链走到底的结点D.从 k 的左子女开始沿左子女链走到底的结点6.假定一组元素序列为38，42，55，15，23，44，34，74，45，26，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为( )。（分数：2.00）A.1B.3C.4D.57.由 23、12、45、36 构成的二叉排序树有( )个，其中 AVL 树有( )个。（分数：2.00）A.13；4B.13；5C.14；5D.14；48.对图 41 进行拓扑排序，可以得到不同的拓扑序列的个数是( )。 （分数：2.00）A.4B.3C.2D.19.无向图 G 有 16 条边，
4、有 3 个度为 4 的顶点，4 个度为 3 的顶点，其余顶点的度均小于 3，则 G 至少有( )个顶点。（分数：2.00）A.10B.11C.12D.1310.以下有关 m 阶 B树的说法中正确的有( )。每个结点至少有两棵非空子树树中每个结点至多有 m1 个关键字所有叶子在同一层上当插入一个数据项引起 B树结点分裂后，树长高一层（分数：2.00）A.仅、B.仅、C.仅、D.仅、11.对以下关键字序列用快速排序进行排序，速度最慢的是( )。（分数：2.00）A.19，23，3，15，7，21，28B.23，21，28，15，19，3，7C.19，7，15，28，23，21，3D.3，7，15，
5、19，21，23，2812.某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多路归并至少需要( )趟可以完成排序。（分数：2.00）A.2B.3C.4D.513.考虑以下 C 语言代码：vc short si=8196；unsingned short usi=si；执行上述程序段后，usi 的值为( )。（分数：2.00）A.8196B.34572C.57339D.5734014.设浮点数的阶码用移码表示，尾数用补码表示，阶码的底数为 2，阶码用 3 位表示（包含一位符号位），尾数用 5 位表示（包含 1 位符号位），则它
6、能表示的最小负数为( )。（分数：2.00）A.8B.75C.128D.25615.硬盘平均寻道时间为 12ms，传输速率为 10MB/s，磁盘控制器延时为 2ms，则一个转速为 7200r/min 的硬盘写 1KB 数据的时间为( )。（分数：2.00）A.1311msB.1413msC.1515msD.1827ms16.下面关于各种存储器的说法中，正确的有( )。静态 RAM 不是易失性存储器，而动态 RAM 是易失性存储器. PROM 只能写录一次EPROM 是可改写的，并且也是随机存储器的一种EEPROM 存储器是可写存储器（分数：2.00）A.仅、B.仅、C.仅、D.仅、17.个 C
7、ache主存系统，采用 50MHz 的时钟，存储器以每一个时钟周期传输一个字的速率，连续传输8 个字，以支持块长为 8 个字的 Cache，每个字 4 个字节。假设读操作所花的时间是：1 个周期接受地址，3 个周期延迟，8 个传输周期传输 8 个字；写操作所花的时间是：1 个周期接受地址，2 个周期延迟，8 个周期传输 8 个字，3 个周期恢复和写入纠错码，则当系统以 35为读操作，65为写操作的访问情况工作，则存储器最大带宽为( )。（分数：2.00）A.1332MB/sB.1144MB/sC.126MB/sD.1203MB/s18.以下是一段指令序列：1 addi R1，20 (R1)20
8、2 1w R2， R0，12 (R2)M(12+(R0)3 add R3，R1，R2 (R3)(R1)+(R2)以上指令序列中，假定采用“取指、译码/取数、执行、访存、写回”这种五段流水线方式，那么在采用“转发”技术时，需要在第 3 条指令之前至少加入( )条空操作(nop)指令，才能使这段程序不发生数据冒险。（分数：2.00）A.0B.1C.2D.319.某计算机采用微程序控制，微指令字中操作控制字段共 12 位，下列说法正确的是( )。若采用直接控制，则此时一条微指令最多可同时启动 11 个微操作若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，则微指令字中的操作控制字段应
9、分 6 段若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含 45 个微操作命令（分数：2.00）A.仅、B.仅、C.仅、D.、和20.一条双字长直接寻址的子程序调用 CALL 指令，其第一个字为操作码和寻址特征，第二个字为地址码5000H。假设 PC（程序计数器）当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先(SP)1SP，后存入数据。则 CALL 指令执行后，SP 及栈顶的内容分别为( )。（分数：2.00）A.00FFH，1000HB.0101H，1000HC.0
10、0FEH，1002HD.00FFH，1002H21.指令流水线将一条指令的执行过程分为 4 步，其中第 1、2 和 4 步的执行时间为t，如图 42 所示。若该流水线顺序执行 50 条指令共用了 203At（无需考虑相关问题），则该流水线的第 3 步的执行时间是( )。（分数：2.00）A.3tB.4tC.5tD.6t22.某总线总共有 88 根信号线，其中数据总线为 32bit，地址总线为 20bit，控制总线为 36 根，总线的工作频率为 66MHz，则总线宽度为( )，传输速率为( )。（分数：2.00）A.32bit 264MB/sB.20bit 264MB/sC.32bit 254M
11、B/sD.20bit 264MB/s23.指令( )从主存中读出。（分数：2.00）A.总是根据程序计数器(PC)B.有时根据 PC，有时根据转移指令C.根据地址寄存器D.有时根据 PC，有时根据地址寄存器24.在操作系统中，用户在使用 I/O 设备时，通常采用( )。（分数：2.00）A.物理设备名B.逻辑设备名C.虚拟设备名D.设备序号25.考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待 CPU 时（在就绪队列中，但未执行），优先权以 速率改变；当它运行时，优先权以 p 速率改变。所有的进程在进入就绪队列被给定优先权数为 O。参数 a 和
12、p 可以设定给许多不同的调度算法。下列( )设定可以实现进程 FIFO (First In First Out)。（分数：2.00）A.0B.0C.0D.026.假设系统有 5 个进程，A、B、C 三类资源。某时刻进程和资源状态如表 41 所示。下面叙述正确的是( )。 （分数：2.00）A.系统不安全B.该时刻，系统安全，安全序列为P1，P2，P3，P4，P5C.该时刻，系统安全，安全序列为P2，P3，P4，P5，P1D.该时刻，系统安全，安全序列为P4，P5，P1，P2，P327.设有一个发送者进程和接收者进程，其流程图如图 43 所示。S 是用于实现进程同步的信号量，mutex 是用于实
13、现进程互斥的信号量。试问流程图中的 A、B、C、D4 个框中应填写什么？假定缓冲区有无限多个且初始为空，S 和 mutex 的初值应该是什么？( ) （分数：2.00）A.P(mutex)、V(mutex)、P(S)、P(mutex) S=缓冲区的个数 mutex=1B.P(S)、V (mutex)、P(S)、P(mutex) S=0 mutex=1C.P(mutex)、V(mutex)、P(S)、P(mutex) S=0 mutex=1D.P(S)、V(mutex)、P(S)、P(mutcx) S=缓冲区的个数 mutex=028.考虑在一个虚拟页式存储管理的系统中，在地址变换过程中，进程状
14、态可能发生的变化有( )。进程被撤销进程变为阻塞（分数：2.00）A.B.C.和D.都不可能29.在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为( )。（分数：2.00）A.决定淘汰页页面调出缺页中断页面调入B.决定淘汰页页面调入缺页中断页面调出C.缺页中断决定淘汰页页面调出页面调入D.缺页中断决定淘汰页页面调入页面调出30.下列关于 Belady 现象和工作集的说法正确的是( )。先进先出(FIFO)页面置换算法会产生 Belady现象最近最少使用(LRU)页面置换算法会产生 Belady 现象为了保证进程高效的运行，它的工作集页面需要都
15、在虚拟存储器内，否则会出现频繁的页面调入/调出现象为了保证进程高效的运行，它的工作集页面需要都在主存储器内，否则会出现频繁的页面调入/调出现象（分数：2.00）A.、B.、C.、D.、31.某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为 1024B，每个盘块索引号占用4B，请问在该文件系统中，最大的文件大小最接近的是( )。（分数：2.00）A.8GBB.16GBC.32GBD.2TB32.信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录 A、B、C、J，它们被存放于磁盘上，每个磁道存放 10 个记录，安排如表 42 所示。 假定要经常顺序处理这些记录，磁盘旋转速度为
16、 20ms/r，处理程序读出每个记录后花 4ms 进行处理。考虑对信息的分布进行优化，如表 43 所示，相比之前的信息分布，优化后的时间缩短了( )。 （分数：2.00）A.60msB.104msC.144msD.204ms33.考虑单用户计算机上的下列 I/O 操作，需要使用缓冲技术的是( )。图形用户界面下使用鼠标在多任务操作系统下的磁带驱动器（假设没有设备预分配）包含用户文件的磁盘驱动器使用存储器映射 I/O，直接和总线相连的图形卡（分数：2.00）A.、B.、C.、D.全选34.假定运行发送窗口大小为 5 和接收窗口大小为 3 的滑动窗口算法，并且在传输过程中不会发生分组失序的问题，帧
17、序号的编码至少有( )位。（分数：2.00）A.2B.3C.4D.535.以下几种 CSMA 协议中，什么协议在监听到介质是空闲时一定发送( )。1持续 CSMA.p 一持续CSMA.非持续的 CSMA（分数：2.00）A.只有B.、C.、D.只有36.10 个站点连接到一个 10Mbit/s 的以太网交换机上，下面说法正确的是( )。（分数：2.00）A.每个站点共享 10Mbit/sB.每个站点都独享 1Mbit/sC.每个站点共享 1Mbit/sD.每个站点都独享 10Mbit/s37.个 IPv6 包中“通信量类”字段的值为 0，表明( )。（分数：2.00）A.该包优先级最低，拥塞时
18、可以被丢弃B.该包优先级最高，拥塞时不能被丢弃C.该包中没有用户数据，只有首部D.该包不可进行路由器转发38.以太网组播 IP 地址 224215，145230 应该映射到组播 MAC 地址( )。（分数：2.00）A.01005E5791E6B.01005ED791E6C.01005E5B91E6D.01005E5591E639.在 IP 首部的字段中，与分片和重组无关的字段是( )。总长度标识标志域片偏移（分数：2.00）A.仅B.仅、C.仅、D.仅、40.以下字段中，TCP 首部和 UDP 首部都有的字段为( )。目标端口号帧序号源端口号校验号（分数：2.00）A.仅、B.仅、C.仅、D
19、.仅、41.路由汇聚是把小的子网汇聚成大的网络，下面 4 个子网：172161930/24、172161940/24、172161960/24、172161980/24，进行路由汇聚后的网络地址是( )。（分数：2.00）A.172161920/21B.172161920/22C.172162000/22D.172162240/20二、综合应用题(总题数：8，分数：48.00)42.综合应用题 41-47 小题。_表 51 给出了某工程各工序之间的优先关系和各工序所需的时间（其中“ ”表示无先驱工序），请完成以下各题： （分数：6.00）(1).画出相应的 AOE 网。（分数：2.00）_(2
20、).列出各事件的最早发生时间和最迟发生时间。（分数：2.00）_(3).求出关键路径并指明完成该工程所需的最短时间。（分数：2.00）_输入一个按升序排序过的整数数组1、2、4、7、11、15以及一个整数数字 15，我们可以从该数组中找到两个数字，即 4 和 11，使得 4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C 或
21、 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度。（分数：2.00）_某高级语言程序中的一个 while 语句为“while(savei=k) i+=1；”，若对其编译时，编译器将 i 和 k分别分配在寄存器 s3 和 s5 中，数组 save 的基址存放在 s6 中，则生成的 MIPS 汇编代码如下：loop: sll t1，s3， 2 #R tlR s3 2，即 R t1=i*4add t1， t1， s6 #R t1R t1+R s6 ，即 R t1 =Address of save it0， 0 (t1) #R t0M R t
22、1 +0， gp Rt0 =save ibne . t0，s5f exit #if Rt0Rs5 then goto exitaddi s3， s3，1 #R s3R s3+1，即 i=i+lj loop #goto loopexit；假设从 loop 处开始的指令序列存放在内存 80000 处，则上述循环对应的 MIPS 机器码如图 51 所示。 （分数：12.00）(1).MIPS 的编址单位是多少？数组 save 每个元素占几个字节？（分数：2.00）_(2).为什么指令“sll t1，s3，2”能实现 4*i 的功能？（分数：2.00）_(3).t0 和 s6 的编号各为多少？（分数：
23、2.00）_(4).指令“jloop”的操作码是什么？（用二进制表示）（分数：2.00）_(5).标号 exit 的值是多少？如何根据指令计算得到？（分数：2.00）_(6).标号 loop 的值是多少？如何根据指令计算得到？（分数：2.00）_假设某计算机的主存地址空间大小为 64KB，采用字节编址方式。其 Cache 数据区容量为 4KB，采用 4 路组相联映射方式、LRU 替换和回写(write back)策略，块大小为 64B，并且每块设置了 1 位有效位。请问：（分数：6.00）(1).主存地址字段如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。（分数：2.00）_(2)
24、.该 Cache 的总容量有多少位？（分数：2.00）_(3).若 Cache 初始为空，CPU 依次从 0 号地址单元顺序访问到 4344 号单元，重复按此序列共访问 16 次。若 Cache 命中时间为 20ns，主存存取时间为 200ns，试估计 CPU 访存的平均时间。（分数：2.00）_在下列代码中，有 3 个进程 Pl、P2 和 P3，它们使用了字符输出函数 putc 来进行输出（每次输出一个字符），并使用了两个信号量 L 和 R 来进行进程间的同步。请问：（分数：8.00）(1).这组进程在运行时，最后打印出来了多少个“D”字符？（分数：2.00）_(2).当这组进程在运行的时候
25、，在何种情形下，打印出来的字符“A“的个数是最少的，最少的个数是多少？（分数：2.00）_(3).当这组进程在运行的时候，“CABABDDCABCABD”是不是一种可能的输出序列，为什么？（分数：2.00）_(4).当这组进程在运行的时候，“CABACDBCABDD”是不是一种可能的输出序列，为什么？semaphore L=3，R=0； /*初始化*/*进程 P1*/ /+进程 P2*/ /*进程 P3*/while(1) while (1) while (1) P(L)；P(R)； P(R)；putc(C)； putc(A)； putc(D)；V (R)； putc(B)； V(R)；（分数
26、：2.00）_某操作系统支持页式虚拟存储管理，其中央处理器的周期是 1s。当不是处于同一页面时，访问另一个页面耗时 1s。一个页面含 1K 字。使用磁盘作为外存，其转速为 3 000r/min，传输率 1M 字/s。还测得下列数据：磁盘平均寻道时间为 19ms，1的指令要访问不处于同一页面的其他页面内容，这当中，80的被访问页已经在内存中。需要新页面时，50的被换出页面已经修改过了。（分数：4.00）(1).如果磁盘设备要连续传输 10K 字的数据，请计算出平均情况下总的访问时间。（分数：2.00）_(2).请计算该系统的有效指令时间，假设系统只有一个 CPU，而且它在磁盘传输数据时是空闲的。
27、（假设逻辑相邻的页面在磁盘上都不相邻。）（分数：2.00）_某单位有 1 个总部和 6 个分部，各个部门都有自己的局域网。该单位申请了 6 个 C 类 IP 地址 202115 100/24202115150/24，其中总部与分部 4 共用一个 C 类地址。网络采用 R1R7 共 7 台路由器，采用动态路由协议 OSPF，并划分了 3 个 OSPF 区域。网络拓扑图如图 52 所示，路由器的 lP 地址分配见表 52。 （分数：6.00）(1).请指出本网中哪个区域为主干区域，以及指出主干区域中的区域边界路由器及区域内路由器。（分数：2.00）_(2).R3 路由器各端口 IP 地址如何设置？
28、（分数：2.00）_(3).如部门 4 共有 110 台计算机，通过交换机连接路由器 R5 接入网络。其中一台计算机 IP 地址为202115135，试给出其子网掩码和网关地址。（分数：2.00）_计算机专业（基础综合）-试卷 100 答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.在 n 个结点的线性表的数组表示中，以下算法的时间复杂度是 O(1)的操作是( )。访问第 i 个结点(1=i=n)和求第 i 个结点的直接前驱
29、(2=i=n)在最后一个结点后插入一个新的结点删除第一个结点在第 i 个结点后插入一个结点(1=i=n)（分数：2.00）A.仅B.仅、C.仅、 D.仅、解析：解析：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号访问，所以的时间复杂度一定是 O(1)。 ：由于是在最后一个结点处插入一个结点，所以不需要移动元素，故时间复杂度为O(1)。 ：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为 O(n)。 ：由于i 是不固定的，所以后续结点 i+1，1+2，n1，都需要向后移动，所以时间复杂度为 O(n)。3.中缀表达式 a * (b+c)一 d 的后缀表达式是( )。（分数
30、：2.00）A.abcd * +B.abc+ * d C.abc * +dD.+ * abcd解析：解析：本题转化过程如图 45 所示。 由图 45 可以写出以下转化过程： 第一步：b+cbc+（假设 x=“bc+”） 第二步：a * xax * （假设 y=“ax * ”） 第三步：ydyd 将 xy 还原后得到：abc+ * d。 补充知识点(1):中缀表达式转换成后缀表达式的另一种方式。 解析：可以通过手工加上、除掉括号来将中缀表达式转换成后缀表达式，其过程如下：先根据中缀表达式的求值次序加上括号，将右括号用相应的运算符替换，再除掉所有的左括号。 例如，中缀表达式“5+2 * (1+6)
31、 8/2”转换成后缀表达式的过程如下：手工判断该表达式的计算过程。首先肯定是先计算 2 * (1+6)，加上括号变为“5+(2 * (1+6)8/2”，再计算除法 8/2，加上括号变为“5+（2 * （1+6） (8/2)”，接着进行加法运算，加上括号变为“(5+(2 * (1+6)一(8/2)”，最后再进行减法运算，加上括号变为“(5+(2 * (1+6)一(8/2)”。运算符和右括号的对应关系如图 4.6 所示，将右括号用对应的运算符替换，变为“（5（2（16+ * +（8 2/一”，最后除掉所有左括号得到的后缀表达式为“5216+ * +82/一”。 4.设线性表有 n 个元素，以下操作
32、中，( )在顺序表上实现比链表上实现效率更高。（分数：2.00）A.输出第 i(1in)个元素值 B.交换第 1 个元素与第 2 个元素的值C.顺序输出这 n 个元素的值D.输出与给定值 x 相等的元素在线性表中的序号解析：解析：顺序表支持随机存储，链表不支持，因此顺序表输出第 i 个元素的值的时间复杂度为 O(1)，链表则为 O(n)，因此 A 正确。 交换第 1 个与第 2 个元素的值，对于顺序表和链表，时间复杂度均为 O(1)，因此 B 不对。 输出 n 个元素的值，两者时间复杂度均为 O(n)，因此 C 不对 输出与给定值 x 相等的元素在线性表中的序号，对于顺序表和链表，count
33、需要搜索整个表，因此时间复杂度为 O(n)，因此 D 不对。【注】 有的同学认为 B 也是正确的，其实严格来说 B 确实是对的，因为线性表交换要执行 3 次操作：temp=a 1 ；a 2=temD；而链表要执行 5 次：p=headnext；q=headnextnext；temp=pdata；pdata=qdata；qdata=temp； 但本题是单选题的时候，考生需要选择更准确的一项，显然与 B 项相比，A 项更准确。5.设 k 是中序线索二叉树中一个有左子女的结点，且 k 不是根结点，则 k 在中序序列下的直接前驱结点是( )。（分数：2.00）A.k 的左线索（指示中序前驱）所指示的结
34、点B.从 k 父结点的左子女开始沿右子女链走到底的结点C.从 k 的左子女开始沿右子女链走到底的结点 D.从 k 的左子女开始沿左子女链走到底的结点解析：解析：如果 k 没有左子女，则 k 的左指针即为指向 k 的中序前驱的线索；当 k 有左子女时，k 的中序直接前驱结点是 k 的左子树中中序的最后一个结点，即从 k 的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为 k 的中序前驱结点。 说明：上述二叉树的线索化算法其实考试中涉及的不多，本节在考试中涉及最多的是，在选择题中给你一棵二叉树，让你指出其中一个结点的线索按照某种线索化方法所应该指向的结点。 例如：请画出图 47 中按照
35、中序线索化方法线索化后 E 结点的右线索的接连情况。6.假定一组元素序列为38，42，55，15，23，44，34，74，45，26，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为( )。（分数：2.00）A.1B.3C.4 D.5解析：解析：根据题目所给的元素序列，可以得到以下的平衡二叉树，如图 49 所示。7.由 23、12、45、36 构成的二叉排序树有( )个，其中 AVL 树有( )个。（分数：2.00）A.13；4B.13；5C.14；5 D.14；4解析：解析：该题的结点不多，可以采用枚举法。但枚举法比较容易造成遗漏，所以在枚举时要按照一定
36、的规律，而且在枚举完之后看是否有重合的树并将其去掉，为避免重复可以采用根结点来枚举，枚举得二叉排序树共有 14 个，其中 5 个为 AVL 树。8.对图 41 进行拓扑排序，可以得到不同的拓扑序列的个数是( )。 （分数：2.00）A.4B.3 C.2D.1解析：解析：寻找拓扑排序的步骤： (1)在有向图中选一个没有前驱的顶点并且输出。 (2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。 题中所给图有 3 个不同的拓扑排序序列，分别为： 1)a，b， c， e， d。 2)a，b， e， c， d。 3)a，
37、 e， b， c， d。9.无向图 G 有 16 条边，有 3 个度为 4 的顶点，4 个度为 3 的顶点，其余顶点的度均小于 3，则 G 至少有( )个顶点。（分数：2.00）A.10B.11 C.12D.13解析：解析：度的定义指的是进入一个顶点的边数和从该顶点出去的边数之和。我们可以根据这个关系来求解此题。由于题目已经告诉度为 4 的顶点有 3 个，度为 3 的顶点有 4 个，其余的顶点的度均小于 3，而已知有 16 条边，则总的度数应为 162=32。所以要求最小的顶点个数，我们应当尽量增加每个顶点的度数，这里将剩下的结点的度数全部看成 2，设结点数为 x，则 34+43+(x34)2
38、32，解得 x 至少为 11。 补充：解这题的过程中，我们是从假设剩下的结点的度数为 2 来考虑的，这样才能最大程度地减小结点的个数。这其实用到了一种称为贪心的思想，这是一种很重要的思想，每次决策的时候都是按照最有利的情况去考虑。这种思想在其他几门课程当中也会有体现，读者应自己去发现和总结。10.以下有关 m 阶 B树的说法中正确的有( )。每个结点至少有两棵非空子树树中每个结点至多有 m1 个关键字所有叶子在同一层上当插入一个数据项引起 B树结点分裂后，树长高一层（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：中：m 阶 B树根结点至少有两棵子树，并且这两颗子树可以是空树，其
39、余结点至少有m/2个分支，即m/2个子树，所以错误。 补充：B树中每个结点至多有 m 棵子树，m1 个关键字值。 中：每个结点中关键字的个数比分支数少 1，m 阶 B树的一个结点中至多有 m 个分支，因此至多有 ml 个关键字，所以正确。 中：B树是平衡的多路查找树，叶子结点均在同一层上，所以正确。 中：发生结点分裂的时候不一定会使树长高。比如向图 410 中的 B树插入一个关键字 10 变成图 411 中的 B树，使得第二层右端的一个结点分裂成两个，但是树并没有长高，所以错误。11.对以下关键字序列用快速排序进行排序，速度最慢的是( )。（分数：2.00）A.19，23，3，15，7，21，
40、28B.23，21，28，15，19，3，7C.19，7，15，28，23，21，3D.3，7，15，19，21，23，28 解析：解析：这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，很少有考生在做这种选择题的时候能够分析其算法来选择答案。这里就是变相地考查快速排序算法的最坏情况。快速排序法的最坏情况为待排序列是有序或接近有序的时候，由于 D 中元素已经有序，所以选择 D。 评注：本题是指定了使用某种排序方法，当题目中没有指定具体的排序方法的时候，我们一定不要急于挨个用每个算法去试，而应该从所给的待排序列出发，观察序列元素的信息，找出某种特殊的性质。12.某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多路归并至少需要(
