2022年江西财经大计算机与技术专业《数据结构与算法》目期末试卷A(有答案).docx

2022年江西财经大学计算机科学与技术专业数据结构与算法科目期末试卷A(有答案)一、选择题1、设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all为第一元素,其存储地址为1,每个元素占一个地址空间，则a85的地址为()。A.13B.33C.18D.402、无向图G=(V,E),其中:V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历，得到的顶点序列正确的是()OA.a,b,e,c,d,fB.a,c,£e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b3、算法的计算量的大小称为计算的()。A.效率B.复杂性C.现实性D.难度4、下面关于串的叙述中，不正确的是()。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、在下列表述中，正确的是()A.含有一个或多个空格字符的串称为空格串B.对n(n>0)个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过16、若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是()。7、下列选项中，不能构成折半查找中关键字比较序列的是()。A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,4508、一个具有1025个结点的二叉树的高h为()。A.11B.10C.11至1025之间D.10至1024之间9、有n(n>0)个分支结点的满二叉树的深度是()。A.n2-1B.l0g2(n+l)+1C.l0g2(n+l)D.I0g2(n-I)10、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的()的两趟排序后的结果。A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、若用n表示图中顶点数目，则有条边的无向图成为完全图。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元素。13、文件由组成；记录由组成。14、设单链表的结点结构为(data,next),next为指针域，已知指针PX指向单链表中data为X的结点，指针py指向data为V的新结点，若将结点V插入结点X之后，则需要执行以下语句：15、一个算法具有5个特性：有零个或多个输入、有一个或多个输出。16、模式串P='abaabcad的next函数值序列为017、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是o18、已知链队列的头尾指针分别是f和r,则将值X入队的操作序列是O三、判断题19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）21、设模式串的长度为叫目标串的长度为n,当nxn且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）22、广义表（a,b,c）,d,e,f）的长度是4。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）25、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）26、归并排序辅助存储为O（1）。（）27、B-树中所有结点的平衡因子都为零。（）28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）四、简答题29、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15,13,20,18,12,60o下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12,13,15,18,20,60（）排序的结果为:13,15,18,12,20,60（）排序的结果为：13,15,20,18,12,60（）排序的结果为：12,13,20,18,15,6030、写出下列排序算法的基本思想，并写出对序列（23,12,35,47,16,25,36,19,21,16）进行排序时每一趟的结果。PROCbbsort(VARr:sequence;n:integer);“是,个敌组dl;pos(-1)：sl;pos1):«n;i:«l;exchanged:-true;WHILEexchangedDOexchanged：afalse;WHILEi<>pos(dJDO(IF(r(i-r(i+d)*d>0THENri)与ri+d交换;exchanged:-true;i:i÷d;os(dI:=os(d-d;i:=pos(d;d:="ci;JENDP:31、用单链表保存m个整数，节点的结构为(data,link),且Idatal<n(n为正整数)°现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。例如若给定的单链表head如下HEAD-1515-T T-卜5闪删除节点后的head为HEAD03EH-ElD要求(1)给出算法的基本思想(2)使用C或C+十语言，给出单链表节点的数据类型定义C(3)根据设计思想，采用C或C+语言描述算法，关键之处给出注释。说明所涉及算法的时间复杂度和空间复杂度。五、算法设计题32、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点(链表A的元素类型为整型，要求B、C表利用A表的结点)。33、编写递归算法，从大到小输出给定二叉排序树中所有关腱字不小于X的数据元素。要求你的算法的时间复杂度为O(log2(x+m),其中，2为排序树中所含结点数，m为输出的关键字个数。34、已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(a,a2,.,an-,an)改造为(a,a2an-l,an,an-l,.,a2,al)o35、设在4地(A,B,C,D)之间架设有6座桥，如图所示。2要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。(1)试就以上图形说明：此问题有解的条件是什么？(2)设图中的顶点数为n,试用C或PASCAL语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。参考答案一、选择题1、【答案】B2、【答案】D3、【答案】B4、【答案】B5、【答案】C6、【答案】D7、【答案A8、【答案】C9、【答案】C10、【答案】C二、填空题11、【答案】n(n-l)212、【答案】2(N-1)13、【答案】记录；数据项14、【答案】py->next=px->next; px->next=py15、【答案】有穷性；确定性；可行性16、【答案】0112231217、【答案】+a*b3*4cd; 18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】s=(LinkedList*)malloc(sizeof(LNode);s->data=x;s->next=r->next;r->next=s;r=so三、判断题19、【答案】X20、【答案】×21、【答案】22、【答案】X23、【答案】24、【答案】X25、【答案】×26、【答案】×27、【答案】28、【答案】四、简答题29、答：快速排序起泡排序直接插入排序堆排序30、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值C第一趟：12,23,35,16,25,36,19,21,16,47第二趟：12,16,23,35,16,25,36,19,21,47第三趟：12,16,23,16,25,35,19,21,36,47第四趟：12,16,16,23,19,25,35,21,36,47第五趟：12,16,16,19,23,25,21,35,36,47第六趟：12,16,16,19,21,23,25,35,36,47第七趟：52,16,16,19,21,23,25,35,36,4731、答：算法思想：算法的核心思想是用空间换时间。定义一个大小为n的布尔数组flag,初始时所有的元素都赋值为false,用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链表，遍历过程中，每一个当前结点daa域的绝对值所对应的flag位：若为真，则删除该结点；若为假(false),则将flag位置为(true)。(2)节点的数据结构定义如下：tyedefstructNode(intdata;structNode*next;)；(3)boolflagn;全局数组标志节点的绝对值是否出现过Node*deleteABSEnqualNode(Node*head)(memset(flag,false,SiZeof(flag);Node*pre=head;Node*p=head->next;while(p!=NULL)(if(flagabs(p->data)如果此绝对值已经在节点值的绝对值中出现过则删除该节点pre->next=p->next;deletep;p=pre->next;)else否则，将flag中对应的位置匿为true,并将指针指向下一个元素agabs(p->data)=true;p=p->next:)returnhead;)(4)只遍历一次链表，所以时间复杂度为O(m)(m为单链表中元素的个数)，申请大小为n的数组，所以空间复杂度为O(n)(n为节点绝对值的最大值)。五、算法设计题32、答：算法如下：voidDisCreatl(LinkedListA)本算法将带头结点的单链表A分解成数据域值小于零和大F零的两个单.链表B和CB=A;C=(LinkedList)malIoc(sizeof(LNode)"/为C申请结点空间C->next=nullC初始化为空表pA->next;P为工作指针B->next=null;/B表初始化while(p!=null)r=p->next;暂存P的后继if(p->data<O)小于O的放入B表p->next=B->next;B->next=p;将小干。的结点徒人B丧elsep->next=C->next;C->next=p;P=r；P指向新的待处理结点)算法结束33、答:算法如下:voidoutput(BSTreebst,intx)从大到小输出二叉排序树bst中所有关键字不小于X的数据元素if(bst)if(bst->data>x)output(bst->rchiId,x);if(bst->data>=x)printf(,%4d"rbst->data);if(bst->data>=x)output(bst->lchiId,x);/ifoutputLinkedListCyclInscrt(LinkedListp)本妖法将找性去(a,a，all.,)改施为(1fj,.»,f3ft.j/3%.：,.，a；,a：)q-p>>next;/qfii向转点t(LNode*)malloc(sizeof(LNode);t->datq->data;r«t;/rid住d?占点的拧Ht->next"p->next;p->nextt;/先将如结息放到正确位优qq->next;从a：结点开始while(q!p)sq>>ne×t;哲存后继t(LNode)maHoc(sizeof(LNode);t->dataq->data;t->nextp->next;p->next-t;/对称放胃q-s；恢复待处理结点p=r;returnp；)35、答：(1)只有所有的顶点的度都是偶数，才能有解。defineMAXNODE7/图中顶点的我大个数tyedefstructarc/%(边)结点(intadjvex;num;/adjvex是邻接点在顶点向量中的下标,num是边的编号structarc*next;/指向下一邻接点的指什infotype*info;/与孤(或边)相关的信.以指针ArcNode;typedefstruct/顶点结点vertypevertex;ArcNode*firstarc;VerNode;/顶点信息及指向第,邻接点的指针typedefVerNodeAdjList(MAXNODE)/邪接表(2)算法如下：修改常规访问标志数组ViSited的含义：当元索值为1时表示该边已访问；当元素值为O时表示该边尚未访问。visited1.n*0;AdjListg；voiddfs(intv)用邻接表作为存储结构的深度优先遍历算法(-gvJ.firstarc;第一邻接点While(P)jp->num;if(visitedj-0)visited(j)-1;dfs(->adjvex);)pp->next;>)结束df8()intdegree(AdjListg)求顶点的度for(ilji<nji÷+)count0;p-g(i).firstarc;while()count÷*;pp->next;if(count0IIcount21-0)return0;/若顶点度为0,或顶点的度不是偶数，无肺)return1;voidEulerCycle(AdjListg)intflag-degree(g);if(iflag)(rintf("无解n");exit(O);)dfs(l);