数据结构复习题及答案.pdfVIP

一、选择题 1、一个n 个顶点的无向连通图，其边的个数至少为（ ）。 A ．n-1 B ．n C ．n+1 D ．nlogn 2、以下数据结构中，（）是非线性数据结构。 A ．树 B ．字符串 C ．队列 D ．栈 3、在长度为n 的顺序表的第i个位置上插入一个元素（1≤i ≤n+1 ），元素的移动次数为（ ）。 A ．n –i+1 B ．n –i C ． i D ． i-1 4 、与线性表的链接存贮不相符合的特性是（ ）。 A ．便于插、删运算 B ．需要连续的存贮空间 C ．只能顺序查找 D ．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear ，则当前队列中的元素个数 为（ ）。 A ．(rear-front+m)%m B ．rear-front+1 C ．(front+rear+m)%m D ．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A ．n(n-1)/2 B ．n (n-1) C ．n-1 D ．n+1 7 、设栈的入栈序列是1，2，3，4 ，则（ ）不可能是其出栈序列。 A ．1，2，4 ，3 B ．2，1，3，4 C ．1，4 ，3，2 D ．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 ．5 B ．6 C ．7 D ．8 14、设栈的输入序列是A 、B 、C，则（ ）不可能是其出栈序列。 A ．CBA B ．CAB C ．BCA D ．ACB 15、有一个含头结点的单链表，头指针为head ，则判断其是否为空的条件为（ ）。 A ．head==NULL B ．head-next==NULL C ．head-next== head D ．head ！=NULL 16、栈和队都是（ ） A ．顺序存储的线性结构 B ．链式存储的非线性结构 C ．限制存取点的线性结构 D ．限制存取点的非线性结构 17、在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2 ； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 18、以下数据结构中，（ ）是非线性数据结构。 A ．树 B ．字符串 C ．队列 D ．栈 19、设森林F 中有三棵树，第