数据结构复习——个人mooc学习错题和相关知识点整理

目录

第七周 树与二叉树（下）

第八周 图（上）

第九周 图（下）

第十周 查找（上）

第十一周 查找（下）

第十二周 排序（上）

---

第七周 树与二叉树（下）

1、叶结点多于1的赫夫曼树不存在度为1的结点

2、赫夫曼树中权值最小的两个结点互为兄弟结点

注：感觉有点疑问，如叶结点是四个5的话，两个5之间可能是兄弟关系，也可能是堂兄弟关系。但题干中又说是最小的两个结点，说明这两个结点小于其他的结点，这样解释也可以。

3、已知一颗有2011结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点的个数是：A 1895 B 116 C115 D 1896 正确答案D，错选为B

注：可用特殊情况去解，设题意中的树前1894层均仅有一个度唯一的结点，第1895层是一个有116个叶子的结点。

4、森林的先序与中序遍历即其对应的二叉树的先序与中序遍历。

树的先根遍历与后根遍历即对应二叉树的先序与中序遍历。

5、在后序线索树中找结点后继，有三种情况：（1）若结点x是二叉树的根，则其后继为空；（2）若结点x是其双亲的右孩子 或是 其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；（3）若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。（不是右子树最左下的结点，那是中序遍历）。

6、n叉树中某结点的度实质是该结点的孩子个数，相当于有向图中的出度。//与这一学期学的离散数学的定义不一样，将就着看。

第八周 图（上）

1、最小生成树的代价唯一，但最小生成树不唯一。

2、具有n个顶点有向强连通图，其弧条数的最小值为n。（这里的弧就是有向线段）

3、无向连通图特点：所有顶点的度之和为偶数，边数>=顶点个数减一，所有顶点度>=1（可以所有顶点的度都大于1）。

4 图的遍历

图的存储结构 二维数组 深度优先搜索遍历图所需时间为O（n^2）n为图中顶点数；

邻接表? ? dfs时间为O(n+e) e为无向图中边的个数或有向图中弧的个数。

广度优先搜索遍历图所需时间与深度优先相同，不同点仅仅在于对顶点的访问顺序不同。

5、图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次。

图的深度优先遍历适用于有向图与无向图。

图的广度优先生成树的树高一定<=它自己深度优先生成树的树高。

第九周 图（下）

1、通路 回路 简单通路 简单回路 基本通路 基本回路

回路是通路的一种特殊形式，回路的起点和终点相同。

“简单”XX，通路中的所有边各不相同。

“基本”XX，通路中的所有点各不相同（从而所有边各不相同）

范围：“基本”XX<“简单”XX<一般情况

2、关键路径上的所有活动都是关键活动，最早开始时间==最晚开始时间。

关键路径决定整个工程的工期，可能不止一条。

第十周 查找（上）

1、插值查找算法与数据结构——插值查找（c/c++实现）_数据结构与算法c语言插值查找代码-CSDN博客

2、静态查找表与动态查找表的根本区别在于施加其上的操作不同，而不是逻辑结构、存储实现、所包含的数据类型。

3、对含有600个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（）

A 11 B 10 C 9 D 300 正确答案B，错选C

注：若采取折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为n，二叉搜索树高度为h= 上取整log(n+1) +1，代入n=600，可得h=10。如果这个题问顺序表中存在的元素的最大比较次数，那就是9次。

4、折半查找关键字比较序列就是折半查找树从根节点到叶子结点的路径。

5、在二叉排序树中，新节点总是作为叶子结点插入的。注意区分二叉排序树与平衡二叉树。

6、在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（）量级相当。

A 以上都不对? B 折半查找 C 分块查找 D 顺序查找

注：被关键字随机分布给迷惑住了。不是顺序排列，应该是要找的数字随机分布。

7、在平衡树上进行查找的时间复杂度为O（logn）。

8、平衡二叉树就是AVL树，下面这个写的很好

平衡二叉树 —— 如何优雅的进行旋转 - 知乎 (zhihu.com)

LL —— 单向右旋平衡处理 LR（双向旋转（先左后右）平衡处理）

RR——单向左旋平衡处理 RL （双向旋转（先右后左）平衡处理）

为什么LL、RR字母和名称不对应？因为LL的含义是危机节点在根结点的左孩子的左子树上，强调的是位置。为什么LR、RL又对应上了？详见上面的链接。

第十一周 查找（下）

1、B-树的定义

一颗m阶B-树，或为空树，或为满足下列特性的m叉树。

（1）根节点要么是叶子，要么至少有两颗子树；

（2）树中的每个结点至多有m棵子树；

（3）除根以外的所有非终端结点至少有棵子树。

结点所含关键字个数应该-1<=x<=m-1个，所以一个5阶B-树结点所含关键字个数应该2<=x<=4，但有个特例，就是根结点可以只有1个。

注意：B-树的叶子结点没有关键字，是F，上面的定义中没把终端结点叫成叶子。

2、B-查找的最坏情况为以为底，（n+1)/2的对数，再加上1。

3、B-树的插入与删除

插入：从最下层非终端结点开始插入，若被插入结点关键字个数<=m-1，则无事发生；若>=m，则分裂。结点的分裂就是从中间任取一个关键字变成根结点（若有上一层父结点，插入上一层的父结点），其余两部分变成父结点的两颗子树。

删除：1、删除非最下层非终端结点 2、删除最下层的非终端结点

删除非最下层非终端结点只需两步，（1）将该结点的直接前驱（或后继）放到该结点，相当于删除的是该结点直接前驱（或后继）。若该结点直接前驱（或后继）也不是最下层非终端结点，重复上述（1）步骤，如果是，则进行（2）删除最下层的非终端结点。所以，只要解决删除最下层的非终端结点，就可以解决删除非最下层非终端结点的问题。

删除非最下层非终端结点：3种可能。

（1）被删关键字所在结点中的关键字数目不小于则只需从该结点中删去该关键字Ki和相应指针Ai，树的其他部分不变。

（2）被删关键字所在结点中的关键字数目等于-1，而与该结点相邻的右兄弟（或左兄弟）结点的关键字数目大于-1。则需将其兄弟结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。

（3）被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于-1。被删关键字所在结点+双亲结点的某关键字+某兄弟结点，合并成新结点，新结点与旧结点的双亲结点一致。

4、哈希表查找失败的平均长度

Hash表查找成功和查找不成功的平均查找长度（附总结）_哈希表查找失败的平均查找长度-CSDN博客

（1）现有长度为?5?，初始为空的散列表HT，散列表函数H(k)=(k+4)?mod?5，用线性探查再散列法解决冲突。若将关键字序列?2022,?12,?25?依次插入HT中，然后删除关键字?25?，则HT中查找失败的平均查找长度（????????）。

A 1?B 2.2 C 1.6 D 1.8 答案D 错选 C

2022插入到1号单元，12插入到2号单元，25插入到4号单元；删除25后，需要在4号单元增加删除标记。
假设分别散列到0到4号单元，按照冲突处理方法，计算出每种情况查找失败需要的次数，即失败查找长度，求和后除以表长5即为所求。
当查找过程中遇到删除标记，仍需按照冲突处理方法继续查找其可能的后继单元，直到后继单元为空才意味着这次查找失败。故当散列到4号单元时，需要两次查找才能确定查找失败。 //错选原因

（2）现有长度为?11?且初始为空的哈希表?HT，散列函数是?H(key)?=?key?%?7，采用线性探查（线性探测再散列）法解决冲突将关键字序列?87,?40,?30,??6,?11,?22,?98,?20?依次插入到?HT?后，HT?查找失败的平均查找长度是（）

A 4.28 B 5.25 C 6 D 6.29 答案 C 错选 A

这题搞得我晕头转向

现有长度为11且初始为空的散列表HT，散列函数是H(key)__牛客网 (nowcoder.com)

我懂了！查找成功要找元素个数，查找失败要找位置个数。像（2）题，查找成功要除以8，查找失败要除以7，而且是（9+8+7+6+5+4+3）/ 7? == 6。为什么？因为查找失败的元素第一次比较时只能在0到6的地址上出现，也就是7种位置情况。实质是加权平均数，第二题各元素的权重为八分之一，各位置的权重为七分之一。

5、哈希表处理冲突的方法

1……开放选址法 Hi = （H(key) + di）MOD m? i = 1,2,…,k（k<=m-1）

（1）di = 1,2,3,...,m-1,线性探测再散列 （2）di = 1,-1,4,-4,...,,（k<=m/2）二次探测再散列

（3）di=伪随机数序列，成伪随机探测再散列

2……再哈希法

3……链地址法

4……建立一个公共溢出区

6、为提高散列(Hash)?表的查找效率，可以采取的正确措施是（????????）。
?I.??增大装填(载)因子
?II.?设计冲突(碰撞)少的散列函数
?III.处理冲突(碰撞)时避免产生聚集(堆积)现象

只有第二个对，第一个应该是减少，第三个不能“避免”，只能“减少”。

第十二周 排序（上）

1、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是（????????）。

A 快速排序 B 简单选择排序 C 起泡排序 D 堆排序 答案ABCD 错选 ABC

2、序列关于大根堆（至少含2个元素）的叙述中正确的是（????????）。(4分)
A从根结点到某个叶子结点所经路径上的结点一定构成一个递减有序序列
B可采用顺序存储方式保存堆
C堆中的次大值一定在根的下一层
D可以将堆看成一棵完全二叉树?

答案BCD 错选ABCD 注：A：可能是非递增序列，孩子是<=父结点的

3、堆排序

输出堆顶元素，并将最后一个元素放到堆顶，最后再对堆进行排序；堆排序从小堆到大堆挨个排序；递归是交换完大堆后要维护后面的小堆，因为大堆排完后会影响后面小堆的顺序。//不用看这一段话，只要看后面的博客和视频就好，建议直接看视频。

堆排序详细图解（通俗易懂）-CSDN博客

排序算法：堆排序【图解+代码】_哔哩哔哩_bilibili

4、下列排序算法中，不稳定的有（）

A shell排序 B 堆排序 C 快速排序 D 简单选择排序 答案ABCD

直接插入排序是稳定的

5、希尔排序的组内用的是直接插入排序

6、建议讲解与评论一起看数据结构：下列选项中，不可能是快速排序第2趟排序结果的是（2019年全国试题10）_不可能是快速排序第二趟结果的是-CSDN博客

快排阶段性排序结果特点:第i趟完成时，会有个i个及以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。
题目问第二趟排序的结果，即要找不存在2个这样的数的选项。

7、简单选择排序比较次数与序列初态无关。