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

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

ID:14206130

大小:61.50 KB

页数:4页

时间:2018-07-26

数据结构07~08第二学期b卷_第1页
数据结构07~08第二学期b卷_第2页
数据结构07~08第二学期b卷_第3页
数据结构07~08第二学期b卷_第4页
资源描述:

《数据结构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、编写递归

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。