2023年自考数据结构历年考题综合答案

C.索引存储结构D.散列存2.在长度为n的顺序表的第i(l≤i≤n+1)A.顺序表B.用头指针表达C.用尾指针表达的单循环链表5.一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别6.设有一5阶上三角矩阵A[1.5,1..5],现将其上三角中的元素按列优先顺序存放在一堆数组B[1..15]中。已知B[1]的地址为100,每个元素占用2个存储单元，则A[3,4]的地址为()7.一个带权的无向连通图的最小生成树()8.下列有关图遍历的说法中不对的的是()A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特性D.图的遍历规定每一顶点仅被访问一次9.某算法的空间花费s(n)=2°+n¹00+nlogzn+n¹⁰1,则其空间复杂度为()。10.单链表中的存储密度一定()。A.小于0.5B.等于1C.大于0.1D.小于111.在顺序栈中删除一个元素，至少要移动()元素。12.空串是()。A.只包含空格符的串B.长度为0的串C.只包含一个空格符的串D.不含字母的串13.采用三元组表存储稀疏矩阵，是为了()。A.节省存取时间B.节省存储空间C.提高对矩阵元素的访问速度D.提高对矩阵运算的可靠性14.高度为h的二叉树最多有()个节点。A.nB.n-e16.直接选择排序在最佳情况下的时间复杂度是()。A.O(n)B.O(nlogzn)C.O17.N个结点的m阶B树至少包含()个关键字。18.在散列文献中，同一个桶内的所有记录应当具有()。A.相同的关键字B.相同的散列值C.相同的某个属性值D.相同的存取频率19.在最坏的情况下，查找成功时二叉排序树的平均查找长度()A.小于顺序表的平均查找长度B.大于顺序表的平均查找长度C.与顺序表的平均查找长度相同D.无法与顺序表的平均查找长度比较20.散列表中由于散列到同一个地址而引起的“堆积”现象，是由()A.同义词之间发生冲突引起的二、填空题(每空1.5分，计15分)23.单链表的存储密度()顺序表的存储密度。24.设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是27.N(n>0)个节点的哈夫曼树恰含()个度为1的节点。28.深度为n的二叉树最少有()个结点。29.N(n>0)个顶点的连通有向图至少有()条边。④32.一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点?36.画出对下面的5阶B树插入关键字37后的结果。四、理解设计题(每小题5分，计15分)typedefstructnodel{intdata;structnodel且以head2为头指针的单链表中。(5分)typedefstruct{KeyTypekey;typedefnodeTypeSqLisvoidsort(SqListR,intn){//n小于MAXLEN-1if(R[k].key>R[k+1].key)for(i=k+1;R[i].key<R[n+1].key;i++)39.下面函数Binlnsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入适当的语句，使TYPEDEFSTRUCTNODVOIDBININSERT(SEQLISTR,INTN)NODET; }五、算法实现题(共10分)哨兵。避免边界检测，提高程序运营效率。low=mid+1;up=mid-1;low=mid+1;1.某算法的空间花费s(n)=2+n¹+nlogzn+n¹0I,则其空间复杂度为()。2.单链表中的存储密度一定()。A.小于0.5B.等于1C.大于0.1D.小于13.在顺序栈中删除一个元素，至少要移动()元素。当结点个数为0时，循环次数为3次。(7为栈顶)C.O(nlogzn)元素为D,则输出序列为输入端栈19.队列中允许进行删除的一端为20.设一棵二叉树中度为2的结点数为10,则该树的叶子数为021.如图所示的二叉树，若按后根遍历，则其输出序列为_。22.一个具有n个顶点的有向完全图的弧数为_。23,查找表的数据结构有别于线性表、树型结构等，其逻辑结构为24,长度为L的顺序表，采用设立岗哨方式顺序查找，若查找不成功，其查找长度为25.在开散列表上查找某元素时，通常分两步进行，一方面必须计算该键值的散列地址，然后在地址指针所指 中查找该结点26.文献的检索有顺序存取、和按关键字存取三种方式。27.在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所提成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为_。28.在对一组记录关键字(54,38,96,23,15,72,60,45,83)进行冒泡排序时，整个冒泡排序过程中需进行 趟才干完毕。三、应用题(本大题共5小题，共30分)29.设有一顺序队列sq,容量为5,初始状态时sq.front=sq.rear=0,画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。(6分)30.已知无向图G的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V₀开始的深度优先搜索的序列。31.画出下列二叉树的二叉链表表达图。(6分)32.用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。(8分)33.已知序列(10,18,4,3,6,12,1,9,15,8),请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。(6分)四、设计题(本大题共2小题，共14分){以head2为头指针的单链表中。(6分)一、单项选择题二、填空题16.索引存储方式17.q->next->prior=q->prior;18.DCBA19.队首三、应用题：29、图形略，提醒对于使用顺序表的队列，一般使用循环结构，否则随着出队入队次数的增多，一定会出现队尾益出顺序表的情况。32、比较次数顺序为：3、2、3、4、1、3、4、2、3、4在本趟末尾并入剩余的一组，结果为：if(p==NULL){printf(“Error1.在数据结构中，数据的逻辑结构可以提成()A.内部结构和外部结构B.线性结构和非线性结构C.紧凑结构和非紧揍结构D.动态结构和静2.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用()A.数据元素的相邻地址表达B.数据元素在表中的序号表达C.指向后继元素的指针表达D.数据元素的值表达3.设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是()s->next=p->next;t=p->data;p->data=s->data;s->data=t;D.在结点*p之前插入结点*s4.栈和队列都是()A.限制存取位置的线性结构B.顺序存储的线性结构5.若数组s[0.n-1]为两个栈s1和s2的共用存储空间，且仅当s[0.n-1]全满时，各栈才不能进行进栈操作，则为这两个6.执行下列程序段后，串X的值为()A.”cdefgh"B.”cdC."cdefxy"D."cdefef"7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是由于()A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在顺序关系D.数组是多维结构，内存是一维结构8.从广义表LS=((p,q),r,s)中分解出原子q的运算是()A.tail(head(LS))C.head(tail(LS))9.在具有n个叶子结点的严格二叉树中，结点总数为()LinkListpa=La->next;->data)while(pa&&pd)pre=pb;next;}elseif(pa>data>pb(1)写出执行函数调用strc(s,r)的返回结果，其中s=“aba”,r="abababa”;(2)简述函数strc的功能。{while(i<str->length-sub->length+1){j=i;k=0;while(k<sub->length&&str->ch[j]==sub->ch[kj++;k++;}if(k==sub->length)typedefstruct{typedefenum{FALSE,TRUE}Boolean;{}intj;|}}{printf("<%c,%c>"G->vexs[i],G->vexs }33.已知整形数组L[1..8]中的元素依次为(9,8,5,7,6,3,2,1),阅读下列函数，并写出执行函数调用sort(L,8)时，对L进行的头两趟(pass分别为0和1)解决结果。Voidsort(intR[],intn){{if(R[k]>R[k+1])注：找17需1次比较，找33需1次比较，找31需3次比较，找40需2次比较，找48需4次注：找17需1次比较，找33需1次比较，找31需3次比较，找40需2次比较，找48需4次30、pre->next=pb;pre->next=pa;假设BinNode是如图所示的结点类型，BinTree是指向树根的指针类型；{也可以写成下面的形式：一方面定义全局变量count,并赋初值0。voidtongji(Bintre{}1.下列数据组织形式中，()的各个结点可以任意邻接。A.集合B.树形结构C.线性结构D.图状结构2.设某二维数组A[1.n,1.n],则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为()A.O(log₂n)B.O(n)C.O(nlogzn)D.O(n²)3.在线性表的下列存储结构中，读取元素花费时间最少的是()A.单链表B.双链表C.循环链表D.顺序表4.将一个头指针为p的单链表中的元素按与原单链表相反的顺序存放，则下列算法段中的空白处应为{}p=q;A.r=q;q=p;p=p->next;q->nB.q=p;r=q;p=p->next;q-D.q=p;p=p->next;r=q;q-5.数组通常具有两种基本运算，即()A.创建和删除B.索引和修改C.读和写D.排序和查找15.在列各种文献中，不能进行顺序查找的文献是()。第二部分非选择题二、填空题(每题2分，计20分)16.抽象数据类型是指数据逻辑结构及与之相关的()。17.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的()结点。q=p;while(q->next!=p18.假设S和X分别表达进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由a*b+c/d得到ab*cd/+的操作序列为()。19.在文本编辑程序中查找一个特定单词在文本中出现的位置，可以运用串的()运算。20.假设以行优先顺序将一个n阶的5对角矩阵矩阵压缩存储到一维数组Q中，则数组Q的大小至少为()。21.在具有100个结点的完全二叉树中，叶子结点的个数为()。22.在无向图中，若从顶点a到顶点b存在(),则称a与b之间是连通的。23.假如排序过程不改变()之间的相对顺序，则称该排序方法是稳定的。24.索引顺序查找适宜对()的顺序表进行查找。25.文献的检索操作可按检索条件不同分为下列四种询问，它们是简朴询问，范围询问，函数询问和()询问。三、解答题(每题5分，计20分)E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。voidMergeSortDC(Seqliif(low<high){mid=(loMergeSortDC(R,low,mid);MergeSortDC(R,mid}29.由于元素的插入先后顺序不同，所构成的二叉排序树也许有多种形态，请画出4棵含1,2,3,4,5,6六个元素并且以1为跟，深度为4的二叉排序树。四、算法阅读题(每题5分，计20分)30.L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组LinkListf30(LinkListL,ip=(①);Lc=(LinkList)Malloc(sizeof(ListNode));Lc->if(p->data>c){pre->next=p->next;(②);Lc->next=p;p=pre->next;}31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。if((i=!i)!=0)Push(&Twhile(!StackEmpty(&T))Push(S,Pop(while(!QueueEmpty(&T))Push(S,DeQueueintedges[MaxNum][MaxNum];intn,e;}Mgraph;voidf33(intR[],intn)while(low<high&&R[low]<0}}五、算法设计题(每题5分，计20分)34.假设以二叉链表作为二叉树的存储结构，其结点结构为：依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中参数level为函数执行过程中T当前所指结点的层次，其初值为1;*lmin与*lmax分别为叶子结点的最小层次和最大层次，它们的初值均为0。voidf34(BinTreeT,in21.50(只有一个度为1的结点，且n0=n2+1)1A13B313C134D420E20typedefstructnode{}EdgeNode;//边表结点结构描述VertexNodeadjlist[MaxNu}ALGraph;//邻接表结构描述typedefenum{FALSE,TRUE}for(i=0;in;i++)if(!visited[i])DFSTree(Gi);}printf(”<%c,%c>",G->adjlist (1)假设数组L[8]={3,0,5,1,6,4,2,7},写出执行函数调用f32(L,8)后的L;voidf33(LinkListL,LinkListH[],in{ }}五、算法设计题(本大题10分)34.假设以带双亲指针的二叉链表作为二叉树的存typedefBinTNode*BinTr若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。/继续遍历Lb)假如*px无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点；(2)BinTNode*fintNext(BinTNode{while(q->Ichild)q=q->Ichild;//寻找其右孩子的最左点returnq;while(qp)/未回溯到根结点{}}C.快速排序D.选择排序二、填空题(本大题共13小题，每小题2分，共26分)21.二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[o][0]的存储地址是100,23.若某二叉树中度为1的结点数为4,度为2的结点数为6,则该树叶子结点数为。28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据所有存放在计算机的 三、应用题(本大题共5小题，每小题6分，共30分)30、设散列函数为H(Key)=Key%11,散列表长度为11(散列地址空间为0…10),在else{f35(T->Ichild);}}1.下面程序段的时间复杂度是()A.O(n)B.O(m+n+1)C.O(m+n)2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()A.p=p->next;B.p->next=p->next->next;C.p->next=pD.p=p->next-3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则()C.*p的直接后继是头结点D.*P的直接后继是尾结点4.鉴定“带头结点的链队列为空”的条件是()A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear5.设有两个串T和P,求P在T中初次出现的位置的串运算称作()7.一棵含18个结点的二叉树的高度至少为()广度优先遍历也许得A.acefbd题10图A.便于进行插入和删除运算B.便于进行文献的恢复二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)题19图18.在队列中，允许进行插入操作的一端21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100,则元素A[9][8][7]的存22.已知在一棵具有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中具有的叶子结点的数目为三、解答题(本大题共4小题，每小题5分，共20分)名字符在电文中出现的频度分别为：34,5,12,23,8,18,试为这6邻接表进行深度优先遍历时得到的顶点序列为acbefd,进行广度优先遍历时得到的顶点序列为acbdfe。14221422344202343题27图28.已知两个4×5的稀疏矩阵的三元组表分别如下：2225344229.从空树起，依次插入关键字40,8,90,15,62,95,12,23,56,32,构造一棵二叉排序树。(2)画出删去该树中元素值为90的结点之后的二叉排序树。四、算法阅读题(本大题共4小题，每小题5分，共20分)题30图对于i=0或1,front[i]和length[]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队intEnQueue(Queue2*Q,inti,DataTypex){//若第i个队列不满，则元素x入队列，并返回1,否则返回0已知邻接表的顶点表结点结构为：边表结点EdgeNode结构为：已知邻接表的顶点表结点结构为：边表结点EdgeNode结构为：31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答(1)写出执行函数调用f(p)的输出结果；BB{AAF题31题31图}32.下列函数FindCycle(Gi)的功能是，对一个采用邻接表作存储结构的有向图G,运用深度优先搜索策略寻找一条通过顶点v;的简朴回路。数组cycle_path用于一个顶点是vj。请在空缺处填入合适的内容，使其成为一个完整的算法。intFindCycle(ALGraph*G,inti){//若回路存在，则返回1,否则返回0intj;for(j=0;j<G->n;j++)cycl}intDFSPath(ALGraph*Gintj,inti)for(p=G->adjlist[j].firstedge;p&&!cyc{(1)假设整型数组A[1..8]中的元素依次为(3,8,9,1,7,4,2,6)。执行函数调用algo(A,8)时，外层while的循环体intalgo(intL[],intn){{五、算法设计题(本大题共10分)17.向前移动ae1114222534042四.算法阅读题30.(1)Q->length[0]+Q->lengt33.(1)函数的返回值为：4,得到的序列是：21346789外层循环执行了5次。(2)函数的功能是把无序序列划分为以首关键字为界的两个序列。左边序列的关键字都比3小，右边序列的关键字都比3大。1.根据数据元素的关键字直接计算出该元素存储地址的存储方法是()A.顺序存储方法B.链式存储方法C.索引存储方法D.散列存储方法2.下述程序段中语句①的频度是()C.(m+2)(m-1)/2A.0(n)和0(1)B.0(1)和0(1)A.rear->next==headB.rear->next->next==headC.head->next==rearD.head->next->next==rear次数是()7.串s=“DataStructure”中长度为3的子串的数目是()A.9B.11则存储地址为2836的元素是()A.R[3][3][3]B.R[3][3][4]A.0(n)C.0(n+e)A.0(n²logzn)B.0(n²)C.0(nlog₂n)D.0(log₂n)关键字应为()二、填空题(本大题共10小题，每小题2分，共20分) 三、解答题