数据结构07～08第二学期b卷

《数据结构07～08第二学期b卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、领导审批并签名B卷广州大学2007-2008学年第二学期考试卷课程《数据结构》考试形式（闭卷，考试）物理与电子工程学院电子系电子061、062、063专业学号姓名题号一二三四总分评卷人1234100分数1520678935评分一、判断题（对打√，错打×。每题1分，共15分）1、在单链表中，任何两个元素的存储位置之间都有固定的联系，因此以从头结点进行查找任何一个元素。(T)2、线性表的线性存储结构优于链表存储结构。(F)3、完全二叉树的某结点若无左孩子，则必定是叶子结点。(T)4、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。(T)5、在图结构中，结点可以没有任何前趋和后继。(

2、T)6、在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。(F)7、结点数固定的二叉树中，完全二叉树具有最小路径长度(T)。8、中序线索树中，右线索若不为空，则一定指向其双亲结点(F)。9、有向图用邻接矩阵表示，容易实现求结点度数的操作(T)。10、二叉树是度最大为2的有序树(T)。11、按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问(T)12、若有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在(T)。13、若有向图G中包含一个环，则G的结点间不存在拓扑排序(T)。14、图的拓扑排序序列是唯一的(F)。15、网络的最小代价生成树是

3、惟一的(F)。二、选择题（每题2分，共20分）1．在数据结构中，从逻辑上可以把数据结构分成（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．常对数组进行的两种基本操作是(C)。A．建立与删除B．索引和修改C．查找和修改D．查找和索引3．下列结论中不正确的是(B)。4A．按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问。B．一个图按广度优先搜索法遍历的结果是唯一的。C．无向图的邻接表表示法中，表中结点的数目是图中边的条数2倍。D．图的多重邻接表表示法中，表中结点的数目是图中边的条数。4．已知一个图如下所示，则由该图得到的

4、一种拓扑序列为（A）。123456（A）v1,v4,v6,v2,v5,v3(B)v1,v2,v3,v4,v5,v6(C)v1,v4,v2,v3,v6,v5(D)v1,v2,v4,v6,v3,v55．设有一个堆栈，元素进栈的次序为12345。不可能得到(C)出栈序列：A．12345B．54321C．45312D．435216．设n为正整数。下列程序段中前置以记号@的语句的频度为（C）。i=1;k=0;while(i

5、简单图8．下列结论中正确的是(C)。A．在无向图中，边的条数是结点度数之和。B．用Prim算法和Kruskal算法求得的图的最小生成树相同。C．在图的邻接多重表表示中，任意一条边只用一个表目表示。D．在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。9．循环队列Q采用数组空间Q.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判断此循环队列Q为空的条件是(C)。A．Q.rear–Q.front==nB．Q.rear–Q.front-1==nC．Q.rear==Q.frontD．Q.rear+1==Q.frontabecdf10．如图所示，

6、若从顶点a出发对图按深度优先搜索法进行遍历，则可能得到的一种顶点序列为(D)。A．abecdfB．acfebdC．acebfdD．acfdeb三、问答题（共30分）1．指出树和二叉树的主要差别。对于一个有1004个结点的二叉树，树叶最多有多少个？最少有多少个？（4分）42．画出和下列已知序列对应的森林F（6分）：森林的先序次序访问序列为：ABCDEFGHIJKL；森林的中序次序访问序列为：CBEFDGAJIKLH。3．已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD13。请写出用线性探测法处理冲突构造所得的哈希表。（

7、11分）4．图G的邻接矩阵如下所示：4试画出该图，并使用Kruskal算法构造出一棵最小生成树。（9分）四、程序题（第1题15分，第2题20分）1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删除结点空间（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。0iugf1、编写递归