算法与数据结构核心概念.pdfVIP

算法与数据结构作业3

单项选择题

第1题在树中，树的度与结点的度之间的关系是：（）。

A、树的度就是结点的度

B、树的度为2，结点的度可以是0，1和2

C、结点度中最大值为树的度

D、树的度与结点的度无关

：C

第2题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层

上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问各层的结点

数？（）。

A、第i层的结点数2i-1

B、第i层的结点数Ki-1

C、第i层的结点数是K

D、第i层的结点数是1+2+3+…+K

：B

第3题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层

上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问编号为n的

结点的父结点（若存在）的编号？（）

A、2n-1

B、Kn-1

C、K

D、1+2+3+…+K

：B

第4题通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度增加而：

（）。

A、增加

B、减少

C、不变

D、无规律

：A

第5题树最适合用来表示：

A、有序数据元素

B、无序数据元素

C、元间具有分支层次关系的数据

D、元间无联系的数据

：C

第6题一个具有n个顶点的连通无向图的生成树中有（）条边

A、n-1

B、n

C、n/2

D、n+1

：A

第7题关键路径是结点网络中（）

A、最长的回路

B、最短的回路

C、从开始结点到完成结点的最长路径

D、从开始结点到完成结点的最短路径

：C

第8题对稀疏矩阵进行压缩目的是（）。

A、便于进行矩阵运算

B、便于输入和输出

C、节省空间

D、降低运算的时间复杂度

：C

第9题设无向图的顶点个数为n，则该图最多有（）条边。

A、n-1

B、n(n-1)/2

C、n(n+1)/2

D、0

：B

第10题下列不正确的是（）。

A、图的遍历是从给定的源点出发每一个顶点仅被一次

B、遍历的基本算法有两种：深度遍历和广度遍历

C、图的深度遍历不适用于有向图

D、图的深度遍历是一个递归过程

：A

第11题下面关于求关键路径的不正确的是（）。

A、求关键路径是以拓扑排序为基础的

B、任何一个关键活动提前完成，那么整个工程将会提前完成

C、所有的关键活动提前完成，那么整个工程将会提前完成

D、某些关键活动提前完成，那么整个工程将会提前完成

：D

多项选择题

第12题一棵含有25个结点的完全二叉树的深度():

A、4

B、5

C、6

D、log225

：A|D

第13题稀疏矩阵的存贮结构要满足哪些条件？()

A、每个非零元素存贮其行号、列号以及值

B、存贮矩阵的行数和列数

C、所有的非零元素以行优先的排列规则存贮

D、只存贮上三角的元素

E、只存贮下三角的元素

：A|B|C

第14题图的邻接矩阵存贮结构包括():

A、表示图中顶点间相邻关系的矩阵

B、对称矩阵

C、表示图中顶点元素的数组

D、表示入度的数组

E、表示出度的数组

：A|C

判断题

第15题有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到

编码后的内容后，不能转换为原来的正文。该是否正确？

：正确

第16题树是一种特殊的图。

：正确

第17题将左边的树转换为二叉树，右边的结果是否正确。

：正确

第18题二叉树只能用链表方式存贮。

：错误

第19