软考软件设计师考试知识点填空检测（4）

为方便软考考生对软件设计师考试知识点的检测，希赛软考频道为考生带来软考软件设计师考试知识点填空检测的内容（完整版可在本文文首本文资料处或文末的资料下载栏目下载）。

软考软件设计师考试知识点填空检测（4）内容如下：

第4章 数据结构

1 考点精讲

1.1 线性结构

1、线性结构是一种基本的数据结构， 主要用于对客观世界中具有____和____的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系， 即元素“一个接一个排列”。

2、线性表的存储结构分为____和____。

3、栈和队列是程序中常用的两种数据结构,它们的逻辑结构和线性表相同。其特点在于运算有所限制。栈按____的规则进行操作，队列按____的规则进行操作，故称为运算受限的线性表。

4、长度为零的串称为____，它不包含任何字符。

1.2 树

1、双亲、孩子和兄弟：结点的子树的根称为该结点的____;相应地，该结点称为其子结点的____。具有相同双亲的结点互为____。

2、结点的度：一个结点的____记为该结点的度。

3、叶子结点：叶子结点也称为____，指度为____的结点。

4、内部结点：度不为0的结点，也称为____或____。除根节点以外，分支结点也叫____。

5、树的高度：一棵树的最大层数记为树的____。

6、对于任何一棵二叉树，若其终端结点数为n0,度为2的结点数为n2，则满足等式____。

7、具有n个结点的完全二叉树的深度为____。

8、最优二叉树又称为____，它是一类带权路径长度最短的树。

9、前序遍历：又称为先序遍历，按____的顺序进行遍历。

10、后序遍历：按____的顺序进行遍历。

11、中序遍历：按____的顺序进行遍历。

12、____：按层次顺序进行遍历。

1.3 图

1、有向图。若图中每条边都是____的，那么顶点之间的关系用<v，y>表示，它说明从v到y有一条有向边(也称为弧)。v是有向边的起点，称为弧尾，y是有向边的终点，称为弧头。所有边都有方向的图称为____。

2、无向图。若图中的每条边都是____的，顶点v和y之间的边用(v，y)表示。因此,在有向图中<v，y>与<y，v>分别表示两条边，而在无向图中(v，y)与(y，v)表示的是____。

3、完全图。若一个无向图具有n个顶点，而每一个顶点与其他n -1个顶点之间都有边，则称之为____。显然，含有n个顶点的无向完全图共有____条边。

4、度：顶点v的度是指关联于该顶点的____的数目。

5、图的基本存储结构有____表示法和____表示法两种。

6、无向图的邻接矩阵是____的，有向图的邻接矩阵则不一定____。

7、____搜索和____搜索是两种遍历图的基本方法。

8、对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为____。

9、普里姆算法的时间复杂度为O(n^2),与图中的边数无关，因此该算法适合于求____的网的最小生成树。

10、克鲁斯卡尔算法的时间复杂度为O(eloge)，与图中的顶点数无关，因此该算法适合于求____的网的最小生成树。

11、AOV网从源点到汇点的路径中，长度最长的路径称为____。关键路径上的所有活动均是关键活动。

1.4 查找

1、顺序查找的基本思想是:从表的一端开始，逐个将记录的____和给定值比较，若找到一个记录的关键字与给定值相等,则查找成功;若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

2、____:首先将待查元素的关键字(Key) 值与表中间位置上的关键字进行比较，若相等，则查找成功;否则需重新在上、下部分的表查找。

3、二叉排序树又称____，它或者是一棵空树，或者是具有以下性质的二叉树。

(1)若它的左子树非空，则左子树上所有结点的值均____根结点的值。

(2)若它的右子树非空，则右子树上所有结点的值均____根结点的值。

(3)左、右子树本身是____。

4、____又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过____。

2 章节问答

1、强连通图和有向完全图的区别？

答：