数据结构（西安理工大学）智慧树知到期末考试答案章节答案2024年西安理工大学

数据结构（西安理工大学）智慧树知到期末考试答案+章节答案2024年西安理工大学强连通图的各顶点间均可达。

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

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

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

答案:对在一个无向图中，所有顶点的度数之和等于边数的（）倍。

答案:2对稀疏矩阵进行压缩的目的是（）。

答案:节省存储空间有n个权重构造的哈夫曼树中共有（）个结点。

答案:2n-1算法计算量的大小称为算法的（）。

答案:时间复杂度设一棵完全二叉树共有700个结点，则该完全二叉树中的叶子结点数为（）。

答案:350设T是一棵哈夫曼树，具有5个叶子结点，树T的高度最高可以是（）。

答案:5若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是（）。

答案:FEGHDCB下列选项中，能构成折半查找中关键字比较序列的是（）。

答案:500，450，200，180把一棵树转换为二叉树，这棵树的形态是（）。

答案:唯一的内排序方法要求数据一定要以顺序方式存储。

答案:错循环链表是线性表的一种存储方式。

答案:对广义表中的单元素（原子）个数即为广义表的长度。

答案:错设n0为哈夫曼树叶子结点的数目，则该哈夫曼树共有2n0个结点。

答案:错用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

答案:对队列的操作特点是后进先出

答案:错已知广义表L=(((a)))，则A的表头和表尾是（）。

答案:((a))###()三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含三个数据项，分别是（）。

答案:列号###数据###行号下面关于哈希查找的说法中，不正确的是()。

答案:哈希函数构造得越复杂则冲突越少###哈希查找的平均查找长度与哈希表中的元素个数有关###除留余数法是所有哈希函数中最好的对表中任一结点都可访问其直接前驱和直接后继的是（）

答案:双向静态链表###顺序表###双链表设无向图的顶点数为n，则该图最多有（）条边

答案:n(n-1)/2在一棵二叉排序树上查找指定关键字值的元素，在等概率条件下查找成功时的时间复杂度大致为（）。

答案:O(log2n)已知一个三对角矩阵A的行、列下标均由1到100，并以行为主序存入下标由1到298的一维数组B中。则A中元素a66,65（注：行、列下标由1开始，即该元素行下标为66，列下标为65）在数组B中的位置k为()。

答案:195若串S=”software”，其子串的数目是（

）

答案:37字符串的长度是指（）。

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

）

答案:9174一个有n个顶点的连通图，其边的个数至少有（）

答案:n-1在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）二叉树的时候。

答案:单支树一个顺序栈一旦定义，那么它的大小是（）

答案:固定的用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9，1，4，13，7，8，20，23，15，则该趟排序采用的增量（间隔）可能是（）。

答案:3已知广义表L=((a,b,c),(d,e,f))，运用head和tail取表头和表尾两种操作，取出L中的原子e的过程是（）。

答案:head(tail(head(tail(L))))数据的(

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

答案:逻辑结构若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历算法最合适。

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

）

答案:栈n个元素构成的降序顺序表，采用冒泡排序按照关键字升序排列时共需进行（

）趟排序。

答案:n-1下面算法的时间复杂度为(

)。for(i=0;i答案:O(m×n)一个队列的入队序列是1，2，3，4，则队列的出队序列是（

）

答案:1，2，3，4数据的存储结构包括顺序、链式、散列和(

)4种基本类型。

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

）

答案:行号设用链表作为栈的存储结构则退栈操作（

）

答案:必须判别栈是否为空用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用空间大小与图的顶点数有关，与图的边数无关。

答案:对空串与空格串是相同的。

答案:错广义表中元素的个数即为广义表的深度（）。

答案:错由3个结点所构成的二叉树有6种形态。

答案:错已知二叉树的中序遍历序列是DBGEAFHC，后序遍历序列是DGEBHFCA，则前序遍历序列是ABDGECFH。

答案:错数组是一种复杂的数据结构；数组元素之间的关系既不是线性的，也不是树形的。（）

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

答案:对在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next=s;s->next=p->next;

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

答案:错一个图的广度优先生成树是唯一的。

答案:错栈可作为函数调用的一种数据结构。

答案:对对于一个有向图，除了拓扑排序的方法外，还可以通过对有向图进行深度优先遍历的方法来判断有向图是否有回路存在。

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

答案:错若采用某种排序方法对某一组数据进行排序后，关键字值相同的元素的相对次序与排序前保持一致，则说明该排序算法具有稳定性。

答案:错数据的存储结构是指数据在计算机内的物理存储形式。

答案:对顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

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

答案:对数据结构概念包括数据的逻辑结构、数据在计算机中的存储结构以及数据的运算三个方面。

答案:对在循环队列中，front指向队头，rear指向队尾元素的后一个位置，则队满条件是front==rear。

答案:错以下排序方法中，空间复杂度为O(1)的是（

）。

答案:希尔排序###堆排序###冒泡排序###直接插入排序下列哪些算法是属于图的应用算法（

）

答案:迪杰斯特拉（Dijkstra）算法###克鲁斯卡尔（Kruskal）算法###拓扑排序算法串可以用以下方法存储（）

答案:顺序存储###链式存储###块链存储下面关于哈希查找的说法中，正确的是()

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

答案:线性表在链式存储时，查找第i个元素的时间同i值无关###线性表在顺序存储时，查找第i个元素的时间同i值成正比以下排序方法中，属于交换排序的是（）。

答案:快速排序###冒泡排序下列（）结构是非线性结构?

答案:树###图一棵二叉树是由（）组成。

答案:度数为0的结点，度数为1的结点和度数为2的结点###根结点、左子树、右子树以下（

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

答案:效率与低存储量要求###可读性###健壮性###正确性以下关于二叉排序树的说法中，正确的是()

答案:对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列###在二叉排序树上的查找过程与折半查找过程类似###二叉排序树中左子树上所有结点的关键字值均小于它的根结点###二叉排序树中右子树上所有结点的关键字值均大于它的根结点串是一种特殊的线性表，下列不能体现其特殊性的是（

）

答案:可以链接存储###数据元素可以是非字符数据###可以顺序存储已知一个栈的进栈序列是a1,a2,a3....an.其输出序列为1,2,3...n,若a3=1则a1为（

）

答案:不可能是2###可能是3###一定是2在用Kruskal算法求解带权连通图的最小生成树时，选择边的原则是（）。

答案:权值最小的###该边不能在图中最小生成树中构成回路以下排序方法中，具有稳定性的是（

）。

答案:直接插入排序###冒泡排序###折半插入排序下面结论正确的是（）。

答案:广义表L=((),(A,B))的表头为空表###一个广义表的表尾肯定是个广义表可以判断一个有向图是否有回路的方法有（）。

答案:拓扑排序###深度遍历以下关于折半查找的说法，正确的是()。

答案:折半查找不适用于元素频繁变化的顺序表###折半查找只适用于顺序表###折半查找的平均时间复杂度低于顺序查找一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树满足表述正确的是（）

答案:只有一个叶子结点###所有的结点均无左孩子###所有的结点均无右孩子下列关于链式存储结构，那一项是正确的（ ）

答案:结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构###插入、删除操作方便，不必移动结点###逻辑上相邻的结点物理上不必邻接关于哈夫曼编码的说法正确的是（

）

答案:是一种最佳编码###WPL最小###编码无二义性快速排序当数据表每次划分得到的子表长度均衡时，算法的效率最高，时间复杂度为O(n)。

答案:错空间复杂度是衡量排序算法在执行过程中存储全部待排序数据所使用的总空间大小的一个指标。

答案:错对于任意一组数据，采用折半插入排序时的关键字比较次数一定小于直接插入排序。

答案:错四种排序方法中，排序的趟数与数据表的初始排列顺序无关的是（

）。

答案:堆排序###简单选择排序###直接插入排序对同一组数据分别采用直接插入排序和折半插入排序进行排序，二者可能存在的不同之处在于（

）。

答案:整个排序过程中的关键字比较次数在外排序中需要使用外存储器来保存待排序的数据。

答案:对以下关于排序算法的说法中正确的是（

）。

答案:对同一组数据采用不同的排序算法，排序的结果有可能不同希尔排序属于（

）类排序方法。

答案:插入堆排序中所采用的堆的形态为一棵（

）。

答案:完全二叉树折半查找的效率与二叉排序树的查找效率是一样的。

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

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

答案:平均查找长度对于一棵二叉排序树进行（）遍历可得到按关键字有序排列的数据序列。

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

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

（

）。

答案:采用顺序存储结构且元素按查找关键字有序排列哈希查找中的冲突是指（

）。.

答案:不同关键字值对应相同的存储地址折半查找过程所对应的判定树一定是一棵平衡二叉树。

答案:对顺序查找适合于采用（

）存储结构的线性表。

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

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

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

）

答案:层次遍历用邻接表存储的图所用空间大小（

）

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

答案:对下列（

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

答案:DFS###kruskal###BFS###Prim下列（

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

答案:Dijkstra###Floyd无向图的邻接矩阵是（

）矩阵。

答案:对称具有n个顶点的连通有向图中，至少需要（

）条边。

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

）

答案:极小连通子图若一个结点是二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。

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

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

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

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

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

答案:A～C都不对对于二叉树，下列描述正确的是（）

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

答案:适合于顺序存储结构存储###某些结点有右子树时则必有左子树树的基本遍历策略可分为先根遍历和后根遍历，而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则（）是正确的。

答案:树的先根遍历与其对应的二叉树先序遍历序列相同存在这样的二叉树，对它采用任何次序进行遍历得到的结果都相同。

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

答案:n+1二叉树就是结点度为2的有序树。

答案:错下面说法不正确的是（

）

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

）

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

）

答案:p+(i*n+j)*k广义表中元素的个数即为广义表的深度。

答案:错广义表((a),(a))的表头和表尾是（

）

答案:((a))###(a)以下属于特殊矩阵的是(

)

答案:对称矩阵###对角矩阵###上三角矩阵###下三角矩阵以下不属于数组操作的是(

)

答案:删除###插入广义表中原子个数即为广义表的长度。

答案:错数组的存储结构是一组连续的内存单元。

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

）

答案:-1,0,1,2设串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))的结果是（

）

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

）次匹配成功。

答案:6下面（

）不是“abcd321ABCD”的子串（

）

答案:abcAB以下说法中错误的是(

)

答案:串中的元素只能是字母###空串就是空白串###串的长度必须大于零设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。

答案:对串的长度是指串中不同字符的个数。

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

答案:对两个串相等必须有（

）

答案:串中各位置字符均对应相等###串长度相等栈的特点是（

）

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

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

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

答案:错以下说法中正确的是（

）

答案:当队列中无数据元素时，称空队列。###栈是一种只允许在一端进行插入和删除的线性表。以下说法中错误的是(

) 。

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