数据结构难题小解析

8.1

（1）

  如果是有向完全图，那么它的邻接矩阵是一个只有主对角线元素为零的矩阵

连通图同上，强连通图同理。

邻接矩阵为对角线元素均为0的上三角矩阵时，某个点只能到达比他标号大的点。不可能形成循环。所以选D

（2）

当图为无向图时，每条边连着两个点，那么必定产生两个表结点。

也就是表结点个数等于边的个数*2
（3）

同理，无向图的度数等于边的两倍，其他选项与无向连通图没关系。

（4）
某个顶点的出度最多是n-1，删掉要O(n)

某个顶点的入度最多是e，删掉要O(e）

所以是O（n+e）

画图：

从a->e->d->f->c 然后到a但是a访问过了，所以沿路返回回溯至a，然后再->b 

 根据kruskal算法，第一次选取边权最小的边，所以它一定包含在最小生成树

连通分量就是极大连通子图，

邻接多重表（很难好像不会考）

 邻接表头后面跟着的表结点就是它所连接的边

就是说当有16条边时，无论你怎么摆放这些边都可以使其连通

当有17条边时，同  无论你怎么摆放这些边都可以使其连通

....

但是当你只有15条边时，我来个特殊情况，15条边把6个点全连上，孤立掉第7个点，就不连通了。

所以保证任何情况都连通的最少边数是16

（7）

这道题你画完A选项后就会发现这是一颗三层的满二叉树，这肯定是高度最小的

不然就变成四层了

（8）

B树没学 好像不会考 很难

（9）

同义词即哈希值相等

25%13==51%13

最佳分块数一般是开根号sqrt（256）=16（题目超纲了！！）

平均检索万能公式

平均检索长度=（1+板块数）/2+（1+每块内的元素个数）/2

(1+32）/2+(1+8)/2=21

(1)

这里的快速排序按字母表顺序排的，前半部分每个元素小于中间，后半部分每个元素大于中间 

（2）

实型数据包含小数

D不适合小数排序吧

（3）

知识点：根据序列建立堆

D选项建立如图小根堆：

 

 如果原始状态就是有序的，冒泡排序只需一次遍历就结束了