数据结构与算法智慧树知到期末考试答案章节答案2024年中国民用航空飞行学院

数据结构与算法智慧树知到期末考试答案+章节答案2024年中国民用航空飞行学院对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。

答案:对顺序存储结构的主要缺点是不利于插入或删除操作。

答案:对非空线性表具有哪些结构特征？

答案:存在唯一的开始结点和终端结点。###除开始结点外，每个结点只有一个前驱结点。###除终端结点外，每个结点只有一个后继结点。在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。

答案:对栈是一种对进栈、出栈操作总次数做了限制的线性表。

答案:错设树中某结点不是根结点，则离它最近的祖先结点是（）。

答案:父结点利用二叉链表存储树，则根结点的右指针是（）。

答案:空已知L是带头结点的单链表，则摘除首元结点的语句是（）。

答案:L->next=L->next->next;已知一个栈的进栈序列为1，2，3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=n，则pi的值是（）。

答案:n-i+1一段文本中包含对象{a,b,c,d,e}，其出现次数相应为{3,2,4,2,1}，则经过哈夫曼编码后，该文本所占总位数为：

答案:27以下关于huffman树说法错误的是（）。

答案:若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的huffman树若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素的合法值应该是（）。

答案:1≤i≤n+1从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：

答案:X=ST->data;ST=ST->next;从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，需要平均比较（）个结点。

答案:(n+1)/2给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是（）。

答案:O(n*n)顺序表的优点是（）。

答案:存储密度(存储利用率)高链表不具有的特点是（）。

答案:可随机访问任一元素哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

答案:对完全二叉树的存储结构通常采用顺序存储结构。

答案:对树最适合用来表示（）。

答案:元素之间具有分支层次关系的数据线性表中每个元素都有一个直接前趋和一个直接后继。

答案:错若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。

答案:对完全二叉树一定存在度为1的结点。

答案:错某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。

答案:对数据结构是介于()的之间的一门核心课程。

答案:硬件###数学###软件栈底元素是不能删除的元素。

答案:错顺序栈中元素值的大小是有序的。

答案:错已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，则后序遍历序列为（）。

答案:DCBFGEA已知单链表中结点q是结点p的直接前趋，若在q与p之间插入结点s，则应执行以下（）操作。

答案:q->next=s;s->next=p;若一棵二叉树具有10个度为2的结点、5个度为1的结点，则度为0的结点个数是

答案:11为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？

答案:队列在以下有关顺序表的叙述中正确的是（）。

答案:顺序表的优点是存储密度高，且插入与删除运算的时间效率高采用邻接表存储的图的广度优先遍历算法类似于二叉树的____算法。

答案:层次遍历若想在单链表中摘除结点p（p既不是第一个也不是最后一个结点）的直接后继，则应执行以下（）操作。

答案:p->next=p->next->next;在顺序表中，在删除表中第i个元素时，为保持删除后表中原有元素的相对次序不变，需要从前向后依次前移（2）个元素。

答案:n-i在Data_Structure=(D，R)中，D是（）的有限集合。

答案:数据元素二叉树的先序序列和中序序列相同的条件是（）。

答案:任何结点至多只有右子女的二叉树已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，则该二叉树形态中，父节点的右子节点为（）。

答案:G一个有n个顶点的无向图最多有____条边。

答案:n(n-1)/2为了增加内存空间的利用率和减少溢出的可能，在两个栈共享一片连续的存锗空间时，应将两个栈的栈顶分设在这片存储空间的两端，当（）时才产生上溢。

答案:两个栈的栈顶在栈空间的某一位置相遇设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？

答案:32154单链表又称为线性链表，在单链表上实施插入和删除操作（）。

答案:不需移动结点，只需改变结点指针设T是非空二叉树，若T的先序遍历和中序遍历序列相同，则T的形态是（）。

答案:所有结点只有右孩子顺序表中，在向表中第i个元素（1≤i≤n+1）位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移（）个元素。

答案:n-i+1哈夫曼树的结点个数不能是偶数。

答案:对完全二叉树中，若一个结点没有左孩子，则它必是树叶。

答案:对将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。

答案:错若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。

答案:错数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。

答案:错带头结点的单循环链表中，任一结点的后继结点的指针域均不空。

答案:对栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。

答案:对非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。

答案:对在一棵非空二叉树的中序序列中，根结点的右边（）。

答案:只有右子树上的所有结点KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为

答案:O(m+n)一棵二叉树的后序序列：fdbgheca，中序序列：bfdagehc。前序遍历序列为（）。

答案:abdfcegh以下关于二叉排序树的叙述中正确的是

答案:在构造二叉排序树时，若关键字序列有序，则二叉排序树的高度最大单链表中，增加一个头结点的目的是（）。

答案:方便运算的实现。根据教科书中线性表的实现方法，线性表中的元素必须是（）。

答案:相同类型一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是（）。

答案:2^(k-2)+1二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。

答案:A[3,10]一棵树可转换成为与其对应的二叉树，则下面叙述正确的是（）。

答案:树的先根遍历序列与其对应的二叉树的先序遍历相同在二叉树中某一结点的深度为3，高度为4，该树的高度至少为（）。

答案:6链接存储表示中数据元素之间的逻辑关系是由（）表示的。

答案:指针若二叉树中结点的先序序列是...a...b...，中序序列是...b...a...，则（）。

答案:结点b在结点a的左子树中在一棵3次树中度为3的结点数为两个，度为2的结点数为一个，度为1的结点数为两个，则度为0的结点数为____个

答案:6已知单链表A长度为m,单链表B长度为n，若将B连接在A的末尾，在没有链尾指针的情形下，算法的时间复杂度应为（）。

答案:O(m)设链式栈中结点的结构为（data，next），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行的操作是（）。

答案:x=top->data；top=top->next；在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）。

答案:O(1)顺序表是线性表的（）存储表示。

答案:数组下面几个符号串编码集合中，不是前缀编码的是（）。

答案:{11,10,001,101,0001}线性表、堆栈、队列的主要区别是什么？

答案:堆栈和队列都是插入、删除受到约束的线性表设链式栈中结点的结构为（data,next），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行的操作是（）。

答案:s->next=top；top=s；在一个具有72个结点的单链表中插入一个新结点并可以不保持原有顺序的算法的时间复杂度是（）。

答案:O(1)如果哈夫曼树有67个结点，则可知叶结点总数为：

答案:34带头结点的单链表head为空的判定条件是（）。

答案:head->next==NULL;Dijkstra算法是____方法求出图中从某顶点到其余顶点的最短路径的

答案:按长度递增的顺序求出图中某顶点到其余顶点的最短路径用双亲存储结构表示树，其优点之一是比较方便

答案:找指定结点的双亲结点能在O(1)时间内访问线性表的第i个元素的结构是（）。

答案:顺序表在下列排序方法中，若待排序的数据已经有序，花费时间反而最多的是

答案:快速排序若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

答案:2和0一棵有n个结点的树的所有结点的度数之和为（）。

答案:n-1若一棵二叉树的先序序列和后序遍历分别是1、2、3、4和4、3、2、1，则该二叉树的中序序列不会是()。

答案:3、2、4、1假设每个结点值为单个字符，而一棵树的层次遍历序列为ABCDEFGHIJ，则其根结点的值是（

）。

答案:A对于一棵具有n个结点、度为4的树来说，（）。

答案:树的高度最多是n-3二叉树若用顺序方法存储，则下列4种运算中()最容易实现。

答案:层次遍历二叉树根据使用频率为5个字符设计的哈夫曼编码不可能是（）。

答案:100,11,10,1,0设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按照行优先存放在一维数组B[0..n(n+1)/2-1]中，对于下三角部分的任一元素a_{i,j}(i>=j，i和j从0开始取值），在一维数组B中的下标k的值是____。

答案:i(i+1)/2+j设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为____。

答案:(i-1)*n+j二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为()。提示：是按列存放。

答案:SA+180有一个二维数组A[6][8]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（）个字节。

答案:288稀疏矩阵一般的压缩存储方法有____两种。

答案:三元组和十字链表任何一个递归过程都可以转换成非递归过程。

答案:对若一个问题既可以用迭代方式也可以用递归方式求解，则____的方法具有更髙的时空效率。

答案:迭代设有一个递归算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。

答案:n+1下列说法中，正确的是（）。

答案:消除递归不一定需要使用栈一个递归算法必须包括____。

答案:终止条件和递归部分在用KMP算法进行模式匹配时，模式串“ababaaababaa”的next数组值为____。

答案:-1，0，0，1，2，3，1，1，2，3，4，5串的长度是指____。

答案:串中所含字符的个数下面关于串的叙述中，哪一个是不正确的____。

答案:空串是由空格构成的串串是一种特殊的线性表，其特殊性体现在____。

答案:数据元素是一个字符若串S=“software”，则其子串数目是____，其中空串和S串本身这两个字符串也算作S的字串

答案:37设栈S和队列Q的初始状态均为空，元素{1,2,3,4,5,6,7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2,5,6,4,7,3,1}，则栈S的容量至少是：

答案:4栈可用于（）。

答案:A、B、C都是表达式a*(b+c)-d的后缀表达式是（）。

答案:abc+*d-设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是（）。

答案:1或者5设一个栈的输入序列为a，b，c，d，则借助一个栈所得到的输出序列不可能是（）。

答案:d，