2010年全国自考数据结构模拟试卷(十)及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你.2010年全国自考数据结构模拟试卷(十)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的()A.索引表B.链接表C.符号表D.交叉访问题答案：A2.Aarr和Barr两个数组的说明如下：VARAarr:Array07of char;Barr:Array-52,3,8of char;这两个数组分别能存放的字符的最大个数是()A.7和35B.1和5C.8和48D.1和6答案：C3.在下面的排序方法中，属于不稳定的排序方法的是()A.直接插入排序B.冒泡法排序C.堆排序D.归并排序答案：C4.散列表的目的是()A.插入B.删除C.快速查找D.排序答案：C5.在一个长度为n的顺序表(顺序存储的线性表)中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动()个元素。A.n-iB.n-i+1C.n-i-1D.i答案：B6.如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数()对应的判定树的高度(假设树高h2)。A.大于B.小于C.等于D.无法确定答案：B7.树最适合用来表示()A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答案：C8.在单链表中，删除p所指结点的直接后继的操作是()A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next；答案：A9.以下有关数据结构的叙述，正确的是()A.AB.BC.CD.D答案：C10.设有一个用线性探测法解决冲突得到的散列表：散列函数为H(k)kmod ll ，若要查找元素14，探测的次数(比较的次数)是A.8B.9C.3D.6答案：D11.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是()A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代C.将与该元素有相同Hash地址的后继元素顺次前移一个位置D.用与该无素有相同Hash地址的最后插入表中的元素替代答案：B12.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是bgbaechf，则其后序遍历的结点访问顺序是()A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca答案：D13.从一个长度为n的顺序表中删除第i个元素(1in)时，需要向前移动()A.n-iB.n-i+1C.n-i-1D.i答案：A14.对广义表(a),(b)进行下面的操作head(head(a),(b)后的结果是()A.aB.(a)C.()D.不确定答案：A15.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是()A.a c b e dB.d e c a bC.d e a b cD.c e d b a答案：D二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。(1)删除P结点的语句序列是_；(2)删除尾元结点的语句是_。aP-next=P-next-nextbP=P-next-nextcwhile(P-next!=Q)P=P-nextdwhile(P-next!-next!=Q)P=P-nextewhile(P-next!-next!=NULL)P=P-nextfQ=PgQ=P-nexthP=LiL=L-nextjfree(Q)答案：f-h-c-a-be-g-c-j2.顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即_和_。答案：静态存储分配的顺序串 动态存储分配的顺序串3.假设在图G中任意的顶点设为vi，此顶点对应的度为D(vi)，此图的顶点数为n。则边数e和度数之间的关系为_。答案：4.在串的匹配运算中，一般我们将主串称为_，而将子串称为_。答案：目标串 模式串5.N个顶点的连通图，至少有_条边。答案：N-16.散列函数的作用是：_。答案：压缩待处理的下标范围，待处理的|u|个值减少到m个值，从而降低空间开销7.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和_进行查找。答案：二分查找法 分块查找8.已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为_。答案：n+2e9.判断一个没有头结点的单链表head为空的条件是_。答案：head=NULL10.在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的_加上排在aij前面的元素所占用的单元数。答案：基地址三、解答题（本大题共4小题，每小题5分，共20分）1.对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。答案：图的广度优先遍历类似于树的按层遍历：首先访问源点，并将其记为访问过，接着访问vi的所有未被访问的邻接点vi1，vi2，vit。并将它们均记为已经访问过，然后再按照vi1，vi2，vit的次序，访问每个顶点的所有未被访问的邻接点，并均记它们为已访问过，按此规则类推，直到图中所有和源点vi有路径相通的顶点都访问过为止。则按照广度优先遍历规则，我们得到此遍历序列为ABCDEFGHI。相应的子树为：2.已知有一个关键字序列为(99，38，309，08，27，145，67，96，186，122，71，63，59)，假设用散列函数为h(key)=key%13,现在如果采用拉链法解决冲突问题，请画出这组关键字的散列表。答案：采用散列函数为：h(key)=key%13,得到对应的上述关键字序列的散列地址为(8，2，10，8，1，2，2，5，4，5，6，11，7)，用拉链法解决冲突的问题时，就是将所有关键字为同义词的结点连接在同一个单链表中，且当把h(key)=i的关键字插入到第i个单链表中时，既可以插入到单链表的头上，也可以插入到链表的尾上。根据上述规则，我们可以得到此序列的散列表形式如下图。3.已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。答案：构造最小生成树的过程如下：4.已知有如右图所示的一棵树，请将其转化成二叉树。答案：将一棵树转换成二叉树的规则如下：(1)在所有的兄弟结点之间加一条线；(2)对于每个结点，除了保留与长子的连线外，去掉该结点和其他孩子的连线，则根据以上两个规则，我们得到转换后的二叉树为(从此图我们可以得到，将一棵普通树转换成二叉树后，其对应的二叉树的右子树为空)：自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部四、算法阅读题（本大题共4小题，每小题5分，共20分）1.简述一下算法的功能：statusA(linkedlistL)/L是无表头结点的单链表if(L &L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;return ok;/A答案：本程序实现的功能就是：如果L的长度不小于2，则将首元结点删去并插入到表尾。2.求下面算法中变量count的值：(假设n为2的乘幂，并且n2)int Timeint ncount=0;x=2;while(xkey= =K:_;case_: return(search-bst(T-lchild,K);case_: return(search-bst(T-rchild,K);答案：return(T) T-keyK T-keydata=x;s-next=_;p-next=s; 答案：malloc(size)p-next五、算法设计题（本题10分）1.采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。答案：首先定义单链表的结点：struct nodeint key；struct node * link;函数如下：struct *selectsort(struct node * h)struct node *p,*q,*r,*s,*t;t=Null；while(h!=Null)p=h;q=