2019年04月自学考试02331《数据结构》真题.docx

2018年4月高等教育自学考试数据结构试题课程代码：02331一、单项选择题1 .线性表是一种由n个数据元素组成的数据结构，n的取值是.0或者任意一个正整数或者8B.非负整数C.任意一个正整数或者8D.某个正整数2 .在一个单链表中，己知q所指结点是P所指结点的后继结点，若在P和q之间插入S所指结点，则正确的操作是.s->next=p->next:p->next=s;B.s->next=q:p->next=s->next;C.q->next=s;s->next=p;D.p->next=s;s->next=p;3 .下列选项中，不宜通过栈求解的问题是Ao判断字符串是否是回文B.检验圆括号是否匹配c.不同数制之间进行转换D.图的广度优先搜索遍历4 .设栈S的输入序列为1,2,3,4,5,则下列选项中不可能是S的输出序列的是A.2,3,4,1,5B.5,4,1,3,2C.2,3,1,4,5D.1,5,4,3,25 .使用一个大小为6的数组保存循环队列Q。若从Q中出队两个元素，并入队一个元素，此时队尾rear和队头front的值分别为2和4。则在执行这三个操作之前rear和front的值分别是A.0和3B.1和2C.2和5D.4和56 .设二维数组M有3行4歹U，按行优先的方式存储，每个元素占6个存储单元。第1个元素的存储地址为100,则M2II2的存储地址为A.135B.153C.160D.1657 .设/2阶方阵M是对称矩阵，采用压缩存储方式将M中的元素保存在一维数组B中，则下列选项中，正确的是A.保存M中的主对角线中的元素，B的元素个数是B.保存M中上三角部分的元素，B的元素个数是5-1)/2C.保存M中上三角部分的元素，B的元素个数是(+1)/2D.保存”中的全部元素，B的元素个数是8 .己知完全二叉树T的第4层有5个叶结点，则T的结点个数最多是A.12B.20C.21D.369 .在一棵非空二叉树的后序遍历序列中，所有列在根结点前面的是.左子树中的部分结点B.右子树中的全部结点C.左右子树中的部分结点D.左右子树中的全部结点10 .若对题10图所示的无向图进行深度优先搜索遍历，则下列选项中正确的遍历序列是A. h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC. d,b,c»a,h,e,f,gD.a,b,c,d,h,e,f,gH.对题11图所示的有向图进行拓扑排序。下列选项中能够得到的拓扑序列是A.3,1,2,4,5,6B.3,1,2,4,6,5D. 3,1,4,2,5,6D.3,1,4,2,6,512 .己知数据序列(8,9,10,4,5,6,20,1,2)是某种排序算法第一趟排序后得到的结果，则该算法可能是A.选择排序B.起泡排序c.直接插入排序D.快速排序13 .下列选项中，每一趟都能选出一个元素放在其最终位置上，且不稳定的排序算法是A.起泡排序B.希尔排序c.归并排序D.快速排序14 .对有序表(1,9,12,41,62,77,82,95,100)采用二分查找方法查找值82,查找过程中关键字的比较次数是A.1B.2C.4D.715o将下列数据依次插入到初始为空的二叉排序树中，能得到高度最小的二叉排序树的序列是A.2,4,7,5,8,10B.5,1,2,6,3,4C.6,4,1,8,10,5Do9,7,2,1,4,0二、填空题16 .线性表的存储方式中，能够随机存取表中任一元素的存储结构是。17 .用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342的出栈顺序，相应的S、X操作串为o18 .若广义表L的深度是8,则L一定是o19 .广义表(a,b),(c,d),e)的表尾是。20 .利用二叉树中的空指针域，使之指向结点在某种遍历次序下的前趋或后继结点，此时域中的内容称为O21 .若用个带权字符构造哈夫曼树T,则T中结点的总数是o22 .设连通带权图G中有个顶点，使用普里姆算法构造G的最小生成树T,T中含有的边数是23 .要使n个记录的关键字序列&&，勺成为小根堆，关键字之间必须满足的关系是024 .索引顺序查找是一种将顺序查找和二分查找思想结合在一起的查找方法，又称为O25o5阶B树T中，除根结点之外每个结点中所含关键字个数最少是o三、解答题26 .设稀疏矩阵M如下所示。矩阵的行列下标均从1开始。请画出M按行优先存储的三元组表。(0-8060、70000-500030000;27.己知二叉树T的前序遍历序列是A,B,C,D,E,L,M,O,N,中序遍历序列是C,B,E,D,A,M,O,L,N,请画出T。28.已知有向带权图G如题28图所示。题28图29 .设有关键字序列(65,23,31,26,7,91,53,15,72,52),散列函数为H(key)=key%II,将关键字依次放入表长为11的散列表H中，采用线性探测法处理冲突。请回答下列问题。(1)画出构造的散列表，并给出查找每个关键字的探查次数。(2)求散列表的平均查找长度ASL0四、算法阅读题30 .顺序表类型定义如下:#defineListSize100typedefstructintdataListSize;htlength；JSeqList;阅读下列算法，并回答问题。voidmysum(SeqList*SLI,SeqList*SL2)(intminlength,k=O;minlength=SL2->length;for(k=O;k<minlength;k+)if(SLl->datak<SL2->datak)SLl->datak+=SL2->datalk;elseSL2->datak+=SLl->datak;return;void130(SeqList*SL1,SeqList*SL2)if(SLl->length>SL2->length)mysum(SL1,SL2);elsemysum(SL2,SLl);return;)(1)若SLl->dataW(52J4,256,-9,-38,30J28,257,64),SL2->data中的数据为(32,14,-63,15,29,51,16,8),则执行算法f30(&SLl,&SL2)后SLl->dataSL2->data中的数据各是什么？(2)该算法的功能是什么？31.二叉树的存储结构类型定义如下：typedefintDataType;typedefstructnode(DataTypedata;/data:是数据域structnode*1child,*rchild;/分别指向左右孩子BinTNode;typedefBinTNode*BinTree;阅读下列算法，并回答问题。ihtheight(BinTreeT)(int!high=0,rhigh=0;if(T=NULL)return0;else!high=height(T->lchiId);rhigh=height(T->rchild),if(Ihigh>rhigh)returnIhigh÷1;elsereturnrhigh+1;voidf31(BinTreeT)intIeftHigh=O,rightHigh=O;BinTreetemp;if(T=NULL)return;elseif(height(T->lchiId)<height(T->rchild)temp=T->lchiId;T>lchild=T>rchild;rP>rchild=temp;)1f31(T->lchild);l(T->rchild);return;(1)设二叉树T如题31图所示，画出执行f31(T)后得到的二叉树T1。题31图给出函数131()的功能。32 .设顺序表的存储类型定义如下：/defineListSize100typedefintKeyType;typedefstruct(KeyTypekey;)NodeType;typedefNodeTypeSeqListListSize;函数G2()的功能是，基于二分查找在长度为n的有序表R中插入一个关键字x,并保持R的有序性。请在空白处填上适当语句使算法正确。voidf32(SeqListR,KeyTypex,ihtn)intlow=0,high=n-l,mid,inspaee,i,find=0;while(low<=high&&!find)mid=(low+high)/2;if(x<RmidJ.key)(1);elseif(x>Rmid.key)low=mid+1;elsefind=1;if(find)inspace=(2);elseinspaee=low;for(i=n;(3):i-)Ri+1=Ri;Rinspace.key=x;33 .设顺序表的存储类型定义如下：typedefintKeyType;typedefstructKeyTypekey;RecType;阅读下列算法，并回答问题。intf33(RecTypeR,inti,ihtj)RecTypeX=Ri;while(i<j)while(i<j&&Rj.key>=x.key)j-;if(i<j)Ri.key=Rj.key;i+;)while(i<j&&Ri.key<=x.key)i+;if(i<j)fRfjLkey=Ri,key;j-;)Ri.key=x.key;returni;(1)设RecTypeR=52,14,256,-9,-38,30,128,258,64),给出执行f33(R,0,8)后R的结果。(2)给出该算法的功能。五、算法设计题34 .已知二叉树的存储结构类型定义如下：typedefstructnodeihtdata;stmctnode*lchild,*rchild;BinNode;typedefBinNode*BinTree;编写递归算法，对于给定的一-棵二叉树T,计算并返回所有结点dala域的值之和。函数原型为：intf34(BhhreeT)；。例如，对于题34图所示的二叉树Tf34(T)应返回24。题34图