02331数据结构201804真题及答案.docx

2018年4月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）本试卷共8页，满分100分，考试时间150分神。考生答SS注意事项：1 .本卷所有试Sfi必须在答题卡上作答.答在试卷上无效，试卷空白处和背面均可作草稿纸.2 .第一部分为选择题，必须对应试卷上的摩号使用28铅笔将“答题卡”的相应代码涂黑,3.第二部分为非选择题.必须注明大'小题号，使用0.5充米黑色字迹签字笔作答。4.合理安排答题空间.超出答迤区域无效.第一部分选择题一、单项选界I1.本大题共15小题，每小题2分,共30分.在每小JB列出的备轲中只有一项是符合题目要求的，靖珞其选出.1 .数据结构不包含的内容是A.数据的元素来源B.数据的选卷结构C.数据的存储结构D.对数据脩加的操作2 .下列选项中璃于逻辑结构的是.循环队列B.二叉树C.欣列表D.邻接表3 .下列选项中，属于顺序存储结构优点的是A.插入运算方便B.删除运算方便C.存储密度大D.方便存储各种逻辑结构-1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和刷除第一个元素，则下列存储结构中，酸节省运分时间的是A.单链表B,仅有头指针的单循环链表C.双向混表D.仅有尾指针的单.循环鞋表5.用不带头结点的单链衣存储队列,在进行删除运券时A.仅修改头指针B.仅修改尾指针C.头、尾指针一定都要脩改D.头、尾指针可能都要修改6 .二维数组M,行下标取值数因为08,列下标取值范围为1.10.若按行优先存储时，元素M85的存储地址为ar，则按列优先存储时,地址r存储的数纲元索应A.M8(5B.M(S8C.M(31OD.M(097 .根据二叉树的定义,3个结点构成的二叉树的树型有A2种B.3肿C.4种D.5种8 .一棵有序树可转换为一榇二叉轲，树的后序遍历对应二叉树的A.前序迫历B.中序迫历C.后序遍历D.以上都不对9 .若图G的邻接我中有奇数个衰结点，则G是A.含奇数个顶点的图B,无向图C.含儡数个JJ1.点的图D.有向图10 .若用邻接矩阵存储科向图,矩阵中主对角线以下的元素均为零，则关于该图拓扑抻序序列的结论是A.存在.且唯一B.存在,且不睢一C.存在,可能不唯一D,无法确定是否存在11 .如果无向图G的最小生成树7中含有边Gb)和G,c)则下列选项中,一定不在T中的边是12 .下列排序算法中，在每一物都能选出一个元素放到其量终位上的是A.插入排序B.希尔精序C.归并排序D.堆排序13 .若数据元素序列11,13,15,7,8,9,23.2.5是采用下列排序方法之一得到的第二削抻序后的结果，财谟)序算法是A.冒泡推序B.结入排序C.选择排序D.归井持序14 .我性我采用顺序存储或链式存储，对其进行杳找的方法应是A.修序查找B.二分查找C.般列查找D.索引jg找15 .设有序表为1,3,9,12,32,41,45,62,75,77,82),采用二分查找法查找关键字7S查找过程中关键字之间的比较次数是A.IB.2C.3D.4第二部分非选择题二'填空题：本大县共K)小题，每小2分，共20分.16 .在数据结构中，从逻辑上可以把数据结构分为线性结构和.17 .为便于实现单链表的推入及除运算，It要在单链表中if加一个结点.该结点称为18 .在二修df1.A10M8中.每个效蛆元素占用4个存得单元，则敷If1.A需要的存储单元个数是.19 .对长度为I的广义表A,若有Head（八）Ti1.（八）,MA-.20 .设高为劣的二叉树T中只有度为。和2的结点.则7包含的结点数多为.21 .一个连通图的是包含图中所有顶点的极小连通子图.22 .无向图G中含7个点.顶点间的边是Ia机设置的,为保证图G在任何情况下修是连i的.则偌要的边数最少是,23 .求学源最迫路校的逑杰斯特拉(Dijkstra)算法是按照路梗不减的次序求出各条路径的.24 .一蛆记录的关9字为(45.53.18,49,36.76.13.97,36,32),利用快H排序方法对其进行排序.选择4S为基准.一次划分后的结果为25 .对IU抻序的改进和推广的持序算法是.三'MSH：本大题共4小题，每小JK5分,共20分.26 .两个枝共享数出空间data(m(定义如下M它的的根底分别设在数里的两墙初始化后topi三-I,top2=m).typedefstructDataTypcdaum;irttop】，top2;ScqStack;回答下列问题.编写判断收满的函数HStackfuJKScqSttcks):(2)编写进极函数VOidPUSh(SeqSIaCks,.intsi,DataIyPex)>其中，Si取值为0、I.分别表示枝底为0或m的栈.27 .已知二叉树T中含有元素A.B,C,D,E,F,G,H,7的前序遍历序列、中序遍历序列和后序造历序列如下，其中符号.表示未知元素.试写出到所代表的正确元素ffi.GFCFGFECH前序遍历序列ABD中序也历序列BA后序造历序列28 .设图G如题28图所示/队列定义/队列初始化/判队列是否空回答下列问JK.(1)图G是否是有向无环图？(2)给出图G所有的拓扑排序序列.29 .设关健字序列为：53,15,72,52,48,67,63.23.已知敢列表地址空间为。11散列由数为H(k)-kmodi1,采用线性探查再敢列法解决冲突.(I)将所给关键字数据依次填入该股列表中：(2)计算等概率下查找成功的平均查找长度.四、算法阅读胸：本大题共4小题，银小题5分，共20分30 .已知队列的基本掾作定义如下，请在空白处填写适当的语句,完成指定的功能.dcfincQueueSize100tyedefstructchardataQucucSize;i11tfront,rear;CuQucue;CirQueueQ;voidInitQucuc(CirQucueQ)Q->frort-Q->rear-0;intQueueEmpty(CirQueueQ)i11tQueueFuIKCiiQueueQ)return(Q->rear÷1)%QueueSize三三Q->front;charEnQueue(CirQueue,Q.charc)if(QeeFuKQ)return0'e1.seQ->dataQ->rearJ=c;Q->rear-2;returnc;charDeQUeUe(CirQueucQ)Charx；if(QUeueEmP(y(Q)returnW;e1.seX=Q-><fattQ->front;Q->front三(3;returnx;/判队列是否清U入队操作H掾作失败U操作成功/出队列掾作/掾作失败U掾作成功31 .程序G1.是将恰入的m行n列的二致组a交换为三元蛆表形式存储在数组b中.请在空白处填上适当内容将第法扑充完整.MefineMAXSIZE100typedcfi11tDataiype;Iypcdcfstructi,j;非等元素行列下标Dateiypev;/非零元素值DiRip1.eNode;typcdcfstructTri-HipteNodedMa(MAXS1.ZE;存储三元SHSif1.int11n,t;/m矩阵的行.n：矩阵的界.U聋零元素数量JTSMatrk;voidG1.(TSMafrixb,inta,i11tmaintn)将m行n列的矩阵a变换为三元窃我形式存储在b中i11ti,j,k-0;for（三）;i<m;r+)酎(j-0；j<n;j+)if(a!-0)b-><fate(k.i-i;b->uk.j三j;b->dta(k).v三;_(2):b->n三n;32.已知二叉树7如题32图所示.阅读程序B2,写出执行B2(T)的*出结果typcdcfcharDataTypc;typedefstructnode(Data1.ypedata;structnode!chi1.d,rchi1.d;JBinTNode;typedcfBinTNodeBinTree;VOidOZ(Bin1.reebc)(if(b1.!-NU1.1.)(D2(b<->du1.d);printfC%c'.b<->da);02(b<->1.chjd);/data是数据域U分别指向左右孩子执行结果：3.阅读程序，写出执行结果.voidG3(i11ta(,intn)(Hi；for(iiy2;A0;i-)Sift(a,1.n1.);)VOidSift(inta,inti,inth)tj.temp三i;j-2i+1.;VdIiIe(j<h)if(j<ha(j)<aj+1.)+iif(tempxa(j)break;ra-;i-j；j-2i+1.;ai=temp；)in(mai110(inta10-10,20,5,23,25.62,21.1,32.91;03(a,10);for(PO;i<10;i+÷)printf("%d=",a(i);printf("n");returnO;执行结果：五'算法设计JK：本JK1.o分.M.已知带有头结点的单修表定义如下：typcdcfstructnodecharch;structnode*next;1.istNode;typedef1.istNodee1.ink1.ist;请编写函JSHM1.ink1.isth.CharsringU),根据箱入的字符串.建立不含工复字符的链表.绝密启用前2018年4月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）一、单项选瑾题：本大题共15小题，每小题2分，共30分1.A2.B3.C4.D5.D6.C7.D8.B9.D10.C11.A12.D13.B14.A15.B二、填空题：本大题共10小题，每小题2分，共20分.16.非线性结构17.头结点18.32019.(O)20.2h-1.21.生成树22.1623.长度24.32,36,18,!3,36,45,76,97.49.5325.基数排序解答题：本大题共4小题，每小题S分,共20分.26 .答案:（I）判断栈满intstackfu1.1.(SeqSuck*s)returns->top1.+1.-s->top2;(1分)(2)进栈voidpush(ScqStacks,intsi,DataTypeX)if(stackfu1.1.(s)printf("satckoverf1.ow”);(1