2022下半年软件设计师考试知识点100条（9）

为帮助大家备考软考中级软件设计师考试，希赛小编整理了2022下半年软件设计师考试知识点100条（9），希望对大家备考有帮助。

81、最优二叉树的概念

最优二叉树：又称为哈弗曼树，它是一类带权路径长度最短的树。

路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。

82、二叉树的遍历操作

前序遍历：又称为先序遍历，按根左右的顺序进行遍历。

后序遍历：按左右根的顺序进行遍历。

中序遍历：按左根右的顺序进行遍历。

层次遍历：按层次顺序进行遍历。

83、图的概念

完全图

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图（complete graph）。

在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。

强连通图：在有向图中，对于每一对顶点，从顶点vi到顶点vj和从顶点vj到顶点vi都存在路径，则称为强连通图。

84、图的遍历特点

深度优先遍历：

当以邻接矩阵作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n2)

当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)

广度优先遍历和深度优先搜索遍历图的运算时间复杂度相同，其不同之处仅仅在于对顶点的访问次序不同。

85、算法特性

有穷性：执行有穷步之后结束，且每一步都可在有穷时间内完成。

确定性：算法中每一条指令都必须有确切的含义，不能含糊不清。

输入（>=0）

输出（>=1）

有效性(可行性)：算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a=0，b/a就无效

86、常见算法策略

87、常见的对算法执行所需时间的度量

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

88、常见排序算法对比

89、常见排序算法适用常见对比1

若待排序列的记录数目n较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量大时，用简单选择排序方法较好。

若待排记录按关键字基本有序，宜采用直接插入排序或冒泡排序。

当n很大且关键字位数较少时，采用基数排序较好。

若n很大，则应采用时间复杂度为O(nlog2n)的排序方法，例如快速排序、堆排序或归并排序：

快速排序目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短；

堆排序只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况。

快速排序和堆排序都是不稳定的排序方法，若要求排序稳定，可选择归并排序。

90、编译与解释的区别

编译方式下机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程，因此执行时效率较高；

解释方式下解释程序和源程序（或某种等价表示）要参与到程序的运行过程中，边解释边执行，执行效率较低。

即：解释方式，翻译程序不生成独立的目标程序，而编译方式则生成独立保持的目标程序。