2017年4月自考02331数据结构试题及答案.docx

2017 年 4 月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码 02331) 本试卷共 7 页。满分 l00 分，考试时间 l50 分钟。考生答题注意事项： 本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均 可作草稿纸。 第一部分为选择题。必须对应试卷上的题号使用 2B 铅笔将“答题卡”的相应代码涂黑。 第二部分为非选择题。必须注明大、小题号。使用 0．5 毫米黑色字迹签字笔作答。 合理安排答题空间，超出答题区域无效。 第一部分选择题(共 30 分) 一、单项选择题(本大题共 l5 小题，每小题 2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并 将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列叙述中，不正确的是 A．算法解决的只能是数值计算问题 B．同一问题可以有多种不同算法 C．算法的每一步操作都必须明确无歧义D．算法必须在执行有限步后结束 下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是A．顺序存储时不一定相邻，链式存储时一定相邻 B．顺序存储时不一定相邻，链式存储时也不一定相邻 C．顺序存储时一定相邻，链式存储时也一定相邻 D．顺序存储时一定相邻，链式存储时不一定相邻 设栈的入栈序列为1,2, 3, 4,5, 经过入、出栈操作后，可能得到的出栈序列是 A. 2, 3, 5, I, 4 B. 4, 2, l1 3, 5 c. 3, 4, 1, 2, 5 D. 3,4,2, 1,5 数组A[2][3]按行优先顺序存放， A 的首地 址为 10。若 A 中每个元素占用一个存储 - 单元，则 元素 A[1][2]的存储地址是 A. 10 B. 12 广义表((a, b), (c, d)）的表尾是  C. 14 D. 15 b B. d C. (c, d) D. ((c, d)) 若完全二叉树T包含 20 个终端结点，则T 的结点数 最多是 A. 38 B. 39 C. 40 D. 41 对下面的二叉树进行中序线索化后， 结点f 的右指针指向的结点是 a B. b C. c D. e 若图G 是一个含有n 个顶点的强连通有向图，则G 的边数至少是 A. n-1 B. n C. n*(n+l)/2 D. n*(n+l) 若从顶点a 开始对下图进行广度优先遍历，则 不可能 得到的遍历序列是 a, b, c, e, f, d C. a, c, e, b, d, f 下列排序算法中，稳 定的是 堆排序 C. 冒泡排序 B. a, c, b, e, f, d D. a, e, b, c, f, d B. 直接选择排序 D. 希尔排序 下列排序算法中， 比较操作的 次数与待排序序列初始排列状态无关的是 快速排序 B. 直接选择排序 C. 冒泡排序 D. 直接插入排序 若对二叉排序树进行遍历， 则下列遍历方式中，其遍 历结果为递增有序的是 前序遍历 C. 后序遍历 B．中序遍历 D. 按层遍历 14. 设一组记录的关键字为{12, 22, 10, 20, 88, 27, 54, 11}，散列函 数为H(key)=key% 11, 用拉链法解决冲突，则散列地 址为0 的链中结点数是 A. 1 B. 2 C. 3 D. 4 在下面3 阶B 树中插入关键字 65 后， 其根结点内的关键字是 53 90 53 90 50 61 70 100 A. 53 90 B. 53 C. 90 D. 65 第二部分 非选择题（共70 分） 二、填空题（本大题共10 小题， 每小题 2 分，共 20 分） 散列方法的基本思想是根据元素的关键字直接计算出该元素的 。 一个需要频繁增删的线性表宜选择 存储结构。 若中缀表达式为9 + (6- 2) * 8, 则相应的后缀表达式是 。 对任何一棵二叉树 T, 若其叶子结点数为 n。，度 数为 2 的结点数为 n2 ， 则 n2 等 于 若某二叉树T的前序遍历序列是A, B, C, D, 中序遍历序列是B, A, D, C, 则T的后序遍历序列是 。 在给定n 个叶子结点权值且不含度数为 1 的结点的所有二叉树中，其 最小的二叉树称为哈夫曼树。 用邻接表存储含n 个顶点 e 条边的有向无环图G, 对G 进行拓扑排序，算法的时间复杂度为 。 连通图 G 的一个子图如果是一棵包含 G 的所有顶点的树， 则 该 子图称为 G 的树。 二分查找的速度快效率高， 但是它要求表按关键字有序并且 。 除了问题的规模和分量个数之外，还有 是影响基数排序时间复杂度的主要因素。 三、解答题（本大题共4 小题， 每小题 5 分， 共20 分） 对题 2