数据结构07～08第二学期B卷.doc

领导审批并签名B 卷广州大学2007-2008学年第二学期考试卷课程数据结构考试形式（闭卷，考试）物理与电子工程学院 电子 系 电子061、062、063 专业 学号 姓名 题号一二三四总分评卷人1234100分数1520678935评分一、 判断题（对打，错打。每题1分，共15分）1、 在单链表中，任何两个元素的存储位置之间都有固定的联系，因此以从头结点进行查找任何一个元素。( T )2、 线性表的线性存储结构优于链表存储结构。( F )3、 完全二叉树的某结点若无左孩子，则必定是叶子结点。( T )4、 无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。( T )5、 在图结构中，结点可以没有任何前趋和后继。( 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、 网络的最小代价生成树是惟一的( F )。二、选择题（每题2分，共20分）1在数据结构中，从逻辑上可以把数据结构分成（ C ）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构2常对数组进行的两种基本操作是( C )。A建立与删除 B索引和修改 C查找和修改D查找和索引3下列结论中不正确的是( B )。A按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问。B一个图按广度优先搜索法遍历的结果是唯一的。C无向图的邻接表表示法中，表中结点的数目是图中边的条数2倍。D图的多重邻接表表示法中，表中结点的数目是图中边的条数。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 )出栈序列：A12345B54321C45312D435216 设n为正整数。下列程序段中前置以记号的语句的频度为（ C ）。i=1;k=0;while(in-1)k+=10*i; i+; AnBn-1Cn-2Dn-37具有n个顶点且每一对不同的顶点之间都有一条边的图被称为( B )。A线性图B无向完全图C无向图D简单图8下列结论中正确的是( C )。A在无向图中，边的条数是结点度数之和。B用Prim算法和Kruskal算法求得的图的最小生成树相同。C在图的邻接多重表表示中，任意一条边只用一个表目表示。 D在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。9循环队列Q采用数组空间Q.base0,n-1存放其元素值，已知其头尾指针分别是front和rear，则判断此循环队列Q为空的条件是 ( C )。AQ.rear Q.front = =nBQ.rear Q.front -1 = = n CQ.rear = = Q.front DQ.rear + 1 = = Q.frontabecdf10如图所示，若从顶点a出发对图按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( D )。AabecdfBacfebdCacebfdDacfdeb三、问答题（共30分）1指出树和二叉树的主要差别。对于一个有1004个结点的二叉树，树叶最多有多少个？最少有多少个？（4分）2 画出和下列已知序列对应的森林F（6分）：森林的先序次序访问序列为：ABCDEFGHIJKL；森林的中序次序访问序列为：CBEFDGAJIKLH。3已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）key MOD 13。请写出用线性探测法处理冲突构造所得的哈希表。（11分）4 图G的邻接矩阵如下所示：试画出该图，并使用Kruskal算法构造出一棵最小生成树。（9分）四、 程序题（第1题15分，第2题20分）1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有值大于mink且小于maxk