1、第1页 共 4页三 峡 大 学2016年研究生入学考试试题(A卷)科目代码： 838 科目名称： 数据结构 考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、选择题 (每小题3分，共 60 分)1、数据在存储器内表示时，物理地址与逻辑地址相同且连续，称为（ ）。A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 A. 110 B. 108 C. 100 D. 1203、栈中元素的进出原则是（ ）。A.先进先出 B.后进先出 C.栈空则进 D.栈满则出4、如下陈述中正确的是（
2、）。A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母 D. 空串就是空白串5、设有一个二维数Bmn，假设B00存放位置在544，B22存放位置在576，每个元素占一个空间，B55在（ ）位置。A. 592 B. 586 C. 624 D. 6086、设5个字符的频度分别为1,2,3,4,5，其哈夫曼树的带权路径长度为（ ）。A. 34 B. 33 C. 35 D. 377、链式存储的存储结构所占存储空间：（ ）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值第 2 页C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放
3、结点值，另一部分存放结点所占单元数8、下述几种排序方法中，要求内存最大的是（ ）。A插入排序 B快速排序 C归并排序 D选择排序9、二叉树是非线性数据结构，关于它的存储，以下哪个描述正确（ ）。A它不能用顺序存储结构存储 B顺序存储结构和链式存储结构都能存储C顺序存储结构和链式存储结构都不能使用 D它不能用链式存储结构存储10、用改进的起泡排序算法对n个元素进行排序时最多比较次数为( )。A. n B. n-1 C. n2 D. n (n-1)/211、 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1, p2, p3, , pn,若p1=n，则pi为（ ）。A. i B. n = i
4、 C. n-i+1 D. 不确定12、若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ ）。A. 79, 46, 56, 38, 40, 84 B. 84, 79, 56, 38, 40, 46 C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 38 13、线性表在什么情况下适用于使用链式结构实现（ ）。A需经常修改中的结点值 B需不断对进行删除插入 C中含有大量的结点 D中结点结构复杂14、向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动多少个元素（ ）。A8 B
5、62 C63 D6415、 深度优先遍历类似于二叉树的（ ）。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历16、 任何一个无向连通图的最小生成树（ ）。A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在第 3 页17、 有7个结点的无向图最多有多少条边（ ）。A. 14 B. 28 C. 56 D. 2118、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败（ ）。A. 20，70，30，50 B. 30，88，70，50 C. 20，50 D. 30，88，50
6、19、链表适用于哪种查找（ ）。A. 顺序 B. 二分法 C. 顺序，也能二分法 D. 随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（ ）。A. 是唯一的 B. 有多种C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子二、填空题(每小题2 分，共 30分)1、快速排序的平均时间复杂度是 ，它在最坏情况下的时间复杂度是 。（要求用大O表示法表示）2、一棵具有257个结点的完全二叉树，它的深度为 。3、已知一采用空闲单元法的循环队列容量为20，队列的首、尾指针分别用f和r表示，f3，r18时队列的长度为 ，f15，r7时队列的长度为 。 4、三元素组表中的每
7、个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。5、如果一棵完全二叉树具有500个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。6、由3个结点所构成的二叉树有 种形态。 7、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为了寻找插入位置至少需要比较 次。8、稠密图适合采用 存储结构。第 4 页三、综合题(共60分)1、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？（1
8、5分）2、根据下图回答问题（15分）（1）要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）（2）上图中的关键路径是什么（用顶点序列表示）？将活动a10的时间改成2能否提前完成？（5分）（3）若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为0的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）3、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。（15分）4、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，.，n6个度为6的结点，则该树中有多少个叶子结点，并证明。（5分）5、请对下图的无向带权图, 要求写出详细过程：（10分）（1）按普里姆算法求其最小生成树；（从顶点a开始） （5分）（2）按克鲁斯卡尔算法求其最小生成树。 （5分）
