20春学期(1709、1803、1809、1903、1909、2003)《数据结构》在线作业DAB.doc

第页共NUMPAGES7页
20春学期（1709、1803、1809、1903、1909、2003）《数据结构》在线作业DAB

20春学期（1709、1803、1809、1903、1909、2003）《数据结构》在线作业---------------------------单选题1.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以正确答案:D2.一棵具有n个结点的完全二叉树的树高度（深度）是（）A.B.C.D.正确答案:A3.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()A.110B.108C.100D.120正确答案:B4.折半搜索与二叉搜索树的时间性能()A.相同B.完全不同C.有时不相同D.数量级都是O（log2n）正确答案:C5.对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
A.3B.4C.5D.6正确答案:C6.有8个结点的无向图最多有（）条边A.14B.28C.56D.112正确答案:B7.深度优先遍历类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.层次遍历正确答案:A8.用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的A.栈B.队列C.树D.图正确答案:A9.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2B.1C.2D.4正确答案:B10.设串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正确答案:D11.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位臵，ｒ为队尾元素的位臵，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A.r－fB.（n＋f－r）%nC.n＋r－fD.（n＋r－f）%n正确答案:D12.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）A.0321B.0123C.0132D.0312正确答案:A13.具有n(n0)个结点的完全二叉树的深度为（）A.B.C.D.正确答案:C14.下述几种排序方法中，要求内存最大的是()A.插入排序B.快速排序C.归并排序D.选择排序正确答案:C15.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个A.n-1B.nC.n+1D.n+2正确答案:C16.链接存储的存储结构所占存储空间（）A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数正确答案:A17.链表是一种采用存储结构存储的线性表A.顺序B.链式C.星式D.网状正确答案:B18.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构正确答案:C19.任何一个无向连通图的最小生成树()A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在正确答案:A20.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)正确答案:B21.有8个结点的无向连通图最少有（）条边A.5B.6C.7D.8正确答案:C22.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的A.栈B.队列C.树D.图正确答案:B23.单链表的存储密度（）A.大于1B.等于1C.小于1D.不能确定正确答案:C24.链表适用于()查找A.顺序B.二分法C.顺序，也能二分法D.随机正确答案:A25.在一个图中，所有顶点的度数之和等于图的边数的（）倍A.1/2B.1C.2D.4正确答案:C26.设有两个串p和q，求q在p中首次出现的位臵的运算称作（）A.连接B.模式匹配C.求子串D.求串长正确答案:B27.堆的形状是一棵()A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树正确答案:C28.判定一个队列QU（最多元素为m0）为满队列的条件是（）A.QU-rear－QU-front==m0B.QU-rear－QU-front－1==m0C.QU-front==QU-rearD.QU-front==QU-rear+1正确答案:A29.从未排序序列中挑选元素，并将其依