智慧树知到《算法与数据结构（山东联盟）》章节测试答案

智慧树知到《算法与数据结构（山东联盟）》章节测试答案
绪论单元测试
1、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。
A.结构
B.关系
C.运算
D.算法
正确答案：关系
2、算法的描述形式包括
A.N-S图
B.流程图
C.自然语言
D.类程序设计语言
正确答案：N-S图；流程图；自然语言；类程序设计语言
3、算法的特征包括有穷性、确定性、可行性和输入输出。
A.正确
B.错误
正确答案：正确
4、对算法的描述包括程序形式和描述形式。
A.正确
B.错误
正确答案：正确
5、描述形式是算法的最终形式。
A.正确
B.错误
正确答案：错误
6、“数据结构”是介于（）、（）和（）三者之间的一门核心课程。
A.语句
B.计算机软件
C.数学
D.计算机硬件
正确答案：计算机软件；数学；计算机硬件
7、著名计算机科学家沃思教授提出的公式：； 程序 = （） + （），也说明了数据结构的重要性。
A.算法
B.编程环境
C.数据结构
D.语法
正确答案：算法；数据结构
8、描述非数值计算问题的数学模型不再是数学方程，而是数据结构（）。
A.集合
B.图
C.表
D.树
正确答案：集合；图；表；树
9、数据结构是一门研究（）程序设计问题中计算机的（）以及它们之间的（）和（）等的学科。
A.非数值计算
B.操作对象
C.操作
D.关系
正确答案：非数值计算；操作对象；操作；关系
10、顺序存储结构：借助元素在存储器中的（）来表示数据元素间的逻辑关系。
A.结构
B.相对位置
C.地址
D.数值
正确答案：相对位置
第一章单元测试
1、（）是一种最简单的线性结构。
A.集合
B.图
C.树
D.线性表
正确答案：线性表
2、（）线性表的数据元素可以由所描述对象的各种特征的数据项组成。
A.有序存储
B.链式存储
C.散列存储
D.顺序存储
正确答案：链式存储
3、已知单向链表中指针p指向结点A，（）表示删除A的后继结点（若存在）的链操作（不考虑回收）。
A.p（）>；next=p
B.p=p（）>；next
C.p=p（）>；next（）>；next
D.p（）>；next=p（）>；next（）>；next
正确答案：p（）>；next=p（）>；next（）>；next
4、已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是（）。
A.s->；next=NULL， last->；next=s，last=s
B.last->；next=s，s->；next=NULL，last=s
C.last->；next=s，last=s，last->；next=NULL
D.s->；next=NULL， last->；next=s， s=last
正确答案：s->；next=NULL， last->；next=s， s=last
5、已知h是指向单向加头链表的首指针，删除表头结点的操作是（）。
A.free（h->；next）；h=h->；next
B.p=h，h=p->；next；free（p）
C.p=h->；next；free（p）；h=h->；next
D.p=h->；next，h->；next=p->；next；free（p）
正确答案：p=h->；next，h->；next=p->；next；free（p）
6、有N个元素组成的线性表，我们说此线性表的长度为（）
A.n-1
B.n+1
C.0
D.n
正确答案：n
7、对线性表中的数据元素进行（）和（）等操作，实现表的长度的增长或缩短。
A.插入
B.删除
C.遍历
D.访问
正确答案：插入；删除
8、线性表的抽象数据类型定义
A.基本操作
B.函数关系
C.数据关系
D.数据对象
正确答案：基本操作；数据关系；数据对象
9、我们使用（），实现线性表的顺序存储。
A.数值
B.数组
C.语句
D.函数
正确答案：数组
10、线性表的基本操作是用C语言中的（）对其进行表示的。
A.循环语句
B.条件语句
C.函数
D.结构体
正确答案：函数
11、在链表中第i；个结点之前插入新的元素；e ，表的逻辑结构不变。
A.正确
B.错误
正确答案：错误
12、在单链表中插入结点只需要（）。但同时，若要在第（）个结点之前插入元素，修改的是第（）个结点的指针。
A.i
B.i+1
C.修改指针
D.i-1
正确答案：i；修改指针；i-1
13、单链表和线性表中所有基本操作相同，且编程实现方法相同。
A.正确
B.错误
正确答案：错误
14、数字钟程序中使用的时间，可以是系统时间。
A.正确
B.错误
正确答案：正确
15、和单链表的差别仅在于，判别链表中最后一个结点的条件不再是（），而是（）。
A.“前继是否为空”
B.“后继是否为头结点”
C.“后继是否为空”
D.“前继是否为头结点”
正确答案：“后继是否为头结点”；“后继是否为空”
16、双向链表的“删除”；时需要同时修改两个方向上的指针，改变结点之间的逻辑关系。
A.正确
B.错误
正确答案：正确
17、双向链表的“插入”；时不需要同时修改两个方向上的指针，改变结点之间的逻辑关系。
A.正确
B.错误
正确答案：错误
18、双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）
A.p->；next->；prior=p
B.p->；next；=p->；prior
C.p=p->；prior->；next
D.p=p->；next
正确答案：p->；next->；prior=p；p=p->；prior->；next
19、双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）
A.p=p->；prior
B.p->；prior=p->；next
C.p->；next=p；->；prior
D.p->；next->；prior=p
正确答案：p->；next->；prior=p
20、双向链表需要在结点中设两个指针域（）
A.prior指针域
B.parent指针域
C.next指针域
D.数据域
正确答案：prior指针域；next指针域
第二章单元测试
1、队列是一种（）的线性表。
A.先进先出
B.只能插入
C.先进后出
D.只能删除
正确答案：先进先出
2、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。
A.s->；next=front；front=s
B.s->；next=rear；rear=s
C.rear->；next=s；rear=s
D.front->；next=s；front=s
正确答案：rear->；next=s；rear=s
3、栈操作数据的原则是（）。
A.后进先出
B.先进先出
C.不分顺序
D.后进后出
正确答案：后进先出
4、栈与队列是一种特殊操作的线性表（）。
A.正确
B.错误
正确答案：正确
5、和链栈类似，用单链表来实现链队。根据队的先入先出（FIFO）原则，为了操作上的方便，使用一个（）和（）。
A.数据域
B.指针域
C.头指针
D.尾指针
正确答案：头指针；尾指针
6、队列的顺序存储结构用C语言中（）数据类型实现。
A.二维数组实现
B.结构体
C.一维数组实现
D.枚举型
正确答案：一维数组实现
7、栈和队列不能进行再分配了。
A.正确
B.错误
正确答案：错误
8、队列允许在表的一端进行插入操作和删除操作。
A.正确
B.错误
正确答案：错误
9、入栈需要修改地址指针。
A.正确
B.错误
正确答案：正确
10、链栈主要的运算，如插入、删除是在栈顶执行的。链表的头部作栈顶是最方便的，需要像单链表那样为了运算方便附加一个头结点。
A.正确
B.错误
正确答案：错误
11、链栈的结点结构与单链表的结点结构相同，由（）和（）组成。
A.数据域；指针域
B.指针域；双亲域
C.双亲域
D.孩子域；指针域
正确答案：数据域；指针域
12、构造一个空栈S；时，不需要用动态存储空间分配函数。
A.正确
B.错误
正确答案：错误
13、顺序栈中数据元素与栈顶指针的变化：非空栈中的栈顶指针top始终在的（）下一个位置
A.栈中任意元素
B.栈中元素
C.栈底元素
D.栈顶元素
正确答案：栈顶元素
14、在初始化空顺序栈时一般不限定栈的最大容量，因为，栈在使用过程中所需最大空间的大小很难估计。
A.正确
B.错误
正确答案：正确
15、利用（）的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。
A.一组地址不连续
B.一组地址连续
C.一组地址断开
D.一组地址相同
正确答案：一组地址连续
第三章单元测试
1、串（即字符串）是一种特殊的线性表，它的数据元素是（）。
A.单个字符
B.图
C.表
D.数字
正确答案：单个字符
2、包含零个字符（n=0）的串称为空串，通常记为Ф，其长度为零；空串是任意串的子串。
A.正确
B.错误
正确答案：正确
3、空串与空格串相同。
A.正确
B.错误
正确答案：错误
4、串比较是按字符的ASCII值比较的，而不是按串的长度比较的。；StrCompare（'；data'；， '；structures'；）（）； 0。
A.等于
B.大于
C.小于等于
D.小于
正确答案：小于
5、SubString（sub， '；commander'；， 1， 9）； 求得； sub = '（）'。
A.commanr
B.commander
C.coander
D.comander
正确答案：commander
6、串的基本操作中，操作对象大多为“串的整体”。
A.正确
B.错误
正确答案：正确
7、在串的表示和实现过程中，用一组地址不连续的存储单元存储串值中的字符序列，称为串的定长顺序存储方式。
A.正确
B.错误
正确答案：错误
8、在顺序串中，用一个指针来指向最后一个字符，C语言的表示如下：typedef struct{； char； data[MAXSIZE]； int； curlen；} SeqString；请定义一个串变量：
A.SeqString s
B.SqString s
C.structg s
D.typedef struct s
正确答案：SeqString s
9、在C语言中，存在一个称为“堆”的自由存储区，并由C语言的动态分配函数（）来管理。
A.free（）
B.malloc（）和free（）
C.main（）
D.malloc（）
正确答案：malloc（）和free（）
10、堆分配存储结构的串有顺序存储结构的特点，在操作中对串长又没有任何限制，因而在串处理的应用程序中常被选用。
A.正确
B.错误
正确答案：正确
第四章单元测试
1、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
A.2i+1
B.2i-1
C.i/2
D.2i
正确答案：2i
2、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
A.高度等于其结点数
B.任一结点无右孩子
C.空或只有一个结点
D.任一结点无左孩子
正确答案：任一结点无右孩子
3、二叉树的第k层的结点数最多为（）
A.2K-1
B.2的k-1次幂
C.2的k次幂-1
D.2K+1
正确答案：2的k-1次幂
4、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列
为（）。
A.BCDA
B.CDAB
C.BADC
D.CBDA
正确答案：BADC
5、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）
A.正确
B.错误
正确答案：正确
6、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）
A.正确
B.错误
正确答案：错误
7、深度为k的完全二叉树中最少有（）个结点。
A.2k-1
B.2k-1-1
C.2k-1+1
正确答案：2k-1
8、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
A.N0=N2+1
B.N0=N1+1
C.N0=Nl+N2
D.N0=2N1+l
正确答案：N0=N2+1
9、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
A.任一结点无左孩子
B.高度等于其结点数
C.空或只有一个结点
D.任一结点无右孩子
正确答案：任一结点无右孩子
10、树的带权路径长度定义为，树中所有叶子结点的带权路径长度之和（对所有叶子结点）。（）
A.正确
B.错误
正确答案：正确
第五章单元测试
1、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
A.n（n-1）
B.n
C.n/2
D.2n
正确答案：n
2、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
A.第i行0元素的个数之和
B.第i列非0或非∞元素的个数之和
C.第i行非0或非∞元素的个数之和
D.第i列0元素的个数之和
正确答案：第i列非0或非∞元素的个数之和
3、设某完全无向图中有n个顶点，则该完全无向图中有（）条边
A.n的2次幂-1
B.n（n-1）/2
C.n（n-1）
D.n的2次幂
正确答案：n（n-1）/2
4、子串“ABC”在主串“AABCABCD”中的位置为2。（）
A.正确
B.错误
正确答案：正确
5、对链表进行插入和删除操作时不必移动链表中结点。（）
A.正确
B.错误
正确答案：正确
6、深度为k的完全二叉树中最少有（）个结点。
A.2k-1+1
B.2k-1-1
C.2k-1
正确答案：2k-1
7、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
A.N0=Nl+N2
B.N0=2N1+l
C.N0=N2+1
D.N0=N1+1
正确答案：N0=N2+1
8、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
A.第i列0元素的个数之和
B.第i行非0或非∞元素的个数之和
C.第i列非0或非∞元素的个数之和
D.第i行0元素的个数之和
正确答案：第i列非0或非∞元素的个数之和
9、简单回路就是回路。
A.正确
B.错误
正确答案：错误
10、图中任两点有路径相通，该图称为连通图（）。
A.正确
B.错误
正确答案：正确
第六章单元测试
1、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。
A.冒泡排序
B.快速排序
C.堆排序
D.希尔排序
正确答案：堆排序
2、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。
A.45
B.40
C.20
D.30
正确答案：45
3、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）
A.20
B.30
C.40
D.45
正确答案：45
4、连通图的最小生成树的边上的权值之和是唯一的。（）
A.正确
B.错误
正确答案：正确
5、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
A.n（n-1）
B.n/2
C.n
D.2n
正确答案：n
6、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
A.第i行非0或非∞元素的个数之和
B.第i列0元素的个数之和
C.第i列非0或非∞元素的个数之和
D.第i行0元素的个数之和
正确答案：第i列非0或非∞元素的个数之和
7、以数据集{1，3，5，7}为叶结点的权值，构造一棵哈夫曼树，求出带权路径长度WPL（）。
A.29
B.30
C.28
D.26
正确答案：29
8、设某完全无向图中有n个顶点，则该完全无向图中有（）条边
A.n（n-1）
B.n的2次幂-1
C.n的2次幂
D.n（n-1）/2
正确答案：n（n-1）/2
9、查找表可分为两类（）
A.动态查找表
B.静态查找表
C.顺序查找表
D.起泡查找表
正确答案：动态查找表；静态查找表
10、使用折半方法进行查找的表是一个有序表。
A.正确
B.错误
正确答案：正确
第七章单元测试
1、执行一趟快速排序能够得到的序列是（）。
A.[63，12，34，45，27] 55 [41，72]
B.[45，34，12，41] 55 [72，63，27]
C.[41，12，34，45，27] 55 [72，63]
D.[12，27，45，41] 55 [34，63，72]
正确答案：[41，12，34，45，27] 55 [72，63]
2、排序分稳定排序和不稳定排序。（）
A.正确
B.错误
正确答案：正确
3、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）
A.45
B.20
C.40
D.30
正确答案：45
4、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）
A.正确
B.错误
正确答案：正确
5、设一组初始记录关键字序列为（45，80，55，40，42，85），则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。
A.42，40，45，85，55，80
B.42，40，45，80，85，88
C.42，40，45，55，80，85
D.40，42，45，55，80，83
正确答案：42，40，45，55，80，85
6、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，80，20，85，40，70，36
B.15，25，35，50，80，20，36，40，70，85
C.15，25，35，50，80，85，20，36，40，70
D.15，25，35，50，20，40，80，85，36，70
正确答案：15，25，35，50，20，40，80，85，36，70
7、设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。
A.15，40，60，20
B.45，40，15，20
C.15，20，40，45
D.40，50，20，95
正确答案：15，40，60，20
8、执行一趟快速排序能够得到的序列是（）。
A.[45，34，12，41] 55 [72，63，27]
B.[63，12，34，45，27] 55 [41，72]
C.[41，12，34，45，27] 55 [72，63]
正确答案：[41，12，34，45，27] 55 [72，63]
9、队列的顺序存储结构用C语言中（）数据类型实现。
A.二维数组实现
B.枚举型
C.一维数组实现
D.结构体
正确答案：一维数组实现
10、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。
A.堆排序
B.冒泡排序
C.希尔排序
D.快速排序
正确答案：堆排序