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

2010年全国自考数据结构模拟试卷(二)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.非空的循环单链表head的尾结点(由指针p所指)满足()A.p-next=NULLB.p=NULLC.p-next=headD.p=head答案：C2.邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.按层遍历答案：A3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(ne)答案：B4.在Hash函数H(k)k MOD m中，一般来讲，m应取()A.奇数B.偶数C.素数D.充分大的数答案：C5.对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是()A.(N-1)(N-1)B.NNC.(N+1)(N+1)D.不确定答案：B6.快速排序在最坏情况下的时间复杂度是()A.AB.BC.CD.D答案：B7.已知一个单链表中有3000个结点，每个结点存放一个整数，()可用于解决这3000个整数的排序问题且不需要对算法作大的变动。A.直接插入排序方法B.简单选择排序方法C.快速排序方法D.堆排序方法答案：D8.设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B.栈C.队列D.线性表的链式存储结构答案：B9.顺序存储结构()A.仅适合于静态查找表的存储B.仅适合于动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储答案：C10.用二分查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为()A.AB.BC.CD.D答案：D11.与其他查找方法相比，哈希查找法的特点是()A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字计算记录存储地址，并进行一定的比较进行查找D.通过关键字记录数据进行查找答案：C12.倒排文件的主要优点是()A.便于进行插入和删除运算B.便于进行文件的合并C.能大大提高基于非关键码数据项的查找速度D.能大大节省存储空间答案：C13.设数组A0，m作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是()A.sq.front=(sq.front+1)%mB.sq.front=(sq.front+1)%(m+1)C.sq.rear=(sq.rear+1)%mD.sq.rear=(sq.rear+1)%(m+1)答案：D14.串是一种特殊的线性表，其特殊性体现在()A.可顺序存储B.数据元素是一个字符C.可链接存储D.数据元素可以是多个字符答案：B15.深度为k的二叉树，所含叶子的个数最多为()A.AB.BC.CD.D答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.从树的根结点到树中的其余结点之间的路径_惟一的。答案：是2.查找表中主关键字指的是_，次关键字指的是_。答案：能惟一标识数据元素的数据项不能惟一标识数据元素的数据项3._的有向图，其全部顶点有可能排成一个拓扑序列。答案：存在入度为0的结点且没有回路4.如果一个图中有n条边，则此图的生成树含有_条边，所以生成树是图的边数_的连通图。答案：n-1 最少5.在散列技术中，处理冲突的方法有：_和_。答案：开放定址法 拉链法6.对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为_，如果k不在表中，则需要进行_次比较后才能确定查找失败。答案：(n+1)/2 n+17.查找表按其所包括的运算的不同分为_查找表和_查找表。答案：静态 动态8.给定一个具有n个元素的向量，建立一个有序单链表的时间复杂度是_。答案：9.设线性表(a1,a2，a500)元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下，至多需比较_次。答案：910.设有一元多项式A(x)7+3x+10x30-4x100+13x101，用单链表给出A(x)的存储表示为_。答案：三、解答题（本大题共4小题，每小题5分，共20分）1.已知串S=(xyz)*,t=(x+z)*y,试利用串的基本运算将s串转化为t串，t串转化为s串。答案：t=CONCAT(Rep(sup(s,1,5),y,+),Rep(sub(s,6,1),*,*y)s=CONCAT(Rep(sub(t,1,5),+,y),Rep(sub(t,6,2),*y,*)2.已知有一关键字序列为486，79，596，34，900，120，789，179，703，307，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。答案：基数排序的基本思想是：从低位到高位依次对kj(j=d-1,d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果：初始：486，79，596，34，900，120，789，179，703，307第1趟：(按个位进行排序)：120，900，703，34，486，596，307，79，179，389第2趟：(按十位进行排序)：307，703，900，120，34，79，179，486，789，596第3趟：(按百位进行排序)：34，79，120，179，307，486，596，703，789，9003.对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30，11，27，04，19，86，73，89，32，05，103，58，45，67，77，81，08，48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法。答案：磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。如果一个桶能放m个记录，则如果现在已经存放了m个记录时，继续存放记录就会产生“溢出”，当发生“溢出”时，一般采用拉链法，就是将第m+1个同义词存放在另外一个桶中，通常此桶就称为“溢出桶”，相应的前m个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同。根据散列函数，得到对应的关键字的散列地址为：2，4，6，4，5，2，3，5，4，5，5，2，3，4，0，4，1，6，则得到的散列文件表示如下：4.假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c),请用树形结构画出此树，并回答下面的问题。(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?(8)树的深度是多少?(9)树的度数是多少?答案：树的结构如下图所示：(1)a是根结点(2)m,n,d,f,l,j,k是叶结点(3)c是g的双亲(4)a和c是g的祖先(5)j,k是g的孩子(6)i,m,n是e的子孙(7)d是e的兄弟(8)树的深度是5(9)树的度数是3四、算法阅读题（本大题共4小题，每小题5分，共20分）1.请将下面的程序改成递归的过程。voide ditui (int n)int i;i=n;while(i1)prinft(i-);答案：此递推过程可以改写成如下递归过程：voide ditui (int j)if(i1)printf(j);digui(j-1);2.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。lklist create-lklist2()/*直接实现的建表算法。*/ head=malloc(size);p=head;scanf(%f,&x);while(x!=$) q=malloc(size);q-data=x;p-next=q;_;scanf(%f,&x);_;return(head);此算法的量级为_。答案：p=q p-next=NULL O(n)3.下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的_处填上正确的语句。int dlink_symmetry (dlklist s) j=true;p=s-next;q=s-prior;while(p!=q)&(_)if(p-data=q-data) (_); (_); elsej=false;return(j);答案：p-prior! =qq-next! =p p=p-next q=q-prior。4.以下将ah,am,和am+1,an,两个有序序列(它们相应的关键字值满足KhKm,Km+1Kn,)合并成一个有序序列Rh,，Rn,(使其关键字值满足Kh,Kn,)。请分析算法，并在_上填充适当的语句。void merge(list a,list R,int h,int m,int n)i=h;k=h;j=m+1;while(im)&(j=n) if(ai.key=aj.key) Rk=_;_ ;else Rk=_; _; k+;while(i=_)Rk=ai;i+;k+;while(jflag) case0:p-flag=1;if (p-lchild!=Null)p=p-lchild;break;case1:p-flag=2更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/53