2022年桂林航天工业学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx

2022年桂林航天工业学院计算机科学与技术专业数据结构与算法科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式（A+B）*（A+B）/A）,至少需要顶点的数目为（）。A.5B.6 C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.N B.2N-1 C.2N D.N-13、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、若一棵二叉树的前序遍历序列为a, e, b, d, c,后序遍历序列为b, c, d, e, a, 则根结点的孩子结点（）。A.只有e B.有e、b C.有e、c D.无法确定30637095(2) 若查找元素54,需依次和元素30、63、42、54比较，查找成功。(3) 若查找元素90,需依次和元素30、63、87、95比较，查找失败。(4)ASLqc = (1*1 + 2*2 + 4*3 + 5*4)/12 = 37/1230、答：赋值语句一共被执行了 m*n次，所以该程序段的时间复杂度是O (m*n)。31、答：(1)算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当 前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路 径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时 只需要将这个形参加一即可。(2)typedef struct BiNode血weighj权值struct BiNode左孩子指针struct BiNode *right: 右孩子指针BiNode5 *BiTree:(3)具体算法实现如下：mt CalcTL(BiTree BT, mt height)(if(BT = NULL)/如果当前节点为空节点return 0;如果当前节点的左右孩子节点都为空，即当前节点为叶子节点,直接返回当前节点的WPL !BT->right)return BT. weight * height;如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL之和elsereturn CalcTL(BT->left: height-1) - CalcVTL(BT->right5 height*1):五、算法设计题32、答：算法如下：void EnQueue (LinkedList rear, ElemType x)/ “ar是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾 s= (LinkedList) malloc (sizeof (Lnode) ); /申请结点空间 s->data=x; s->next=rear->next;/将 s结点链入队尽rear->next=s; rear=s;rear 指向新队尾void DeQueue (LinkedList rear) / rear是带头结点的循环链队列的尾指针/本算法执行出队操作，成功输出队头元素；否则给出出错信息/s指向队头元素 队头元素出队/空队列void DeQueue (LinkedList rear) / rear是带头结点的循环链队列的尾指针/本算法执行出队操作，成功输出队头元素；否则给出出错信息/s指向队头元素 队头元素出队/空队列/s指向队头元素 队头元素出队/空队列/s指向队头元素 队头元素出队/空队列 if(rear->next=rear) printf("队空n"); exit(0);) s=rear->next->next;rear->next->next=s->next;printf ("出队元素是“，s->data); if(s=rear) rear=rear->next; free(s);33、答：算法如下：BiTree Search(BiTree btfElemType x) 在二叉树t中查找结点值等于x的结点 if(bt)Search(bt->lchildrx);Search(bt->rchildz x);if(bt->data=x) return bt;/if 结束void Count (BiTree t.int *nOr) 统计以t为根结点的干树的叶结点数nOCount(bt->IchiIdr &n);Count(bt->rchildr &n);if ( ! t->lchild && J t->rchild) /叶结点 printf (t->data); !()+; 输出并计数) 结束 Count34、答：算法如下：LinkedList Delete(LinkedList L)L於带头结点的单链表，本算法刷除其最小值结点p=L->next;/p为工作指针。指向待处理的结点。假定链表非空pre=L;/ /pre指向最小值结点的前驱q=P；q指向最小值结点，初始假定第一元素结点是最小值结点while(p->next)if (p->next->data<q->data) pre=p;q=p->next;查最小值结点p»p->next; 指针后移): .pre->next=q->next; 从链表上删除及小值结点 free(q) ;return L; 释放最小值结点空间结束算法Delete35、答：算法如下：void Snake_Number(int A(nnr int n)将自然数l”n,按“蛇形”填入n阶方阵A中i=0; j=0; k=l;while(i<n && j<n)while(i<n && j>-l)A(i)j«k+; i+ ;j -；) if(j<0)&&(i<n) j»0; else j=j+2; i=n-l; while(i>-l && j<n)Ai j =k+; i； j+；> if(i<0 && j<n) i-0;elsei=i+2; j-n-1; 最外层while /Snake_Numberi=0; j=0; k=l;while(i<n && j<n)while(i<n && j>-l)A(i)j«k+; i+ ;j -；) if(j<0)&&(i<n) j»0; else j=j+2; i=n-l; while(i>-l && j<n)Ai j =k+; i； j+；> if(i<0 && j<n) i-0;elsei=i+2; j-n-1; 最外层while /Snake_Numberi=0; j=0; k=l;while(i<n && j<n)while(i<n && j>-l)A(i)j«k+; i+ ;j -；) if(j<0)&&(i<n) j»0; else j=j+2; i=n-l; while(i>-l && j<n)Ai j =k+; i； j+；> if(i<0 && j<n) i-0;elsei=i+2; j-n-1; 最外层while /Snake_Number/id站矩阵元素的下标，k走要填入的自然数从右上向左下填数副对角线及以上部分的新i, j坐标 /副对角线以下的新的i,j坐标 从左下向右上7、循环队列放在一维数组A中，endl指向队头元素，end2指向队尾元素的后一个位置。 假设队列两端均可进行入队和出队操作，队列中最多能容纳M 1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是()。A.队空：endl = =end2 ;队满：endl = = (end2 + l) mod MB.队空：endl = =end2 ;队满：end2 = = (endl + 1) mod (M 1)C.队空：end2 = = (endl + 1) mod M ;队满：endl = = (end2 + l) mod MD.队空：endl = = (end2 + l) mod M ;队满：end2 = = (endl + 1) mod (M 1)8、在下述结论中，正确的有()。只有一个结点的二叉树的度为0。二叉树的度为2O二叉树的左右子树可任意交换。深度为K的完全二叉树的结点个数小于或等于深度相 同的满二叉树。A.B.C.D.9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有()个叶子。Alog2n B. (n1) /2 C.log2n+1 D. (n+1) /210、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作()型调整以使其平衡A.LL B.LR C.RL D.RR二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排 序树检索时，平均比较次数为O12、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。 请填充算法中标出的空白处，完成其功能。typedef struct node int data; struct node *next; yiinknode,*link; void Insertsort(link L) link p,q,r,u; p=L->next；(I)；while (2) r=L; q=L->next;while(3&& q->data<=p->data) r=q; q=q->next;uup->next:(4):(5): p=u;13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是 14、数据结构是研讨数据的 和 以及它们之间的相互关系，并对与这种结构定义相应的,设计出相应的 O15、应用Prim算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边0(始顶点号，终顶点号，权值)(, ,)(, ,)(, ,)(2)下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。INT_MAX的值在limits - h中 图的顶点数，应由用户定义 用维数组作为邻接矩阵表示 生成树的边结点边的起点与终点边I的权侑最小生成树定义TreeEdgeNode e; int i for(i*0;i<n;i*+),k-0 rmin<minposrv;if(i!-rt)T(k.fromVex=rt; for(k»0;k<n-l;k+) /初始化般小生成树T;T().weightaG(rt) (i ； 依次求MST的候选边for (i=k;i<n-l;i+) if(Ti).weight<min) min=Ti).weight;if(min= =MaxInt)；)遍历当前候选边奥合选具有最小权值的候选边图不连通，出错处理const int MaxInt=INT_MAX;const int n«6;typedef int AdjMatrix(n1(n);typedef structint fromVex,toVex;int weight;TreeEdgeNode;typedef TreeEdgeNode MST(n-1； void PrimMST(AdjMatrix G, MST T,int rt)/从顶点rt出发构造图G的最小生成树T,rt成为树的根结点cerr«MGraph is disconnected! w«endl; g ; e=T(minpos;T(minpos-T(k); T(k=e;v=T(k.toVex;for( i=k+l；i<n-l;) 修改候选边第合if(Gv)(Ti).toVex)<T(i).weight)T(i.weight«G(v(T(i).toVex J; ： ) 16、模式串P二，abaabcad的next函数值序列为o17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 o18、当两个栈共享一存储区时，栈利用一维数组stack (1, n)表示，两栈顶指针为top1与top2,则当栈1空时，topl为,栈2空时，top2为,栈满时为o三、判断题19、倒排文件是对次关键字建立索引。()20、直接访问文件也能顺序访问，只是一般效率不高。() 21、数组不适合作为任何二叉树的存储结构。()22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、对于有n个结点的二叉树，其高度为log2no （）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）26、排序算法中的比较次数与初始元素序列的排列无关。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查 找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定 是零。（）四、简答题29、假定对有序表：（3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95）进行折半查找, 试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54,需依次与哪些元素比较？（3）若查找元素90,需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。30、下面程序段的时间复杂度是什么？for(i=0;i<n;i) for(j=0;j<mj) AiD=0；31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定 一棵二叉树T,采用二叉链表存储，节点结构为：leftweightright其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计 求T的WPL的算法。要求：（1）给出算法的基本设计思想。（2）使用C或C+语言，给出二叉树结点的数据类型定义。（3）根据设计思想，采用C或C+语言描述算法，关键之处给出注释。五、算法设计题32、在一个循环链队中只有尾指针（记为rear,结点结构为数据域data,指针域next）, 请给出这种队列的入队和出队操作的实现过程。33、设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重 复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。34、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法delete （Linklist&L） o35、编写算法，将自然数1I?按“蛇形”填nxn矩阵中。例（1-42）如图所示（用程序 实现）O1341025；9 31168 j| 12157131416参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】D5、【答案】B6、【答案】A7、【答案】A8、【答案】D9、【答案】D10、【答案】C二、填空题11、【答案】(n+1) /212、【答案】(1) L->next=NULL 置空链表，然后将原链表结点逐个插入到有序表中(2) p!二NULL 当链表尚未到尾，p为工作指针(3) q!=NULL 查P结点在链表中的插入位置，这时q是工作指针(4)p->next=r->next 将P结点链入链表中(5) r->next=p r是q的前驱，u是下个待插入结点的指针13、 【答案】f->next=p->next ; f->prior=p ; p->next->prior=f ; p->next=fo14、【答案】逻辑结构；物理结构；操作(运算)；算法15、【答案】(1)(0, 3, 1) ; (3, 5, 4) ; (5, 2, 2) ; (3, 1, 5) ; (1, 4, 3)（2） Tk ; toVex=i（2）min=MaxInt;（3）mispos=i（4）exit（O） Ti ; fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N=V, E是连 通图，Et是N上最小生成树边的集合。算法从V产uo, Et开始，重复执行下述操作： 在所有u属于Vt, v属于V-Vt的边（u, v）属于E中找一条代价最小的边（uo, vo）加 入集合Et,同时将Vo并入Vt,直到Vt=V为止。16、【答案】01122312 17、【答案】+a*b3*4-cd ; 18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】0 ; n+l ; topl+l=top2三、三、三、三、判断题19、【答案】V20、【答案】X21、【答案】X22、【答案】23、【答案】/24、【答案】X25、【答案】X26、【答案】X27、【答案】«28、【答案】XU!U!简答题29、答：（1）判定树如图所示：