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

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

1、快速排序在最坏情况下的时间复杂度是（ ） 。

A、 O(n²log₂n)

B、 O(n²)

C、 O(nlog₂n)

D、 O(log₂n)

2、已知一个线性表(38, 25, 74, 63, 52, 48), 假定采用散列函数h(key)=key%7计算散列地址，并将散列存储在散列表A[0,.....,6]中，若采用链地址法，求1号地址元素的个数（  ）。

A、0

B、1

C、2

D、3

3、下列序列中，（ ）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。

A、[da,ax,eb,de,bb]fp[hq,gv]

B、[cd,eb,ax,da]fp[hq,gv,bb]

C、[gv,ax,eb,cd,bb]fp[da,hq]

D、[ax,bb,cd,da]fp[eb,gv,hq]

4、某算法代码段如下，其时间复杂度是（ ）。for(i=1;i<=n;++i) for(j=1;j<=n;++j) { c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; }

A、O(n²)

B、O(n³)

C、O(n)

D、O(nlog₂n)

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

A、便于插入和删除

B、便于随机存取

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

D、便于查找

1、试题答案：B

试题解析：

【考点】本题考查快速排序的时间复杂度。
【解析】快速排序最坏的情况是序列本身正序或者逆序，此时每趟排序基准元素会将序列分成两部分，其中有一部分是空，这样递归树就变成了一棵倾斜的树，树的深度n-1，块排时的间复杂度就变成O(n²)。故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查链地址法
【解析】38%7=3；25%7=4,74%7=4；63%7=0；52%7=3；48%7=6，1号地址元素个数为0，故本题选A。

3、试题答案：A

试题解析：

根据快速排序的思想可知，在执行第一趟快速排序之后，基准值左边的关键字都比基准值小，基准值右边的关键字都比基准值大。A选项符合快速排序的基本思想。对于B，bb比fp小，bb不应当出现在fp的右边，因此B错误；对于C，gv比fp大，gv不应当出现在fp左边，da比fp小，da不应当出现在fp右边，因此C错误；对于D，eb比fp小，不应当出现在fp右边，因此D错误。故本题选A。

4、试题答案：B

试题解析：

上述代码是由三层for循环构成的，每层循环的时间复杂度为O(n)，因此三层循环嵌套的时间复杂度为O(n³)，故本题选B。

5、试题答案：A

试题解析：

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