2010年云南昆明理工大学数据结构教程考研真题A卷.doc

发布时间：2022-09-17 发布人：admin 分类：说明书资料大小：0.05M 资料格式：doc 举报版权申诉

第1页 / 共3页

2010年云南昆明理工大学数据结构教程考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共3页

2010年云南昆明理工大学数据结构教程考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共3页

文本预览

2010 年云南昆明理工大学数据结构教程考研真题 A 卷一、单项选择题：（每题 3 分，共 30 分） 1．非线性结构中每个结点。 A. 无直接前驱结点 B. 只有一个直接前驱和直接后继结点 C. 无直接后继结点 D. 可能有多个直接前驱和多个直接后继结点 2．在表长为 n 的单链表中，算法时间复杂度为 O(n)的操作是。 A. 查找单链表中第 i 个结点 B. 在 p 结点之后插入一个结点 C. 删除表中第一个结点 D. 删除 p 结点的直接后继结点 3．在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是。 A. 仅有头指针的单链表 B. 仅有头指针的单循环链表 C. 仅有头指针的双向链表 D. 仅有尾指针的单循环链表 4. 设有 10 阶矩阵 A，其对角线以上的元素 aij(1≤j≤10，11）的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点。 A. 仅有左孩子 B. 仅有右孩子 C. 仅有一个孩子 D. 都有左、右孩子 7. 关于连通图的 BFS 和 DFS 生成树高度论述正确的是。 A. BFS 生成树高度DFS 生成树高度 D. BFS 生成树高度≥DFS 生成树高度 8．对线性表用二分法查找时要求线性表必须是。 A. 顺序表 B. 单链表 C. 顺序存储的有序表 D. 散列表 9. 在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的健值。 A. 一定都是同义词 B. 一定都不是同义词 C. 不一定是同义词 D. 无任何

关系 10．堆排序是一种。 A) 插入排序 B) 选择排序 C) 交换排序 D) 归并排序二、判断题（每题 2 分，共 20 分） 1．在单链表中存取某个元素，只要知道指向该元素的指针，因此单链表是随机存取的存储结构。（） 2．若一个有向图的邻接矩阵中对角线以下的元素均为零，则该图的拓扑序列必定存在。（） 3．消除递归必须用栈来实现。（） 4．稀疏矩阵压缩存储后必会失去随机存取的功能。（） 5．堆排序所需要附加空间数取决于待排序的记录的个数。（） 6．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（） 7．采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（） 8．对于 n 个顶点的无向图，若其边数大于或等于 n-1，则其必是连通图。（） 9．一棵完全二叉树中的结点若无左孩子，则其必是叶结点。（） 10．将二叉排序树的中序序列中的关键字依次插入初始为空的树中，所得到的二叉排序树与原二叉排序树是相同的。（）三、简答题（共 50 分） 1．对 n 个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题：（1）图中有多少条边？（2）任意两个顶点 i 和 j 是否有边相连？（3）任意一个顶点的度是多少？（18 分） 2．判断下列序列是否为堆，若不是堆则把它们调整为堆。（12 分）（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，一个元素出栈后即进入队列，若 6 个元素出队的序列是 bdcfea，则栈 s 的容量至少应该存多少个元素？（10 分）四、已知一组记录的关键字为{18，2，10，6，78，56，45，50，110，8}。（1）按输入顺序画出此组记录的平衡二叉树，求等概率情况下查找成功的平均查找长度。若查找每个元素的概率不等时，这时的平衡二叉树是否是最佳查找树？为什么？（2）设装填因子α=0.77，散列函数 H（key）=key MOD 11，用线性探测再散列方法解决冲突，试构造散列表，并求出在等概率情况下查找成功和查找不成功的平均查找长度。（15 分）五、设图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。（10 分）六、已知线性表（a0，a1，…an-1）按顺序存储于内存，每个元素都是整数，用 C 或类 Pascal 语言编写一个函数，用最少的时间把所有值为负数的元素移到全部正数值元素前面的算法。（10 分）七、某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表并存于计算机中，链表的每个结点指出同样价格的若干台。现在又新到 m 台价格为 h 元的电视机入库。试编写出仓库电视机链表增加电视机的算法。（简要说明算法思想，算法描述用类 Pascal 或者类 C 语言均可）（15 分）

分享到：

赞收藏

资料库

2010年云南昆明理工大学数据结构教程考研真题A卷.doc

相关推荐

考研

热门标签

最新资料