数据结构(本科)武汉理工大学在线作业

1、-WORD格式-可编写-专业资料-数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。（）正确错误答案:【A】2、调用一次深度优先遍历能够接见到图中的所有极点。（）正确错误答案:【B】3、对连通图进行深度优先遍历能够接见到该图中的所有极点。（）正确错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。（）正确错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）A.正确B.错误答案:【B】6、先序遍历一棵二叉排序树获取的结点序列不用然是有序的序列。（）A.正确B.错误答案:【A】

2、7、不论线性表采用次序储藏结构还是链式储藏结构，删除值为X的结点的时间复杂度均为O(n)。（）A.正确B.错误答案:【A】8、满二叉树必然是完满二叉树，完满二叉树不用然是满二叉树。（）-完满版学习资料分享-WORD格式-可编写-专业资料-正确错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的地址为2。()正确错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。（）正确错误答案:【A】11、分块查找的平均查找长度不但与索引表的长度有关，而且与块的长度有关。（）正确错误答案:【A】12、线性表的次序储藏结构比链式储藏结构更好。（）正确错误答案:【B】13、向二叉排序

3、树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）正确错误答案:【B】14、层次遍历初始堆能够获取一个有序的序列。（）正确错误答案:【B】15、冒泡排序在初始要点字序列为逆序的情况下执行的交换次数最多。（）正确错误答案:【A】16、设初始记录要点字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）正确错误-完满版学习资料分享-WORD格式-可编写-专业资料-答案:【B】二、单项选择(共计60分,每题2.5分)17、在二叉排序树中插入一个要点字值的平均时间复杂度为（）。O(n)O(1og2n)O(nlog2n)O(n2)答案:【B】18、设有序次序表中有n个数据元素，则利用二

4、分查找法查找数据元素X的最多比较次数不高出（）。A.log2n+1B.log2n-1C.log2nD.log2(n+1)答案:【A】19、设用毗邻矩阵A表示有向图G的储藏结构，则有向图G中极点i的入度为（）。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和答案:【B】20、对n个记录的文件进行快速排序，所需要的辅助储藏空间大体为()O（1）O（n）O（1og2n）O（n2）答案:【C】21、用链接方式储藏的队列，在进行插入运算时()-完满版学习资料分享-WORD格式-可编写-专业资料-仅更正头指针头、尾指针都要更正仅更正尾指针头、尾指

5、针可能都要更正答案:【D】22、设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是（）。线性结构树型结构物理结构图型结构答案:【B】23、以下数据结构中哪一个是非线性结构？()队列栈线性表二叉树答案:【D】24、以下排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是堆排序冒泡排序直接选择排序快速排序答案:【C】25、设次序线性表中有n个数据元素，则删除表中第i个元素需要搬动（）个元素。n-in+l-in-1-i-完满版学习资料分享-WORD格式-可编写-专业资料-D.i答案:【A】26、设指针q指向单链

6、表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。A.s-next=p-next；p-next=-sB.q-next=s；s-next=pC.p-next=s-next；s-next=pD.p-next=s；s-next=q答案:【B】27、设一棵完满二叉树中有65个结点，则该完满二叉树的深度为（）。8765答案:【B】28、设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（）。O(1)O(log2n)O(nlog2n)O(n2)答案:【B】29、设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则

7、输出序列中的第i个输出元素是（）。A.n-iB.n-1-iC.n+l-iD.不能够确定答案:【C】30、树最适合用来表示()。-完满版学习资料分享-WORD格式-可编写-专业资料-有序数据元素无序数据元素元素之间拥有分支层次关系的数据元素之间无联系的数据答案:【C】31、以下各种排序算法中平均时间复杂度为O(n2)是（）。快速排序堆排序归并排序冒泡排序答案:【D】32、设有6个结点的无向图，该图最少应有()条边才能保证是一个连通图。5678答案:【A】33、设某链表中最常用的操作是在链表的尾部插入或删除元素，则采用以下（）储藏方式最节约运算时间。单向链表单向循环链表双向链表双向循环链表答案:【

8、D】34、设散列表中有m个储藏单元，散列函数H(key)=key%p，则p最好选择（）。小于等于小于等于小于等于小于等于答案:【B】的最大奇数的最大素数的最大偶数的最大合数35、在二叉排序树中插入一个结点的时间复杂度为（）。O(1)O(n)-完满版学习资料分享-WORD格式-可编写-专业资料-O(log2n)O(n2)答案:【C】36、（）是线性表。A.(1,2,3,)a,b,c,d,e(1,3,5,7)A,B,C答案:【C】37、设某完满无向图中有n个极点，则该完满无向图中有（）条边。n(n-1)/2n(n-1)n2n2-1答案:【A】38、设某无向图有n个极点，则该无向图的毗邻表中有（）个

9、表头结点。2nnn/2n(n-1)答案:【B】39、设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。251071答案:【B】40、设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。O(n)O(n2)O(nlog2n)O(1og2n)-完满版学习资料分享-WORD格式-可编写-专业资料-答案:【D】41、设一组初始记录要点字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录要点字序列进行一趟归并后的结果为（）。15，25，35，50，20，40，80，85，36，7015，

10、25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，85答案:【A】42、设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。A.n-iB.n-1-iC.n+1-iD.不能够确定答案:【C】43、设输入序列为1、2、3、4、5、6，则经过栈的作用后能够获取的输出序列为（）。5，3，4，6，1，23，2，5，6，4，13，1，2，5，4，61，5，4，6，2，3答案:【B】44、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结

11、点。99100101102答案:【B】45、设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。2k-12k2k-12k-1答案:【D】-完满版学习资料分享-WORD格式-可编写-专业资料-46、设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有（）个度数为0的结点。A.5B.6C.7D.8答案:【C】47、设某强连通图中有n个极点，则该强连通图中最少有（）条边。n(n-1)n+1nn(n+1)答案:【C】48、算法必定具备输入、输出和计算方法排序方法解决问题的有限运算步骤程序设计方法答案:【C】49、图G的某一最小生成树的代价必然小于其他生成树的代价

12、必然是必然不是不用然是都不对答案:【C】50、设一棵为Nm，则m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数N0=（）。Nl+N2+Nml+N2+2N3+3N4+(m-1)NmN2+2N3+3N4+(m-1)Nm2Nl+3N2+(m+1)Nm答案:【B】51、下面程序的时间复杂度为（）for（i=1，s=0；i=n；i+）t=1；for(j=1；jright=s；s-left=p；p-right-left=s；s-right=p-right；B.s-left=p；s-right=p-right；p-right=s；p-right-left=s；C.p-right=s；

13、p-right-left=s；s-left=p；s-right=p-right；D.s-left=p；s-right=p-right；p-right-left=s；p-right=s；答案:【A】63、设依照从上到下、从左到右的次序从1开始对完满二叉树进行次序编号，则编号为i结点的左孩子结点的编号为（）。A.2i+1B.2iC.i/2D.2i-1答案:【B】64、设某散列表的长度为100，散列函数H(k)=k%P，则P平时情况下最好选择（）。99979193答案:【B】64、二叉树的第k层的结点数最多为()。2k-12K+12K-12k-1答案:【D】65、设次序表的长度为n，则次序查找的平均

14、比较次数为（）。nn/2-完满版学习资料分享-WORD格式-可编写-专业资料-(n+1)/2(n-1)/2答案:【C】66、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。O(n)O(nlog2n)O(n2)O(1og2n)答案:【C】67、以下四种排序中（）的空间复杂度最大。插入排序冒泡排序堆排序归并排序答案:【D】68、设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。head=0head-next=0head-next=headhead!=0答案:【A】69、若线性表最常用的操作是存取第i个元素的值，则采用_储藏方式节约时间。单链表双链表单循环链表次序表答案:【D】70、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。top=top+1;top=top-1;top-next=top;top=top-next;-完满版学习资料分享-WORD格式-可编写-专业资料-答案:【D】71、在一个单链表中，若P所指节点不是最后节点，在P此后插入S所指节点，则执行A.Snext=Pnext;Pnext=S;B.Pnext=Snext;Snext=P;C.Snext=P;Pnext=S;D.Pnext=S;Snext=P;答案:【A】72、深度为k的完满二叉树中最稀有（）个结点。2k-1-1