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