自考2021年4月数据结构真题及答案

2021年4月高等教育自学考试全国统。命题考试

数据结构一、单项选择题:本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。下列选项中，不属于线性结构的是A.线性表B.双向链表.C.循环队列D.二叉树某线性表L含有n个元素，釆用单循环链表保存，仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是A.0(l)和0(1)B.O([)和0() C.O(n)和0(1)D.O(n)和0()下列应用中会用到栈的是A.计算后缀表达式的值B.图的广度优先遍历C.对数组进行希尔排序D.对散列表法行查找设栈初始为空，入栈序列为1,2,345,下列选项中，不可能得到的出栈序列是A.1,2,345B.3,1,4,2,5C.4,3,2,5,1D.5,4,3,2,1己知广义表LS=((C,()),(e,)),(g,b),(m,n)),,head(LS)是A.CB.(C)C.(C,(d))D.())(,()0)设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存储地址为200,则第s个元素占用的最后一个存储单元的地址是A.239.B.240.C.247D.248-棵完全•.又树T的全部k个叶结点都在同"层中，每个分戈结点都有两个核于结点.T中包含的結点数是A.k B.2k-l C.F D.^-1设字符集中有n个字符.对其进行哈夫曼编码.得到的哈夫曼树的結点兑敷是A.2n-l B.2n C.2n+】 D.不确定设图G的邻接电阵A如下所示。G的各顶点的度依次是0101*X=°°1'0100.1000A.1,2,1,2B.2,2,1,1C.3,4,2,3D・4,4,12对題10-11图进行深度优先遍历，下列选项中，止确的逼历序列是题10-11图AL234SB.2.3.5.4.1C.3.5.1.2.4D.4.3.5.1.2对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是A.1,23,4,5 B.2,3,1,4,5C.3,5,1,2,4D.5,3,1,2,4下列排序方法中，不是稳定排序方法的是A.直接插入排序B.冒泡排序C.归并排序D.快速排序已知数据序列(18,19,20,4,51,6,30.1,2)是某种排序算法第二趟排序后得到的结果，则该算法可能是A.选择排序B.冒泡排序C.直接插入排序D.快速排序对有序表(1,3,9.12.32,41,45,62,7,7)进行二分查找，查找关键字9时，进行比较的关键字依次是A.1,3,9B.32,3,9C.32,12,9D.41,12,9分别使用下列数据序列建立二叉排序树，能得到高度最高的二叉树的是A.10,8,9,6,12,11,13B.10,6,8,9,12,11,13C.10,12,11,13,8,6,9D.10,8,6,9,12,13,11.第二部分非选择题二、填空题:本大题共10小题，每小题2分，共20分。数据的运算，即对数据元素施加的操作，是定义在数据的_结构.上的。在顺序表中，因为访问任一•结点的方式是 ,所以访问每个结点的时间复杂度均为0(1)。带头结点的链队列可以由一个头指针和一个尾指针唯--确定。当头指针和尾指针相等时，表示队列稀疏矩阵釆用压缩存储，只保存非零元素，得到的顺序存储结构称为 。广义表((a),(b,0),(d,c,(,gh)))的表尾是中序线索化二叉树的过程，是在中序遍历过程中用线索取化 在有n个顶点、e条边的无向连通图中，e的取值范围是 对数据序列进行升序排序。采用堆排序算法时，首先应对初始数据建立.堆。在无序数组中进行査找操作，应使用的査找方法是 -•棵高度为2的4阶B树中能够保存的关键字个数最多是三、解答题:本大题共4小题，每小题5分，共20分。请画出题26图所示的二叉树对应的树或森林。題26图求题27图从顶点A到其余各顶点的最短路径，给出各条路径包含的県点序列及路径长度。題27图有以下数据序列(20,84,19,14,23,01,68,27,s,II,10,79,12),使用二路归并排序算法将其排成升序序列。给出各趟排序结果。设有以下关键字：Is,72.5s2.65,23,68,散列函数H(key)=key%7.散列表空间为0~6,釆用线性探査法解决冲突。请回答下列问题。构造散列表。计算等概率情况下查找成功时的平均查找长度。四、算法阅读题:本大题共4小题，每小题5分，共20分。顺序表类型定义如下。^defineListSize100typedefstruct{inidata[ListSize1;intlength;}Seqg阅读下列函数.并回答问is.SoqlJst•00(int*pd«rfa.itrtn)(in!k,m;ScqList*SL；SL=(SeqListQmalkx^sizeoRScqList));SL>length-0;forS0;k<n;k++){if(pdala[kJ%2!=0)SL~>data(SL>length]•,pdata[k];else{fbr(m-SL->lcngth;m>0;m-)SL>data[m]-SL>dala(m-1];SL->data(0J=pdata[k];else{for(m=SL->lcngih;m>0;m—)SL>data[m]~SL>data[mT];SL>data(0]=pdata(k);}SL->lcngthi;for(k=0;k<SL->lcngth;k-w-)prinlR"%d,",SL>data(k]);returnSL;(丨)若已^1：intarray[J{10,2,9,5,30,3};,执行语句：60(array,sizeoRarray)/sizcoRin。);函數130()的输出是什么？(2)函数仃0()的功能是什么？阅读函数Bl(),并回答问袈。f3l(inta(J,intn)(intk,m-0,temp;•*********-***-"-** -•:while(a[m]<0&&m<n) 〃说明木循环的作用: m=m+l;k~m;while(k<n){whilc(a(k]>-0&&k<n)k=kH;if(k<n)(temp=a(k];a[m]=temp;m=m+1:m=m,1;(1〉若int町={25,4.256,9,-38.47,128,-256,64};,则执行语句:⑶(a,9)；数组a中的数据是什么？(2)说明方框内while语句的作用.

二又排序树的存储结构类型定义如卜《typedefintKeyType;typedefstructnode(Keyiypedata; //data赴数据域structnode*Ichild,*rchild;//分别指向左右孩子}BinNode;typedefBinNcxle•BinTree;阅读下列算法，并回答问题.void(32(BinTreeI.Kcyl^pcKI,KcyTypeK2)(if(t!=NULL){132(t->lchild,KI.K2);if(r>data>=K1&&t->data<=K2)printf("%d\t~>data);f32(L>rchild,KI,K2);}}(1)设二叉排序树T如題32图所示，给出执行语句：B2(T,I4,5O);输出结果.题32图（2）函数（320的功能是什么？待排序记录的数据类型定义如下。^defineMAXSIZE100typedefintKeyType;typedefstruct(KeyTypekey;}RecType;typedefRecTypcSeqList[MAXS1ZE];函数f33O对R采用宜接选择排序进行升序排序，清在空白处填上适当内容使算法完整.voidB3(SeqListR,intn){intfor(i»1;i<=n;i++)(k-i;TOC\o"1-5"\h\zfor(j-i*l; ⑴ :ix)if( (21 )k・j;jf( 02 )(R(0]-R(i]；R[i】=R[k]；R叶R[0];}}}五、算法设计毒本題2分.己知単链表的存储结构类型定义如卜・typcdefintDataiypc;typedcfstnictnodc(Dataiypedata;structnode*next;}I.istNodc;typedefListNode•LinkList;ListNode，p;LinkListheadl;双向链羨的存储结构类型定义如下・typedefstructdInode(Dalaiypedata;structdlnodcprior,*next;}DLNodc;typedefDLNode•DUnkList;DLinkListhead2;编写程序，財给定的単链表headl,将其中的数据按原次序复制到双向链表head2中.函数懺型为：voidf34(headl,&head2);.2021年4月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考(课程代码02331)-、单项选择题:本大题共15小题，每小题2分，共30分。1.D2.A3.A4.B5.D6.A7.B8.A9.C10.A11.D12.D13.C14.B15.B二、填空题:本大题共10小题，每小题2分，共20分。16.逻辑17.随机访问18.为空19.三元组表20.((b,c),(d,e,(f,g.b)))空指针n-lWeWn(n-l)/223.大24.顺序査找(或线性査找)25.15三、解答题：本大题共4小题，每小题5分，共20分.26- ”切27.目标顶点路径所含顶点序列路径长度到顶点BACB12（1分）到顶点CAC）0（1分）到顶点DACD13（1分）到顶点EACBE19<1分〉覧顶点FACF20(丨分)（1（1分）（2分）（I分）（I分〉《3分）初始：20,84,19.14,23,01,68.27,55,II.10,79,12一趟归并：20.84.14.19.01,23,27,68,11.55.10,79,12二趟归并：14.19,20,84,01,23.27.68,10.11.55.79.12三越归并：01.14.19.20.23,27,68,84,10,11.12.55,79四趙归并:01.10,11.12.14,19,20,23.27.55.68.79.84(I)15 72 52 65I23 68【评分说明】故列衣中每正确填入2个项.脩丨分.（2分）(2)ASL—（2分）四、算法阅读題：本大題共4小題，每小題5分，共20分.TOC\o"1-5"\h\z<1）30,2,10,9,5,3. （3分）（2）根据所给的数据建立顺序表，将偶数从水头插入，奇数从表尾抽入.（2分）（1）-38.-256,256.9.25.47.128.4.64 （3分）（2）找到数爼中第一个非负数的位置一 （2分）（1）1618253650 （3分）<2）斉找义惜序列T中所冇満足大干等于心且小于等于K2的元素.并按升序输出. （2分）（I）j<-n （2分）（2） R（j）.key<R（k|Jcey （2分）（3） k!-i （I 分）丘、算法设计题：本題10分.34.，号程序如下.voidf34(LinkListhl.Dl.inkList•hl)(ListNodc*tcmpl