数据结构刷题2023.02.27小记

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

数据结构刷题2023.02.27小记

2023-02-27 12:58:45 来源：博客园

(资料图片仅供参考)

单循环链表

A从表中任一结点出发都能扫描到整个链表B不再需要头指针了C在进行插入、删除操作时，能更好地保证链表不断开D已知某个结点的位置后，能够容易找到它的直接前趋正确答案 A

归并排序相对于快速排序的优点不包括（）

A：归并排序是稳定排序，快速排序是不稳定排序，故A对。B：归并排序的最坏时间复杂度为O(nlogn)，而快速排序的最坏时间复杂度为O(n^2)，故B对。C：归并排序需要额外的O(n)的空间，快速排序需要额外的O(1)的空间，故C错。D：归并排序的平均时间复杂度和最坏时间复杂度均为O(nlogn)，不会退化；快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，会退化；故D对。

对给定的关键字序列110， 119， 007， 911， 114， 120， 122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是（）。

基数排序一般从最低有效位开始即个位开始排序，第一趟排出110,120,911,122,114,007,119，第二趟按照次高有效位即十位排序，第二趟排出007,110,911,114,119,120,122.基数排序与关键字的位数有关，但也是一种稳定排序。

在快速排序中，要使最坏情况的空间复杂度为O(log2n )则要对快速排序作( )修改。

A划分元素为三者取中B采用表排序C先排最小集合D先排大集合

快速排序的思想：先从数列中取出一个数作为基准数分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边再对左右区间重复第二步，直到各区间只有一个数最优的情况下空间复杂度为：O(log2n) ；每一次都平分数组的情况，基准数尽量为中间数。快速排序的最坏情形是数组为正序或逆序，如果pivot总是选择第一个元素，那么每次划分只得到一个比上一次划分少一个记录的子序列，此时需要执行次递归调用。显然，采用A（划分元素为三者居中），能够将每次待排序的part尽可能一分为二，从而使得递归深度为)，即空间复杂度为

在一般包含n个节点的二叉搜索树中查找的最差时间复杂度是?

AO(log(n))BO(n)CO(n^2)DO(1)二叉搜索树可以不平衡

关于双链表的搜索给定元素操作的说法正确的是?

A从两个方向搜索双链表，比从一个方向搜索双链表的速度慢B从两个方向搜索双链表，比从一个方向搜索双链表的方差要小C从两个方向搜索双链表，比从一个方向搜索双链表速度要快D以上说法都不正确B 如果链表数据是无序的，则单向搜索与双向搜索平均速度相同如果链表是有序的，而要搜索的数据距离最小值（最大值）较近，这种情况下双向搜索平均速度更快。因此双向搜索更稳定，方差更小