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

《2022年桂林航天工业学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx》由会员分享，可在线阅读，更多相关《2022年桂林航天工业学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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

2、-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 +

3、 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)具

4、体算法实现如下：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

5、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) /

6、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中查找结

7、点值等于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於带头结点的单链

8、表，本算法刷除其最小值结点p=L-next;/p为工作指针。指向待处理的结点。假定链表非空pre=L;/ /pre指向最小值结点的前驱q=P；q指向最小值结点，初始假定第一元素结点是最小值结点while(p-next)if (p-next-datadata) pre=p;q=p-next;查最小值结点pp-next; 指针后移): .pre-next=q-next; 从链表上删除及小值结点 free(q) ;return L; 释放最小值结点空间结束算法Delete35、答：算法如下：void Snake_Number(int A(nnr int n)将自然数l”n,按“蛇形”填入n阶方阵A中

9、i=0; j=0; k=l;while(in & jn)while(i-l)A(i)jk+; i+ ;j -；) if(j0)&(i-l & j if(i0 & jn) i-0;elsei=i+2; j-n-1; 最外层while /Snake_Numberi=0; j=0; k=l;while(in & jn)while(i-l)A(i)jk+; i+ ;j -；) if(j0)&(i-l & j if(i0 & jn) i-0;elsei=i+2; j-n-1; 最外层while /Snake_Numberi=0; j=0; k=l;while(in & jn)while(i-l)A(i)

10、jk+; i+ ;j -；) if(j0)&(i-l & j if(i0 & jnext；(I)；while (2) r=L; q=L-next;while(3& q-datadata) r=q; q=q-next;uup-next:(4):(5): p=u;13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是 14、数据结构是研讨数据的 和 以及它们之间的相互关系，并对与这种结构定义相应的,设计出相应的 O15、应用Prim算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边0(始顶点号，终顶点号，权值)(

11、, ,)(, ,)(, ,)(2)下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。INT_MAX的值在limits - h中 图的顶点数，应由用户定义 用维数组作为邻接矩阵表示 生成树的边结点边的起点与终点边I的权侑最小生成树定义TreeEdgeNode e; int i for(i*0;in;i*+),k-0 rminminposrv;if(i!-rt)T(k.fromVex=rt; for(k0;kn-l;k+) /初始化般小生成树T;T().weightaG(rt) (i ； 依次求MST的候选边for (i=k;in-l;i+) if(Ti).weightmin)

12、 min=Ti).weight;if(min= =MaxInt)；)遍历当前候选边奥合选具有最小权值的候选边图不连通，出错处理const int MaxInt=INT_MAX;const int n6;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成为树的根结点cerrMGraph is dis

13、connected! wendl; g ; e=T(minpos;T(minpos-T(k); T(k=e;v=T(k.toVex;for( i=k+l；in-l;) 修改候选边第合if(Gv)(Ti).toVex)T(i).weight)T(i.weightG(v(T(i).toVex J; ： ) 16、模式串P二，abaabcad的next函数值序列为o17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 o18、当两个栈共享一存储区时，栈利用一维数组stack (1, n)表示，两栈顶指针为top1与top2,则当栈1空时，topl为,栈2空时，top2为,栈满时为o三

14、、判断题19、倒排文件是对次关键字建立索引。()20、直接访问文件也能顺序访问，只是一般效率不高。() 21、数组不适合作为任何二叉树的存储结构。()22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、对于有n个结点的二叉树，其高度为log2no （）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）26、排序算法中的比较次数与初始元素序列的排列无关。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查 找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的

15、。（）28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定 是零。（）四、简答题29、假定对有序表：（3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95）进行折半查找, 试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54,需依次与哪些元素比较？（3）若查找元素90,需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。30、下面程序段的时间复杂度是什么？for(i=0;in;i) for(j=0;jnext=NULL 置空链表，然后将原链表结点逐个插入到有序表中(2) p!二NUL

16、L 当链表尚未到尾，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）misp

17、os=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）判定树如图所示：