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

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

1、在下图所示的5阶B树T中，删除关键字260之后需要进行必要的调整，得到新的B树T1。下列选项中，不可能是T1根结点中关键字序列的是（ ）。

A、 60，90，280

B、 60，90，350

C、 60，85，110，350

D、 60，90，110，350

2、5个字符有如下4种编码方案，不是前缀编码的是（  ）。

A、 01，0000，0001，001，1

B、 011，000，001，010，1

C、 000，001，010，011，100

D、 0，100，110，1110，1100

3、树最适合用来表示（ ）。

A、有序数据元素

B、无序数据元素

C、元素之间具有分支层次关系的数据

D、元素之间无联系的数据

4、若某链表最常用的操作是在末尾插入结点和删除尾结点，则该链表最节省时间的存储方式是（ ）。

A、单链表

B、单循环链表

C、带尾指针的单循环链表

D、带头结点的双循环链表

5、下面程序段的时间复杂度是（ ）。for(i=0;i<m;i++) A[i]=0;for(i=0;i<m;i++) for(j=1;j<n;j++) A[i]+=5;

A、O(m+n)

B、O(m+n+1)

C、O(n)

D、O(m*n)

1、试题答案：D

试题解析：

【考点】本题考查B树的删除操作
【解析】一棵m阶的B树除根结点以外的所有非叶子结点至少有m/2向上取整棵子树，根结点若非叶子结点，则至少含有两棵子树。本题是5阶B数，所以关键字的数量n满足2<=n<=4。画出上述各选项对应的B树，并检查是否符合B树的性质，即可得出正确答案。

2、试题答案：D

试题解析：

【考点】本题考查哈夫曼编码的特性。
【解析】判定某字符集的不等长编码是否具有前缀特性的过程描述为字符集的每一个编码应该对应一条路径。初始时，二叉树仅含有一个根结点，其左右指针为空。依次读入字符集中的编码，每读入一个编码从根结点开始，若为0则沿左子针向下移动，若为1则沿右指针向下移动，当指针指向的下一个结点为空且当前结点未标记，则创建一个结点并标记；若编码至最后一位且指针指向的是非空结点，则不具有前缀特性，返回；若当前编码没有至最后一位且遇到已标记的叶子结点，则不具有前缀特性，返回。当所有编码读入完毕且通过验证则具有前缀性。按照上述方法将ABCD选项分别转换为一棵树，根据创建树的过程是否符合哈夫曼树的特性来判断是否为前缀编码。A选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此A正确。
B选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此B正确。
C选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此C正确。
D选项中的110是110的缀。而在一棵哈夫曼树中，树的叶子结点表示字符，因此110在树中不是叶子结点，因此该字符集不具有前缀性。故本题选D。

3、试题答案：C

试题解析：

本题考查树结构的概念。
根据数据元素之间存在的逻辑关系，通常有四种数据结构，分别为线性结构、树型结构、图状或网状结构、纯集合结构。有序和无序数据元素通常采用线性结构较为合适，因此A和B错误。树型结构是一对多的逻辑结构，能够很好表示数据之间的分支层次关系，因此C正确。树型结构具有一对多的逻辑关系，数据间并非无联系，因此D错误。故本题选C。

4、试题答案：D

试题解析：

选项A的单链表和选项B的单循环链表在末尾插入结点和删除尾结点时均需要遍历链表，时间复杂度为O(n)。选项C的带尾指针的单循环链表在末尾插入结点的时间复杂度为O(1)，删除尾结点时需要获取尾结点的前驱结点，时间复杂度为O(n)。选项D的带头结点的双循环链表在末尾插入结点和删除尾结点的时间复杂度为O(1)。故本题选D。

5、试题答案：D

试题解析：

第一个for循环内的语句执行m次，时间复杂度是O(m)，双层for循环内的语句执行m*n次，时间复杂度为O(m*n)，故本题选D。