数据结构 复习题及答案

一、选择题1、一个n个顶点的无向连通图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn2、以下数据结构中，（）是非线性数据结构。A．树B．字符串C．队列D．栈3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。A．n–i+1B．n–iC．iD．i-14、与线性表的链接存贮不相符合的特性是（）。A．便于插、删运算B．需要连续的存贮空间C．只能顺序查找D．存贮空间动态分配5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front+rear+m)%mD．(rear-front)%m6、一个有n个顶点的无向图最多有()条边。A．n(n-1)/2B．n(n-1)C．n-1D．n+17、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。A．1，2，4，3B．2，1，3，4C．1，4，3，2D．4，3，1，2，8、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．初等结构、构造型结构C．线性结构、非线性结构D．树型结构、图型结构9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）A．空或只有一个根结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。A．将邻接矩阵的第i行删除B．将邻接矩阵的第i行元素全部置零C．将邻接矩阵的第i列删除D．将邻接矩阵的第i列元素全部置零11、算法分析的两个主要方面是（）A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以13、具有6个顶点的无向连通图的生成树应有（）条边。A．5B．6C．7D．814、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。A．CBAB．CABC．BCAD．ACB15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。A．head==NULLB．head-next==NULLC．head-next==headD．head！=NULL16、栈和队都是（）A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构17、在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④18、以下数据结构中，（）是非线性数据结构。A．树B．字符串C．队列D．栈19、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M320、在下面的程序段的时间复杂度为（）。for(inti=1;in;i++)for(intj=1;jn;j++)a[i][j]=i*j;A．O(m2)B．O(m*n)C．O(n2)D．O(log2n)21、二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-122、下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A．选择B．冒泡C．归并D．堆23、线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()A．110B．108C．100D．12024、栈中元素的进出原则是（）。Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出25、下列字符串中（）不是．．串ABCABDEABX的子串。A．ABCB．BXC．ABD．AD26、对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度27、设二维数组A[1..5,1..6]的每个元素占5个存储单元，将其按行优先顺序存储在起始地址是1000的连续内存单元中，则A[5,5]的存储地址是（）。A．1140B．1145C．1120D．112528、外排序是指（）。A．数据量很大，排序时要借外存进行的排序方法B．不需要使用内存的排序方法C．数据量很大，需要人工干预的排序方法D．没有正确答案29、下列数据中不可能是平衡二叉树上结点的平衡因子的是（）。A．-1B．0C．1D．230、在下面的程序段的时间复杂度为（）。for(inti=1;im;i++)for(intj=1;jn;j++)a[i][j]=i*j;A．O(m2)B．O(m*n)C．O(n2)D．O(log2n)31、深度为K的二叉树最多含有结点数为（）A．2kB．2k-1-1C．2k-1D．2k-132、设二维数组A[0..10,0..20]按行优先顺序存储，每个元素占4个存储单元，A[2,1]的存储地址是1000，则A[5,6]的存储地址是（）。A．1021B．1056C．1260D．120033、有三个结点的二叉树的基本形态有（）种。A．2B．3C．4D．534、有三个结点的树的基本形态有（）种。A．2B．3C．4D．535、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定36、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）A．41B．82C．113D．12237、对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）A．该树一定是一棵完全二叉树B．树中一定没有度为1的结点C．树中两个权值最小的结点一定是兄弟结点D．树中任一非叶结点的权值一定不小于下一任一结点的权值38、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front+rear+m)%mD．(rear-front)%m39、若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A．dcebfaB．cbdaefC．dbcaefD．afedcb40、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（）A．bacdeB．dbaceC．dbcaeD．ecbad41、散列表中的冲突是指（）A．两个元素具有相同的序号B．两个元素的关键字相同，而其他属性相同C．相同的关键字对应不相同的存储地址D．数据元素的地址相同42、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。43、非空的循环单链表head的尾结点p↑满足（）。A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head44、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;45、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A．1，2，4，3，B．2，1，3，4，C．1，4，3，2，D．4，3，1，2，E．3，2，1，4，46、栈在（）中应用。A．递归调用B．子程序调用C．表达式求值D．A，B，C47、下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网48、下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示49、线性表是具有n个（C）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项50、输入序列为ABC，可以变为CBA时，经过的栈操作为（B）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop51、从邻接阵矩可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则共有（）条边。①．A．9B．3C．6D．1E．以上答案均不正确②．A．5B．4C．3D．2E．以上答案均不正确③．A．5B．4C．3D．2E．以上答案均不正确52、最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（A）。A.(rear+1)%n=frontB.rear=frontC．rear+1=frontD.(rear-l)%n=front010101010A53、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(A)。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front54、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（B）。A.(rear+1)%n=frontB.rear=frontC．rear+1=frontD.(rear-l)%n=front55、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（C）A．5B．6C．7D．856、有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-157、有关二叉树下列说法正确的是（A）A．一棵二叉树的度可以小于2B．二叉树中至少有一个结点的度为2C．二叉树的度为2D．二叉树中任何一个结点的度都为258．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是(A)。A.选择B.冒泡C.快速D.插入59、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（C）排序。A.选择B.快速C.希尔D.冒泡60、若序列{15，9，7，8，20，-1，4}经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（C）排序。A．选择B.堆C.直接插入D.冒泡61、下列排序算法中(B)不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序62、下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆63、以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)64、下列四个序列中，哪一个是堆（C）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1565、散列文件使用散列函