《自学考试_全国2014年10月高等教育自学考试数据结构导论试题(02142)》由会员分享，可在线阅读，更多相关《自学考试_全国2014年10月高等教育自学考试数据结构导论试题(02142)（5页珍藏版）》请在金锄头文库上搜索。
1、 绝密考试结束前 全国2 0 1 4年1 0月高等教育自学考试 数据结构导论试题 课程代码: 0 2 1 4 2 请考生按规定用笔将所有试题的答案涂、 写在答题纸上。 选择题部分 注意事项: 1.答题前, 考生务必将自己的考试课程名称、 姓名、 准考证号用黑色字迹的签字笔或钢笔 填写在答题纸规定的位置上。 2.每小题选出答案后, 用2 B铅笔把答题纸上对应题目的答案标号涂黑。如需改动, 用橡 皮擦干净后, 再选涂其他答案标号。不能答在试题卷上。 一、 单项选择题( 本大题共1 5小题, 每小题2分, 共3 0分) 在每小题列出的四个备选项中只有一个是符合题目要求的, 请将其选出并将“ 答题纸”
2、 的相 应代码涂黑。错涂、 多涂或未涂均无分。 1.下列算法的时间复杂度为 f o r(i =1;i p r i o r =p;t -n e x t =p -n e x t;p -n e x t -p r i o r = t ; ; 。 1 8.线性表中所含结点的个数称为 。 1 9.在带 有 头 结 点 的 循 环 链 表 中, 头 指 针 为h e a d, 判 断p所 指 结 点 为 尾 结 点 的 条 件 是 。 2 0.链栈L S中,L S - n e x t指向栈顶结点, 则新结点 * p 入栈的操作为: p - n e x t =L S -n e x t; 和 ; 。 2 1.为
3、了节省存储空间, 将矩阵中多个值相同的元素只分配一个存储空间, 零元素不存储, 这种 存储方式通常称为矩阵的 。 2 2. 1 0 0个结点的二叉树采用二叉链表存储时, 空指针域NU L L有 个。 2 3.已知完全二叉树的第5层有5个结点, 则整个完全二叉树有 个叶结点。 2 4.一个树的最少结点个数为 。 2 5.索引顺序表由两部分组成: 一个是顺序表, 另一个是 。 2 6.二叉排序树上的平均查找长度介于 和O(n) 之间。 2 7.二分查找算法的时间复杂度是 。 2 8.最好情况下, 冒泡排序算法的时间复杂度为 , 它是一种稳定的排序方法。 三、 应用题( 本大题共5小题, 每小题6分
4、, 共3 0分) 2 9.如题2 9图所示, 在栈的输入端元素的输入顺序为A,5,8, 试写出在栈的输出端可以得到的 以数字开头的所有输出序列, 并写出进栈、 出栈的操作过程( 用p u s h(x) 表示x进栈, p o p 题2 9图 ( x) 表示x出栈) 。 )页 5 共(页 3 第 题试论导构结据数 #24120 浙 3 0.分别写出题3 0图所示二叉树的先序遍历、 中序遍历和后序遍历的结点序列。 题3 0图 3 1.写出题3 1图所示有向图顶点的所有拓扑排序序列。 题3 1图 3 2.将题3 2图所示的一棵树转换为二叉树。 题3 2图 3 3.判断序列(2 8,7 5,3 3,6
5、8,2 5,5 6,4 7,9 9,8 6,3 6) 是否为堆? 如果不是, 则把它调整为堆( 最小 堆) 。 )页 5 共(页 4 第 题试论导构结据数 #24120 浙 四、 算法设计题( 本大题共2小题, 每小题7分, 共1 4分) 3 4.单链表的结构定义如下: t y p e d e f s t r u c tn o d e i n td a t a; s t r u c tn o d e*n e x t; N o d e,*L i n k L i s t; 试编写算法i n tC o u n t L i n k l i s t(L i n k L i s th e a d, i n tx) 实现在带头结点的单链表h e a d中计算 值为x的结点数。 3 5.假设线性表中结点是按键值递增的顺序排列, 试编写一个顺序查找算法, 将岗哨设在高下 标端。并说明等概率情况下查找成功和不成功时的平均查找长度。 )页 5 共(页 5 第 题试论导构结据数 #24120 浙
