Question

数据结构与算法选择题！

1.在最坏的情况下，查找成功时二叉排序树的平均查找长度（）
A.无法与顺序表的平均查找长度比较
B.大于顺序表的平均查找长度
C.小于顺序表的平均查找长度
D.与顺序表的平均查找
2.弱线性表次啊用链式存储结构，则使用的查找方式（）
A.随机查找
B.散列查找
C.二分查找
D.顺序查找长度相同
第一题是选择C吗？能不能说说理由啊？我不太确定，但是感觉是D啊，不是在最坏的情况下不是退化成顺序表吗？就是只有一侧子树的那种！所以是不是应该是D啊？
请给我解释一下选择C的理由啊。谢谢

第二题我打错了，最后一个选项是顺序查找，没有后面那几个字。

Answer 1

第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列
第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；
第三题：A：极小连通图是一棵生成树，只有N-1条边，但是连通分量可能有N条边，例如极小连通图A—— B——C，连通分量“A”——B——C——“A”(这里的最后一个“A”跟第一个“A”一致）：；
B:你查下极大强连通子图概念就明白了；
C:你看看第二题的例子就明白了，AC之间没有弧，但他们是一个拓扑序列；
D：例如：环形图就不满足，比如长方形，四个顶点，两种遍历都能访问到每个顶点，但不是完全图

Answer 2

第一题是应该选D
最坏的情况下蜕变为单支树 树的深度为n 那么其平均查找长度为(n+1)/2
跟顺序查找是相同的
第二题没看懂。。

Answer 3

baidu

Answer 4

1.C
2.D