全国2014年4月自学考试数据结构导论试题

《全国2014年4月自学考试数据结构导论试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一直豳E3只为证明自己少机会能力并不比谁差求职被拒加薪无望却始终不甘于现状坏做更优秀的自己，从提升学历开始#温馨提示:试卷网(www.4juan.com)试题均来自互联网，部分试题答案由网友提供整理而成,非官方标准答案，仅供广大考生参考。如需获取更权威的官方参考答案，请大家联系"中国自考人网校(www.zk8.com.cn)"在线老师,或关注微信公众号"自考人",开通精华版课程即可获得试题答案免费下载权限.全国2014年4月自学考试数据结构导论试题课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1.答题前，考

2、生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。1.下列几种算法时间复杂度中，最小的是A.O(log2n)B.O(n)C.O(n2)D.O(l)1.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有A.索

3、引存储方式和树形存储方式B.线性存储方式和散列存储方式C.线性存储方式和索引存储方式D.索引存储方式和散列存储方式3.表长为n的顺序表屮做删除运算的平均时间复杂度为A.O(l)B.O(log2n)C.O(n)D.O(n2)4•顺序表中定位算法(查找值为x的结点序号最小值)的平均吋间复杂度为A.O(l)B.O(log2n)C.O(n)D.O(n2)5•元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为A.DB.CC.BD.A6•带头结点的链队列中，队列头和队列尾指针分别为fmnl和rear,则判断队列空的条件为A.front

4、==reardear!二二NULLB.front!=NULLD.front==NULL7.深度为5的二叉树，结点个数最多为A.31个B.32个C.63个D.64个8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为A.lB.3C.4D.59.将题9图所示的一棵树转换为二叉树，结点C是A.A的左孩子B.A的右孩子C.B的右孩子D.E的右孩子lO.n为图的顶点个数，e为图屮弧的数目，则图的拓扑排序算法的时间复杂度为A.O(n)B.O(e)C.O(n-e)D.O(n+e)11.无向图的邻接矩阵是A.对角矩阵B.稀疏矩阵C.上三角矩阵D.对称矩阵12.

5、在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为A.50B.51C.100D」0113.构造散列函数的方法很多，常用的构造方法有A.数字分析法、除留余数法、平方取屮法A.线性探测法、二次探测法、除留余数法B.线性探测法、除留余数法、链地址法C.线性探测法、二次探测法、链地址法14.就平均时I'可性能而言，快速排序方法最佳,其时I'可复杂度为B.O(nlog2n)D.O(logon)B.冒泡排序D.归并排序A.O(n)C.O(n2)15.下述算法中，不稳定的排序算法是A.直接插入排序C.堆排序非选择题部分注意事项：用黑色字迹的签

6、字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共13小题，每小题2分，共26分)16.数据的基本单位是o17.双向循坏链表中，在p所指结点的后面插入一个新结点呛，需要修改四个指针，分别为t->prior=P；t->next=p->next；；p->next=t；。18.在带有头结点的循坏链表中，尾指针为rear,判断指针P所指结点为首结点的条件是。19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是20.不含任何数据元素的栈称为o21.稀疏矩阵一般采用的压缩存储方法是o22.100个结点的

7、二叉树采用二叉链表存储时，用來指向左、右孩子结点的指针域有个。23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有个结点。24.n个顶点的有向图G用邻接矩阵A[l..n,1..n]存储，其第i列的所有元素之和等于顶点Vj的025.具有10个顶点的有向完全图的弧数为。26.要完全避免散列所产生的“堆积"现象，通常采用解决冲突。27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为2&归并排序算法的时间复杂度是o三、应用题(本大题共5小题，每小题6分，共30分)29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表

8、示法。_00-10A=000000_0750000_0000000020008000500000000_题2