（数据构造）期末考试题及答案.docx
（数据构造）期末考试题及答案2020-2021学年第一学期期末考察（数据构造）试卷答案一律写在答题纸上，在本试卷上做答无效一、选择每题1分，共10分1.长度为n的线性表采用顺序存储构造，一个在其第i个位置插入新元素的算法时间复杂度为DA.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素根据6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？DA.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为BA.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是BA.m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是BA.9B.11C.15D.不确定6.下列哪一个方法能够判定出一个有向图能否有环。AA.深度优先遍历B.拓扑排序C.求最短途径D.求关键途径7.第7层有10个叶子结点的完全二叉树不可能有B个结点。A.73B.234C.235D.2368.分别用下面序列构造二叉排序树，与用其他三个序列构造的结果不同的是BA.100,80,90,60,120,110,130B.100,120,110,130,80,60,90C.100,60,80,90,120,110,130D.100,80,60,90,120,130,1109.对一组数据84，47，25，15，21排序，数据的排列次序在排序经过中变化如下：18447251521215472584213152125844741521254784则采用的排序方法是BA.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须DA.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空每空1分，共15分1.数据构造中评价算法的两个重要指标是时间复杂度、空间复杂度。2.在单链表中，指针P所指结点有后继的条件是p->next.data!=null。结点构成：data和next3.栈的特点是先进后出。4.判定循环队列能否队满的条件表达式是。5.完全二叉树中的结点个数为n，则编号最大的分支结点的编号为2n-1。6.假如A有7个兄弟，而B是A的双亲，则B的度是2。7.假如二叉树中有20个叶子节点，30个度为1的结点，则该二叉树的总结点数为。8.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用.表示。现前序遍历二叉树的结点序列为ABD.GCE.H.F.，则中序遍历二叉树的结点序列为。9.若用n表示图中的顶点数目，则有条边的无向图被称为完全图。10.假如具有n个顶点的图是一个环，则它有棵生成树。11.克鲁斯卡尔算法的时间复杂度是，它合适求图的最小生成树。12.顺序查找n个元素的线性表，若查找成功时的平均查找长度为。13.高度为5的完全二叉树，其结点最少有个。14.直接插入排序中使用的监视哨的作用是。三、判定题每题1分，共10分1.算法独立于详细的程序设计语言，与详细的计算机无关。2.线性表采用链式存储时，结点内部的存储空间能够是不连续的。3.栈和队列的存储方式，既能够是顺序方式，又能够是链式方式。4.哈夫曼树的结点总个数一定是偶数。5.已知二叉树的先序遍历序列和中序遍历序列，能够画出这棵二叉树。6.有e条边的无向图，在其对应的邻接表中有e个结点。7.连通分量指的是无向图的极大连通子图。8.在哈希表的查找经过中的“比拟操作是无法避免的。9.完全二叉树肯定是平衡二叉树。10.堆排序是稳定的排序算法。四、简答题共30分1.线性构造的特点是？4分2.已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从A出发的广度优先搜索序列，以及相应的广度优先生成树。6分ABCDEFBCDEF3.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为CEIFGBADH，请画出这棵二叉树，并把这棵二叉树转换成相应的树或森林。6分4.已知电文内容为：ACACBACDAACDBAACADAA，字符集为A，B，C，D，设计一套二进制编码，使得上述电文的编码最短。6分5.已知有序序列3，7，11，20，45，77，90，请分别写出折半查找10和查找99的经过，并求出ASL4分6.已知序列34，17，6，29，33，11，80，37请用快速排序的方法进行排序，并给出具体经过。4分五、算法填空每空5分，共20分1按先序次序输入二叉树中的结点值(字符)构造二叉树StatusCreateBiTree(BiTree&T)charch;read(ch);if(ch='')T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);(1);CreateBiTree(T->lchild);(2);returnOK;2在顺序表L的第i个元素之前插入新的元素eStatusListInsert(SqList&L,inti,ElemTypee)if(iL.length+1)returnERROR;/插入位置不合法for(j=L.length;j>i;j-)(3);L.elemi-1=e;/插入e(4);returnOK;/ListInsert_Sq六、写算法共15分1.请写出链式存储的线性表中，删除第i个位置数据元素的实现算法。给出相应的构造体定义，关键部分给出注释。20202021学年第一学期期末考察（数据构造）标准答案一、选择每题1分，共10分1-5DBBBB6-10ACCDB二、填空每空1分，共15分1.时间复杂度，空间复杂度3.Q.rear=Q.front4.75.86.O(n2)，稠密图7.极大连通子图8.n(n-1)9.n-110.集合构造，树形构造，图状构造三、判定题每题1分，共10分1.×2.3.4.×5.6.×7.×8.×9.×10.×四、简答题共30分1.(1)在二叉树的第i层上至多有2i-1个结点；(i1)(2)深度为k的二叉树上至多含2k-1个结点k1；(3)对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1；(4)具有n个结点的完全二叉树的深度为?log2n?+1。(5)若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：若i=1，则该结点是二叉树的根，无双亲，否则，编号为?i/2?的结点为其双亲结点；若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。评分标准：答对5条中的4条得4分。2.深度优先遍历序列：abefdc深度优先生成树：a-.>b->c->e->f->d->c评分标准：深度优先遍历序列33.(1)T->next->next=P->next;(2)Q=T;While(Q->!=P)Q=Q->next;Q->next=P->next;free(P);评分标准：回答1或者2都正确。4.5.11，3，7，77，20，45，90查找经过：11，3，7，77或者90，45，20，776.34，17，6，29，33，11，80，37d=511，17，6，29，33，34，80，37d=311，17，6，29，33，34，80，37d=16，11，17，29，33，34，37，80五、算法填空每空5分，共20分1.(1)visit(T->data);或者printf(T->data);(2)PreOrderTraverse(T->rchild);2.(1)returnmid;(2)high=mid-1;六、写算法共15分/删除表L中第i个元素，结果用e返回，操作成功返回OK，失败时返回ERRORStatusListDelete(SqList&L,inti,ElemType&e)if(iL.length)returnERROR;e=L.elemi-1;for(intj=i+1;j
