2010年1月自考数据结构试题和答案

═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第1页-2010年1月高等教育考试数据结构试题和答案课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（A）A．问题规模B．语句条数C．循环层数D．函数数量2．具有线性结构的数据结构是（C）A．树B．图C．栈和队列D．广义表线性结构有：顺序表、栈和队列、串3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（C）A．O(1)B．O(m)C．O(n)D．O(m+n)4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（D）A．2个B．3个C．4个D．6个P28中voidDInsertBefore(DListNode*p,DataTypex)//在带头结点的双链表中，将值为x的新结点插入结点*p之前，设p≠NULL{DListNode*s=malloc(sizeof(ListNode));①s-data=x;②s-prior=p-prior;③s-next=p;④p-prior-next=s;⑤p-prior=s;⑥}5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（D）A．3B．37C．50D．97辅导书P22中对于循环向量中的循环队列，写出通过队头队尾指针表示的队列长度公式。（front指向实际队头，rear指向实际队═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第2页-尾的下一元素位置。）当rear≥front时，队列长度L=rear-front；当rearfront时，L=m+(rear-front)。这两种情况可统一为L=(m+(rear-front))%m，这里m为向量的大小。本题中m=606．若栈采用链式存储结构，则下列说法中正确的是（B）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满也不需要判断栈空P36中因为链栈中的结点是动态分配的，可以不考虑上溢，所以无需定义stackFull运算。7．若串str=”Software”，其子串的数目是（D）A．8B．9C．36D．37P51中任意个连续字符组成的子序列称为该串的子串。8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（C）A．1012B．1017C．1032D．1039P61中在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0≤in）有i+1个元素，元素总数为：n(n+1)/2，并将元素放在一个向量sa[0..n(n+1)/2-1]中。若i≥j，则aij在左下三角矩阵中，sa[k]与aij的对应关系是k=i(i+1)/2+j。若ij，则aij在右上三角矩阵中，sa[k]与aij的对应关系是k=j(j+1)/2+i。若all为第一个元素，a85与a00为第一个元素时的a(85-(11-00))=a74位置一样，k=7*8/2+4=32，则a85的地址=1000+32=1032；若a44为第一个元素，a85与a00为第一个元素时的a(85-(44-00))=a41位置一样，k=4*5/2+1=11，则a85的地址=1000+11=1011；9．允许结点共享的广义表称为（D）P67A．纯表B．线性表C．递归表D．再入表10．下列数据结构中，不属于二叉树的是（B）B树是一种平衡的多叉树A．B树B．AVL树AVL树是自平衡二叉查找树C．二叉排序树D．哈夫曼树哈夫曼树是最优二叉树═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第3页-11．对下面有向图给出了四种可能的拓扑序列，其中错误．．的是（C）辅导书中P97第10题A．1，5，2，6，3，4B．1，5，6，2，3，4C．5，1，6，3，4，2D．5，1，2，6，4，312．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v4P108P110的图7.10P114~115的图7.12、图7.13、7.14深度优先遍历类似于树的前序遍历。其特点是尽可能先对纵深方向进行搜索。13．下列排序算法中不稳定的是（A）P164A．快速排序B．归并排序C．冒泡排序D．直接插入排序稳定：直接插入、冒泡、归并、基数不稳定：直接选择、希尔、快速、堆14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（B）mid1=45，mid2=9，mid3=32A．2B．3C．4D．8P171中二分查找（BinarySearch）又称折半查找，它是一种效率较高的查找方法。但是，二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。一般设有序表是递增有序的。二分查找的基本思想是：设R[low...high]是当前的查找区间，首先确定该区间的中点位置mid=└(low+high)/2┘，然后将待查的K值与R[mid].key比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间；若R[mid].keyK，则由表的有序性可知R[mid...n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1...mid-1]中，故新的查找区间是左子表R[1...mid-1]；类═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第4页-似地，若R[mid].keyK，则要查找的K必在mid的右子表R[mid+1...n]中，即新的查找区间是右子表R[mid+1...n]。下一次查找是针对新的查找区间进行的。因此，我们可以从初始的查找区间R[1...n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）时为止。15．采用ISAM组织文件的方式属于（D）P211-212A．链组织B．顺序组织C．散列组织D．索引组织二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16．数据元素及其关系在计算机存储器内的表示称为存储结构。P117．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是O(n)。18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_取栈顶元素_。P34typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypeStackTop(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；returnS-data[S-top]；}19．在串匹配中，一般将主串称为目标串，将子串称为_模式串_。P5520．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))=__()__。P66中若广义表LS非空（n≥1）（通常用圆括号将广义表括起来，用逗号分割其中的元素。用大写字母表示广义表，用小写字母表示原子。），则a1是LS的表头，其余元素组成的表称为LS的表尾。长度：元素的个数深度：表展开后所含括号的层数（从最里面往最外面数）21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为___231__。P90中结点的带权路径长度，是该结点到树根之间的路径长度与结点上权的乘积。WPL=30×1+18×2+16×3+13×4+6×5+7×5=30+36+48+52+30+35=231═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第5页-22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是__35__。P90中树的路径长度是从树根到树中每一结点的路径长度之和。显然，在结点数目相同的二叉树中，完全二叉树的路径长度最短。P122中源点s到终点v的最短路径长度简称为最短距离。P73中完全二叉树（CompleteBinaryTree，见图6.7的b）若一颗二叉树至多只有最下面的两层上结点的度数（P70中，一个结点拥有的子树数称为该结点的度Degree。一颗树的度是指该树中的结点的最大度数。度为零的结点称为叶子Leaf或终端结点。）可以小于2，而且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是42,13,94,55,05,46,17。P162中基数排序的基本思想是：从低位到高位依次对Kj（j=d-1,d-2,d-3…,0）进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd。如被排序的记录关键字Ki取值范围是0-99间整数的例子，就是一个基数radix为10，d为2的基数排序。箱号0123456789内容42139455,054617箱号0123456789内容513,1742,465594第一次装箱(a)第二次装箱(b)24．高度为3的3阶B-树最少的关键字总数是__7__。辅导书P147中（最多关键字总数的解答）一颗高度为h的k阶B-树中最多可容纳多少个关键字？解要使高为h的k阶B-树容纳最多的关键字，则每个结点中的关键自数据就必须达到最大值k-1.因此这时的B-树实际上可看成是满k叉树。不妨设根的层数为1，则第1层只有1个根结点，第2层上共有k个结点，第3层上共有k2个结点，…，第h层上共有kh-1个结点，树中结点总数为：═════════════════════════════════════════════════════════════════════════════════-本套试题共分13页，当前页是第6页-由每个结点可容纳k-1关键字可知，树中可容纳的关键字总数为：n=(k-1)×m=(k-1)×=kh-1以h=3，k=101为例，相应的B-树最多可容纳1013-1=100+10100+1020100=1030300个关键字，树中结点总数为(1013-1)/100=1+101+10201=10303。示意图如下：第1层：1个结点100个关键字第2层：101个结点101×100=10100个关键字第3层：1012=10201个结点10201×100=1020100个关键字P182中（最少关键字总数的解答）一颗m（m≥3）阶的B-树，每个非根结点中所包含的关键字个数j满足：┌m/2┐-1≤j≤m-1。即每个非根结点至少应有┌m/2┐-1个关键字，至多有m-1个关键字。