智慧树知到《数据结构（西安理工大学）》章节测试答案

智慧树知到《数据结构（西安理工大学）》章节测试答案
第一章单元测试
1、研究数据结构就是研究（）。
A.数据的逻辑结构和存储结构
B.数据的逻辑结构、存储结构及其数据在运算上的实现
C.数据的逻辑结构
D.数据的存储结构
正确答案：数据的逻辑结构、存储结构及其数据在运算上的实现
2、关于算法的说法，错误的是（）。
A.为解决某问题的算法和为该问题编写的程序含义是相同的
B.其他三项都是错误的
C.算法最终必须由计算机程序实现
D.算法的可行性是指指令不能有二义性
正确答案：其他三项都是错误的
3、数据的（）包括集合、线性、树和图4种基本类型。
A.存储结构
B.算法描述
C.基本运算
D.逻辑结构
正确答案：逻辑结构
4、数据的存储结构包括顺序、链式、散列和（）4种基本类型。
A.数组
B.集合
C.索引
D.向量
正确答案：索引
5、下面算法的时间复杂度为（）。for（i=0；i<；m；i++） for（j=0；j<；n；j++） ；A[i][j]=i*j。
A.O（n2）
B.O（m2）
C.O（m×n）
D.O（m+n）
正确答案：O（m×n）
6、以下（）属于设计一个“好”的算法应考虑达到的目标。
A.健壮性
B.正确性
C.可读性
D.效率与低存储量要求
正确答案：健壮性；正确性；可读性；效率与低存储量要求
7、依据所有数据成员之间的逻辑关系的不同，数据结构分为（）。
A.物理结构
B.逻辑结构
C.非线性结构
D.线性结构
正确答案：非线性结构；线性结构
8、在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储数据元素之间的关系。
A.正确
B.错误
正确答案：正确
9、在逻辑结构定义的操作与具体实现有关。
A.正确
B.错误
正确答案：错误
10、算法是对解题方法和步骤的描述。
A.正确
B.错误
正确答案：正确
11、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
A.正确
B.错误
正确答案：正确
第二章单元测试
1、线性表是（）。
A.一个有限序列，可以为空。
B.一个有限序列，不能为空。
C.一个无限序列，不能为空。
D.一个无限序列，可以为空。
正确答案：一个有限序列，可以为空。
2、若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（）存储方法最节省时间。
A.单链表
B.循环链表
C.双向链表
D.顺序表
正确答案：顺序表
3、单链表中，增加一个头结点的目的是为了（）。
A.方便运算的实现
B.说明单链表是线性表的链式存储
C.标识表结点中首结点的位置
D.使单链表至少有一个结点
正确答案：方便运算的实现
4、在带有头结点的单链表Head中，要向表头插入一个由指针p指向的结点，则执行（）。
A.p->；next=Head->；next；Head->；next=p
B.Head=p；p->；next=Head
C.p->；next=Head；Head=p
D.p->；next=Head；p=Head
正确答案：p->；next=Head->；next；Head->；next=p
5、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。
A.访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.将n个元素从小到大排序
C.删除第i个元素（1≤i≤n）
D.在第i个元素后插入一个新结点（1≤i≤n）
正确答案：访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
6、下列说法正确的有（）。
A.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数相等
B.数据的逻辑结构与数据元素本身的内容和形式无关
C.从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构
D.所谓数据的逻辑结构是指数据元素之间的逻辑关系
E.算法和程序原则上没有区别，在讨论数据结构时二者通用
正确答案：数据的逻辑结构与数据元素本身的内容和形式无关；从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构；所谓数据的逻辑结构是指数据元素之间的逻辑关系
7、线性表的逻辑顺序和存储顺序总是一致的。
A.正确
B.错误
正确答案：错误
8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
A.正确
B.错误
正确答案：正确
9、顺序存储结构只能存储线性结构，链式存储结构只能存储非线性结构。
A.正确
B.错误
正确答案：错误
10、线性表的链式存储结构优于顺序存储结构。
A.正确
B.错误
正确答案：错误
11、链式存储方式以指针表示元素间的逻辑关系。
A.正确
B.错误
正确答案：正确
第三章单元测试
1、在顺序栈空的情况下不能进行出栈操作，否则将产生“下溢”。
A.正确
B.错误
正确答案：正确
2、栈和队列都是限制存取位置的线性表。
A.正确
B.错误
正确答案：正确
3、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，则不可能得到出栈序列：a，f，e，d，c，b。
A.正确
B.错误
正确答案：错误
4、入栈操作和入队列操作在链式存储结构上实现时一般不需要考虑栈溢出的情况。
A.正确
B.错误
正确答案：正确
5、同一个栈内的各个数据元素类型可以不一致。
A.正确
B.错误
正确答案：错误
6、以下说法中正确的是（）
A.队列被称为“先进后出”表。
B.栈是一种只允许在一端进行插入和删除的线性表。
C.当队列中无数据元素时，称空队列。
D.栈是一种操作不受限制的线性表。
正确答案：栈是一种只允许在一端进行插入和删除的线性表。；当队列中无数据元素时，称空队列。
7、以下说法中错误的是（）。
A.利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。
B.栈不能对输入序列部分或全局求逆。
C.当top等于数组最大下标时则栈满。
D.top=-1时为空栈，元素进栈时指针top不断减1。
正确答案：栈不能对输入序列部分或全局求逆。；top=-1时为空栈，元素进栈时指针top不断减1。
8、已知一个栈的进栈序列是a1，a2，a3....an.其输出序列为1，2，3...n，若a3=1则a1为（）
A.可能是2
B.可能是3
C.不可能是2
D.一定是2
E.不可能是3
正确答案：可能是3；不可能是2；一定是2
9、栈的特点是（）
A.先进后出
B.进优于出
C.先进先出
D.出优于进
正确答案：先进后出
10、设循环队列的容量为20，序号从0到19，经过一系列的入队和出队后，front=5，rear=10，问队列中有多少个元素（采用节省一个队列存储空间的方式）。
A.7
B.6
C.5
D.4
正确答案：5
11、一个队列的入队序列是1，2，3，4，则队列的出队序列是（）
A.1，4，3，2
B.4，3，2，1
C.1，2，3，4
D.3，2，4，1
正确答案：1，2，3，4
12、一般情况下，将递归算法转换成等价的非递归算法应该设置（）
A.栈
B.栈或队列
C.队列
D.数组
正确答案：栈
13、设用链表作为栈的存储结构则退栈操作（）
A.必须判别栈是否为满
B.对栈不作任何判别
C.判别栈元素的类型
D.必须判别栈是否为空
正确答案：必须判别栈是否为空
第四章单元测试
1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。
A.正确
B.错误
正确答案：正确
2、空串与空格串是相同的。
A.正确
B.错误
正确答案：错误
3、串的长度是指串中不同字符的个数。
A.正确
B.错误
正确答案：错误
4、设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。
A.正确
B.错误
正确答案：正确
5、设模式串（子串）的长度为m，目标串（主串）的长度为n。当n≈m且处理只匹配一次的模式时，简单模式匹配（BF）算法所花费的时间代价也可能会比KMP算法更节省。
A.正确
B.错误
正确答案：正确
6、串是一种特殊的线性表，下列不能体现其特殊性的是（）
A.数据元素是字符型数据
B.可以链接存储
C.可以顺序存储
D.数据元素可以是非字符数据
正确答案：可以链接存储；可以顺序存储；数据元素可以是非字符数据
7、以下说法中错误的是（）
A.串的长度必须大于零
B.串中的元素只能是字母
C.空串就是空白串
D.串是一种特殊的线性表
正确答案：串的长度必须大于零；串中的元素只能是字母；空串就是空白串
8、两个串相等必须有（）
A.串中的各位置字符任意
B.串中各位置字符均对应相等
C.串长度任意
D.串长度相等
E.串长度不相等
正确答案：串中各位置字符均对应相等；串长度相等
9、若串S=”software”，其子串的数目是（）
A.36
B.37
C.9
D.8
正确答案：37
10、下面（）不是 “abcd321ABCD”的子串（）
A.abcAB
B.321AB
C.abcd
D.21AB
正确答案：abcAB
11、已知模式串为“aaab”，其next数组值为（）
A.0，1，2，0
B.-1，1，0，0
C.0，0，1，2
D.-1，0，1，2
正确答案：-1，0，1，2
12、设主串为“abccdcdccdbaa”，模式串为“cdcc”，用BF算法在第（）次匹配成功。
A.4
B.6
C.7
D.5
正确答案：6
13、设串s1=“ABCDEFG”，s2=“12345”，用字符数组从0下标位置存储，函数strcat（s， t）返回s和t串的连接串，strsub（s， i， j）返回串s中从第i个字符开始的连续j个字符组成的子串，strlen（s）返回串s的长度，则strcat（strsub（s1， 2， strlen（s2））， strsub（s1， strlen（s2），2））的结果是（）
A.CDEFG12
B.CD12345
C.CDEFGFG
D.BCDEFG1
正确答案：CDEFGFG
第五章单元测试
1、稀疏矩阵压缩存储后，必会失去随机存取功能。
A.正确
B.错误
正确答案：正确
2、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
A.正确
B.错误
正确答案：错误
3、数组的存储结构是一组连续的内存单元。
A.正确
B.错误
正确答案：正确
4、广义表中原子个数即为广义表的长度。
A.正确
B.错误
正确答案：错误
5、广义表中元素的个数即为广义表的深度。
A.正确
B.错误
正确答案：错误
6、广义表（（a），（a））的表头和表尾是（）
A.（a）
B.b
C.a
D.（（a））
正确答案：（a）；（（a））
7、以下属于特殊矩阵的是（）
A.对角矩阵
B.上三角矩阵
C.对称矩阵
D.下三角矩阵
正确答案：对角矩阵；上三角矩阵；对称矩阵；下三角矩阵
8、以下不属于数组操作的是（）
A.查找
B.删除
C.插入
D.修改
E.存取
正确答案：删除；插入
9、对行下标由1到50、列下标由1到80的二维数组a，若该数组的起始地址为2000且每个元素占2个存储单元，并以行为主序顺序存储，则元素a[45][68]的存储地址为（）
A.9174
B.9175
C.9173
D.9172
正确答案：9174
10、在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）
A.非零元素个数
B.列号
C.行号
D.元素值
正确答案：行号
11、设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）
A.28
B.19
C.55
D.10
正确答案：19
12、设二维数组A[0~m][0~n]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则a[i][j]的地址为（）
A.p +（i*n+j）*k
B.p +（（j-1）*n+i-1）*k
C.p +（（i-1）*n+j-1）*k
D.p +（j*n+i-1）*k
正确答案：p +（i*n+j）*k
13、下面说法不正确的是（）
A.广义表难以用顺序结构存储
B.广义表的表尾总是一个广义表
C.广义表可以是一个多层次结构
D.广义表的表头总是一个广义表
正确答案：广义表的表头总是一个广义表
第六章单元测试
1、 一棵完全二叉树上有1001个结点，其叶子结点的个数是（）。
A.250
B.A～C都不对
C.505
D.500
正确答案：A～C都不对
2、一棵有124个叶结点的完全二叉树最多有（）个结点。
A.250
B.249
C.248
D.247
正确答案：248
3、在n个结点的线索二叉树中，线索的数目为（）
A.n+1
B.2n
C.n-1
D.n
正确答案：n+1
4、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。
A.13
B.26
C.25
D.12
正确答案：25
5、树的基本遍历策略可分为先根遍历和后根遍历，而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则（）是正确的。
A.树的后根遍历与其对应的二叉树后序遍历序列相同
B.树的先根遍历与其对应的二叉树先序遍历序列相同
C.树的先根遍历与其对应的二叉树中序遍历序列相同
正确答案：树的先根遍历与其对应的二叉树先序遍历序列相同
6、完全二叉树（）。
A.适合于顺序存储结构存储
B.某些结点有左子树时则必有右子树
C.叶子结点可在任一层出现
D.不一定适合顺序存储结构存储
E.某些结点有右子树时则必有左子树
正确答案：适合于顺序存储结构存储；某些结点有右子树时则必有左子树
7、对于二叉树，下列描述正确的是（）
A.高度为k的二叉树结点数最多时一定是满二叉树
B.第k层上最多有2k-1个结点
C.边的个数比结点个数少1个
D.一定有度数为1的结点
E.叶子结点数目比度数为2的结点数目多1个
F.n个结点共有n-1个非空指针域
正确答案：高度为k的二叉树结点数最多时一定是满二叉树；边的个数比结点个数少1个；叶子结点数目比度数为2的结点数目多1个；n个结点共有n-1个非空指针域
8、关于哈夫曼编码的说法正确的是（）
A.编码无二义性
B.两个频度相同的字符其编码长度一定相等
C.WPL最小
D.是一种最佳编码
E.不允许出现频度相同的字符
正确答案：编码无二义性；WPL最小；是一种最佳编码
9、存在这样的二叉树，对它采用任何次序进行遍历得到的结果都相同。
A.正确
B.错误
正确答案：正确
10、二叉树就是结点度为2的有序树。
A.正确
B.错误
正确答案：错误
11、若一个结点是二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。
A.正确
B.错误
正确答案：错误
12、 一棵含有n个结点的完全二叉树，它的高度是⌊log2n⌋+1。
A.正确
B.错误
正确答案：正确
13、线索二叉树的左线索指向其某种遍历序列的直接前驱结点，右线索指向其某种遍历序列的直接后继结点。
A.正确
B.错误
正确答案：正确
第七章单元测试
1、无向图的邻接矩阵是（）矩阵。
A.上三角阵
B.下三角阵
C.对称
D.稀疏矩阵
正确答案：对称
2、用邻接表存储的图所用空间大小（）
A.与边数的平方有关
B.与图的顶点数和边数都有关
C.只与图的顶点数有关与边数的平方有关
D.只与图的边数有关
正确答案：与图的顶点数和边数都有关
3、不论基于图的邻接表还是基于邻接矩阵存储，图的广度优先遍历算法类似于树的（）
A.中序遍历
B.后序遍历
C.层次遍历
D.先序遍历
正确答案：层次遍历
4、一个连通图的生成树是包含该图的所有顶点的（）
A.极大连通子图
B.极小子图
C.极小连通子图
D.极大子图
正确答案：极小连通子图
5、具有n个顶点的连通有向图中，至少需要（）条边。
A.n
B.2n
C.n+1
D.n-1
正确答案：n
6、下列哪些算法是属于图的应用算法（）
A.拓扑排序算法
B.克鲁斯卡尔（Kruskal）算法
C.欧几里德算法
D.哈夫曼（Huffman）算法
E.迪杰斯特拉（Dijkstra）算法
正确答案：拓扑排序算法；克鲁斯卡尔（Kruskal）算法；迪杰斯特拉（Dijkstra）算法
7、下列（）算法可用于构造图的生成树。
A.Floyd
B.Prim
C.BFS
D.kruskal
E.DFS
正确答案：Prim；BFS；kruskal；DFS
8、下列（）是构造最短路径的方法。
A.Prim
B.Floyd
C.Dijkstra
D.Kruskal
E.BFS
正确答案：Floyd；Dijkstra
9、n个结点的无向图，若没有顶点到自身的边，也没有一个顶点到另一个顶点的多重边，此时若有n（n-1）/2条边 ，则该无向图一定是连通图。
A.正确
B.错误
正确答案：正确
10、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用空间大小与图的顶点数有关，与图的边数无关。
A.正确
B.错误
正确答案：正确
11、对于任意一个图，从它的某个顶点出发进行一次深度或者广度遍历可以访问到该图的每个顶点。
A.正确
B.错误
正确答案：错误
12、对于无向图的生成树，从同一顶点出发所得的生成树相同。
A.正确
B.错误
正确答案：错误
13、有向图顶点v的度是其邻接矩阵中第v行1的个数。
A.正确
B.错误
正确答案：错误
第八章单元测试
1、衡量一个查找算法执行效率高低的最重要的指标是（）。
A.平均查找长度
B.所需的内存大小
C.查找表中的元素个数
D.查找过程中关键字比较的最大次数
正确答案：平均查找长度
2、对线性表进行二分查找时，要求线性表必须（）。
A.采用顺序存储结构
B.采用顺序存储结构且元素按查找关键字有序排列
C.采用链接存储结构且结点按查找关键字有序排列
D.采用链接存储结构
正确答案：采用顺序存储结构且元素按查找关键字有序排列
3、哈希查找中的冲突是指（）。.
A.不同关键字值对应相同的存储地址
B.两个元素的关键字值相同
C.两个元素具有相同序号
D.两个元素的关键字值不同
正确答案：不同关键字值对应相同的存储地址
4、对于一棵二叉排序树进行（）遍历可得到按关键字有序排列的数据序列。
A.中序
B.层序
C.先序
D.后序
正确答案：中序
5、顺序查找适合于采用（）存储结构的线性表。
A.索引
B.顺序或链式
C.散列
D.压缩
正确答案：顺序或链式
6、下面关于哈希查找的说法中，正确的是（）
A.用链地址处理冲突，不会引起二次聚集的现象
B.采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的
C.用链地址处理冲突，适合表长不确定的情况
D.链地址法处理冲突的平均查找长度小于线性探测和二次探测
E.采用链地址法处理冲突时，查找任何一个元素的时间都相同
正确答案：用链地址处理冲突，不会引起二次聚集的现象；采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的；用链地址处理冲突，适合表长不确定的情况；链地址法处理冲突的平均查找长度小于线性探测和二次探测
7、以下关于二叉排序树的说法中，正确的是（）
A.二叉排序树一定为一棵平衡二叉树
B.在二叉排序树上的查找过程与折半查找过程类似
C.二叉排序树中左子树上所有结点的关键字值均小于它的根结点
D.对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列
E.二叉排序树中右子树上所有结点的关键字值均大于它的根结点
正确答案：在二叉排序树上的查找过程与折半查找过程类似；二叉排序树中左子树上所有结点的关键字值均小于它的根结点；对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列；二叉排序树中右子树上所有结点的关键字值均大于它的根结点
8、在一个结点值按照查找关键字有序排列的单链表上可以采用折半查找方法来提高查找速度。
A.正确
B.错误
正确答案：错误
9、折半查找过程所对应的判定树一定是一棵平衡二叉树。
A.正确
B.错误
正确答案：正确
10、在任意一个数据表上，采用折半查找一定比采用顺序查找的查找速度快。
A.正确
B.错误
正确答案：错误
11、在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最好的情况是二叉排序树为平衡二叉树的时候。
A.正确
B.错误
正确答案：正确
12、折半查找的效率与二叉排序树的查找效率是一样的。
A.正确
B.错误
正确答案：错误
第九章单元测试
1、对同一组数据分别采用直接插入排序和折半插入排序进行排序，二者可能存在的不同之处在于（）。
A.整个排序过程中的元素移动次数
B.排序的总趟数
C.整个排序过程中的关键字比较次数
D.占用的辅助内存空间大小
正确答案：整个排序过程中的关键字比较次数
2、希尔排序属于（）类排序方法。
A.交换
B.归并
C.插入
D.选择
正确答案：插入
3、堆排序中所采用的堆的形态为一棵（）。
A.完全二叉树
B.二叉排序树
C.满二叉树
D.平衡二叉树
正确答案：完全二叉树
4、以下关于排序算法的说法中正确的是（）。
A.对同一组数据采用不同的排序算法，排序的结果有可能不同
B.排序算法都是应用在顺序表上的，在链表上无法应用
C.在顺序表上可以应用的排序算法都可以应用在链表上
D.稳定的排序算法执行效率优于不稳定的排序算法
正确答案：对同一组数据采用不同的排序算法，排序的结果有可能不同
5、n个元素构成的降序顺序表，采用冒泡排序按照关键字升序排列时共需进行（）趟排序。
A.1
B.n-1
C.log2n
D.趟数不确定
正确答案：n-1
6、四种排序方法中，排序的趟数与数据表的初始排列顺序无关的是（）。
A.冒泡排序
B.快速排序
C.简单选择排序
D.直接插入排序
E.堆排序
正确答案：简单选择排序；直接插入排序；堆排序
7、以下排序方法中，具有稳定性的是（）。
A.快速排序
B.简单选择排序
C.希尔排序
D.直接插入排序
E.冒泡排序
F.堆排序
G.折半插入排序
正确答案：直接插入排序；冒泡排序；折半插入排序
8、以下排序方法中，空间复杂度为O（1）的是（）。
A.希尔排序
B.快速排序
C.直接插入排序
D.堆排序
E.冒泡排序
正确答案：希尔排序；直接插入排序；堆排序；冒泡排序
9、若采用某种排序方法对某一组数据进行排序后，关键字值相同的元素的相对次序与排序前保持一致，则说明该排序算法具有稳定性。
A.正确
B.错误
正确答案：错误
10、在外排序中需要使用外存储器来保存待排序的数据。
A.正确
B.错误
正确答案：正确
11、空间复杂度是衡量排序算法在执行过程中存储全部待排序数据所使用的总空间大小的一个指标。
A.正确
B.错误
正确答案：错误
12、对于任意一组数据，采用折半插入排序时的关键字比较次数一定小于直接插入排序。
A.正确
B.错误
正确答案：错误
13、快速排序当数据表每次划分得到的子表长度均衡时，算法的效率最高，时间复杂度为O（n）。
A.正确
B.错误
正确答案：错误