数据结构（西安理工大学）智慧树知到课后章节答案2023年下西安理工大学

数据结构（西安理工大学）智慧树知到课后章节答案2023年下西安理工大学西安理工大学

第一章测试

研究数据结构就是研究(

)。

A:数据的存储结构B:数据的逻辑结构C:数据的逻辑结构、存储结构及其数据在运算上的实现D:数据的逻辑结构和存储结构

答案:数据的逻辑结构、存储结构及其数据在运算上的实现

关于算法的说法，错误的是(

)。

A:其他三项都是错误的B:算法的可行性是指指令不能有二义性C:算法最终必须由计算机程序实现D:为解决某问题的算法和为该问题编写的程序含义是相同的

答案:其他三项都是错误的

数据的(

)包括集合、线性、树和图4种基本类型。

A:存储结构B:逻辑结构C:算法描述D:基本运算

答案:逻辑结构

数据的存储结构包括顺序、链式、散列和(

)4种基本类型。

A:向量B:索引C:数组D:集合

答案:索引

下面算法的时间复杂度为(

)。for(i=0;i<m;i++)for(j=0;j<n;j++)

A[i][j]=i*j;

A:O(n2)B:O(m+n)C:O(m×n)D:O(m2)

答案:O(m×n)

以下（

）属于设计一个“好”的算法应考虑达到的目标。

A:可读性B:正确性C:效率与低存储量要求D:健壮性

答案:可读性;正确性;效率与低存储量要求;健壮性

依据所有数据成员之间的逻辑关系的不同，数据结构分为（

）。  

A:物理结构B:线性结构C:逻辑结构D:非线性结构

答案:线性结构;非线性结构

在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储数据元素之间的关系。

A:错B:对

答案:对

在逻辑结构定义的操作与具体实现有关。

A:错B:对

答案:错

算法是对解题方法和步骤的描述。

A:对B:错

答案:对

算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

A:错B:对

答案:对

第二章测试

线性表是（

）。

A:一个无限序列，可以为空。B:一个有限序列，可以为空。C:一个无限序列，不能为空。D:一个有限序列，不能为空。

答案:一个有限序列，可以为空。

若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（）存储方法最节省时间。

A:双向链表B:单链表C:循环链表D:顺序表

答案:顺序表

单链表中，增加一个头结点的目的是为了（

）。

A:使单链表至少有一个结点B:说明单链表是线性表的链式存储C:方便运算的实现D:标识表结点中首结点的位置

答案:方便运算的实现

在带有头结点的单链表Head中，要向表头插入一个由指针p指向的结点，则执行（

）。

A:p->next=Head->next;

Head->next=p;B:p->next=Head;

Head=p;C:p->next=Head;

p=Head;D:Head=p;p->next=Head;

答案:p->next=Head->next;

Head->next=p;

在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A:将n个元素从小到大排序B:访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C:删除第i个元素（1≤i≤n）D:在第i个元素后插入一个新结点（1≤i≤n）

答案:访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

下列说法正确的有(

)。

A:所谓数据的逻辑结构是指数据元素之间的逻辑关系 B:算法和程序原则上没有区别，在讨论数据结构时二者通用C:从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构D:数据的逻辑结构与数据元素本身的内容和形式无关E:“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数相等

答案:所谓数据的逻辑结构是指数据元素之间的逻辑关系 ;从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构;数据的逻辑结构与数据元素本身的内容和形式无关

线性表的逻辑顺序和存储顺序总是一致的。

A:错B:对

答案:错

在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

A:对B:错

答案:对

顺序存储结构只能存储线性结构，链式存储结构只能存储非线性结构。

A:错B:对

答案:错

线性表的链式存储结构优于顺序存储结构。

A:对B:错

答案:错

链式存储方式以指针表示元素间的逻辑关系。

A:对B:错

答案:对

第三章测试

在顺序栈空的情况下不能进行出栈操作，否则将产生“下溢”。

A:对B:错

答案:对

栈和队列都是限制存取位置的线性表。

A:对B:错

答案:对

若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，则不可能得到出栈序列：a,f,e,d,c,b。

A:对B:错

答案:错

入栈操作和入队列操作在链式存储结构上实现时一般不需要考虑栈溢出的情况。

A:对B:错

答案:对

同一个栈内的各个数据元素类型可以不一致。

A:对B:错

答案:错

以下说法中正确的是（

）

A:当队列中无数据元素时，称空队列。

B:栈是一种操作不受限制的线性表。C:队列被称为“先进后出”表。D:栈是一种只允许在一端进行插入和删除的线性表。

答案:当队列中无数据元素时，称空队列。

;栈是一种只允许在一端进行插入和删除的线性表。

以下说法中错误的是(

) 。

A:栈不能对输入序列部分或全局求逆。B:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。C:当top等于数组最大下标时则栈满。D:top=-1时为空栈，元素进栈时指针top不断减1。

答案:栈不能对输入序列部分或全局求逆。;top=-1时为空栈，元素进栈时指针top不断减1。

已知一个栈的进栈序列是a1,a2,a3....an.其输出序列为1,2,3...n,若a3=1则a1为（

）

A:可能是3B:不可能是3C:一定是2D:不可能是2E:可能是2

答案:可能是3;一定是2;不可能是2

栈的特点是（

）

A:先进后出B:进优于出C:出优于进D:先进先出

答案:先进后出

设循环队列的容量为20，序号从0到19，经过一系列的入队和出队后，front=5,rear=10,问队列中有多少个元素（采用节省一个队列存储空间的方式）。

A:4B:6C:5D:7

答案:5

一个队列的入队序列是1，2，3，4，则队列的出队序列是（

）

A:3，2，4，1B:1，2，3，4C:4，3，2，1D:1，4，3，2

答案:1，2，3，4

一般情况下，将递归算法转换成等价的非递归算法应该设置（

）

A:栈B:栈或队列C:数组D:队列

答案:栈

设用链表作为栈的存储结构则退栈操作（

）

A:对栈不作任何判别B:必须判别栈是否为满C:必须判别栈是否为空D:判别栈元素的类型

答案:必须判别栈是否为空

第四章测试

KMP算法的特点是在模式匹配时指示主串的指针不会变小。

A:错B:对

答案:对

空串与空格串是相同的。

A:对B:错

答案:错

串的长度是指串中不同字符的个数。

A:错B:对

答案:错

设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。

A:错B:对

答案:对

设模式串（子串）的长度为m，目标串（主串）的长度为n。当n≈m且处理只匹配一次的模式时，简单模式匹配（BF）算法所花费的时间代价也可能会比KMP算法更节省。

A:对B:错

答案:对

串是一种特殊的线性表，下列不能体现其特殊性的是（

）

A:可以链接存储B:数据元素可以是非字符数据C:可以顺序存储D:数据元素是字符型数据

答案:可以链接存储;数据元素可以是非字符数据;可以顺序存储

以下说法中错误的是(

)

A:串中的元素只能是字母B:串的长度必须大于零C:空串就是空白串D:串是一种特殊的线性表

答案:串中的元素只能是字母;串的长度必须大于零;空串就是空白串

两个串相等必须有（

）

A:串中各位置字符均对应相等B:串长度任意C:串长度不相等D:串长度相等E:串中的各位置字符任意

答案:串中各位置字符均对应相等;串长度相等

若串S=”software”，其子串的数目是（

）

A:36B:9C:8D:37

答案:37

下面（

）不是“abcd321ABCD”的子串（

）

A:abcABB:abcdC:21ABD:321AB

答案:abcAB

已知模式串为“aaab”，其next数组值为（

）

A:0,1,2,0B:-1,0,1,2C:-1,1,0,0D:0,0,1,2

答案:-1,0,1,2

设主串为“abccdcdccdbaa”，模式串为“cdcc”，用BF算法在第（

）次匹配成功。

A:5B:6C:4D:7

答案:6

设串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:CDEFGFGB:CDEFG12C:BCDEFG1D:CD12345

答案:CDEFGFG

第五章测试

稀疏矩阵压缩存储后，必会失去随机存取功能。

A:对B:错

答案:对

数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

A:对B:错

答案:错

数组的存储结构是一组连续的内存单元。

A:错B:对

答案:对

广义表中原子个数即为广义表的长度。

A:错B:对

答案:错

广义表中元素的个数即为广义表的深度。

A:对B:错

答案:错

广义表((a),(a))的表头和表尾是（

）

A:aB:((a))C:(a)D:b

答案:((a));(a)

以下属于特殊矩阵的是(

)

A:对称矩阵B:对角矩阵C:下三角矩阵D:上三角矩阵

答案:对称矩阵;对角矩阵;下三角矩阵;上三角矩阵

以下不属于数组操作的是(

)

A:修改B:删除C:插入D:存取E:查找

答案:删除;插入

对行下标由1到50、列下标由1到80的二维数组a，若该数组的起始地址为2000且每个元素占2个存储单元，并以行为主序顺序存储，则元素a[45][68]的存储地址为（

）

A:9174B:9172C:9175D:9173

答案:9174

在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（

）

A:元素值B:非零元素个数C:行号D:列号

答案:行号

设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（

）

A:28B:55C:10D:19

答案:19

设二维数组A[0~m][0~n]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则a[i][j]的地址为（

）

A:p+((i-1)*n+j-1)*kB:p+(j*n+i-1)*kC:p+((j-1)*n+i-1)*kD:p+(i*n+j)*k

答案:p+(i*n+j)*k

下面说法不正确的是（

）

A:广义表的表头总是一个广义表B:广义表的表尾总是一个广义表C:广义表可以是一个多层次结构D:广义表难以用顺序结构存储

答案:广义表的表头总是一个广义表

第六章测试

一棵完全二叉树上有1001个结点，其叶子结点的个数是（）。

A:A～C都不对B:500C:250D:505

答案:A～C都不对

一棵有124个叶结点的完全二叉树最多有（）个结点。

A:248B:247C:250D:249

答案:248

在n个结点的线索二叉树中，线索的数目为（）

A:nB:2nC:n+1D:n-1

答案:n+1

设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。

A:13B:12C:25D:26

答案:25

树的基本遍历策略可分为先根遍历和后根遍历，而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则（）是正确的。

A:树的先根遍历与其对应的二叉树先序遍历序列相同B:树的后根遍历与其对应的二叉树后序遍历序列相同C:树的先根遍历与其对应的二叉树中序遍历序列相同

答案:树的先根遍历与其对应的二叉树先序遍历序列相同

完全二叉树（）。

A:适合于顺序存储结构存储B:叶子结点可在任一层出现C:某些结点有左子树时则必有右子树D:不一定适合顺序存储结构存储E:某些结点有右子树时则必有左子树

答案:适合于顺序存储结构存储;某些结点有右子树时则必有左子树

对于二叉树，下列描述正确的是（）

A:高度为k的二叉树结点数最多时一定是满二叉树B:一定有度数为1的结点C:第k层上最多有2k-1个结点D:叶子结点数目比度数为2的结点数目多1个E:边的个数比结点个数少1个F:n个结点共有n-1个非空指针域

答案:高度为k的二叉树结点数最多时一定是满二叉树;叶子结点数目比度数为2的结点数目多1个;边的个数比结点个数少1个;n个结点共有n-1个非空指针域

关于哈夫曼编码的说法正确的是（

）

A:是一种最佳编码B:编码无二义性C:WPL最小D:不允许出现频度相同的字符E:两个频度相同的字符其编码长度一定相等

答案:是一种最佳编码;编码无二义性;WPL最小

存在这样的二叉树，对它采用任何次序进行遍历得到的结果都相同。

A:错B:对

答案:对

二叉树就是结点度为2的有序树。

A:错B:对

答案:错

若一个结点是二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。

A:对B:错

答案:错

一棵含有n个结点的完全二叉树，它的高度是⌊log2n⌋+1。

A:错B:对

答案:对

线索二叉树的左线索指向其某种遍历序列的直接前驱结点，右线索指向其某种遍历序列的直接后继结点。

A:错B:对

答案:对

第七章测试

无向图的邻接矩阵是（

）矩阵。

A:上三角阵B:下三角阵C:稀疏矩阵D:对称

答案:对称

用邻接表存储的图所用空间大小（

）

A:只与图的顶点数有关与边数的平方有关B:与边数的平方有关C:与图的顶点数和边数都有关D:只与图的边数有关

答案:与图的顶点数和边数都有关

不论基于图的邻接表还是基于邻接矩阵存储，图的广度优先遍历算法类似于树的（

）

A:先序遍历B:中序遍历C:后序遍历D:层次遍历

答案:层次遍历

一个连通图的生成树是包含该图的所有顶点的（

）

A:极大连通子图B:极大子图C:极小子图D:极小连通子图

答案:极小连通子图

具有n个顶点的连通有向图中，至少需要（

）条边。

A:n-1B:n+1C:2nD:n

答案:n

下列哪些算法是属于图的应用算法（

）

A:拓扑排序算法B:欧几里德算法C:克鲁斯卡尔（Kruskal）算法D:哈夫曼（Huffman）算法E:迪杰斯特拉（Dijkstra）算法

答案:拓扑排序算法;克鲁斯卡尔（Kruskal）算法;迪杰斯特拉（Dijkstra）算法

下列（

）算法可用于构造图的生成树。

A:FloydB:DFSC:PrimD:BFSE:kruskal

答案:DFS;Prim;BFS;kruskal

下列（

）是构造最短路径的方法。

A:PrimB:FloydC:KruskalD:BFSE:Dijkstra

答案:Floyd;Dijkstra

n个结点的无向图，若没有顶点到自身的边，也没有一个顶点到另一个顶点的多重边，此时若有n(n-1)/2条边，则该无向图一定是连通图。

A:对B:错

答案:对

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用空间大小与图的顶点数有关，与图的边数无关。

A:对B:错

答案:对

对于任意一个图，从它的某个顶点出发进行一次深度或者广度遍历可以访问到该图的每个顶点。

A:对B:错

答案:错

对于无向图的生成树，从同一顶点出发所得的生成树相同。

A:对B:错

答案:错

有向图顶点v的度是其邻接矩阵中第v行1的个数。

A:错B:对

答案:错

第八章测试

衡量一个查找算法执行效率高低的最重要的指标是（）。

A:所需的内存大小B:查找表中的元素个数C:查找过程中关键字比较的最大次数D:平均查找长度

答案:平均查找长度

对线性表进行二分查找时，要求线性表必须

（

）。

A:采用链接存储结构B:采用顺序存储结构且元素按查找关键字有序排列C:采用链接存储结构且结点按查找关键字有序排列D:采用顺序存储结构

答案:采用顺序存储结构且元素按查找关键字有序排列

哈希查找中的冲突是指（

）。.

A:两个元素的关键字值相同B:两个元素的关键字值不同C:不同关键字值对应相同的存储地址D:两个元素具有相同序号

答案:不同关键字值对应相同的存储地址

对于一棵二叉排序树进行（）遍历可得到按关键字有序排列的数据序列。

A:先序B:层序C:后序D:中序

答案:中序

顺序查找适合于采用（

）存储结构的线性表。

A:顺序或链式B:散列C:压缩D:索引

答案:顺序或链式

下面关于哈希查找的说法中，正确的是()

A:采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的B:链地址法处理冲突的平均查找长度小于线性探测和二次探测C:用链地址处理冲突，适合表长不确定的情况D:用链地址处理冲突，不会引起二次聚集的现象E:采用链地址法处理冲突时，查找任何一个元素的时间都相同

答案:采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的;链地址法处理冲突的平均查找长度小于线性探测和二次探测;用链地址处理冲突，适合表长不确定的情况;用链地址处理冲突，不会引起二次聚集的现象

以下关于二叉排序树的说法中，正确的是()

A:对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列B:二叉排序树中右子树上所有结点的关键字值均大于它的根结点C:二叉排序树一定为一棵平衡二叉树D:二叉排序树中左子树上所有结点的关键字值均小于它的根结点E:在二叉排序树上的查找过程与折半查找过程类似

答案:对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列;二叉排序树中右子树上所有结点的关键字值均大于它的根结点;二叉排序树中左子树上所有结点的关键字值均小于它的根结点;在二叉排序树上的查找过程与折半查找过程类似

在一个结点值按照查找关键字有序排列的单链表上可以采用折半查找方法来提高查找速度。

A:错B:对

答案:错

折半查找过程所对应的判定树一定是一棵平衡二叉树。

A:错B:对

答案:对

在任意一个数据表上，采用折半查找一定比采用顺序查找的查找速度快。

A:对B:错

答案:错

在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最好的情况是二叉排序树为平衡二叉树的时候。

A:对B:错

答案:对

折半查找的效率与二叉排序树的查找效率是一样的。

A:错B:对

答案:错

第九章测试

对同一组数据分别采用直接插入排序和折半插入排序进行排序，二者可能存在的不同之处在于（

）。

A:整个排序过程中的关键字比较次数B:整个排序过程中的元素移动次数C:占用的辅助内存