数据结构复习题参考答案.doc

《数据结构复习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构总复习第一部分课后习题第一章课后习题P161、2、5、6、9第三章课后习题P662、3第四章课后习题P881第五章课后习题P1021、2第六章课后习题P134-1351、3、16、18完成P137实验二构造哈夫曼编码第七章课后习题P1771、2、4、8、10第二部分综合习题一、单项选择题1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）A.栈B.队列C.树D.图2.下面程序段的时间复杂度为（B）for(i=0;i

2、O(m+n)3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（A）A.p->next==headB.p->next->next==headC.p->next==NULLD.p==head第9页共9页4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（D）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX5.两个字符串相等的条件是（D）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为

3、（D）A.0B.1C.48D.497．算法分析的目的是：（C）（A）找出数据结构的合理性（B）研究算法中输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性8．用链表表示线性表的优点是：（C）（A）便于随机存取（B）花费的存储空间比顺序表少（C）便于插入和删除（D）数据元素的物理顺序与逻辑顺序相同9．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxsize为数组的最大长度，队满的条件是：（D）（A）front=rear（B）rear=maxsize（C）rear=front（D）（rear+1）%maxsize=front10．若

4、已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为：（A）（A）CDBGFEA（B）CDBFGEA（C）CDBAGFE（D）BCDAGFE11．执行下列程序段，执行S的次数（S这段程序的时间复杂度）是：（D）for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)第9页共9页S;（A）n2（B）n2/2（C）n(n+1)（D）n(n+1)/212．以下数据结构中哪一个是非线性结构的是：（D）（A）队列（B）栈（C）线性表（D）图13.设有6个结点的无向图，该图至少有多少条边才能确保是一个连通图：（A）（A）5（B）6（C）7

5、（D）814．树形结构数据元素之间的关系是：（C）（A）一对一关系（B）多对多关系（C）一对多关系（D）多对一关系15．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是：（C）（A）edcba（B）decba（C）dceab（D）abcde16．静态查找和动态查找的根本区别在于：（B）（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储的实现不一样17．关键路径是AOE网中：（A）（A）从源点到终点的最长路径（B）从源点到终点的最短路径（C）最长的回路（D）最短的回路18．采用折半查找方法进行查找，数据文件为，且限于；（

6、A）（A）有序表顺序存储结构（B）有序表链式存储结构（C）随机表顺序存储结构（D）随机表链式存储结构19．一个高度为h的完全二叉树共有n个结点，其中m个叶子结点，则下列式子成立的是（D）（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2m-120．下列说法中不正确的是：（C）（A）数组时一种线性结构（B）数组是一种定长的线性结构（C）除了插入和删除操作外，数组的基本操作还有存取、修改、检索和排序等第9页共9页（D）数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作21．设无向图G有n个顶点e条边，则该无向图中所有顶点的度之和为：（D）（A）n（B）e（C）

7、2n（D）2eABCDEF22．对下面的无向图进行广度优先搜索后所得到的顶点访问序列，正确的是：（A）（A）ABDEFC（B）ABFEDC（C）ADCBEF（D）ADCBFE23.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D）存储方式最节省时间。A单链表B双链表C单向循环D顺序表24.串是任意有限个（C）A符号构成的序列B符号构成的集合C字符构成的序列D字符构成的集合25.设矩阵A（aij，l≤i,j≤10）的元素满足：aij≠0(i≥j,l≤i,j≤10)ai