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

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。（）A.正确B.错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。（）A.正确B.错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）A.正确B.错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。（）A.正确B.错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）A.正确B.错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）A.正确B.错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）A.正确B.错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）A.正确B.错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。()A.正确B.错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。（）A.正确B.错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）A.正确B.错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。（）A.正确B.错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）A.正确B.错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。（）A.正确B.错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）A.正确B.错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）A.正确B.错误答案:【B】二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)答案:【B】18、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素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个记录的文件进行快速排序，所需要的辅助存储空间大致为()A.O（1）B.O（n）C.O（1og2n）D.O（n2）答案:【C】21、用链接方式存储的队列，在进行插入运算时()A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改答案:【D】22、设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（）。A.线性结构B.树型结构C.物理结构D.图型结构答案:【B】23、以下数据结构中哪一个是非线性结构？()A.队列B.栈C.线性表D.二叉树答案:【D】24、下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是A.堆排序B.冒泡排序C.直接选择排序D.快速排序答案:【C】25、设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。A.n-iB.n+l-iC.n-1-iD.i答案:【A】26、设指针q指向单链表中结点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个结点，则该完全二叉树的深度为（）。A.8B.7C.6D.5答案:【B】28、设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（）。A.O(1)B.O(log2n)C.O(nlog2n)D.O(n2)答案:【B】29、设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。A.n-iB.n-1-iC.n+l-iD.不能确定答案:【C】30、树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答案:【C】31、下列各种排序算法中平均时间复杂度为O(n2)是（）。A.快速排序B.堆排序C.归并排序D.冒泡排序答案:【D】32、设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8答案:【A】33、设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。A.单向链表B.单向循环链表C.双向链表D.双向循环链表答案:【D】34、设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（）。A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数答案:【B】35、在二叉排序树中插入一个结点的时间复杂度为（）。A.O(1)B.O(n)C.O(log2n)D.O(n2)答案:【C】36、（）是线性表。A.(1,2,3,…)B.{a,b,c,d,e}C.(1,3,5,7)D.{‘A’,’B’,’C’}答案:【C】37、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1答案:【A】38、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A.2nB.nC.n/2D.n(n-1)答案:【B】39、设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A.25B.10C.7D.1答案:【B】40、设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。A.O(n)B.O(n2)C.O(nlog2n)D.O(1og2n)答案:【D】41、设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，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，则通过栈的作用后可以得到的输出序列为（）。A.5，3，4，6，1，2B.3，2，5，6，4，1C.3，1，2，5，4，6D.1，5，4，6，2，3答案:【B】44、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。A.99B.100C.101D.102答案:【B】45、设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。A.2k-1B.2kC.2k-1D.2k-1答案:【D】46、设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有（）个度数为0的结点。A.5B.6C.7D.8答案:【C】47、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。A.n(n-1)B.n+1C.nD.n(n+1)答案:【C】48、算法必须具备输入、输出和A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法答案:【C】49、图G的某一最小生成树的代价一定小于其他生成树的代价A.一定是B.肯定不是C.不一定是D.都不对答案:【C】50、设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+(m-1)NmC.N2+2N3+3N4+……+(m-1)NmD.2Nl+3N2+……+(m+1)Nm答案:【B】51、下面程序的时间复杂度为（）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}A.O(n)B.O(n2)C.O(n3)D.O(n4)答案:【B】52、函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”答案:【A】53、两个字符串相等的充要条件是（）。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备(A)和(B)两个条件D.以上答案都不对答案:【C】54、把长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为A.O(m)B.O(n)C.O(m+n)D.O(1)答案:【D】55、设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。A.n2B.n(n+1)C.n(n+1)/2D.n(n-1)/2答案:【D】56、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A.快速排序B.堆排序C.归并排序D.插入排序答案:【B】57、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。A.O(log2n)B.O(1)C.O(n2)D.O(n)答案:【D】58、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A.O(n)B.O(n2)C.O(n1/2)D.O(1og2n)答案:【A】59、数据的最小单位是（）。A.数据项B.数据类型C.数据元素D.数据变量答案:【A】60、设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。A.O(n+e)B.O(n2)C.O(ne)D.O(n3)答案:【A】61、某二叉树的后序遍历序列为DABEC、中序遍历序列为DEBAC，则前序遍历为A.ACBEDB.DECABC.DEABCD.CEDBA答案:【D】62、设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。A.p-right=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；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通常情况下最好选择（）。A.99B.97C.91D.93答案:【B】64、二叉树的第k层的结点数最多为()。A.2k-1B.2K+1C.2K-1D.2k-1答案:【D】65、设顺序表的长度为n，则顺序查找的平均比较次数为（）。A.n