资源描述：
《自学考试_全国2014年10月高等教育自学考试数据结构导论试题(02142)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、绝密★考试结束前全国2014年10月高等教育自学考试数据结构导论试题课程代码:02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项:1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应
2、代码涂黑。错涂、多涂或未涂均无分。1.下列算法的时间复杂度为for(i=1;i<=n;i++){m++;for(j=1;j<=n;j++)k*=m;}2)C.O(n3)D.O(log)A.O(n)B.O(n2n2.根据数据元素之间关系的不同特性,通常将数据结构分为四类基本结构,即A.集合、顺序结构、树形结构、图结构B.集合、线性结构、链式结构、图结构C.集合、线性结构、树形结构、图结构D.线性结构、顺序结构、链式结构、图结构3.在表长为101的顺序表中做删除运算,平均移动元素的次数为A.25B.50C.51D.1004.在表长
3、为n的顺序表中做插入运算的时间复杂度为2)A.O(n)B.O(log2n)C.O(1)D.O(n浙02142#数据结构导论试题第1页(共5页)5.单链表与顺序表相比,其特点是A.运算算法实现简单B.便于随机存取数据C.不需要预先分配存储空间D.结点个数受到限制6.关于链栈的说法,正确的是A.链栈不用预先考虑容量的大小B.链栈出栈时不需要判断栈空C.链栈进栈时需要判断栈满D.链栈出栈时需要判断栈满7.循环队列存储在数组A[m]中,则入队列操作中队列尾指针rear的变化为A.rear=rear+1B.rear=(rear+1)%(
4、m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)8.深度为k的二叉树,结点个数最多为kkk-1A.2B.2-1C.2D.2k-19.已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,……,nk个度为k的结点,则该树中的叶结点个数为kkkkA.∑niB.1+∑(i-1)niC.∑niD.∑(i-1)nii=1i=1i=2i=210.具有10个叶结点的哈夫曼树中度为1的结点数为A.0个B.10个C.19个D.20个11.设图的顶点数为n,则采用邻接矩阵作为存储结构的图的深度优先搜索算
5、法的时间复杂度为2)D.O(log)A.O(1)B.O(n)C.O(n2n12.n个顶点的无向图若采用邻接矩阵存储,则该矩阵的大小是A.n×(n-1)B.(n-1)×(n-1)C.(n+1)×(n+1)D.n×n13.已知一个有序表为(15,19,30,33,49,50,65,88,93,126,164),当二分查找值为126的元素时,检索成功需进行的比较次数为A.1次B.2次C.3次D.4次14.直接选择排序算法的时间复杂度为2)A.O(1)B.O(log2n)C.O(n)D.O(n15.下述四种排序算法中,所需辅助存储量最
6、多的是A.堆排序B.快速排序C.归并排序D.直接选择排序浙02142#数据结构导论试题第2页(共5页)非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。二、填空题(本大题共13小题,每小题2分,共26分)16.在数据库中,又称为字段或域。p17.双向循环链表中,在所指结点的后面插入一个新结点*t,需要修改四个指针,分别为:t->prior=p;t->next=p->next;p->next->prior=t;;。18.线性表中所含结点的个数称为。19.在带有头结点的循环链表中,头指针为head
7、,判断p所指结点为尾结点的条件是。20.链栈LS中,LS->next指向栈顶结点,则新结点*p入栈的操作为:p->next=LS->next;和;。21.为了节省存储空间,将矩阵中多个值相同的元素只分配一个存储空间,零元素不存储,这种存储方式通常称为矩阵的。22.100个结点的二叉树采用二叉链表存储时,空指针域NULL有个。23.已知完全二叉树的第5层有5个结点,则整个完全二叉树有个叶结点。24.一个树的最少结点个数为。25.索引顺序表由两部分组成:一个是顺序表,另一个是。26.二叉排序树上的平均查找长度介于和O(n)之间。2
8、7.二分查找算法的时间复杂度是。28.最好情况下,冒泡排序算法的时间复杂度为,它是一种稳定的排序方法。三、应用题(本大题共5小题,每小题6分,共30分)29.如题29图所示,在栈的输入端元素的输入顺序为A,5,8,试写出在栈的输出端可以得到的以数字开头的所有输出序列,并写出进
