还剩12页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
2022年桂林航天工业学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
一、选择题
1、用有向无环图描述表达式(A+B)*((A+B)//A)至少需要顶点的数目为()A.5B.6C.8D.
92、将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()A.NB.2N-1C.2ND.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=s
5、下面关于串的叙述中,不正确的是()A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存储
6、若一棵二叉树的前序遍历序列为aebdc后序遍历序列为bcdea则根结点的孩子结点()A.只有eB.有e、bC.有e、cD.无法确定若查找元素54需依次和元素
30、
63、
42、54比较,查找成功若查找元素90需依次和元素
30、
63、
87、95比较,查找失败4ASLqc=1*1+2*2+4*3+5*4/12=37/
1230、答赋值语句一共被执行了m*n次,所以该程序段的时间复杂度是Om*n
31、答1算法的基本思路是利用递归的思想来求解二叉树的带权路径长度,如果当前节点不是叶子节点,那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和,对于此函数要传入一个当前节点的树高的形参,那么递归调用孩子节点时只需要将这个形参加一即可2typedefstructBiNode血weighj权值structBiNode〃左孩子指针structBiNode*right:右孩子指针}BiNode5*BiTree:3具体算法实现如下mtCalc\\TLBiTreeBTmtheightifBT=NULL/如果当前节点为空节点return0;〃如果当前节点的左右孩子节点都为空,即当前节点为叶子节点直接返回当前节点的WPL!BT-rightreturnBT.weight*height;〃如果当前节点不是叶子节点,则对当前节点的左右子树进行递归,返回左右子树WPL之和elsereturnCalc\\TLBT-left:height-1-Calc\VTLBT-right5height*1:
五、算法设计题
32、答算法如下voidEnQueueLinkedListrearElemTypex//“ar是带头结点的循环链队列的尾指针,本算法将元素x插入到队尾{s=LinkedListmallocsizeofLnode;//申请结点空间s-data=x;s-next=rear-next;//将s结点链入队尽rear-next=s;rear=s;〃rear指向新队尾voidDeQueueLinkedListrear//rear是带头结点的循环链队列的尾指针//本算法执行出队操作,成功输出队头元素;否则给出出错信息{ifrear-next==rear{printf队空\n;exit0;s=rear-next-next;rear-next-next=s-next;printf出队元素是“,s-data;ifs==rearrear=rear-next;frees;
33、答算法如下BiTreeSearchBiTreebtfElemTypex〃在二叉树t中查找结点值等于x的结点{ifbt{Searchbt-lchildrx;Searchbt-rchildzx;ifbt-data==xreturnbt;}//if}〃结束voidCountBiTreet.int*nOr〃统计以t为根结点的干树的叶结点数nO{Countbt-IchiIdrn;Countbt-rchildrn;if!t-lchildJt-rchild//叶结点{printft-data;★!!++;}〃输出并计数}〃结束Count
34、答算法如下LinkedListDeleteLinkedListL〃L於带头结点的单链表,本算法刷除其最小值结点{p=L-next;//p为工作指针指向待处理的结点假定链表非空pre=L;//pre指向最小值结点的前驱q=P;〃q指向最小值结点,初始假定第一元素结点是最小值结点whilep-next{ifp-next-dataq-data{pre=p;q=p-next;}〃查最小值结点p»p-next;〃指针后移:.pre-next=q-next;〃从链表上删除及小值结点freeq;returnL;〃释放最小值结点空间}〃结束算法Delete
35、答算法如下voidSnake_NumberintAn][n]rintn〃将自然数l・・”n按“蛇形”填入n阶方阵A中
7、循环队列放在一维数组A中,endl指向队头元素,end2指向队尾元素的后一个位置假设队列两端均可进行入队和出队操作,队列中最多能容纳M—1个元素初始时为空,下列判断队空和队满的条件中,正确的是A.队空endl==end2;队满endl==end2+lmodMB.队空endl==end2;队满end2==endl+1modM—1C.队空end2==endl+1modM;队满endl==end2+lmodMD.队空endl==end2+lmodM;队满end2==endl+1modM—
18、在下述结论中,正确的有
①只有一个结点的二叉树的度为0
②二叉树的度为2O
③二叉树的左右子树可任意交换
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树A.
①②③B.
⑦③④C.
②④D.
①④
9、每个结点的度或者为0或者为2的二叉树称为正则二叉树n个结点的正则二叉树中有个叶子A・log2nB.n—1/2C.log2n+1D.n+1/
210、在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A并已知A的左孩子的平衡因子为0右孩子的平衡因子为1则应作型调整以使其平衡A.LLB.LRC.RLD.RR
二、填空题
11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,平均比较次数为O
12、对单链表中元素按插入方法排序的C语言描述算法如下,其中L为链表头结点指针请填充算法中标出的空白处,完成其功能typedefstructnode{intdata;structnode*next;yiinknode*link;voidInsertsortlinkL{linkpqru;p=L-next;I;while2{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、数据结构是研讨数据的和以及它们之间的相互关系,并对与这种结构定义相应的设计出相应的O
15、应用Prim算法求解连通网络的最小生成树问题1针对如图所示的连通网络试按如下格式给出在构造最小生成树过程中顺序选出的各条边0始顶点号,终顶点号,权值2下面是Prim算法的实现,中间有5个地方缺失,请阅读程序后将它们补上constintMaxInt=INT_MAX;constintn«6;typedefintAdjMatrixn1n;typedefstruct{intfromVextoVex;intweight;}TreeEdgeNode;typedefTreeEdgeNodeMSTn-1];voidPrimMSTAdjMatrixGMSTTintrt{//从顶点rt出发构造图G的最小生成树Trt成为树的根结点{cerr«MGraphisdisconnected!w«endl;g;}e=Tminpos];Tminpos]-Tk;Tk]=e;v=Tk].toVex;fori=k+l;in-l;〃修改候选边第合ifG[vT[i.toVexTi.weight{Ti].weight«Gv]Ti.toVexJ;
⑤}}
16、模式串P二,abaabcad的next函数值序列为o
17、在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是o
18、当两个栈共享一存储区时,栈利用一维数组stack1n表示,两栈顶指针为top
[1]与top
[2]则当栈1空时,top[l]为栈2空时,top
[2]为栈满时为o
三、判断题
19、倒排文件是对次关键字建立索引
20、直接访问文件也能顺序访问,只是一般效率不高
21、数组不适合作为任何二叉树的存储结构
22、在链队列中,即使不设置尾指针也能进行入队操作()
23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列()
24、对于有n个结点的二叉树,其高度为log2no()
25、数据的逻辑结构是指数据的各数据项之间的逻辑关系()
26、排序算法中的比较次数与初始元素序列的排列无关()
27、对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的()
28、平衡二叉树中,若某个结点的左、右孩子的平衡因子为零,则该结点的平衡因子一定是零()
四、简答题
29、假定对有序表
(34572430425463728795)进行折半查找试回答下列问题
(1)画出描述折半查找过程的判定树
(2)若查找元素54需依次与哪些元素比较?
(3)若查找元素90需依次与哪些元素比较?
(4)假定每个元素的查找概率相等,求查找成功时的平均查找长度
30、下面程序段的时间复杂度是什么?fori=0;in;iforj=0;jmjA[i]D]=0;
31、二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,给定一棵二叉树T采用二叉链表存储,节点结构为其中叶节点的weight域保存该结点的非负权值设root为指向T的根节点的指针,设计求T的WPL的算法要求
(1)给出算法的基本设计思想
(2)使用C或C++语言,给出二叉树结点的数据类型定义
(3)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
五、算法设计题
32、在一个循环链队中只有尾指针(记为rear结点结构为数据域data指针域next)请给出这种队列的入队和出队操作的实现过程
33、设二叉树用二指针结构存储(可以是动态存储结构),元素值为整数,且元素值无重复,请编写子程序,求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点
34、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法delete(LinklistL)o
35、编写算法,将自然数1〜I按“蛇形”填nxn矩阵中例(1-42)如图所示(用程序实现)O参考答案
一、选择题
1、【答案】A
2、【答案】A
3、【答案】C
4、【答案】D
5、【答案】B
6、【答案】A
7、【答案】A
8、【答案】D
9、【答案】D
10、【答案】C
二、填空题
11、【答案】n+1/
212、【答案】L-next=NULL〃置空链表,然后将原链表结点逐个插入到有序表中p!二NULL〃当链表尚未到尾,p为工作指针q!=NULL〃查P结点在链表中的插入位置,这时q是工作指针4p-next=r-next〃将P结点链入链表中5r-next=p〃r是q的前驱,u是下个待插入结点的指针
13、【答案】f-next=p-next;f-prior=p;p-next-prior=f;p-next=fo
14、【答案】逻辑结构;物理结构;操作运算;算法
15、【答案】1031;354;522;315;143
(2)
①T[k];toVex=i
(2)min=MaxInt;
(3)mispos=i
(4)exit(O)
⑤T[i];fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法假设N={VE}是连通图,Et是N上最小生成树边的集合算法从V产{uo}Et开始,重复执行下述操作在所有u属于Vtv属于V-Vt的边(uv)属于E中找一条代价最小的边(uovo)加入集合Et同时将Vo并入Vt直到Vt=V为止
16、【答案】
0112231217、【答案】++a*b3*4-cd;18【解析】中缀式相当于中序遍历,前缀式相当于前序遍历,后缀式相当于后序遍历
18、【答案】0;n+l;top[l]+l=top
[2]
19、【答案】V
20、【答案】X
21、【答案】X
22、【答案】《
23、【答案】/
24、【答案】X
25、【答案】X
26、【答案】X
27、【答案】«
28、【答案】X
29、答
(1)判定树如图所示leftweightright1341025;931168j|12157131416。