21秋学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业试卷总分:100得分:100一、单选题(共30道试题,共60分)1.不含任何结点的空树（）A.是一棵树B.是一棵二叉树C.是一棵树也是一棵二叉树D.既不是树也不是二叉树答案:C2.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）{图}A.0132B.0231C.0321D.0123答案:D3.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答案:D4.对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序答案:B5.有8个结点的无向连通图最少有（）条边A.5B.6C.7D.8答案:C6.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)答案:B7.将5个不同的数据进行排序，至多需要比较()次A.8B.9C.10D.25答案:C8.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.4答案:B9.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序答案:A10.设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）{图}A.循环链表B.单链表C.双向循环链表D.双向链表答案:B11.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）{图}A.0243651B.0136425C.0423156D.0134256答案:B12.链表适用于()查找A.顺序B.二分法C.顺序，也能二分法D.随机答案:A13.有8个结点的有向完全图有（）条边A.14B.28C.56D.112答案:C14.快速排序在下列哪种情况下最易发挥其长处()A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊答案:C15.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50答案:A16.在表长为ｎ的链表中进行线性查找，它的平均查找长度为（）A.ＡＳＬ＝ｎB.ＡＳＬ＝（ｎ＋１）／２C.{图}D.{图}答案:B17.栈中元素的进出原则是（）A.先进先出B.后进先出C.栈空则进D.栈满则出答案:B18.下述几种排序方法中，要求内存最大的是()A.插入排序B.快速排序C.归并排序D.选择排序答案:C19.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个A.n-1B.nC.n+1D.n+2答案:C20.链接存储的存储结构所占存储空间（）A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答案:A21.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（）{图}A.0243156B.0136542C.0423165D.0361542答案:C22.对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。A.3B.4C.5D.6答案:C23.一棵具有n个结点的完全二叉树的树高度（深度）是（）A.{图}B.{图}C.{图}D.{图}答案:A24.广度优先遍历类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.层次遍历答案:D25.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）{图}A.0321B.0123C.0132D.0312答案:A26.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）{图}A.0243165B.0135642C.0123465D.0123456答案:C27.已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（）{图}A.0243156B.0135642C.0423165D.0134256答案:D28.从未排序序列中挑选元素，并将其依次插...
