1、第 1 页 共 3 页 昆明理工大学 2010 年硕士研究生招生入学考试试题 (A 卷 ) 考试科目代码： 835 考试科目名称 ： 数据结构 教程 试题适用招生专业 ： 系统理论、系统分析与集成 考生答题须知 1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。 2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。 4 答题时不准使用涂改液等具有 明显标记的涂改用品。 一、单项选择题： （每题 3 分
2、，共 30 分） 1 非线性结构中每个结点 。 A. 无直接前驱结点 B. 只有一个直接前驱和直接后继结点 C. 无直接后继结点 D. 可能有多个直接前驱和多个直接后继结点 2 在表长为 n 的单链表中，算法时间复杂度为 O(n)的操作是 。 A. 查找单链表中第 i 个结点 B. 在 p 结点之后插入一个结点 C. 删除表中第一个结点 D. 删除 p 结点的直接后继结点 3 在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是 。 A. 仅有头指针的单链表 B. 仅有头指针的单循环链表 C. 仅有头指针的双向链表 D. 仅有尾指针的单
3、循环链表 4. 设有 10 阶矩阵 A，其对角线以上的元素 aij(1 j 10， 11）的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 。 A. 仅有左孩子 B. 仅有右孩子 C. 仅有一个孩子 D. 都有左、右孩子 7. 关于连通图的 BFS 和 DFS 生成树高度论述正确的 是 。 A. BFS 生成树高度 DFS 生成树高度 D. BFS 生成树高度 DFS 生成树高度 第 2 页 共 3 页 8 对线性表用二分法查找时要求线性表必须是 。 A. 顺序表 B. 单链表 C. 顺序存储的有序表 D. 散列表 9. 在采用线性探 查法处理冲 突的散列表 中进行查找
4、，查找成功 时所探测位置 上的健值 。 A. 一定都是同义词 B. 一定都不是同义词 C. 不一定是同义词 D. 无任何关系 10 堆排序是一种 。 A) 插入排序 B) 选择排序 C) 交换排序 D) 归并排序 二、 判断题（每题 2 分，共 20 分） 1在单链表中存取某个元素，只要知道指向该元素的指针，因此单链表是随机存取的存储结构。（ ） 2若一个有向图的邻接矩阵中对角线以下的元素均为零，则该图的拓扑序列必定存在。（ ） 3消除递归必须用栈来实现。（ ） 4稀疏矩阵压缩存储后必会失去随机存取的功能。（ ） 5堆排序所需要附加空间数取决于待排序的记录的个数。（ ） 6在二 叉 排序树上删
5、除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（ ） 7采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（ ） 8对于 n 个顶点的无向图，若其边数大于或等于 n-1，则其必是连通图。（ ） 9一棵完全二 叉 树中的结点若无左孩子，则其必是叶结点。（ ） 10将二 叉 排序树的中序序列中的关键字依次插 入 初始为空的树中，所得到的二 叉 排序树与原二 叉 排序树是相同的。（ ） 三、简答题 （共 50 分 ） 1 对 n 个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题： （ 1）图中有
6、多少条边？ （ 2）任意两个顶点 i 和 j 是否有边相连？ （ 3）任意一个顶点的度是多少？ （ 18 分） 2 判断下列序列是否为堆 ， 若不是 堆 则把它们调整为堆。 （ 12 分） 第 3 页 共 3 页 （ 1）（ 100， 86， 48， 73， 35， 39， 42， 57， 66， 21） （ 2）（ 12， 70， 33， 65， 24， 56， 48， 92， 86， 33） 3 特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能 ？ 为什么 （ 10 分） 4设 栈 s 和 队列 q 初始状态为空，元素 a、 b、 c、 d、 e、 f 依次通过栈 s，一个元素出栈后即进
7、入队列，若 6 个元素出队的序列是 bdcfea，则栈 s 的容量至少应该存多少个元素？ （ 10 分） 四、 已知一组记录的关键字为 18， 2， 10， 6， 78， 56， 45， 50， 110， 8。 （ 1）按输入顺序画出此组记录的平衡二叉树，求等概率情况下查找成功的平均查找长度。若查找每个元素的概率不等时，这时的平衡二叉树是否是最佳查找树？为什么？ （ 2）设装填因子 =0.77，散列函数 H（ key） =key MOD 11，用线性探测再散列方法解决冲突 ，试构造散列表，并求出在等概率情况下查找成功和查找不成功的平均查找长度。（ 15 分） 五、 设图中的顶点表示村庄，有向边
8、代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。（ 10 分） 六、 已知线性表（ a0， a1， an-1）按顺序存储于内存，每个元素都是整数， 用 C 或类 Pascal 语言 编写一个函数，用最少的 时间 把所有值为负数的元素移到全部正数值元素前面的算法 。 （ 10 分） 七、 某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表并存于计算机中，链表的每个结点指出同 样价格的若干台。现在又新到 m 台价格为 h 元的电视机入库。试编写出仓库电视机链表增加电视机的算法。（简要说明算法思想 ， 算法描述用类 Pascal 或者类 C 语言均可） （ 15 分）
