2022年中国海洋大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年中国海洋大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、 无向图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,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b2、 下列排序算法中，占用辅助空间最多的是()。A.归并排序B.快速排序C.希尔排序D.堆排序3、 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，贝U采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D仅有尾指针的单循环链表4、 已知串S='aaab',其next数组值为( )。A.0123B.1123C.1231 D.12115、 在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.0(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、 下列选项中，不能构成折半査找中关键字比较序列的是()°A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,4507、 下列叙述中，不符合m阶B树定义要求的是()。A.根结点最多有m棵了树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链娑8、 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为()。A.CBEFDAB.FEDCBAC.CBEDFA D.不定9、 -•棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足()。其中任意一个结点均无左孩子其中任意一个结点均无右孩子其中只有一个叶结点其中度为2的结点最多为一个10、 对序列{15,9,7,8,20,-1,4}用希尔排序方法排序,经一趟后序列变为{15,-1,4,8,20,9,7}则该次采用的增量是( )0A.1 B.4 C.3 D.2二、填空题11、 对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstructnode{intdata;structnode*next;}linknode,*link;voidInsertsort(linkL)(linkp,q,r,u;ogL->next;(I) ；while((2) ){r»L;q»L->next;while( (3) &&q->data<»p->data)(r=q;q=q->next;}(4) : (5) :p=u;12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是—算法，最费时间的是—算法。13、VSAM(虚拟存储存取方法)文件的优点是：动态地 不需要文件进行 并能较快地 行查找。14、 关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是 ；若采用以第一个元素为分界元素的快速排序法，贝!J扫描一趟的结果是—015、 设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中,free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete-subtree(T,A),首先在二叉排序树T中査找值为A的结点，根据査找情况分别进行如下处理：(1)若找不到值为A的结点，则返回根结点的地让⑵若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是査找树的根结点，删除后变成空的二叉树，则返null;否则返回根结点的地址。typedefstructnode(intdata,structnode*lchild,*rchild}node；voidfree_tree(node*T){if(TJ"null)(free_tree(T->lchild);free_tree(T->rchild); LD——；)node*delete_subtree(node*T,intA){node*p=null,*q=T;while((2)){p»q;if(A<q->data)ggq->lchild:else(3) :}if(qJ^null){free_tree(q);if(p«=null)T=null;elseif(A<p->data)(4) ;else(5)r)return(T);}16、 设正文串长度为n,模式串长度为m,贝II串匹配的KMP算法的时间复杂度为 .17、 模式串P=,abaabcac,的next函数值序列为 018、 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k= o(注：矩阵元素下标从1开始)三、判断题19、 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。()20、 倒排文件的目的是为了多关键字查找。()21、 设模式串的长度为m,目标串的长度为n,当mm11处理只匹配一次的模式时，朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。()22、 稀疏矩阵压缩存储后，必会失去随机存取功能。()23、 哈夫曼树度为1的结点数等于度为2和0的结点数之差。()24、 二叉树是-•般树的特殊情形。()25、 顺序存储方式的优点是存储密度大，且插入、删除這算效率高。()26、 在外部排序过程中，对长度为n的初始序列进行“償换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2o()27、 有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。()28、 B-树屮所有结点的平衡因子都为零。()四、简答题29、 用一个数组S(设大小为MAX)作为两个堆栈的共享空间。清说明共享方法，栈满/栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push(i,x),其中i为0或1,用于表示栈号，x为入栈值。30、请写出应填入下列叙述中()内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15,13,20,18,12,600下面是一组用不同排序方法进行•遍排序后的结果。()排序的结果为：12,13,15,18,20,60()排序的结果为：13,15,18,12,20,60()排序的结果为：13,15,20,18,12,60()排序的结果为：12,13,20,18,15,6031、已知图的邻接矩阵为：

VIV2V3V4V5V6V7VXV9VIOVI011i000000V20001I00000V30001010000V40000011010V5000000]000V60000000110VI0000000010V80000000001V90000000001VIO0000000000(3)该图唯一的拓扑有序序列。五、算法设计题32、已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。33、请编与完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件：A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。34、已知二叉树T,试写出复制该二叉树的算法（-T）。35、编写算法，求二叉树的宽度。参考答案一、 选择题1、 【答案】D2、 【答案】A3、 【答案】D4、 【答案】A5、 【答案】B6、 【答案】A7、 【答案】D8、 【答案】A9、 【答案】C10、 【答案】B二、 填空题11、 【答案】(.1)L->next=NULL〃置空链表，然后将原链表结点逐个插入到有序表中p!=NULL〃当链表尚未到尾，p为工作指针q!=NULL〃査P结点在链表中的插入位置，这时q是工作指针p->next=r->next〃将P结点链入链表中r->next=p〃r是q的前驱，u是下个待插入结点的指针12、 【答案】起泡；快速13、 【答案】分配和释放存储空间：重组；对插入的记录@14、 【答案】(Q,A,C,S,Q,D,F,X,R,H,M,Y);(F,H,C,D,a,A,M,Q.R,S,Y,X)15、【答案】free(T);q&&q->data!=A;q=q->rchild;p->lchild=null;p->rchild=null

16、【答案】0(m+n)17、【答案】0112231218、【答案】93三、判断题19、【答案】X20、【答案】、21、【答案】rV22、【答案】rV23、【答案】X24、【答案】X25、【答案】X26、【答案】X27、【答案】X28、【答案】、四、简答题29、答：两栈共享一向量空间(一维数组)，栈底设在数组的两端，两栈顶相邻时为栈满,，设共享数组为S[MAX],则一个栈顶指针为一1,另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push(i,x)如下：constMAX■共享检可能达到的最大容量typedefstructnode(elemtypes(MAXJ;inttop(2];}anode;anodeds;intpush(intI,elemtypex)//ds为容暈冇MAX个类型为elemtype的元素的一维數组，由两个校共享共空间.[的依为。或1//x为类5?为elemtype的元素.本算法将x压入枝中.如压栈成功，返回，否则，返闵°{if(ds.top[1]-ds.top(0]—1)(printf(•栈凋\n・);return(0>;>switch(i)(case0：ds.s(**ds.top(i]]-x;break;case1：ds.s(—ds.topl}return(l);//入桟成功30、答：①快速排序②起泡排序③直接插入排序④堆排序31、答:(1)V1,V4,V9,V10,V7,V6,V8,V3,V2,V5(2)V1,V4,V3,V2,V9,V7,V6,V5,V10,V8(3)V1,V2,V5,V3,V4,V6,31、答:(1)V1,V4,V9,V10,V7,V6,V8,V3,V2,V5(2)V1,V4,V3,V2,V9,V7,V6,V5,V10,V8(3)V1,V2,V5,V3,V4,V6,V8,V7,V9,V10五、算法设计题32、答：算法如下:voidPrelnCreat(BiTreeroot,ElemTypepre(Jrin[),lntllfhl,12.h2)〃根据二叉树前序序列pro和中序序列in建立二又树.11.hlW12, 个序I悄、区元素卜机(root-(BiTree)nalloc(sizeof(BiNode));//申请姑点root->data"pre(111；//pre(Il]根for(i-12;i<-h2—pre(11))break;//在中将序列中,银结点料树分或左右子例if(i--12)root->lchild"null;〃无左子树elsePreInCreat(root->lchild,prerin,ll*l,lH(i-12),12,i-l)；〃iW建立左子樹if(i-»h2)root->rchild-null;〃无右子树elsePreinCreat(root->rchild,pre,in,11*(i-12)*1,hl,i*bh2) 〃造归建学右子村)〃结束PrelnCreat33、答：算法如下:intm=10,n=10;voidSaddle(intA(m](n])//A足m，n的矩阵,本鼻法求矩阵A中的鸟胶点{inti,j,max[n]-{0},〃max数狙存放各列元素的行号，初始化为行号0〃min散组存放备行故小侦元泰的列号，初始化为列兮0for(i-0;i<m;i**) 〃选各行最小依元素和各列最大值元素for(j=0;j<n；j++)(if(A[max(j]][j]<A(i](jJ)max[j]-i;〃修改第j列最大元奏的佇号if(A[i](min(i)]>A(iH3Bmin(i]-j；〃住改第i行畋小元素的列号>for(i-0;i<ja;i++)〃窮i行域小元麥的列号if(i--max(j])printf("A[%d](td]元制N貼，，j,A(iHj});〃■岛協)}//Saddle34、答：算法如下:BiTreeCopy(BiTreet) //仅制二叉牌t的非递叮。法(typedefstruct(BiTreet,bt}node；nodeQlmaxsize]; 〃Q,&二叉树的結点指针的队列，容最足与大if(It)(bt-null;returnbt;)else(QueuelnfQUt/bt));while(SQueueEmpty(Q)){(t,bt)-QueueOut(Q);bt=(BiNode*jmallocfsizeof(BiNode))；bt->data=t->data:if(t->lchild)QueueIn(Q,(t->lchild,bt->lchi