《数据结构复习题及答案》由会员分享，可在线阅读，更多相关《数据结构复习题及答案（6页珍藏版）》请在金锄头文库上搜索。
1、一、选择题一、选择题 1、一个 n 个顶点的无向连通图，其边的个数至少为（ ） 。 An-1 Bn Cn+1 Dnlogn 2、以下数据结构中， （ ）是非线性数据结构。 A树 B字符串 C队列 D栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1in+1） ，元素的移动次数为（ ） 。 An i+1 Bn i C i D i-1 4、与线性表的链接存贮不相符合的特性是（ ） 。 A便于插、删运算 B需要连续的存贮空间 C只能顺序查找 D存贮空间动态分配 5、顺序存放的循环队列的元素以数组Am存放,其头尾指针分别为front和rear，则当前队列中的元素个 数为（ ） 。 A(rear-
2、front+m)%m Brear-front+1 C(front+rear+m)%m D(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 An(n-1)/2 Bn (n-1) Cn-1 Dn+1 7、设栈的入栈序列是1，2，3，4，则（ ）不可能是其出栈序列。 A1，2，4，3 B2，1，3，4 C1，4，3，2 D4，3，1，2， 8、从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B初等结构、构造型结构 C线性结构、非线性结构 D树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ） A空或只有一个根结点 B高度等于其
3、结点数 C任一结点无左孩子 D任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（ ） 。 A将邻接矩阵的第 i 行删除 B将邻接矩阵的第 i 行元素全部置零 C将邻接矩阵的第 i 列删除 D将邻接矩阵的第 i 列元素全部置零 11、算法分析的两个主要方面是（ ） A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续或不连续都可以 13、具有 6 个顶点的无向连通图的生成树应有（ ）条
4、边。 A5 B6 C7 D8 14、设栈的输入序列是 A、B、C，则（ ）不可能是其出栈序列。 ACBA BCAB CBCA DACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（ ） 。 Ahead=NULL Bhead-next=NULL Chead-next= head Dhead ！=NULL 16、栈和队都是（ ） A顺序存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 17、在下述结论中，正确的是（ ） 只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换; 深度为K的完全二叉树结点个数小
5、于或等于深度相同的满二叉树。 A B C D 18、以下数据结构中， （ ）是非线性数据结构。A树 B字符串 C队列 D栈 19、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二 叉树根结点的右子树上的结点个数是（ ） 。 AM1 BM1+M2 CM3 DM2+M3 20、在下面的程序段的时间复杂度为（ ） 。 for (int i=1;inext=s;s-next=p-next; Bs-next=p-next;p-next=s; Cp-next=s;p-next=s-next; Dp-next=s-next;p-next=s; 45、设栈的输入序列是
6、1，2，3，4,则（）不可能是其出栈序列。 A1，2，4，3， B2，1，3，4， C1，4，3，2， D4，3，1，2， E3，2，1，4， 46、栈在（ ）中应用。 A递归调用 B子程序调用 C表达式求值 DA，B，C 47、下列哪一种图的邻接矩阵是对称矩阵？（ ） A有向图 B无向图 CAOV网 DAOE网 48、下述哪一条是顺序存储结构的优点？（ A ） A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 49、线性表是具有 n 个（ C ）的有限序列（n0） 。 A表元素 B字符 C数据元素 D数据项 E信息项 50、输入序列为 ABC，可以变为 CB
7、A 时，经过的栈操作为（ B ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop51、从邻接阵矩可以看出，该图共有（ ）个顶点；如果是有向图该图共有（ ）条弧； 如果是无向图，则共有（ ）条边。 A9 B3 C6 D1 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确 52、最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队
8、满的条件是（ A ） 。 A. (rear+1) %n=front B. rear=front 010101010 ACrear+1=front D. (rear-l) % n=front 53、循环队列 A0.m-1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是 ( A )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 54、最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（ B ） 。 A. (rear+1) %n=front
9、B. rear=front Crear+1=front D. (rear-l) % n=front 55、设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为（ C ）A5 B6 C7 D8 56、有 n 个叶子的哈夫曼树的结点总数为（ D ） 。 A不确定 B2n C2n+1 D2n-1 57、有关二叉树下列说法正确的是（ A ） A一棵二叉树的度可以小于2 B二叉树中至少有一个结点的度为2 C二叉树的度为2 D二叉树中任何一个结点的度都为2 58对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）
10、 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( 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、下列排
11、序算法中( 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,
12、10,20) 64、下列四个序列中，哪一个是堆（ C ） 。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 65、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的 关系，则选择好的（ D ）方法是散列文件的关键。 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理参考答案参考答案: 0110: A A A B A A D C A B 1120: A D A B B
13、 C D A D C 2130: C C B B D C A A D B 3140: D C D A B B BA D C 4147: D B A B D D B 二判断题二判断题 ( )1、算法分析考虑的两个主要因素是空间复杂性和时间复杂性。 ( )2、非线性数据结构的存储只能选用链式存储结构。 ( )3、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。 ( )4、哈希文件是一种直接存取文件。 ( )5、含有 n 个结点的二叉排序树的平均查找长度和树的形态有关。 ( )6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 ( )7、循环链表不是线性表。 ( )8、文件是记录的集合，文件上的操作主要有两类：检索和维护。 ( )9、对
