资源描述：
《自学考试_全国2015年10月高等教育自学考试数据结构导论试题(02142)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、绝密★考试结束前全国2015年10月高等教育自学考试数据结构导论试题课程代码:02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项:1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2.2B每小题选出答案后,用铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的
2、相应代码涂黑。错涂、多涂或未涂均无分。1.“能正确地实现预定的功能,满足具体问题的需要”。这种评价算法好坏的因素称为A.正确性B.易读性C.健壮性D.时空性2.有一程序片段:{i=0;s=0;while(s<=n){i++;s=s+i;}},其时间复杂度是1/2)D.O(1)A.O(n)B.O(2n)C.O(n3.在如题3图所示的数组A中链接存储了一个线性表,表头指针为A[0].next,则该线性表中第一个数据元素的值是题3图A.60B.50C.78D.404.在一个长度为n(n>1)的单链表上,设有头和尾两个指针,以下操
3、作与链表长度有关的是A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表中第一个元素前插入一个新元素D.在单链表中最后一个元素后插入一个新元素5.某双向链表中的结点如题5图所示,删除t所指题5图结点的操作为A.t->prior->prior=t->next;t->next->prior=t->prior;B.t->prior->prior=t->prior;t->next->next=t->next;C.t->prior->next=t->prior;t->next->prior=t->next;D.t-
4、>prior->next=t->next;t->next->prior=t->prior;浙02142#数据结构导论试题第1页(共4页)6.下列关于栈和队列的叙述中:Ⅰ栈和队列都是线性表;Ⅱ栈和队列都是顺序表;Ⅲ栈和队列都不能为空;Ⅳ栈和队列都能用于递归过程实现;Ⅴ栈的特点是先进后出、队列的特点是先进先出,其中正确的是A.Ⅰ和ⅤB.Ⅰ、Ⅱ、ⅤC.Ⅲ和ⅤD.Ⅱ、Ⅳ、Ⅴ7.二维数组A按行序优先顺序存储,每个数据元素占1个存储单元。若数据元素A[1][1]的存储地址是420,A[3][3]的存储地址是446,则A[5][5]的存
5、储地址是A.470B.471C.472D.4738.若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号,根结点的编号为1,则树中最后一个结点(即编号为199)的双亲结点的编号为A.99B.100C.101D.1989.对长度为15的有序顺序表进行二分查找,在各记录的查找概率均相等的情况下,查找成功ASL时平均查找长度()为39495155A.B.C.D.1515151510.在如题10图所示的有向图中,从顶点1出发进行深度优先搜索可得到的结果序列是题10图A.1423B.1432C.1342D.1243
6、11.设森林F中有三棵树,其结点的个数分别为m1、m2、m3,则与F对应的二叉树根结点的右子树上的结点数是A.m1+m2B.m2+m3C.m1+m3D.m1+m2+m312.假设通信电文使用的字符集为{a,b,c,d,e,f},各字符在电文中出现的频率分别为{34,5,12,23,8,18},利用构造Huffman树对每个字符进行编码,则其中编码长度最长的字符是A.a,bB.a,dC.b,eD.e,f13.元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为A.DB.CC.BD.A14.平均时间复
7、杂度和在最坏情况下的时间复杂度均是O(nlog2n)的排序算法是A.插入排序B.快速排序C.选择排序D.堆排序15.在待排记录中其关键字序列基本有序的前提下,时间效率最高的排序方法是A.直接插入排序B.快速排序C.选择排序D.堆排序浙02142#数据结构导论试题第2页(共4页)非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。二、填空题(本大题共13小题,每小题2分,共26分)16.数据的存储结构又称为物理结构,可分为顺序存储、链式存储、以及散列存储等几种方式。17.一般说来,在每个逻辑结
8、构上都定义了一组基本运算,通常这些运算包括:建立、、读取、插入和删除等。18.某带有头结点的单链表的头指针为head,则判断该单链表为非空的条件是。19.数组Q[n]表示一个循环队列,设f的值为队列中第一个元素的位置,r的值为队列中实际队尾的位置加1,并假定队列中最多只有n-1个元素,则计算队列中元素个
