数据结构 复习题及答案

《数据结构 复习题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择题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．

2、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．任一结点无左

3、孩子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、设栈的

4、输入序列是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．①

5、②③B．②③④C．②④D．①④18、以下数据结构中，（）是非线性数据结构。A．树B．字符串C．队列D．栈19、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M320、在下面的程序段的时间复杂度为（）。for(inti=1;i

6、、下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A．选择B．冒泡C．归并D．堆23、线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()A．110B．108C．100D．12024、栈中元素的进出原则是（）。Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出25、下列字符串中（）不是串"ABCABDEABX"的子串。A．"ABC"B．"BX"C．"AB"D．"AD"26、对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度27、设二维数组A[1..5,1..6]的

7、每个元素占5个存储单元，将其按行优先顺序存储在起始地址是1000的连续内存单元中，则A[5,5]的存储地址是（）。A．1140B．1145C．1120D．112528、外排序是指（）。A．数据量很大，排序时要借外存进行的排序方法B．不需要使用内存的排序方法C．数据量很大，需要人工干预的排序方法D．没有正确答案29、下列数据中不可能是平衡二叉树上结点的平衡因子的是（）。A．-1B．0C．1D．230、在下面的程序段的时间复杂度为（）。for(inti=1;i