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

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

1、计算机算法指的是（ ），它必须具备输入、输出和可行性、确定性和有穷性等5个特性。

A、计算方法

B、排序方法

C、解决问题的有限指令序列

D、调度方法

2、线性表的链式存储结构与顺序（连续）存储结构相比优点是（ ）。

A、便于插入和删除

B、便于随机存取

C、所有的操作/运算的算法简单

D、便于查找

3、如果某应用在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A、仅有头指针的单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

4、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。

A、直接插入排序

B、希尔（ShelI）排序

C、简单选择排序

D、冒泡排序

5、在常用的哈希表处理冲突的方法中，（ ）方法容易产生“二次聚集”，导致哈希表性能变差。

A、开放定址法—线性探测

B、再哈希法

C、链地址法

D、开放定址法—二次探测

1、试题答案：C

试题解析：

法是对特定问题求解步骤的一种描述，它是指令的有序序列，其中每一条指令表示一个或多个操作。故本题选C。

2、试题答案：A

试题解析：

对于A，链式存储结构插入和删除不需要移动元素，仅需要修改指针，其操作的时间复杂度为O(1)，而顺序存储结构插入和删除均需要移动元素，其操作的时间复杂度为O(n)。对于B，链式存储结构不是随机存取结构而顺序表是随机存取结构，因此B错误；对于C和D，对于已知下标的查找，链表的查找操作需要从头开始，时间复杂度为O(n)，而顺序表可以通过下标直接访问，时间复杂度为O(1)，因此C和D错误，故本题选A。

3、试题答案：D

试题解析：

对于仅有头指针的单链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有头指针的单循环链表，在结尾处插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于双向链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有尾指针的单循环链表，在结尾插入元素的时间复杂度为O(1)，删除首元素的时间复杂度为O(1)。故本题选D。

4、试题答案：C

试题解析：

对于A，若初始序列完全有序，则关键字的比较次数为n-1，若无序，则比较次数>n-1，因此A错误；
对于B，希尔排序的关键字比较次数也会受到初始排列次数的影响，因此B错误；
对于C，简单选择排序通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换，选择排序的比较次数为 n*(n-1)/2，关键字的比较次数与关键字的初始状态无关，因此C正确。
对于D，冒泡排序若初始序列有序则仅需要进行一趟冒泡排序，比较次数为n-1，若初始序列无序，则比较次数>n-1，因此D错误。故本题选C。

5、试题答案：A

试题解析：

对于A，线性探测容易发生二次聚集：当表中i、i+1、i+2位置上已填有记录时，下一个哈希地址为i、i+1、i+2的记录都将争夺i+3的位置；对于B，再哈希法会在发生冲突时计算另一个哈希函数的地址，这种方法不易发生聚集，但会增加计算时间；对于C，链地址法会将发生地址冲突的关键字链接到链表中，这种方法不会出现聚集；对于D，二次探测法不易发生聚集，但这种方法只有在表长m形如4j+3（j为整数）时才可能。故本题选A。