数据结构智慧树知到期末考试答案章节答案2024年中南民族大学

数据结构智慧树知到期末考试答案+章节答案2024年中南民族大学无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（）

答案:错在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）。

答案:对有向图的邻接矩阵是对称的。（）

答案:错在队空间大小为n的循环队列中，队满的时候存放了n个元素。（）

答案:错从循环链表的某一结点出发，只能找到它的后继结点,不能找到它的前驱结点。（）。

答案:错设H(x)是一哈希函数，有K个不同的关键字(x1,x2,..xk)满足H(x1)=H（x2)...=H(xk)，若用线性探测法将这K个关键字存入哈希表中，则至少要探测K-1次。（）

答案:错二又树中每个结点的度都为2。（）

答案:错无向图中所有顶点的度之和等于顶点数加1。（）

答案:错强连通分量是无向图的极大强连通子图。（）

答案:错一个任意串是其自身的子串。（）

答案:对冒泡排序法是稳定的排序。（）

答案:对栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）

答案:对树与二叉树是两种不同的树型结构。（）

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

答案:248字符串""所有非空子串（两个子串如果内容相同则只算一个）个数是（）。

答案:50在循环双链表的p所指的结点之前插入s所指结点的操作是（）。

答案:s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s在一个无向图中，所有顶点的度之和等于边数的（）倍。

答案:2若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

答案:连通广度优先遍历类似于二叉树的（）。

答案:层次遍历在数据结构中，以下说法中不正确的是（）。

答案:数据项可由若干个数据元素构成设二维数组a[6][10]，每个数组元素占用4个存储单元，若按列优先顺序存放的数组元素，a[3][5]的存储地址为1000,则a[0][0]的存储地址是（）。

答案:868设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S,若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b,d,c,f,e,a,g,则栈S的容量至少是（）。

答案:3在有向图G的拓扑序列中，若vi在vj之前，则以下情形不可能出现的是（）。

答案:G中有一条vj到vi的路径（）不是算法的基本特性。

答案:长度有限假设一颗二叉树的结点个数为50，则它的最小高度是（）。

答案:6对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

答案:从大到小排列好的用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

答案:队列把一棵树转换为二叉树后，这棵二叉树的形态是（）。

答案:唯一的在下列存储形式中，（）不是树的存储形式。

答案:顺序存储表示法任何有向图的顶点都可以按拓扑排序。（）

答案:错如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。（）

答案:错从n个顶点的连通图中选取n-1条权值最小的边即可构成最小生成树。（）

答案:错有向图中所有顶点的度之和等于边数的两倍。（）

答案:对采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）

答案:对Hash表的平均查找长度与处理冲突的方法无关。（）

答案:错广义表的长度是指广义表中元素的个数。（）

答案:对串既不属于线性结构也不属于非线性结构，它是一种特殊的数据结构。（）

答案:错由后序遍历序列和中序遍历序列能唯一确定一颗二叉树。（）

答案:对数据的存储结构是数据的逻辑结构的存储映象。（）

答案:对数据的逻辑结构与存储结构都是依赖于计算机的。（）

答案:错在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（）

答案:错顺序表具有随机存取特性，所以在含有n个元素的顺序表L中查找值为x的元素所花时间为O(1)。（）

答案:错按照逻辑结构划分，数据结构分为线性结构和非线性结构两大类。（）

答案:对队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（）

答案:错二又树中不存在度大于2的结点。（）

答案:对对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树。（）

答案:错线性表若采用链式存储表示时，所有结点之间的存储单元地址可连续也可不连续。（）

答案:对引入线索二又树的目的是加快查找结点的前驱或后继结点的速度。（）

答案:对若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（）

答案:对在二叉树的第i层上最多有2i-1个结点。（）

答案:错栈是一种特殊的线性表，其特殊之处在于栈的存储结构比较特殊。（）

答案:错F=(a,F)是一个递归的广义表，它的深度是1,长度是2。（）

答案:错在对链接队列作出队操作时，不会改变front指针的值。（）

答案:错若无向图G(V,E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。

答案:16以下关于有向图的说法中，错误的是（）。

答案:图和树的区别在于图的边数大于或等于顶点数设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少是（）。

答案:2h-1若一颗二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点个数是（）。

答案:11下面（）算法适合构造一个稠密图G的最小生成树。

答案:Prim算法链栈与顺序栈相比有一个明显的优点，即（）。

答案:通常不会出现栈满的情况以下关于链式存储结构的叙述中，（）是不正确的。

答案:可以通过计算直接确定第i个结点的存储地址向一个不带头节点的栈指针为L的链栈中删除一个节点时，用x保存被删节点的值，则执行（）。

答案:x=L->data;L=L->next设有5个元素的进栈序列是a,b,c,d,e,其输出序列是c,e,d,b,a,则该栈的容量至少是（）。

答案:4字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。

答案:5在长度为n(n≥1)的双向链表中插入一个结点(非尾结点)要修改（）个指针域。

答案:4给定一个空栈，若元素10、20、23、13依次进栈，然后有两个数出栈，又有3个数进栈，第一次进栈的元素23现在（）。

答案:已出栈若邻接表中有奇数个边结点，则一定是（）。

答案:图为有向图一个无向连通图中有16条边，所有的度小于5，其中度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个，则该图有（）个顶点。

答案:13用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。

答案:栈n个顶点的强连通图至少有（）条边。

答案:n元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留，可出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的序列个数是（）。

答案:4设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为（）。

答案:j*(j-1)/2+i下面关于哈希查找的说法，不正确的是（）。

答案:采用链地址法处理冲突时，查找一个元素的时间是相同的在有n个结点的二叉链表中，值为非空的链域的个数为（）。

答案:n-1下面（）方法可以判断出一个有向图是否有环。

答案:求关键路径已知二维数组A[1:4,1:6]采用列序为主序方式存储，每个元素占用4个存储单元，并且A[3，4]的存储地址为1234，元素A[1,1]的存储地址是（）。

答案:1178设a，b，c三个元素的进栈次序是a，b，c，不可能出现的出栈序列是（）。

答案:cab线性表的基本运算Listlnsert(&L,i,e)表示在线性表L中第i个位置上插入一个元素e，若L的长度为n，则i的合法取值是（）。

答案:1≤i≤n+1对数据序列{8，9，10，4，5，6，20，1，2}采用冒泡排序（从后向前次序进行，要求升序），需要进行的趟数至少是（）。

答案:5下列排序方法中，不属于内部排序方法的是（）。

答案:拓扑排序从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。

答案:插入排序具有12个关键字的有序表，折半查找的平均查找长度为（）。

答案:3.1对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

答案:(n+1)/2适用于折半查找的表的存储方式及元素排列要求为（）。

答案:顺序方式存储，元素有序在一个图中，所有顶点的度数之和等于图的边数的（）倍。

答案:2广度优先遍历类似于二叉树的(

)。

答案:层次遍历G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

答案:9广义表((a,b,c,d))的表尾是（）。

答案:()设广义表L=((a,b,c))，则L的长度和深度分别为（）。

答案:1和2设串S="software",其子串的个数为（）。

答案:37设串sl="DataStructureswithJava",s2="it"，则子串定位函数index(s1,s2)的值为（）。

答案:18下面关于串的的叙述中，（）是不正确的？

答案:空串是由空格构成的串栈在（）中有所应用。

答案:前三个选项都有顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是（）。

答案:110向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

答案:63.5线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

答案:连续或不连续都可以若要在O(1)的时间内实现两个单循环链表的首尾相接，