《全国自考数据结构模拟试卷(一)及答案》由会员分享，可在线阅读，更多相关《全国自考数据结构模拟试卷(一)及答案（9页珍藏版）》请在装配图网上搜索。
1、2010年全国自考数据结构模拟试卷(一)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行()次比较。A.33B.45C.70D.912.假定一棵二叉树的结点为18个，则此二叉树的最大高度为()，最小高度为()A.4B.5C.6D.183.一个具有N个顶点的有向图最多有()条边。A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/24.设一个数
2、组中，行下标i的范围是从1到8，列下标的范围是从1到10，假设此数组的初始存储地址是A，则如果将此数组按照列优先的顺序连续存放，则元素Q58的起始地址是()A.1B.23C.24D.5295.下面程序的时间复杂性是()for(i=1;i=n;i+)for(j=1;j=m;j+) Aij=i*j; A.AB.BC.CD.D6.在下面的排序方法中，不需要通过比较关键字就能进行排序的是()A.箱排序B.快速排序C.插入排序D.希尔排序7.设散列函数为H(k)k mod7，一组关键码为23，14，9，6，30，12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到
3、的散列表为()A.AB.BC.CD.D8.排序的重要目的是为了以后对已排序的数据元素进行()A.打印输出B.分类C.查找D.合并9.线性表L(a1，a2，a1，an)，下列说法正确的是()A.每个元素都有一个直接前趋和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D.除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继10.邻接表存储结构下图的广度优先遍历算法结构类似于树的()A.先根遍历B.后根遍历C.按层遍历D.先序遍历11.下列说法中正确的是()A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有
4、一个结点的度为2D.一棵二叉树的度可以小于212.在一个具有n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是()A.top=top-1B.top=top+1C.top不变D.top不确定13.堆排序的最坏时间复杂度为()A.AB.BC.CD.D14.如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用()A.快速排序B.直接插入排序C.堆排序D.归并排序15.将含100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的结点的双亲的编号为()A.34B.35C.36D.无法确定二
5、、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是_的线性表。答案：线性表2.设二维数组A1020，510按行优先存储，每个元素占4个存储单元，A10，5的存储地址是1000，则A15，10的存储地址是_。答案：17003.在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。答案：相邻位置 链接指针4.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是_。答案：一个数据元素可
6、能有多个直接前趋和多个直接后继5.数组01n表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为_。答案：(n+r-f)mod n6.在具有n个单元的循环队列中，队满时共有_个元素。答案：n-17.内部排序的方法可以分为五类：_、_、_、_、_。答案：插入排序 选择排序 交换排序 归并排序 分配排序8.在单链表中，除了首元结点外，任一结点的存储位置是由_指示。答案：其直接前趋结点的链域的值9.拓扑排序指的是找一个有向图的_的过程。答案：拓扑序列10.在双向链表中，每个结点含有两个指针域，一个指向
7、其_结点，另一个指向_结点。答案：前趋 后继三、解答题（本大题共4小题，每小题5分，共20分）1.答案：(1)第一种表示需要n+2个实数存储单元，其中n为多项式的最高幂数；第二种表示需要2m+1个实数存储单元，其中m为非零系数的个数。显然，当非零系数较少时(m（n+1）/2)，第二种表示法需要较少的存储空间。(2)采用每种表示法处理多项式相加比较简单，只需将次数较低的多项式的各项的系数加到次数较高的多项式的相应项的系数上去即可。而第二种方法要查找到相同的指数才能将系数相加，相加之和可能为0，这就要修改项数m；另外当某个多项式中有的项而在另一个多项式中没有，显然其和也应作相应的修改。2.设有多项
8、式(1)用单链表给出A(x)的存储表示。(2)用单链表给出B(x)的存储表示。(3)以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。答案：3.假设一个循环队列的容量为50，对其进行入队和出队操作，则经过一段时间之后，有：(1)front=35,rear=12;(2)front=12,rear=35。其中front和rear分别是队头和队尾指针。求：循环队列中元素的个数？答案：如果一个循环队列的总容量为N，则当rear-front时，循环队列中的元素的个数为rear-front,当rearlchild=NULL)&(t-
9、rchild=NULL)_;countleaf(1-lchild,count); _;答案：*count + countleaf(1-rchild,count)2.以下为单链表的定位运算，分析算法，请在_处填上正确的语句。int locate-lklist(lklist head,datatype x)/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ p=head;j=0;while(_)p=p-next;j+;if(p-data=x) return(j);else return(0);答案：(p-next!=NULL)&(p-data!=x)3.INITIATE()
10、的功能是建立一个空表。请在_处填上正确的语句。lklist initiate-lklist() /*建立一空表*/_; _;return(t);答案：t=malloc(size) t-next=NULL4.以下为求单链表表长的运算，分析算法，请在_处填上正确的语句。int length-lklist(lklist head)/*求表的长度。*/_;j=0;while(p-next!=NULL) _;j+;return(j);/*回传表长*/答案：p=head p=p-next五、算法设计题（本题10分）1.对一个有t个非零值元素的mn矩阵，用B0.t,1.3的数组来表示，其中第0行的三个元素分
11、别是m,n,t,从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素Aij的位置，并考虑若修改其元素值须用多少时间?(设B中第1列原行号是递增的)答案：分析题意可得其算法思想为：首先可在数组B中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的Aij,原先就具有非零值。从而可将算法描述为：lorte(B,t,i,j,v)/*确定任意一个元素Aij的位置*/datatype B;/*B的杆标为0.t和1.3*/int t,i,j;float v;更多优质自考资料尽在百度贴吧自考乐园俱乐部
12、（ datatype A;/*A的下标为1.m和1.n,A表示mn矩阵*/int p;p=1;while (Bp1!=1)&(pt) printf (hasnt element foundn);else while (Bp1= =i) *(p=t)&(Bpi!=j)p+;if (Bp1= =i)&(Bp2!=j)Bp3=v;else printf (no element foundn);/*lorte*/显然，在本算法中可能出现的最坏情况：一是需要修改的元素位于B中最后一行；二是Bij原先的元素值为零，而无法在B中查找到相应的位置。所以，在这两种情况下的时间复杂度为O(t)。自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部1：C 2：B 3：B 4：C 5：C 6：A 7：B 8：C 9：D 10：C 11：D 12：B 13：C 14：B 15：B
全国自考数据结构模拟试卷(一)及答案
