2020 数据结构（周艳聪）计算1801(天津商业大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-02-22到2020-07-31
本篇答案更新状态:已完结

【作业】第1章 绪论 第1章绪论作业

1、 问题:算法的时间复杂度与（ ）有关。A．问题规模 B．计算机硬件的运行速度C．源程序的长度 D．编译后执行程序的质量
评分规则: 【 选A。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的质量有关，但这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。
】

2、 问题:以下说法错误的是（ ）。A．数据项是数据不可分割的最小单位。B．数据元素常表示为域、属性或字段的形式。C．存储结构可分为顺序存储结构和链式存储结构。D．逻辑结构可分为集合、线性结构、树形结构和图状结构。
评分规则: 【 选 B。数据元素是数据基本的构成单位。常表示为记录或结点。
】

3、 问题:数据的逻辑结构包括（）A 线性结构和非线性结构 B 逻辑结构和物理结构C 顺序结构和链式结构D 虚拟结构和抽象结构
评分规则: 【 选A树形结构和图状结构均属于非线性结构
】

4、 问题:给出下面程序片段的时间复杂度（）for(i=0;i O(n^2)
】

5、 问题:给出以下算法的时间复杂度（）void func(int n)
{
int i=1,k=100;
while (i<=n)
{
k++;
i+=2;
}
}
评分规则: 【 O(n)
】

【作业】第2章 线性表 2.1 顺序存储结构习题

1、 问题:【2-1-1】顺序表是线性表的（ ）存储表示。A. 有序 B. 连续 C. 数组 D. 顺序存取
评分规则: 【 选 C。 顺序表是线性表的数组存储表示，也称为线性表的顺序存储结构。 注意，顺序存取是一种读写方式，不是存储方式，有别于顺序存储。
】

2、 问题:【2-1-2】顺序表的优点是（ ）。A. 插入操作的时间效率高 B. 适用于各种逻辑结构的存储表示C. 存储密度(存储利用率)高 D. 删除操作的时间效率高
评分规则: 【 选 C。顺序表的存储利用率高，没有任何辅助信息（指针）以指明元素间的逻辑顺序。它可以是某些逻辑结构的存储表示的一部分， 但不是适用于所有的逻辑结构， 例如， 它对于一般二叉树就不适用。
】

3、 问题:【2-1-3】若设一个顺序表的长度为n，那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功的数据平均比较次数为（ ） 。A.n B.NULL C. (n+1)/2 D. (n-1)/2
评分规则: 【 选 C。在长度为 n 的顺序表中，若各元素査找概率相等，则查找成功的平均査找长度为(n+1)/2。
】

4、 问题:【2-1-4】在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（ ）。A.O(n) B.O(1) C. O(n^2) D. O(log2n)
评分规则: 【 选 B。在有n个元素的顺序表的表尾插入一个新元素，可直接在表的第n+1个位置插入，渐进时间复杂度为O(1)。
】

5、 问题:【2-1-5】在长度为n的顺序表中删除一个元素的时间复杂度为（ ）。A.O(1) B.O(log2n) C.O(n) D.O(n^2)
评分规则: 【 本题答案为 C。在长度为n的顺序表中删除一个元素平均需要移动(n-l)/2个元素，对应的时间复杂度为O(n)，该算法的主要时间花在移动元素上。
】

【作业】第2章 线性表 2.2 链式存储结构习题

1、 问题:线性表L在（）情况下适用于采用链式结构实现。A. 需经常修改L中的结点值B.需不断对L进行删除、插入C.L中含有大量的结点D.L中结点结构复杂
评分规则: 【 B
】

2、 问题:单链表的存储密度（）A.大于1B.等于1C.小于1D.不能确定
评分规则: 【 C
】

3、 问题:线性表若采用链式存储结构，要求内存中可用存储单元的地址是（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续的都可以
评分规则: 【 D
】

4、 问题:线性表L=（a1，a2，…，an），下列陈述正确的是（）A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中元素的排列必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继结点
评分规则: 【 D
】

5、 问题:在单链表中，要将S所指结点插入插入到P所指结点之后，其语句应为（）A.S->next=P+1；P->next=S；B.P->next=S；S->next=P-next；C.S->next=P->next；P->next=S->next；D.S->next=P->next；P->next=S；
评分规则: 【 D注意：A选项的描述在链表中要坚决避免 B选项和正确答案之间的区别在于语句的顺序，不能颠倒，会断链。
】

【作业】第6章 树与二叉树 【Exercise】 树与二叉树习题

1、 问题:【Ex-6-1-1】树最合适用来表示（ ）。A.有序数据元素 B.元素之间具有分支层次关系的数据 C.无序数据元素 D.元素之间无联系的数据
评分规则: 【 选B。树是层次结构，它适合于存储具有分支层次结构的数据集合。
】

2、 问题:【Ex-6-1-2】在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（ ）。A.5 B.6 C.7 D.8
评分规则: 【 选B。该结点处于第3层，从叶结点向上处于第4层，算来至少有6层。
】

3、 问题:【Ex-6-1-3】设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（ ）。A.n=h+m B.h+m=2n C.m=h-1 D.n=2^h -1
评分规则: 【 选 D。高度为h的满二叉树有2^h-1个结点,m个叶结点是干扰条件。
】

4、 问题:【Ex-6-1-4】具有33个结点的完全二叉树的深度为（1），有（2）个叶结点，有（3）个度为1的结点。（1）A.5 B.6 C.7 D.8（2）A.14 B.15 C.16 D.17（3）A.0 B.1 C.12 D.16
评分规则: 【 （1）选B（2）选D（3）选A。根据二叉树的性质n0=n2+l。因此，n0+n2是一个奇数，按照题意，完全二叉树有33个结点，因此在该树中，没有度为1的结点，只有度为0和度为2的结点。设二叉树的结点总数为n,则有n=n0+n2=2n0-1=33,n0=17,n2=16。该完全二叉树的深度为d=[log2(n+l)]=log234=6
】

5、 问题:【Ex-6-1-5】一颗有124个叶子结点的完全二叉树最多有（ ）个结点。A.247 B.248 C.249 D.250
评分规则: 【 选B。根据n0=n2+l的性质，当n0=124时，n2=123,此完全二叉树最多可有124+123+1=248个结点。
】

6、 问题:【Ex-6-1-6】某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ）。A.空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数
评分规则: 【 二叉树的先序遍历序列是DLR，后序遍历序列LRD，要使DLR=DRL，则L为空或R为空，这样的二叉树每层只有一个结点，即高度等于其结点数。本题答案为D。
】

7、 问题:【Ex-6-2】试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
评分规则: 【 【解答】： 含三个结点的树只有两种形态：（1）和（2）；而含3个结点的二叉树可能有下列5种形态：（一），（二），（三），（四），（五）。
】

8、 问题:【Ex-6-3】已知一棵完全二叉树的第6层（设根结点为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是多少？最少是多少？
评分规则: 【 【解答】：完全二叉树的叶子结点只能在最下面两层，这样最多的结点个数=63+48=111。结点最少的情况是第6层为最下层，即1~5层构成一棵满二叉树，其结点总数为25-1=31,再加上第6层的结点，总计31+8=39。这样最少的结点个数为39。
】

9、 问题:【Ex-6-5】给定5个字符a～f，它们的权值集合W={2，3，4，7，8，9}，试构造关于W的一棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。
评分规则: 【 由权值集合W构建的哈夫曼树如下图所示。其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。各个字符的哈夫曼树编码：a：1110，b：1111，c：110，d：00，e：01，f：10。
】

10、 问题:【Ex-6-7】假设二叉树中每个结点值为单个字符， 采用二叉链存储结构存储。下面算法的功能是：计算一棵给定二叉树 b 中的所有单分支结点个数。请在空白处填入正确的语句。int SSonNodes(BiTNode *b)
{
int num1, num2, n;
if (_①_)
return 0;
else if (__②_||
(b->lchild != NULL && b->rchild == NULL))
_③; //为单分支结点
else
n = 0; //其他结点
num1 = _④_; //递归求左子树中单分支结点数
num2 = SSonNodes(b->rchild); //递归求右子树中单分支结点数
return _⑤__;
}
评分规则: 【 1 b == NULL2 (b->lchild == NULL && b->rchild != NULL)3 n = 14 SSonNodes(b->lchild)5 num1 + num2 + n
】

【作业】第7章 图 【Exercise】 图习题

1、 问题:【Ex-7-1-1】在无向图中定义顶点的度为与它相关联的（ 1 ）的数目，所有顶点的度数之和等于所有边数的（ 2 ）倍。(1) A．顶点 B．边 C．权 D．权值(2) A． 3 B． 2 C． 1 D． 1/2
评分规则: 【 【解析】 (1) 选 B， (2) 选 B。根据定义，一个顶点的度为与该顶点相关联的边的数目。 对于无向图， 顶点 vi 到顶点 vj 的边与顶点 vj 到顶点 vi 的边是同一条边（不考虑重边），计算顶点度数之和时每条边被统计了两次，无向图所有顶点的度数之和为边数的 2 倍。
】

2、 问题:【Ex-7-1-2】具有 n 个顶点且每一对不同的顶点之间都有一条边的无向图被称为（ ）。A．无向完全图 B．无向连通图 C．无向强连通图 D．无向树图
评分规则: 【 【解析】选 A。每一对不同顶点之间都有边关联，这种无向图称为无向完全图。它是无向连通图的特殊情形。强连通图是针对有向图的，没有无向强连通图这一说法。树是极小连通图。
】

3、 问题:【Ex-7-1-3】一个有 n 个顶点的无向图最多有（ ）边。A．n B．n(n-1) C．n(n-1)/2 D．2n
评分规则: 【 【解析】选 C。无向完全图在每一对顶点之间都有边，图中的边数达到最大，就是说，图中每一顶点有 n-1 条边与其他顶点相连，总共n个顶点，去掉重复的，有 n(n-1)/2条边。
】

4、 问题:【Ex-7-1-4】具有 6 个顶点的无向图至少应有（ ）条边才能确保是一个连通图。A．5 B．6 C．7 D．8
评分规则: 【 【解析】选 A。有 n 个顶点的连通图，至少需要 n-1 条边才能保持图的连通。多一条将形成回路，少一条将变成非连通图。当 n = 6 时， n-1 = 5。
】

5、 问题:【Ex-7-1-5】设 G 是一个非连通无向图，有 15 条边，则该图至少有（ ）个顶点。A．5 B．6 C．7 D．8
评分规则: 【 【解析】选 C。设无向图有 n 个顶点，它的边数 e≤n(n-1)/2，若 e = 15，有15≤n(n-1)/2，解得n≥6。在连通图情形至少需有 6 个顶点，在非连通图情形至少需有7 个顶点。
】

6、 问题:【Ex-7-1-6】下列关于无向连通图特性的叙述中，正确的是（ ）。I. 所有顶点的度之和为偶数II. 边数大于顶点个数减 1III. 至少有一个顶点的度为 1A．只有 I B．只有II C．I和II D．I和III
评分规则: 【 【解析】选 A。无向连通图所有顶点度之和为边数的 2 倍，所以一定是偶数。在无向连通图中边数最少可以等于顶点个数减 1（生成树），所以，II 不完全对；而 III 是干扰项，根本不对，例如，若有 n 个顶点和 n-1 条边构成一个环，它可以是连通的但所有顶点的度均为 2。
】

7、 问题:【Ex-7-1-7】图的简单路径是指（ ）不重复的路径。A．权值 B．顶点 C．边 D．边与顶点均
评分规则: 【 【解析】选 B。图的路径是指图的一个顶点序列，由这些顶点构成的边属于图的边集合。而图的简单路径是指没有重复顶点的路径，所以选 B。在定义简单路径时边可以重复也可以不重复。边不重复的路径是一笔划路径。
】

8、 问题:【Ex-7-1-8】对于具有 n（ n＞1）个顶点的强连通图，其有向边条数至少是（ ）。A．n+l B．n C．n-1 D．n-2
评分规则: 【 【解析】选 B。当所有 n 个顶点都在某一个有向环（有向回路）上时，形成一个强连通图，其有向边条数为 n，例外情况是 n = 1 时，至少可以有 0 条有向边。在此情况下，当有向边的条数少于 n 则不能构成环，不再是强连通图。
】

9、 问题:【Ex-7-1-9】在一个具有 n 个顶点的有向图中，若所有顶点的出度之和为 s，则所有顶点的入度之和为（ ）。A．s B．s-1 C．s+1 D．n
评分规则: 【 【解析】选 A。有向图中的每一条边都有一个始顶点和一个终顶点，在有向图中所有顶点的出度之和应等于入度之和。
】

10、 问题:【Ex-7-1-10】在下列有关图的说法中正确的是（ ）。A．在图结构中，顶点可以没有任何前驱和后继。B．具有 n 个顶点的无向图最多有 n(n-1)条边，最少有 n-1 条边。C．在无向图中，边的条数是结点度数之和。D．在有向图中，各顶点的入度之和等于各顶点的出度之和。
评分规则: 【 【解析】选 D。在有向图中，每条边是一个顶点的出边，另一个顶点的入边，设图中有 e 条边，所有顶点出度之和等于所有顶点的出边数（ = e），所有顶点入度之和等于所有顶点的入边数（ =e）。其他选项都是错误的。例如，在有向图中由于有向边的存在，故有前驱和后继之分。此外，具有 n 个顶点的无向图最少可以有 0 条边，只有在连通图的情形下最少是 n-1 条边。而在无向图中，所有顶点度数之和是边的条数的 2 倍。
】

11、 问题:【Ex-7-1-11】对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接矩阵表示，则该矩阵大小是（ 1 ），矩阵中的非零元素个数是（ 2 ）。(1) A．n B．(n-1)^2 C．n-1 D．n^2(2) A．e B．2e C. e^2 D．n^2
评分规则: 【 【解析】 (1) 选 D， (2) 选 B。有 n 个顶点的图的邻接矩阵记录了每一对顶点之间的关系，有 n2 个矩阵元素，其中有 2e 个非零元素用以表示无向图的 e 条边。
】

12、 问题:【Ex-7-1-12】无向图的邻接矩阵是一个（ ）。A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵
评分规则: 【 【解析】选 A。无向图的邻接矩阵是一个对称矩阵，对于同一条边(vi, vj)，它是双向的，故在矩阵的第 i 行第 j 列，以及第 j 行第 i 列都为 1。
】

13、 问题:【Ex-7-1-13】有 n 个顶点和 e 条边的无向图采用邻接矩阵存储，零元素的个数为（ ）。A．e B．2e C．n^2-e D．n^2-2e
评分规则: 【 【解析】选 D。无向图的邻接矩阵共有 n^2 个元素，每条边在邻接矩阵中以主对角线为界，对角线上、下各有一个元素表示它，即非零元素的个数为2e，则零元素的个数为n^2-2e。
】