2012年10月自学考试数据结构试题

全国2012年10月自学考试数据结构试题1全国2012年10月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。1．一个算法的时间耗费的数量级称为该算法的A．效率B．难度C．可实现性D．时间复杂度2．顺序表便于A．插入结点B．删除结点C．按值查找结点D．按序号查找结点3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是A．p-next-next==headB．p-next==headC．p-next-next==NULLD．p-next==NULL4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为A．(rear-front+m)％mB．rear-front+1C．(front-rear+m)％mD．(rear-front)％m全国2012年10月自学考试数据结构试题25．下列关于顺序栈的叙述中，正确的是A．入栈操作需要判断栈满，出栈操作需要判断栈空B．入栈操作不需要判断栈满，出栈操作需要判断栈空C．入栈操作需要判断栈满，出栈操作不需要判断栈空D．入栈操作不需要判断栈满，出栈操作不需要判断栈空6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为A．25B．26C．33D．347．树的后序遍历等价于该树对应二叉树的A．层次遍历B．前序遍历C．中序遍历D．后序遍历8．使用二叉线索树的目的是便于A．二叉树中结点的插入与删除B．在二叉树中查找双亲C．确定二叉树的高度D．查找一个结点的前趋和后继9．设无向图的顶点个数为n，则该图边的数目最多为A．n-lB．n(n-1)／2C．n(n+1)／2D．n210．可进行拓扑排序的图只能是A．有向图B．无向图C．有向无环图D．无向连通图11．下列排序方法中稳定的是A．直接插入排序B．直接选择排序C．堆排序D．快速排序12．下列序列不为．．堆的是A．75,45,65,30,15,25B．75,65,45,30,25,15C．75,65,30,l5,25,45D．75,45,65,25,30,1513．对线性表进行二分查找时，要求线性表必须是A．顺序存储B．链式存储全国2012年10月自学考试数据结构试题3C．顺序存储且按关键字有序D．链式存储且按关键字有序14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同．．的序列是A．(4,1,2,3,5)B．(4,2,3,l,5)C．(4,5,2,1,3)D．(4,2,1,5,3)15．下列关于m阶B树的叙述中，错误．．的是A．每个结点至多有m个关键字B．每个结点至多有m棵子树C．插入关键字时，通过结点分裂使树高增加D．删除关键字时通过结点合并使树高降低非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共10小题，每小题2分，共20分)16．数据元素之间的逻辑关系称为数据的______结构。17．在线性表中，表的长度定义为______。18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为______。19．在二叉树中，带权路径长度最短的树称为______。20．已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是______。21．一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符＇d＇的哈夫曼编码的长度为______。22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。23．直接选择排序算法的时间复杂度是______。24．对于长度为81的表，若采用分块查找，每块的最佳长度为______。25．用二叉链表保存有n个结点的二叉树，则结点中有______个空指针域。三、解答题(本大题共4小题，每小题5分，共20分)全国2012年10月自学考试数据结构试题426．假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0；写出依次执行下列操作后头、尾指针的当前值。a,b,c,d,e,f入队，a,b,c,d出队；(1)Q.front=______；Q.rear=______。g,h,i,j,k,l入队，e,f,g,h出队；(2)Q.front=______；Q.rear=______。M,n,o,P入队，i,j,k,l,m出队；(3)Q.front=______；Q.rear=______。27．已知一个无向图如题27图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。28．用归并排序法对序列(98,36,-9,0,47,23,1,8)进行排序，问：(1)一共需要几趟归并可完成排序。(2)写出第一趟归并后数据的排列次序。29．一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key％11将记录散列到散列表HT[0..12]中去，用线性探测法解决冲突。(1)画出存入所有记录后的散列表。(2)求在等概率情况下，查找成功的平均查找长度。四、算法阅读题(本大题共4小题，每小题5分，共20分)30．顺序表类型定义如下：#defineListSize100typedefstruct{intdata[ListSize]；intlength；}SeqList；全国2012年10月自学考试数据结构试题5阅读下列算法，并回答问题：voidf30(SeqList*L){inti,j；i=0；while(iL-length)if(L-data[i]％2!=0){for(j=i+1;jL-length;j++}L-data[j-1]=L-data[j];L-length--;}elsei++}（1）若L-data中的数据为（22,4,63,0,15,29,34,42,3）,则执行上述算法后L-data中的数据以及L-length的值各是什么？（2）该算法的功能是什么？31.有向图的邻接矩阵类型定义如下：#defineMVN100∥最大顶点数typedefintEType;∥边上权值类型typedefstruct{ETypeedges[MVN][MVN];∥邻接矩阵，即边表intn;∥图的顶点数｝MGraph;∥图类型例如，一个有向图的邻接矩阵如下所示：0100010001010101000000011A阅读下列算法，并回答问题：全国2012年10月自学考试数据结构试题6Voidf31(MGraphG){Inti,j,k=0;Step1:for(i=0;iG.n;i++)for(j=0;jG.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k);step2:for(j=0;jG.n;j++){k=0;for(i=0;iG.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k);}}(1)stepl到step2之间的二重循环语句的功能是什么?(2)step2之后的二重循环语句的功能是什么?32．阅读下列算法，并回答问题：voidf32(intr[]，intn){Inti，j；for(i=2；in；i++){r[0]=r[i]；j=i-l；while(r[0]r[j]){r[j+l]=r[j]；j=j-1；}全国2012年10月自学考试数据结构试题7r[j+l]=r[0]；}}(1)这是哪一种插入排序算法?该算法是否稳定?(2)设置r[0]的作用是什么?33．顺序表类型定义如下：typedefintSeqList[100]；阅读下列算法，并回答问题：voidf33(SeqListr，intn){inta,b，i；if(r[0]r[1]){a=r[0]；b=r[1]；else{a=r[1]；b=r[0]；}for(i=2；in；i++)if(r[i]a)a=r[i];elseif(r[i]b)b=r[i]；printf(＂a=％d，b=％d。n＂，a，b)；}(1)给出该算法的功能；(2)给出该算法的时间复杂度。五、算法设计题(本题10分)34．二叉树的存储结构类型定义如下typedefstructnode{intdata；structnode*lchild，*rchild；}BinNode；typedefBinNode*BinTree；编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。全国2012年10月自学考试数据结构试题8函数的原型为：voidf34(BinTreeT,int*count,int*sum)*count和*sum的初值为0。