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

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

第1页 / 共3页

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

第2页 / 共3页

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

第3页 / 共3页

文本预览

2009 年云南昆明理工大学数据结构教程考研真题 A 卷一、判断题（每题 2 分，共 20 分） 1．在单链表和顺序表中插入一个元素，其时间复杂度均为 O(n)。因此它们的执行时间是相等的。（） 2．若一个栈的输人序列为 1，2，3，…，n，其输出序列的第一个元素为 n，则其输出序列的每个元素 ai 一定满足 ai＝n-i+1(i=1，2，…，n)。（） 3．将一棵树转换为二叉树后，二叉树的根结点没有左子树。（） 4．在 n 个结点的无向图中若边数大于 n-1，则该图必是连通图。（） 5．对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例。（） 6．采用单链表表示的有序表可以使用折半查找方法来提高查找速度。（） 7．将二叉排序树 T 的先序序列中的关键字依次插入初始为空的树中，所得到的二叉排序树 T’与 T 是相同的。（） 8．循环队列是以循环链表为存储结构的队列。（） 9．采用链地址法处理冲突的散列表的装填因子可以大于 1。（） 10．若一个广义表的表头是空表，则此广义表也是空表。（）二、选择题（每题 3 分，共 30 分） 1．若采用以下四种结构表示 n 个元素，那么（）的随机访问速度最快。 A．单链表 B．双链表 C．循环链表 D．顺序表 2．由两个栈共享一个向量空间的好处是（）。 A．减少存取时间，降低下溢发生的几率 B．节省存储空间，降低上溢发生的几率率 C．减少存取时间，降低上溢发生的几率 D．节省存储空间，降低下溢发生的几 3．采用二叉链表存储的二叉树中若有 n 个结点，那么有（）个非空指针域。 A．n-1 B．n+1 C．2n-1 D．2n+1 4．一棵有 124 个叶结点的完全二叉树，最多有（）个结点。

A．247 B．248 C．249 D．250 5．一个有序表为{1，3，12，32，45，62，75，77，82，100}，当折半查找值为 82 的结点时，经过（）次比较后查找成功。 A．1 B．3 C．9 D．2 6．实现二叉树的后序遍历的非递归算法，若不用栈结构，那么最佳实现方案是二叉树采用（）存储结构。 A．二叉链表 B．广义表 C．三叉链表 D．顺序 7．关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路 8．线索二叉树是一种（）结构。 A: 逻辑 B: 逻辑和存储 C: 物理 D: 线性 9．若从二叉树的任意结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（）。 A．二叉排序树 B．平衡二叉树 C．完全二叉树 D．堆 10．散列查找中 k 个关键字具有同一散列地址，若用线性探测法将这 k 个关键字对应的记录存入散列表中，至少要进行（）次探测。 A．k-1 B．k+1 C．k（k+l）/2 D．1+k(k+l）/2 三、简答题（每题 12 分，共 60 分） 1．简述在表示数据元素之间的关系时，顺序存储结构与链式存储结构之间的区别；并回答在什么情况下用顺序结构比链式结构好，请举例说明。 2．简述哈夫曼树的应用领域。已知字符 A、B、C、D、E、F 的权值为 7、12、6、20、3、 10，请写出构造哈夫曼树的过程，并为这些字符设计哈夫曼编码。 3．简述平衡二又树的性质，解释平衡因子的作用。将关键码序列 36，88，100，20， 25，28，96，10 依次插入到初始为空的平衡二叉树中去，请写出构造平衡二又树的过程。 4．什么叫 AOE 网？对如下图所示的 AOE 网，计算每个事件的最早发生时间和最迟发生时间，每个活动的最早发生时间和最迟发生时间；请画出关键路径，并回答提高哪些活动的效率可以缩短工期？

5．对序列{16，25，-12，1，36，18，30，24，-3，-10，-2，9}进行快速排序，请写出排序过程。若在此排好序的序列上进行折半查找，请画出查找过程的判定树。四、算法设计题（共 40 分）要求：①定义有关的数据存储类型；②先简单描述算法的思想，再用类 C 或类 Pascal 语言描述算法；③对算法中的主要语句加以注释。 1．数组 B 中存放着 n 个整数，请设计算法将所有能被 3 整除的数放在数组的前半部分。要求使用尽量少的临时单元，且算法的效率较高，并请分析算法的时间复杂度。(20 分） 2．已知奇偶交换排序算法描述如下：第 1 趟对所有奇数的 i，将 a[i]和 a[i+1]进行比较，第 2 趟对所有偶数的 i，将 a[i]和 a[i+1]进行比较，每次比较时若 a[i]>a[i+1]，则将二者交换，以后重复上述两趟过程，直至整个数组有序。(20 分） (1)试问排序结束的条件是什么？ (2)编写一个实现上述排序过程的算法。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料