1、 第 1 页 共 9 页2016 年 10 月高等教育自学考试全国统一命题考试数据结构 试卷(课程代码 02331)本试卷共 7 页，满分 l00 分，考试时间 l50 分钟。 考生答题注意事项：1本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2第一部分为选择题。必须对应试卷上的题号使用 2B 铅笔将“答题卡”的相应代码涂黑。3第二部分为非选择题。毖须注明大、小题号，使用 05 毫米黑色字迹签字笔作答。4合理安排答题空间，超出答题区域无效。第一部分 选择题(共 30 分)一、单项选择题(本大题共 l5 小题，每小题 2 分，共 30 分在每小题列出的四个备选项中
2、只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。1下列选项中，不属于线性结构特征的是A数据元素之间存在线性关系 B结构中只有一个开始结点C结构中只有一个终端结点 D每个结点都仅有一个直接前趋2设 l7 个元素的顺序表中，若将第 个元素 e 移动到第 个位置，不改变除 e 外其他元素之间的相对次序，则需移动的表中元素个数是3若用一个大小为7 的数组作为循环队列的存储结构，且当前 rew 和盘 0nt 的值分别为 2 和 4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这 3个操作之前 rear 和矗 0nt 的值分别是A0 和 l B0 和
3、 3 C3 和 6 D4 和 54已知广义表 LS=(a)，(b，(c)，(d，(e，f)，0)，LS 的长度是A2 B3 C4 D. 55一棵完全二叉树 T 的全部 k 个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是Ak B. 2k-1 Ck 2 D2 k-16如果某二叉树的前序遍历序列为 abced，中序遍历序列为 cebda，则该二叉树的后序遍历序列是Acedba Bdecba Cecdba Decbad7一个森林有 m 棵树，顶点总数为 n，则森林中含有的总边数是Am B. n-l Cn-m Dn+m8设图的邻接矩阵 A 如下所示。各顶点的度依次是A1，2，1，
4、2 B2，2，1，l C3，4，2，3 D4，4，2，29若对下厦无向图进行深度优先遍历，得到的正确遍历序列是第 2 页 共 9 页Ah，C，a，b，d，e，g，f Be，a，f，g，b，h，c，dC. d，b，c，a，h，e，f，g Da，b，C，d，h，e，f，g10己知有向图 G 如下所示，G 的拓扑序列是Aa，b，e，c，d，f,g Ba，c，b，f，d，e，gC. a，C，d，e，b，f，g D. a，c，d，f，b，e，g11下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是A插入排序 B希尔排序 C归并排序 D直接选择排序12对一组数据(2，l2，16，88，5，10)
5、进行排序，若前 3 趟排序结果如下：第一趟：2，12，l6，5，10，88第二趟：2，12，5，l0，16，88第三趟：2，5，10，l2，l6，88则采用的排序方法是A冒泡排序 B希尔排序 C归并排序 D基数排序13设有序表为9，l2，21，32，41，45，52，当二分查找值为 52 的结点时，元素之间的比较次数是A1 B2 C3 D4 14下列选项中，既熊捌回事存储结构也能在链式存储结构上进行查找的方法是A散列查找 B顺序查找C二分查找 D以上选项均不能15在一棵 5 阶 B 树中，每个非根结点中所含关键字的个数最少是A1 B2 C3 D4第二部分 非选择题(共 70 分)二、填空题(本
6、大题共 l0 小题，每小题 2 分，共 20 分)16两个栈 S1和 S2共用含 100 个元素的数组 S0 一 99，为充分利用存储空间，若 S2的栈底元素保存在 S99中，则 S1的栈底元素保存在_中。17在一个单链表中，已知指针变量 q 所指结点不是表尾结点，若在 q 所指结点之后插入指针变量 S 所指结点，则正确的执行语句是_。18设顺序表第 1 个元素的存储地址是 1000，每个数据元素占 6 个地址单元，则第 11个元素的存储地址是_。19二叉树采用顺序存储方式保存，结点 Z 保存在数组 A7中，若 X 有右孩子结点 L则 Y 保存在_中。20一棵二叉树中，度数为 l 的结点个数为
7、 n1，度数为 2 的结点个数为 n2，则叶结点的个数为_。21已知广义表 LS=(b)，c，d)，head(LS)是_。22在无向图 G 的邻接矩阵 A 中， =_。第 3 页 共 9 页23. 已知大根堆中的所有关键字均不相同，最大元素在难项，第 2 大元素可能存在的位置有 2 个，第 3 大元素可能存在的位置有_个。24在有 n 个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找成功时平均查找长度是_甘肃自考网 www.gsks.cc_。25线性探查法和拉链法解决的是散列存储中的_问题。三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26对题 26 图中所给
8、的二叉排序树 T 回答下列问题。(1)给出能生成 r 的 2 种关键字插入序列；(2)给出 r 的前序遍历序列。27对题 27 图所示的无向带权图 G，回答下列问题。(1)给出图 G 的邻接矩阵；(2)给出图 G 的一棵最小生成树。28现有 5 个权值分别是 20、31、16、7 和 l5 的叶结点，用它们构造一棵哈夫曼树，画出该树。29. 对于给定的一组关键字序列26，l8，60，65，45，13，32，写出使用直接选择排序方法将其排成升序序列的过程。四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30设非空双向循环链表 L 的头指针为 head，表结点类型为 DLNode
9、，定义如下。初始时，L 中所有结点的 prior 域均为空(NULL)，next 域和 data 域中已经正确赋值。如题 30 图 a 所示。第 4 页 共 9 页函数 f30 完成的功能是：将 L 中各结点的 prior 域正确赋值，使 L 成为双向循环链表。如题 30 图 b 所示。 将空白处应填写的内容答在答题卡上。31已知二叉树的二叉链表类型定义如下，阅读程序，并回答问题。若二叉树如下所示，写出调用 f31(T)的输出结果。第 5 页 共 9 页32阅读下列程序，写出 f32 的输出结果。33阅读程序，回答下列问题。五、算法设计题(本题 l0 分)34已知单链表类型定义如下：第 6 页 共 9 页单链表 L 中结点数不少于 2。设计算法判断 L 中存储的全部 n 个数据是否是斐波那契序列的前 n 项。如果是，则函数返回 1，否则返回 0。函数原型如下：第 7 页 共 9 页第 8 页 共 9 页第 9 页 共 9 页
