1、考研计算机学科专业基础综合-4-2 及答案解析(总分：149.99，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在 n 个结点的线性表的数组表示中，以下算法的时间复杂度是 O(1)的操作是_。访问第 i 个结点(1=i=n)和求第 i 个结点的直接前驱(2=i=n)在最后一个结点后插入一个新的结点删除第一个结点在第 i 个结点后插入一个结点(1=i=n) A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.2.中缀表达式 a*(b+c)-d 的后缀表达式是_。 A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd（
2、分数：2.00）A.B.C.D.3.设线性表有 n 个元素，以下操作中，_在顺序表上实现比链表上实现效率更高。 A.输出第 i(1in)个元素值 B.交换第 1 个元素与第 2 个元素的值 C.顺序输出这 n 个元素的值 D.输出与给定值 x 相等的元素在线性表中的序号（分数：2.00）A.B.C.D.4.设 k 是中序线索二叉树中一个有左子女的结点，且 k 不是根结点，则 k 在中序序列下的直接前驱结点是_。 A.k 的左线索(指示中序前驱)所指示的结点 B.从 k 父结点的左子女开始沿右子女链走到底的结点 C.从 k 的左子女开始沿右子女链走到底的结点 D.从 k 的左子女开始沿左子女链走
3、到底的结点（分数：2.00）A.B.C.D.5.假定一组元素序列为38，42，55，15，23，44，34，74，45，26，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为_。 A.1 B.3 C.4 D.5（分数：2.00）A.B.C.D.6.由 23、12、45、36 构成的二叉排序树有_个，其中 AVL 树有_个。 A.13；4 B.13；5 C.14；5 D.14；4（分数：2.00）A.B.C.D.7.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是_。（分数：2.00）A.B.C.D.8.无向图 G 有 16 条边，有 3 个度为 4 的顶
4、点，4 个度为 3 的顶点，其余顶点的度均小于 3，则 G 至少有_个顶点。 A.10 B.11 C.12 D.13（分数：2.00）A.B.C.D.9.以下有关 m 阶 B-树的说法中正确的有_。每个结点至少有两棵非空子树树中每个结点至多有 m-1 个关键字所有叶子在同一层上当插入一个数据项引起 B 一树结点分裂后，树长高一层 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.10.对以下关键字序列用快速排序进行排序，速度最慢的是_。 A.19，23，3，15，7，21，28 B.23，21，28，15，19，3，7 C.19，7，15，28，23，21，3 D.3，7
5、，15，19，21，23，28（分数：2.00）A.B.C.D.11.某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多路归并至少需要_趟可以完成排序。 A.2 B.3 C.4 D.5（分数：2.00）A.B.C.D.12.考虑以下 C 语言代码：short si=-8196;unsigned short usi=si;执行上述程序段后，usi 的值为_。 A.8196 B.34572 C.57339 D.57340（分数：2.00）A.B.C.D.13.32 位字长的浮点数，其中阶码 8 位(含 1 位阶符)，尾数 24
6、 位(含 1 位数符)，机器数采用补码表示，且尾数为规格化形式，则对应的最小正数为_。 A.2127(1-2-23) B.2-129 C.2-1282-23 D.2-1272-23（分数：2.00）A.B.C.D.14.硬盘平均寻道时间为 12ms，传输速率为 10MB/s，磁盘控制器延时为 2ms，则一个转速为 7200r/min 的硬盘写 1KB 数据的时间为_。 A.13.11ms B.14.13ms C.15.15ms D.18.27ms（分数：2.00）A.B.C.D.15.下面关于各种存储器的说法中，正确的有_。静态 RAM 不是易失性存储器，而动态 RAM 是易失性存储器PROM
7、 只能写录一次EPROM 是可改写的，并且也是随机存储器的一种：EEPROM 存储器是可写存储器 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.16.一个 Cache-主存系统，采用 50MHz 的时钟，存储器以每一个时钟周期传输一个字的速率，连续传输 8个字，以支持块长为 8 个字的 Cache，每个字 4 个字节。假设读操作所花的时间是：1 个周期接受地址，3 个周期延迟，8 个传输周期传输 8 个字；写操作所花的时间是：1 个周期接受地址，2 个周期延迟，8 个周期传输 8 个字，3 个周期恢复和写入纠错码，则当系统以 35%为读操作，65%为写操作的访问情况工
8、作，则存储器最大带宽为_。 A.133.2MB/s B.114.4MB/s C.126MB/s D.120.3MB/s（分数：2.00）A.B.C.D.17.以下是一段指令序列：1 addi R1，20 (R1)202 1w R2，R0，12 (R2)M(12+(R0)3 add R3，R1，R2 (R3)(R1)+(R2)以上指令序列中，假定采用“取指、译码/取数、执行、访存、写回”这种五段流水线方式，那么在采用“转发”技术时，需要在第 3 条指令之前至少加入_条空操作(nop)指令，才能使这段程序不发生数据冒险。 A.0 B.1 C.2 D.3（分数：2.00）A.B.C.D.18.某计算
9、机采用微程序控制，微指令字中操作控制字段共 12 位，下列说法正确的是_。若采用直接控制，则此时一条微指令最多可同时启动 11 个微操作若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，则微指令字中的操作控制字段应分 6 段若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含 45 个微操作命令 A.仅、 B.仅、 C.仅、 D.、和（分数：2.00）A.B.C.D.19.一条双字长直接寻址的子程序调用 CALL 指令，其第一个字为操作码和寻址特征，第二个字为地址码5000H。假设 PC(程序计数器)当前值为 10
10、00H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先(SP)-1sP，后存入数据。则 CALL 指令执行后，SP 及栈项的内容分别为_。 A.00FFH，1000H B.0101H，1000H C.00FEH，1002H D.00FFH，1002H（分数：2.00）A.B.C.D.20.指令流水线将一条指令的执行过程分为 4 步，其中第 1、2 和 4 步的执行时间为 t，如图所示。若该流水线顺序执行 50 条指令共用了 203t(无需考虑相关问题)，则该流水线的第 3 步的执行时间是_。（分数：2.00）A.B.C.D.21.某总线总共有 88 根信号
11、线，其中数据总线为 32bit，地址总线为 20bit，控制总线为 36 根，总线的工作频率为 66MHz，则总线宽度为_，传输速率为_。 A.32bit 264MB/s B.20bit 264MB/s C.32bit 254MB/s D.20bit 264MB/s（分数：2.00）A.B.C.D.22.在微程序控制器中，执行指令微程序的首条微指令地址是由_得到的。 A.程序计数器 PC B.前条微指令 C.uPC+1 D.指令操作码映射（分数：2.00）A.B.C.D.23.分布式操作系统与网络操作系统在本质上的不同之处是_。 A.实现各台计算机之间的通信 B.共享网络中的资源 C.系统中若
12、干台计算机相互协同完成某一任务 D.满足较大规模的应用（分数：2.00）A.B.C.D.24.考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待 CPU 时(在就绪队列中，但未执行)，优先权以 速率改变；当它运行时，优先权以 速率改变。所有的进程在进入就绪队列被给定优先权数为 0。参数 和 可以设定给许多不同的调度算法。下列_设定可以实现进程 FIFO(First In First Out)。 A.0 B.0 C.0 D.0（分数：2.00）A.B.C.D.25.假设系统有 5 个进程，A、B、C 三类资源。某时刻进程和资源状态如下表所示。 B某时
13、刻进程和资源状态/BAllocation Max AvailableA B C A B C A B CP12 1 2 5 5 9 2 3 3P24 0 2 5 3 6P34 0 5 4 0 11P42 0 4 4 2 5P53 1 4 4 2 4下面叙述正确的是_。 A.系统不安全 B.该时刻，系统安全，安全序列为P1，P2，P3，P4，P5 C.该时刻，系统安全，安全序列为P2，P3，P4，P5，P1 D.该时刻，系统安全，安全序列为P4，P5，P1，P2，P3（分数：2.00）A.B.C.D.26.设有一个发送者进程和接收者进程，其流程图如图所示。S 是用于实现进程同步的信号量，mutex
14、 是用于实现进程互斥的信号量。试问流程图中的 A、B、C、D4 个框中应填写什么?假定缓冲区有无限多个且初始为空，S 和 mutex 的初值应该是什么? _（分数：2.00）A.B.C.D.27.考虑在一个虚拟页式存储管理的系统中，在地址变换过程中，进程状态可能发生的变化有_。进程被撤销 进程变为阻塞 A. B. C.和 D.都不可能（分数：2.00）A.B.C.D.28.在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为_。 A.决定淘汰页页面调出缺页中断页面调入 B.决定淘汰页页面调入缺页中断页面调出 C.缺页中断决定淘汰页页面调出页面调入
15、 D.缺页中断决定淘汰页页面调入页面调出（分数：2.00）A.B.C.D.29.下列关于 Belady 现象和工作集的说法正确的是_。先进先出(FIFO)页面置换算法会产生 Belady 现象最近最少使用(LRU)页面置换算法会产生 Beladv 现象为了保证进程高效的运行，它的工作集页面需要都在虚拟存储器内，否则会出现频繁的页面调入/调出现象为了保证进程高效的运行，它的工作集页面需要都在主存储器内，否则会出现频繁的页面调入/调出现象 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.30.某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为 1024B，每个盘块索引号
16、占用4B，请问在该文件系统中，最大的文件大小最接近的是_。 A.8GB B.16GB C.32GB D.2TB（分数：2.00）A.B.C.D.31.信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录 A、B、C、J，它们被存放于磁盘上，每个磁道存放 10 个记录，安排如表 1 所示。 B表 1 每个磁道存放 10 个记录/B物理块 1 2 3 4 5 6 7 8 9 10逻辑记录 A B C D E F G H I J假定要经常顺序处理这些记录，磁盘旋转速度为 20ms/r，处理程序读出每个记录后花 4ms 进行处理。考虑对信息的分布进行优化，如表 2 所示，相比之前的信息分布，优化
17、后的时间缩短了_。 B表 2 优化后磁道存放 10 个记录/B物理块 1 2 3 4 5 6 7 8 9 10逻辑记录 A H E B I F C J G D A.60ms B.104ms C.144ms D.204ms（分数：2.00）A.B.C.D.32.考虑单用户计算机上的下列 I/O 操作，需要使用缓冲技术的是_。图形用户界面下使用鼠标在多任务操作系统下的磁带驱动器(假设没有设备预分配)包含用户文件的磁盘驱动器使用存储器映射 I/O，直接和总线相连的图形卡 A.、 B.、 C.、 D.全选（分数：2.00）A.B.C.D.33.假定运行发送窗口大小为 5 和接收窗口大小为 3 的滑动窗
18、口算法，并且在传输过程中不会发生分组失序的问题，帧序号的编码至少有_位。 A.2 B.3 C.4 D.5（分数：2.00）A.B.C.D.34.以下几种 CSMA 协议中，什么协议在监听到介质是空闲时一定发送_。1-持续 CSMA p-持续 CSMA 非持续的 CSMA A.只有 B.、 C.、 D.只有（分数：2.00）A.B.C.D.35.10 个站点连接到一个 10Mbit/s 的以太网交换机上，下面说法正确的是_。 A.每个站点共享 10Mbit/s B.每个站点都独享 1Mbit/s C.每个站点共享 1Mbit/s D.每个站点都独享 10Mbit/s（分数：2.00）A.B.C.
19、D.36.一个 IPv6 包中“通信量类”字段的值为 0，表明_。 A.该包优先级最低，拥塞时可以被丢弃 B.该包优先级最高，拥塞时不能被丢弃 C.该包中没有用户数据，只有首部 D.该包不可进行路由器转发（分数：2.00）A.B.C.D.37.以太网组播 IP 地址 224.215.145.230 应该映射到组播 MAC 地址_。 A.01-00-5E-57-91-E6 B.01-00-5E-D7-91-E6 C.01-00-5E-5B-91-E6 D.01-00-5E-55-91-E6（分数：2.00）A.B.C.D.38.在 IP 首部的字段中，与分片和重组无关的字段是_。总长度 标识标志
20、域 片偏移 A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.39.以下字段中，TCP 首部和 UDP 首部都有的字段为_。目标端口号 帧序号源端口号 校验号 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.40.路由汇聚是把小的子网汇聚成大的网络，下面 4 个子网：172.16.193.0/24、172.16.194.0/24、172.16.196.0/24、172.16.198.0/24，进行路由汇聚后的网络地址是_。 A.172.16.192.0/21 B.172.16.192.0/22 C.172.16.200.0/22 D.172.16.2
21、24.0/20（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)有一结点的关键字序列 F=129，72，180，105，147，96，45，69，散列函数为：H(k)=k mod 11，其中 k 为关键字，散列地址空间为 010。要求：（分数：9.99）(1).画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少?计算在等概率情况下，查找成功和查找不成功时的平均查找长度 ASL。（分数：3.33）_(2).画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功时的平均查找长度 ASL(只将与关键字的比较
22、次数计算在内即可)。（分数：3.33）_(3).试按各关键字在序列 F 中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。若做了某种旋转，请注明旋转的类型。（分数：3.33）_试设计一个算法，判断一个有向无环图 G 中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图 G 以邻接表的形式存储。（分数：12.99）(1).给出算法的基本设计思想以及结点和邻接表的定义。（分数：4.33）_(2).根据设计思想，采用 C、C+语言描述算法，关键之处给出注释。（分数：4.33）_(3).说明你所设计算法的时间复杂度。（分数：4.33）_有以下两段
23、 C 语言程序代码：int fun1 (unsigned short si) int fun2(unsigned short si) return(si*256); return (short)si*256)/256); 请回答下列问题：（分数：11.01）(1).假设计算机硬件不提供直接乘除运算功能，如何实现上述函数的功能?函数 fun1 和 fun2 得到的结果各有什么特征?（分数：3.67）_(2).根据以上程序填写下表(要求机器数用十六进制表示)。（分数：3.67）_(3).表中的哪些数据异常?并分析“异常”产生的原因。（分数：3.67）_以下是计算两个向量点积的程序段：float d
24、otproduct(float x8,float y8);float sum=0.0;int i;for(i=0;i8;i+)sum+=xi*yi;return sum;试回答以下问题：（分数：12.00）(1).访问数组 x 和 y 时的时间局部性和空间局部性各如何?能否推断出命中率的高低?（分数：3.00）_(2).假定该段程序运行的计算机的数据 Cache 采用直接映射方式，其容量为 32B，每个主存块大小为16B。假定编译程序将变量 sum 和 i 分配给寄存器，数组 x 存放在 00000040H 开始的 32B 的连续存储区中，数组 y 则紧跟在 x 后进行存放。试计算该程序数据访
25、问的命中率，要求说明每次访问的 Cache 命中情况。（分数：3.00）_(3).将上述(2)中的数据 Cache 改用 2-路组相联映射方式，块大小改为 8B，其他条件不变，则该程序数据访问的命中率是多少?（分数：3.00）_(4).在上述(2)中条件不变的情况下，如果将数组 x 定义为 float12，则数据访问的命中率又是多少?（分数：3.00）_某系统有 R1、R2 和 R3 共三种资源，在 T0 时刻，P1、P2、P3 和 P4 这四个进程对资源的占用和需求情况如下表所示，此时系统的可用资源向量为(2，1，2)。试问：（分数：8.00）(1).将系统中各种资源总数和此刻各进程对各资源
26、的需求个数用向量或矩阵表示出来。（分数：2.00）_(2).如果此时 P1 和 P2 均发出资源请求向量 Request(1，0，1)，为了保证系统的安全性，应该如何分配资源给这两个进程?说明所采用策略的原因。（分数：2.00）_(3).如果(2)中两个请求立即得到满足后，系统此刻是否处于死锁状态?（分数：2.00）_(4).若已知 P1 运行过程中的全部资源使用情况按时间先后顺序如下表列出。 B4 个进程对资源的占用和需求情况/B最大资源需求量 已分配资源数量进程R1 R2 R3 R1 R2 R3P1 3 2 3 1 0 1P2 6 1 3 4 1 1P3 3 1 4 2 1 1P4 4 2
27、 2 0 0 2iP1 被创建 ii申请 1 个 R1 和 1 个 R3 iii申请 1 个 R1 和 1 个 R3 iv释放 2 个 R3 v申请 1 个 R1、2 个 R2 和 3 个 R3 则(2)中 P1 请求立即得到满足后，系统是否处于不安全状态?（分数：2.00）_某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有 10项，其中前 8 项是直接索引项，第 9 项是一次间接索引项，第 10 项是二次间接索引项，假定物理块的大小是 2KB，每个索引项占用 4 个字节，试问：（分数：7.00）(1).该文件系统中最大的文件可以达到多大?（分数：3.50）_(2).假定一个
28、文件的实际大小是 128MB，该文件实际占用磁盘空间多大(包括间接索引块，不计索引表所占空间)?（分数：3.50）_假定站点 A 和 B 在同一个 10Mbit/s 以太网的网段上，这两个站点之间的传播时延为 225 比特时间。现假定 A 开始发送一帧，并且在 A 发送结束之前 B 也发送一帧。如果 A 发送的是以太网所允许的最短的帧，试问：（分数：9.00）(1).A 在检测到和 B 发生碰撞之前能否把自己的数据发送完毕?如果 A 在发送完毕之前并没有检测到碰撞，那么能否肯定 A 所发送的帧不会和 B 发送的帧发生碰撞?(提示：在计算时应当考虑到每一个以太网帧在发送到信道上时，在 MAC 帧
29、前面还要增加 7 个字节的前同步码和 1 个字节的帧定界符)（分数：4.50）_(2).中的站点 A 和 B 在 t=0 时同时发送了数据帧。当 t=225 比特时间，A 和 B 同时检测到发生了碰撞，并且在 t=225+48=273 比特时间完成了干扰信号的发送。A 和 B 在 CSMA/CD 算法中选择不同的 r 值退避。假定 A 和 B 选择的随机数分别是 0 和 1。试问：A 和 B 各在什么时间开始重传其数据帧?A 重传的数据帧在什么时间到达 B?A 重传的数据会不会和 B 重传的数据再次发送碰撞?B 会不会在预定的重传时间停止发送数据?（分数：4.50）_考研计算机学科专业基础综合
30、-4-2 答案解析(总分：149.99，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在 n 个结点的线性表的数组表示中，以下算法的时间复杂度是 O(1)的操作是_。访问第 i 个结点(1=i=n)和求第 i 个结点的直接前驱(2=i=n)在最后一个结点后插入一个新的结点删除第一个结点在第 i 个结点后插入一个结点(1=i=n) A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C. D.解析：解析 ：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号访问，所以的时间复杂度一定是 O(1)。 ：由于是在最后一个结点处插入一个结点，所以不需要移
31、动元素，故时间复杂度为 O(1)。 ：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为 O(n)。 ：由于 i 是不固定的，所以后续结点 i+1，i+2，n-1，都需要向后移动，所以时间复杂度为 O(n)。2.中缀表达式 a*(b+c)-d 的后缀表达式是_。 A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd（分数：2.00）A.B. C.D.解析：解析 本题转化过程如图所示。*由上图可以写出以下转化过程：第一步：b+cbc+(假设 x=“bc+”)第二步：a *xax *(假设 v=“ax*”)第三步：y-dvd-将 xy 还原后得到：abc+
32、*d-。当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果当成新遇到的数值入栈。如此往复，直到扫描到终止符“/0”，此时栈底元素值即为表达式的值。例：将后缀表达式 xy+z+转换为中缀表达式。先将 x、y 入栈，遇到了+，然后弹出栈项的 2 个元素，即 x、y，然后对 x、y 做加法，现在将(x+y)的值入栈，然后 z 入栈，遇到了操作符+，所以最后的中缀表达式为：(x+y)+z。3.设线性表有 n 个元素，以下操作中，_在顺序表上实现比链表上实现效率更高。 A.输出第 i(1in)个元素值 B.交换第 1 个元素与第 2 个元素的值 C.顺序输出
33、这 n 个元素的值 D.输出与给定值 x 相等的元素在线性表中的序号（分数：2.00）A. B.C.D.解析：解析 顺序表支持随机存储，链表不支持，因此顺序表输出第 i 个元素的值的时间复杂度为 O(1)，链表则为 O(n)，因此 A 正确。 交换第 1 个与第 2 个元素的值，对于顺序表和链表，时间复杂度均为 O(1)，因此 B 不对。 输出 n 个元素的值，两者时间复杂度均为 O(n)，因此 C 不对 输出与给定值 x 相等的元素在线性表中的序号，对于顺序表和链表，count 需要搜索整个表，因此时间复杂度为 O(n)，因此 D 不对。4.设 k 是中序线索二叉树中一个有左子女的结点，且
34、k 不是根结点，则 k 在中序序列下的直接前驱结点是_。 A.k 的左线索(指示中序前驱)所指示的结点 B.从 k 父结点的左子女开始沿右子女链走到底的结点 C.从 k 的左子女开始沿右子女链走到底的结点 D.从 k 的左子女开始沿左子女链走到底的结点（分数：2.00）A.B.C. D.解析：解析 如果 k 没有左子女，则 k 的左指针即为指向 k 的中序前驱的线索；当 k 有左子女时，k 的中序直接前驱结点是 k 的左子树中中序的最后一个结点，即从 k 的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为 k 的中序前驱结点。5.假定一组元素序列为38，42，55，15，23，44
35、，34，74，45，26，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为_。 A.1 B.3 C.4 D.5（分数：2.00）A.B.C. D.解析：解析 根据题目所给的元素序列，可以得到以下的平衡二叉树，如图所示。 * 可以看出度为 2的结点有 4 个。6.由 23、12、45、36 构成的二叉排序树有_个，其中 AVL 树有_个。 A.13；4 B.13；5 C.14；5 D.14；4（分数：2.00）A.B.C. D.解析：解析 该题的结点不多，可以采用枚举法。但枚举法比较容易造成遗漏，所以在枚举时要按照一定的规律，而且在枚举完之后看是否有重合的树
36、并将其去掉，为避免重复可以采用根结点来枚举，枚举得二叉排序树共有 14 个，其中 5 个为 AVL 树。7.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是_。（分数：2.00）A.B. C.D.解析：解析 寻找拓扑排序的步骤： (1)在有向图中选一个没有前驱的顶点并且输出。 (2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。 题中所给图有 3 个不同的拓扑排序序列，分别为： 1)a，b，c，e，d。 2)a，b，e，c，d。 3)a，e，b，c，d。8.无向图 G 有 16 条边，有 3 个度为 4 的顶
37、点，4 个度为 3 的顶点，其余顶点的度均小于 3，则 G 至少有_个顶点。 A.10 B.11 C.12 D.13（分数：2.00）A.B. C.D.解析：解析 度的定义指的是进入一个顶点的边数和从该顶点出去的边数之和。我们可以根据这个关系来求解此题。由于题目已经告诉度为 4 的顶点有 3 个，度为 3 的顶点有 4 个，其余的顶点的度均小于 3，而已知有 16 条边，则总的度数应为 162=32。所以要求最小的顶点个数，我们应当尽量增加每个顶点的度数，这里将剩下的结点的度数全部看成 2，设结点数为，则 34+43+(x-3-4)232，解得 x 至少为11。9.以下有关 m 阶 B-树的说
38、法中正确的有_。每个结点至少有两棵非空子树树中每个结点至多有 m-1 个关键字所有叶子在同一层上当插入一个数据项引起 B 一树结点分裂后，树长高一层 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B. C.D.解析：解析 中：m 阶 B-树根结点至少有两棵子树，并且这两颗子树可以是空树，其余结点至少有m/2个分支，即m/2个子树，所以错误。中：每个结点中关键字的个数比分支数少 1，m 阶 B-树的一个结点中至多有 m 个分支，因此至多有 m-1个关键字，所以正确。中：B-树是平衡的多路查找树，叶子结点均在同一层上，所以正确。中：发生结点分裂的时候不一定会使树长高。比如向图 1 中
39、的 B-树插入一个关键字 10 变成图 2 中的 B-树，使得第二层右端的一个结点分裂成两个，但是树并没有长高，所以错误。综上所述，、正确。*图 1 B-树*图 2 插入一个关键字后的 B-树10.对以下关键字序列用快速排序进行排序，速度最慢的是_。 A.19，23，3，15，7，21，28 B.23，21，28，15，19，3，7 C.19，7，15，28，23，21，3 D.3，7，15，19，21，23，28（分数：2.00）A.B.C.D. 解析：解析 这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，很少有考生在做这种选择题的时候能够分析其算法来选择答案。这里就是变相地考查
40、快速排序算法的最坏情况。快速排序法的最坏情况为待排序列是有序或接近有序的时候，由于 D 中元素已经有序，所以选择 D。11.某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多路归并至少需要_趟可以完成排序。 A.2 B.3 C.4 D.5（分数：2.00）A. B.C.D.解析：解析 不妨设采用 m 路归并，则至少需要 m 个输入缓冲区和 1 个输出缓冲区。因为一个缓冲区对应一个文件，所以 m+1=15，解得 m=14，所以可做 14 路归并。假设需要 s 趟可以完成排序，则 s=log1480=2。12.考虑以下 C 语言代码：short si=-8196;unsigned short usi=s
