考研数据结构在线题库每日一练（六十九）

本文提供考研数据结构在线题库每日一练，以下为具体内容

1、在一棵具有15个关键字的4阶B树中，含关键字的结点个数最多是（  ）。

A、 5

B、 6

C、 10

D、 15

2、在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是（ ）。I. 若v是T1的叶结点，则T1与T3可能不相同II. 若v不是T1的叶结点，则T1与T3一定不相同III. 若v不是T1的叶结点，则T1与T3一定相同

A、 仅I

B、 仅II

C、 仅I、II

D、 仅I、III

3、求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是（  ）。

A、 （V1，V3）

B、 （V1，V4）

C、 （V2，V3）

D、 （V3，V4）

4、一个栈的进栈序列是a b c d e，则栈的输出序列不可能的是（ ）。

A、a b c d e

B、e d c b a

C、d e c b a

D、d c e a b

5、在文件“局部有序”的情况下，最佳内部排序是（ ）。

A、直接插入排序

B、快速排序

C、简单选择排序

D、归并排序

1、试题答案：D

试题解析：

【考点】本题考查B树的应用。
【解析】上述题干结点个数最多，则B-树的每棵树含有的关键字数量最少。根据B树的性质，除终端结点外，其余结点所含的最少关键个数为m/2取上界-1个=1个。因此该B树的每个结点含1个关键字，即每个结点有两个分支。恰好能够构造出一棵树的高度为四的满二叉树。该树的结点个数为15个。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查平衡树的插入和删除
【解析】对于I，若删除叶结点之后引起左右分支的不平衡，此时树会调整，在插入节点后形成叶子结点，此时T1与T3可能不同；若T1删除v后不引起调整，则T1与T3相同，因此I正确。对于II，v是非叶结点，则删除后引起树的调整，再插入v后可能不平衡再次调整，经过两次调整，树T1与树T3可能相同，因此II错误。同理，经过两次调整，树T1与树T3可能不同，因此III错误。故本题选A。

3、试题答案：C

试题解析：

【考点】本题考查最小生成树的两种算法。
【解析】构造最小生成树有两种算法，一种是kruskal算法，一种是Prim算法，kruskal算法主要针对边进行操作，其算法的时间复杂度为O(eloge)。Kruskal算法的基本思想为：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直至该森林成为一棵树为止。Prim算法的思想为首先选取图中任一顶点v作为生成树的根，之后往树中添加顶点w，w v之间必须有边，且该边的权值应在所有和v相连接的边中最小，之后在w v相连的顶点中添加顶点，保证边权值最小，重复上述过程，直至所有的顶点添加到树中。其主要是对顶点进行操作，时间复杂度为O(n2)。按照上述算法思想，kruskal算法是选择边的算法，第一次选的边必为（V1,V4），第二条边必从（V1,V3），（V2,V3），（V3,V4）中选择一条。Prim算法是选择顶点的算法，从V4出发，第一次选择（V1,V4），第二次从（V1,V3），（V3,V4）中选择一条，可能是克鲁斯卡（Kruskal） 算法第2次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是（V2,V3），故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查栈的基本概念。
【解析】根据栈“后进先出”的特点，可知选项D中dce均出栈后，栈中仅剩下ab两个元素。但由于a比b先进栈，故a只能在b出栈之后出栈，因此输出序列不可能是dceab。故本题选D。

5、试题答案：A

试题解析：

假设文件初始时完全有序，此时直接插入排序的时间复杂度为O(n)，快速排序的时间复杂度为O(n²)，简单选择排序的时间复杂度为O(n²)，归并排序的时间复杂度为O(nlogn)。因此文件“局部有序”时，最佳的内部排序为直接插入排序，故本题选A。