数据结构（山东联盟） 知到智慧树网课答案

数据结构（山东联盟）-知到答案、智慧树答案第一章单元测试1、问题：数据在计算机内存中的表示是指（）选项：A:数据结构B:数据元素之间的关系C:数据的存储结构D:数据的逻辑结构答案:【数据的存储结构】2、问题：算法指的是（）选项：A:解决问题的计算方法B:解决问题的有限运算序列C:计算机程序D:排序算法答案:【解决问题的有限运算序列】3、问题：在数据结构中，与所使用的计算机无关的数据结构是（）选项：A:逻辑结构和存储结构B:物理结构C:存储结构D:逻辑结构答案:【逻辑结构】4、问题：算法能正确地实现预定功能的特性称为算法的（）。选项：A:正确性B:可读性C:健壮性D:高效性答案:【正确性】5、问题：已知某算法的执行时间为(n+n2)log2(n+2)，n为问题规模，则该算法的时间复杂度是（）。选项：A:O((n+n2)logn)B:O(nlogn)C:O(n2)D:O(n2logn)答案:【O(n2logn)】6、问题：下面算法将一维数组a中的数据逆序存放到原数组中，空间复杂度为（）。for(i=0;i选项：A:O(n2)B:O(n)C:O(logn)D:O(1)答案:【O(n)】第二章单元测试1、问题：链表不具备的特点是（）。选项：A:不必事先估计存储空间B:所需空间与其长度成正比C:可随机访问任意一个结点D:插入和删除不需要移动任何元素答案:【可随机访问任意一个结点】2、问题：线性表的顺序存储表示优于链式存储表示。选项：A:错B:对答案:【错】3、问题：顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。选项：A:错B:对答案:【对】4、问题：在设头、尾指针的单链表中,与长度n有关的操作是()。选项：A:删除最后一个结点B:在p结点之后插入一个结点C:删除第一个结点D:在第一个结点之前插入一个结点答案:【删除最后一个结点】5、问题：设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为()。选项：A:p->next=s;s->next=q;B:q->next=s;s->next=p;C:p->next=s->next;s->next=p;D:s->next=p->next;p->next=-s;答案:【q->next=s;s->next=p;】6、问题：对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为()。选项：A:用头指针表示的循环单链表B:用尾指针表示的循环单链表C:单链表D:顺序表答案:【用尾指针表示的循环单链表】7、问题：在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行()。选项：A:s->link=p->link;p->link=s;B:s->link=p;p->link=s;C:s->link=p->link;p=s;D:p->link=s;s->link=p;答案:【s->link=p->link;p->link=s;】8、问题：在双向链表存储结构中,删除p所指的结点时须修改指针()。选项：A:p->next=p->next->next;p->next->prior=p;B:p->next->prior=p->prior;p->prior->next=p->next;C:p->prior=p->next->next;p->next=p->prior->prior;D:p->prior->next=p;p->prior=p->prior->prior;答案:【p->next->prior=p->prior;p->prior->next=p->next;】9、问题：若事先不知道线性表的长度,则处理线性表时较好的存储结构是()。选项：A:B和CB:顺序表C:单链表D:静态链表答案:【单链表】10、问题：向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动()个元素。选项：A:7B:8C:63D:63.5答案:【63.5】11、问题：某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为()。选项：A:147B:144C:148D:145答案:【144】12、问题：在一个以h为头的单循环链表中,p指针指向链尾的条件是()。选项：A:p->next==hB:p->data==-1C:p->next->next==hD:p->next==NULL答案:【p->next==h】13、问题：在表头指针为head且表长大于1的单向循环链表中,指针p指向表中的某个结点,若p->next->next=head,则()。选项：A:*p的直接后继是尾结点B:*p的直接后继是头结点C:p指向尾结点D:p指向头结点答案:【*p的直接后继是尾结点】14、问题：线性表若采用链式存储结构时,要求内存中可用存储单元的地址()。选项：A:必须是连续的B:连续不连续都可以C:部分地址必须是连续的D:一定是不连续的答案:【连续不连续都可以】15、问题：在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是()。选项：A:p=p->next;B:p=p->next->next;C:p->next=p;D:p->next=p->next->next;答案:【p->next=p->next->next;】16、问题：可以用带表头结点的链表表示线性表,也可以用不带表头结点的链表表示线性表,前者最主要的好处是()。选项：A:节省存储空间B:使空表和非空表的处理统一C:可以加快对表的遍历D:可以提高存取元素的速度答案:【使空表和非空表的处理统一】17、问题：与单链表相比,双向链表的优点之一是()。选项：A:顺序访问相邻结点更加灵活B:插入、删除操作更加简单C:可以省略表头指针或表尾指针D:可以随机访问答案:【顺序访问相邻结点更加灵活】18、问题：如果最常用的操作是取第i个结点及其前驱,最节省时间的存储方式()。选项：A:单循环链表B:双向链表C:单链表D:顺序表答案:【顺序表】19、问题：线性链表不具有的特点是（）。选项：A:插入与删除时不必移动元素B:所需空间与线性表长度成正比C:不必事先估计所需存储空间大小D:随机访问答案:【随机访问】20、问题：对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的()个元素。选项：A:n/2B:(n+1)/2C:nD:(n-1)/2答案:【n/2】21、问题：链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。选项：A:对B:错答案:【对】22、问题：在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点,则需要相继修改()个指针域的值。选项：A:2B:3C:4D:5答案:【4】23、问题：具有线性关系的集合中，若a，b是集合中的任意两个元素，则必有a选项：A:错B:对答案:【错】第三章单元测试1、问题：设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）选项：A:dcefbaB:bcafedC:fedcbaD:cabdef答案:【cabdef】2、问题：若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=3，则p2为（）选项：A:可能是2B:可能是1C:一定是1D:一定是2答案:【可能是2】3、问题：假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（）。选项：A:front==rearB:front==0C:front+1==rearD:(rear＋1)modMAXSIZE==front答案:【(rear＋1)modMAXSIZE==front】4、问题：队列和栈都是运算受限的线性表，只允许在表的两端进行运算。选项：A:对B:错答案:【对】5、问题：循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()。选项：A:rear-front-1B:rear-frontC:(rear-front+m)%mD:rear-front+1答案:【(rear-front+m)%m】6、问题：不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O(n)。选项：A:对B:错答案:【错】7、问题：若栈采用顺序存储方式存储，两栈共享空间A[1..m]，top[i]代表第i个栈（i=1,2）的栈顶，栈1的底在A[1]，栈2的底在A[m]，则栈满的条件是（）。选项：A:|top[2]-top[1]|=0B:top[1]+top[2]=mC:top[1]=top[2]D:top[1]+1=top[2]答案:【top[1]+1=top[2]】8、问题：输入序列为ABC，若出栈的顺序为CBA时，经过的栈操作为（）。选项：A:push,pop,push,pop,push,popB:push,push,push,pop,pop,popC:push,push,pop,pop,push,popD:push,pop,push,push,pop,pop答案:【push,push,push,pop,pop,pop】9、问题：栈和队都是（）。选项：A:限制存取点的非线性结构B:限制存取点的线性结构C:链式存储的非线性结构D:顺序存储的线性结构答案:【限制存取点的线性结构】10、问题：链栈与顺序栈相比，有一个比较明显的优点是（）。选项：A:删除操作更方便B:插入操作更方便C:会出现栈空的情况D:通常不会出现栈满的情况答案:【通常不会出现栈满的情况】11、问题：设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。选项：A:线性表的链式存储结构B:队列C:线性表的顺序存储结构D:栈答案:【栈】12、问题：某队列允许在其两端进行入队操作，但只允许在一端进行出队操作，若有元素a,b,c,d,e依次入队后再进行出队操作，则不可能得到的出队序列是（）。选项：A:d,b,c,a,eB:d,b,a,c,eC:e,c,b,a,dD:b,a,c,d,e答案:【d,b,c,a,e】13、问题：有如下递归算法：intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需调用该函数的次数是（）。选项：A:n-1B:n+2C:nD:n+1答案:【n+1】14、问题：栈在（）中有所应用。选项：A:表达式求值B:前三个选项都有C:递归调用D:函数调用答案:【前三个选项都有】15、问题：设有一个递归算法如下intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。选项：A:nB:n+2C:n+1D:n-1答案:【n+1】16、问题：（）的一个重要应用是在程序设计语言中实现递归。选项：A:顺序表B:栈C:队列D:数组答案:【栈】17、问题：只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。选项：A:对B:错答案:【错】18、问题：栈是实现过程和函数等子程序所必需的结构。选项：A:错B:对答案:【对】19、问题：通常使用队列来处理函数或过程的调用。选项：A:对B:错答案:【错】20、问题：栈和队列的存储方式，既可以是顺序方式，又可以是链式方式选项：A:错B:对答案:【对】第四章单元测试11、问题：设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，为第1个元素，其存储地址为，每个元素占用1个地址空间，则a85的地址为（）。选项：A:13B:33C:18D:40答案:【33】2、问题：对于以行为主序的存储结构来说．在数组A[c1..d1,c2..d2]中，c1和d1分别为数组A的第一维下标的下、上界，c2和d2分别为第二维下标的下、上界．每个数据元素占k个存储单元，二维数组中任一元素a[i,j]的存储位置可由（）确定。选项：A:Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]×kB:Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kC:Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kD:Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]×k答案:【Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×k】3、问题：A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是选项：A:j（i-1）/2+1B:i（j-i）/2+1C:j（j-1）/2+iD:i（i-1）/2+j答案:【j（j-1）/2+i】4、问题：对矩阵压缩存储是为了（）选项：A:减少存储空间B:方便存储C:方便运算D:提高运算速度答案:【减少存储空间】5、问题：操作取广义表的表尾就是将广义表中最后一个元素值返回。选项：A:对B:错答案:【错】6、问题：若广义表S的表头是空表，则S是一个空表。选项：A:对B:错答案:【错】7、问题：下面说法不正确的是（）。选项：A:广义表的表头总是一个广义表B:广义表难以用顺序存储结构实现C:广义表可以看作是一个多层次结构D:广义表的表尾总是一个广义表答案:【广义表的表头总是一个广义表】第五章单元测试1、问题：二叉树是非线性数据结构，所以。选项：A:顺序存储结构和链式存储结构都能存储B:它不能用链式存储结构存储C:它不能用顺序存储结构存储D:顺序存储结构和链式存储结构都不能使用答案:【顺序存储结构和链式存储结构都能存储】2、问题：二叉树中所有结点个数是2k-1-1，其中k是树的深度。选项：A:对B:错答案:【错】3、问题：二叉树中每个结点有两棵非空子树或有两棵空子树。选项：A:错B:对答案:【错】4、问题：在只有度为0和度为2的二叉树中,设度为0的结点有n0个,度为2的结点有n2个,则有n0=n2+1。选项：A:对B:错答案:【对】5、问题：树中所有结点的度之和等于所有结点数减1。选项：A:对B:错答案:【对】6123123、问题：设森林F中有4棵树,第、、、4棵树的结点个数分别为n、n、n、n4,当把森林F转换成一棵二叉树后,其根结点的左子树中有n1个结点。选项：A:错B:对答案:【错】7、问题：设树的叶子结点数为m,则结点总数为2m-1。选项：A:错B:对答案:【对】8、问题：某二叉树中序序列为后序序列为DBEFCA,则二叉树对应的森林包括()棵树。选项：A:2B:1C:4D:3答案:【3】9、问题：若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是()。选项：B:15C:不能确定D:9答案:【】10、问题：任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()。选项：A:不发生改变B:发生改变C:以上都不对D:不能确定答案:【不发生改变】11、问题：设某棵二叉树的高度为9,则该二叉树上叶子结点最多有()。选项：B:256C:1023D:512答案:【256】12、问题：若完全二叉树的结点个数为100,则第60个结点的度为()。选项：A:1B:2C:不确定D:0答案:【0】13、问题：树的基本遍历策略分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树,其中结论()是正确的。选项：A:以上都不对B:树的先根遍历序列与其对应的二叉树的中序遍历序列相同C:树的后根遍历序列与其对应的二叉树的后序遍历序列相同D:树的先根遍历序列与其对应的二叉树的先序遍历序列相同答案:【树的先根遍历序列与其对应的二叉树的先序遍历序列相同】14、问题：某二叉树的先序和后序遍历序列正好相反,则该二叉树一定是()。选项：A:二叉排序树B:完全二叉树C:空或只有一个结点D:深度等于其结点数答案:【深度等于其结点数】15、问题：一棵二叉树的高度为h,所有结点的度或为0或为2,则这棵二叉树最少有()个结点。选项：A:2h-1B:h+1C:2h+1D:2h答案:【2h-1】16、问题：如果一棵二叉树中所有结点的值都大于其左子树中的所有结点的值,且小于其右子树中所有结点的值,现欲得到各个结点的递增序列,采用的方法是()。选项：A:前序遍历B:后序遍历C:中序遍历D:层次遍历答案:【中序遍历】17、问题：设n,m为一棵二叉树上的两个结点,在中序遍历中,n在m前的条件是()。选项：A:n在m的左子树上B:n是m的祖先C:n是m的子孙D:n在m右子树上答案:【n在m的左子树上】18、问题：深度为5的二叉树至多有()个结点。选项：A:10B:32C:16D:31答案:【31】19、问题：由权值分别为11、86、、2、5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()。选项：A:53B:71C:48D:24答案:【71】20、问题：如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结点,那么该完全二叉树共有多少个结点?()选项：A:71B:39C:31D:63答案:【39】21、问题：某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为则后序遍历序列为（)。选项：A:BDGAECHFB:GDBECFHAC:GDBEHFCAD:BDGCEFHA答案:【GDBEHFCA】22、问题：一个具有1025个结点的二叉树的高h为()。选项：至1025之间C:10至1024之间D:10答案:【至1025之间】2123、问题：设森林中有三棵树,第一、二、三棵树的结点个数分别为n、n、n3,那么将森林转换成二叉树后,其根结点的右子树上有()个结点。选项：A:n1B:n1-1C:其他情况D:n2+n3答案:【n2+n3】第六章单元测试1、问题：任何一个无向连通图的最小生成树选项：A:一定有多棵B:只有一棵C:一棵或多棵D:可能不存在答案:【一棵或多棵】2、问题：用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。选项：A:栈B:图C:树D:队列答案:【队列】3、问题：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。选项：A:1/2B:1C:4D:2答案:【1】4（、问题：已知有向图，其中V={V1，V2，V3，V4，V5，V6，V7},E={，,,,,,,,}，G的拓扑有序序列是）。选项：A:V1，V3，V2，V6，V4，V5，V7B:V1，V3，V4，V6，V2，V5，V7C:V1，V2，V5，V3，V4，V6，V7D:V1，V3，V4，V5，V2，V6，V7答案:【V1，V3，V4，V6，V2，V5，V7】5、问题：对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。选项：A:由n-1条权值之和最小的边构成的连通子图B:由n个顶点构成的边的权值之和最小的连通子图C:由n-1条权值最小的边构成的子图D:由n-1条权值之和最小的边构成的子图答案:【由n个顶点构成的边的权值之和最小的连通子图】6、问题：用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。选项：A:错B:对答案:【对】7、问题：如果有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。选项：A:对B:错答案:【错】8、问题：一个非空图可以没有边，但不能没有顶点。选项：A:错B:对答案:【对】9、问题：有n-1条边的图肯定都是生成树。选项：A:错B:对答案:【错】10、问题：n个顶点的完全有向图含有边的数目是（）。选项：A:n*nB:n(n-1)C:n/2D:n(n+1)答案:【n(n-1)】11、问题：在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（）。选项：A:顶点v的度B:顶点v的出度C:依附于顶点v的边数D:顶点v的入度答案:【顶点v的入度】12、问题：对一个无向图进行深度优先搜索时，得到的搜索序列是唯一的。选项：A:对B:错答案:【错】13、问题：G是一个非连通无向图，有28条边，则G至少有（）个顶点。选项：A:7B:8C:10D:9答案:【9】14、问题：对于一个有n个顶点，e条边的有向图，采用邻接表存储，对其进行广度优先搜索，算法的时间复杂度是（）。选项：A:O(n*e)B:O(e)C:O(n)D:O(n+e)答案:【O(n+e)】15、问题：下列关于无向连通图的叙述中，正确的是（）。所有顶点的度数之和是偶数边数大于顶点数减1至少有一个顶点的度是1选项：A:a和bB:只有cC:只有aD:a和c答案:【只有a】第七章单元测试1、问题：有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分法查找值82的结点时，（）次比较后查找成功。选项：A:1B:4C:8D:2答案:【4】2、问题：若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为()。选项：A:dB:(d+1)/mC:(d+1)%mD:d+1答案:【(d+1)%m】3、问题：若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。选项：A:4B:12C:8D:13答案:【12】4、问题：从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为()。选项：A:O(n)B:O(1)C:O(log2n)D:O(n2)答案:【O(n)】5、问题：对具有n个元素的有序表采用折半查找，则算法的时间复杂度为()。选项：A:O(logn)B:O(n)C:O(n2)D:O(1)答案:【O(logn)】6、问题：对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为()。选项：A:4B:6C:5D:3答案:【4】7、问题：二叉排序树的左右子树都是二叉排序树。选项：A:错B:对答案:【对】8、问题：若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为()。选项：A:nB:(n-1)/2C:n+1D:(n+1)/2答案:【(n+1)/2】9、问题：具有12个关键字的有序表，折半查找的平均查找长度是（）。选项：A:5B:3.1C:4D:2.5答案:【3.1】10、问题：下面关于哈希查找的说法正确的是（）。选项：A:不存在特别好和特别坏的哈希函数，要视情况而定B:除留余数法是所有哈希函数中最好的C:哈希函数构造的越复杂越好，因为这样随机性好，冲突小D:若需要在一个哈希表中删去一个元素，不管何种方法解决冲突都只要将该元素删去即可答案:【不存在特别好和特别坏的哈希函数，要视情况而定】11、问题：将10个元素散列到长度为100000的哈希表中，则（）产生冲突。选项：A:仍可能会B:一定会C:一定不会答案:【仍可能会】12、问题：完全二叉树肯定是平衡二叉树。选项：A:错B:对答案:【错】13、问题：查找n个元素的有序表时，最有效的查找方法是（）。选项：A:二叉排序树B:折半查找C:分块查找D:顺序查找答案:【折半查找】14、问题：当在一个有序顺序存储表中查找一个数据时，既可用折半查找，也可以用顺序查找，但前者比后者的查找速度（）。选项：A:取决于表递增还是递减B:一定快C:一定慢D:大部分情况下快答案:【大部分情况下快】15、问题：有n个数据存在在一维数组a中，进行顺序查找时，这n个数据的排列有序或无序其平均查找长度不同。选项：A:对B:错答案:【错】16、问题：n个结点的二叉排序树有多种形态，其中高度最小的二叉排序树是最佳的。选项：A:对B:错答案:【对】17、问题：假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行（）次探测。选项：A:k-1B:kC:k(k+1)/2D:k+1答案:【k(k+1)/2】第八章单元测试1、问题：如果对n个元素进行直接选择排序，则进行任一趟排序的进程中，为寻找最小值元素所需要的时间复杂度为（）选项：A:O(logn)B:O(n2)C:O(n)D:O(1)答案:【O(n)】2、问题：下列排序算法中，其中（）是稳定的。选项：A:快速排序，冒泡排序B:快速排序，堆排序C:归并排序，冒泡排序D:简单选择排序，归并排序答案:【归并排序，冒泡排序】3、问题：下列序列中，（）是执行第一趟快速排序后所得的序列。选项：A:[27，38，73]49[93，18]B:[93，38，18]49[27，73]C:[27，38，18]49[93，73]D:[27，38，93]49[18，73]答案:【[27，38，18]49[93，73]】4、问题：(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(-1，9，7，8，20，15，4)，则采用的排序方法是（）。选项：A:简单选择排序B:直接插入排序C:快速排序D:希尔排序答案:【简单选择排序】5、问题：从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的排序方法称为（）。选项：A:堆排序B:选择排序C:希尔排序D:插入排序答案:【插入