《数据结构》试卷及答案2

广州大学2017-2018学年第二学期考试卷课程《数据结构》考试形式（闭卷，考试）物理与电子工程学院电子系电子061、062、063专业学号姓名题号一二三四总分评卷人1234100分分判断题（对打√，错打×。每题1分，共15分）在单链表中，任何两个元素的存储位置之间都有固定的联系，因此可以从头结点进行查找任何一个元素。()线性表的线性存储结构优于链表存储结构。()完全二叉树的某结点若无左孩子，则必定是叶子结点。()无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。()在图结构中，结点可以没有任何前趋和后继（）。在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。()结点数固定的二叉树中，完全二叉树具有最小路径长度()。中序线索树中，右线索若不为空，则一定指向其双亲结点()。有向图用邻接矩阵表示，容易实现求结点度数的操作()。二叉树是度最大为2的有序树()。11、按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问()若有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在()。若有向图G中包含一个环，则G的结点间不存在拓扑排序()。图的拓扑排序序列是唯一的()。网络的最小代价生成树是惟一的（）。二、选择题（每题2分，共20分）1．在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．常对数组进行的两种基本操作是()。A．建立与删除 B．索引和修改C．查找和修改 D．查找和索引3．下列结论中不正确的是()。A．按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问。B．一个图按广度优先搜索法遍历的结果是唯一的。C．无向图的邻接表表示法中，表中结点的数目是图中边的条数2倍。D．图的多重邻接表表示法中，表中结点的数目是图中边的条数。4．已知一个图如下所示，则由该图得到的一种拓扑序列为（）。1123456（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,v5设有一个堆栈，元素进栈的次序为12345。不可能得到()出栈序列：A．12345 B．54321 C．45312 D．43521设n为正整数。下列程序段中前置以记号@的语句的频度为（）。i=1;k=0;while(i<n-1){@ k+=10*i; i++; }A．n B．n-1 C．n-2 D．n-37．具有n个顶点且每一对不同的顶点之间都有一条边的图被称为()。A．线性图 B．无向完全图 C．无向图 D．简单图8．下列结论中正确的是()。A．在无向图中，边的条数是结点度数之和。B．用Prim算法和Kruskal算法求得的图的最小生成树相同。C．在图的邻接多重表表示中，任意一条边只用一个表目表示。D．在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。9．循环队列Q采用数组空间Q.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判断此循环队列Q为空的条件是()。A．Q.rear–Q.front==n B．Q.rear–Q.front-1==nC．Q.rear==Q.front D．Q.rear+1==Q.frontabecdabecdfA．abecdfB．acfebdC．acebfdD．acfdeb三、问答题（共30分）1．指出树和二叉树的主要差别。对于一个有1004个结点的二叉树，树叶最多有多少个？最少有多少个？（4分）画出和下列已知序列对应的森林F（6分）：森林的先序次序访问序列为：ABCDEFGHIJKL；森林的中序次序访问序列为：CBEFDGAJIKLH。图G的邻接矩阵如下所示：试画出该图，并使用Kruskal算法构造出一棵最小生成树。（9分）4．已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD13。请写出用线性探测法处理冲突构造所得的哈希表。（11分）程序题（第1题15分，第2题20分）1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删除结点空间（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。编写递归算法，计算二叉树中叶子结点的数目。试卷答案判断题（对打√，错打×。每题1分，共15分）√×√√√×√×√√√√√××选择题（每题2分，共20分）CCBACCBCCD问答题（共30分）1、（4分，每个答案给1分）答：主要差别①树中结点的最大度数没有限制，而二叉树结点的最大度数为2。②树的结点无左右之分，而二叉树的结点有左右之分。最多是完全二叉树的形态，即502个叶子；最少是单支树的形态，即1个叶子。2、（6分）答：AB2CAB2CEFGHIJKLAABDCEFGHIJKL3、（11分，每个关键字1分）答：01234567891011124940173132304647102463237123423712345672520181215810546画出该图给4分112345671812158546得出最小生成树给5分算法题（第1题15分，第2题20分）1、voiddelete(LinkListL,intmink,intmaxk){ p=L->next; while(p&&p->data<=mink) {pre=p;p=p->next;}//查找第一个值>mink的结点 if(p){ while(p&&p->data<maxk)p=p->next; //查找第一个值≥maxk的结点 q=pre->next;pre->next=p;//修改指针 while(q!=p) {s=q->next;deleteq;q=s;}//释放结点空间 }//if}//delete2、typedefstructNode{ ElemTypedata; structNode*lchild,*rchild;}BinNode,*BinTree;方法一：intleafNum=0;voidCountLeaf(BinTreeroot){ /*preordervisitbintreeandcountthenumberofleafnode*/ if(root!=NULL){ if(root->lchild==NULL&&root->rchild==NULL)leafNum++; else{ CountLeaf(root->lchild);CountLeaf(root->rchild); } }}方法二：intCountLeaf(BinTree