暨南大学 2016 考研真题之 830 数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、 单项选择题(每题 2 分，共 30 分) 1. 在线索化二叉树中，T 所指结点没有左子树的充要条件是（ ）。A. T-> lchild=NULL B. T->ltag=1 C. t->ltag=1 且 t-> lchild =Null D. 以上都不对2. 一个带有头结点的单链表为空的判定条件是 ( )。A. head = NULL B. head->next = NULLC. head->next = head D. head != NULL3. 线性链表不具有的特点是（ ）。A. 随机访问 B. 不必预估所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比4. 在下面的排序方法中，稳定的是（ ）。 A. 希尔排序 B. 堆排序 C. 插入排序 D. 快速排序5.设有 n 个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。AO(1) B. O(n) C. O(nlog2n) D. O(n2)6. 数组 A的每个元素占 5 个字节，将其按行优先次序存储。假设A11元素的存储地址为 1000，则元素 A，的存储地址为( )。A. 1140 B. 1145 C. 1120 D. 11257. 高度为 n 的完全二叉树的结点数至少为（ ）。A. 2n-1 B. 2n-1+1 C. 2n D. 2n+18. 设有一个无向图 G=（V，E）和 G=（V，E），如果 G为 G 的生成树，则下面不正确的说法是（ ）。AG为 G 的子图 BG为 G 的连通分量CG为 G 的极小连通子图且 V=V DG为 G 的一个无环子图9. 在有向图的邻接表存储结构中，顶点 V 在表结点中出现的次数是（ ）。A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数 10. 关键路径是事件结点网络中( )。A最短的回路 B从源点到汇点的最短路径C最长的回路 D从源点到汇点的最长路径11. 一个有 n 个结点的无向图最多有（ ）条边。A. n B. n-1 C. n(n-1) D. n(n-1)/212. 对某个无向图的邻接矩阵来说，( )。A第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等B矩阵中的非零元素个数等于图中的边数C第 i 行上，第 i 列上非零元素总数等于顶点 vi 的度数D矩阵中非全零行的行数等于图中的顶点数13. 平衡二叉树的平均查找长度是 ( )。A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）14. 下列哪种排序需要的附加存储开销最大( )。A. 快速排序 B. 堆排序 C. 归并排序 D. 插入 排序 15. 设一数列的顺序为 1,2,3,4,5,6, 通过栈操作可以得到（ ）的输出序列。A. 3,2,5,6,4,1 B. 1,5,4,6,2,3C. 6,4,3,2,5,1 D. 3,5,6,2,4,1二填空题(每空 2 分，共 20 分)1. 在一个长度为 n 的顺序表中删除第 i 个元素时，需向前移动 个元素。2. 设数组 Data0.m作为循环队列 SQ 的存储空间，front 为队头指针，rear为队尾指针则执行出队操作时 front 指针的值应更新为 front= 。3. 在单链表中，若要删除指针 p 所指结点的后一结点，则需要执行下列语句：（设 q 为指针 变量）q=p->next; ； 。4. 在有 n 个结点的二叉链表中，值为 NULL 的链域的个数为 。5. 二叉树中度为 0 的结点数为 30，度为 1 的结点数为 30，总结点数为 。6. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 ，整个堆排序过程的时间复杂度为 。7. 对于 n 个记录（假设每个记录含 d 个关键字）进行链式基数排序，总共需要进行 趟分配和收集。8. 设有向图 G 中有向边的集合E=， ，则该图的一种拓扑序列为 。三判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f）1. 在 n 个顶点的无向图中，若边数 >n-1，则该图必是连通图。 （ ）2. 具有 n 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（ ）3. 使用散列法存储时，哈希表的大小可随意选取，通常取 10 的倍数。（ ）4. 向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（ ）5. 数据元素是数据的最小单位。（ ）6. 普里姆(Prim)算法相对于克鲁斯卡尔(Kruskal)算法更适合求一个稀疏图 G的最小生成树。（ ）7. 向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（ ）8. 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度加 1。（ ）9. 无向图的邻接矩阵一定是对称阵。 ( )10. 对小根堆进行层次遍历可以得到一个有序序列。（ ）四. 简答题（ 45 分）1. 已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，求解下列问题：(1) 画出此二叉树。（4 分）(2) 将该二叉树转换成森林。（4 分）2. 设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H(key)=key %10，采用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列(按从左到右的次序) 构造哈希表，并计算在查找概率相等的前提下，成功查找的平均查找长度。（7 分） 3. 设有一组初始记录关键字为(3,1,4,6,8,2,5) ，要求构造一棵平衡二叉树，并给出构造过程。（5 分 4. 对图 1 所示的无向加权图完成下列要求： （1）写出它的邻接表；（5 分）（2）按克鲁斯卡尔（Kruskal）算法求其最小生成树，并给出其过程。（ 6 分）（3）给出从顶点 a 开始的深度优先搜索序列和深度优先生成树。（ 4 分）5. 已知序列(142,543,123,65,453,879,572,434,111,242,811,102)。(1) 采用希尔排序对该序列作升序排序，请给出第一趟排序的结果（初始步长为 7）。（ 5 分）(2) 采用堆排序对该序列作升序排序，请给出初始堆以及第一趟排序的结果。（5 分）五算法填空，（每空 2 分, 共 20 分）1. 下面算法实现对一个不带头结点的单链表 L 进行就地（不增加额外存储空间）逆置。请在_处填上适当内容，使其成为一个完整算法。六编写算法（25 分）1. 设有一组初始记录关键字序列（K1 ，K2，Kn），要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。（10 分）2. 设有一整型数组 w 保存 n 个字符的权值（均大于 0），请写出(1) 构造赫夫曼树 (Huffman)的算法。（8 分）(2) 求各字符赫夫曼编码的算法。（7 分）考研高分咨询新祥旭罗老师电话/ 微信：13701149740咨询 QQ：3219057729 一、 单项选择题(每题 2 分，共 30 分) 1. 在线索化二叉树中，T 所指结点没有左子树的充要条件是（ ）。A. T-> lchild=NULL B. T->ltag=1 C. t->ltag=1 且 t-> lchild =Null D. 以上都不对2. 一个带有头结点的单链表为空的判定条件是 ( )。A. head = NULL B. head->next = NULLC. head->next = head D. head != NULL3. 线性链表不具有的特点是（ ）。A. 随机访问 B. 不必预估所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比4. 在下面的排序方法中，稳定的是（ ）。 A. 希尔排序 B. 堆排序 C. 插入排序 D. 快速排序5.设有 n 个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。AO(1) B. O(n) C. O(nlog2n) D. O(n2)6. 数组 A的每个元素占 5 个字节，将其按行优先次序存储。假设A11元素的存储地址为 1000，则元素 A，的存储地址为( )。A. 1140 B. 1145 C. 1120 D. 11257. 高度为 n 的完全二叉树的结点数至少为（ ）。A. 2n-1 B. 2n-1+1 C. 2n D. 2n+18. 设有一个无向图 G=（V，E）和 G=（V，E），如果 G为 G 的生成树，则下面不正确的说法是（ ）。AG为 G 的子图 BG为 G 的连通分量CG为 G 的极小连通子图且 V=V DG为 G 的一个无环子图9. 在有向图的邻接表存储结构中，顶点 V 在表结点中出现的次数是（ ）。A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数 10. 关键路径是事件结点网络中( )。A最短的回路 B从源点到汇点的最短路径C最长的回路 D从源点到汇点的最长路径11. 一个有 n 个结点的无向图最多有（ ）条边。A. n B. n-1 C. n(n-1) D. n(n-1)/212. 对某个无向图的邻接矩阵来说，( )。A第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等B矩阵中的非零元素个数等于图中的边数C第 i 行上，第 i 列上非零元素总数等于顶点 vi 的度数D矩阵中非全零行的行数等于图中的顶点数13. 平衡二叉树的平均查找长度是 ( )。A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）14. 下列哪种排序需要的附加存储开销最大( )。A. 快速排序 B. 堆排序 C. 归并排序 D. 插入 排序 15. 设一数列的顺序为 1,2,3,4,5,6, 通过栈操作可以得到（ ）的输出序列。A. 3,2,5,6,4,1 B. 1,5,4,6,2,3C. 6,4,3,2,5,1 D. 3,5,6,2,4,1二填空题(每空 2 分，共 20 分)1. 在一个长度为 n 的顺序表中删除第 i 个元素时，需向前移动 个元素。2. 设数组 Data0.m作为循环队列 SQ 的存储空间，front 为队头指针，rear为队尾指针则执行出队操作时 front 指针的值应更新为 front= 。3. 在单链表中，若要删除指针 p 所指结点的后一结点，则需要执行下列语句：（设 q 为指针 变量）q=p->next; ； 。4. 在有 n 个结点的二叉链表中，值为 NULL 的链域的个数为 。5. 二叉树中度为 0 的结点数为 30，度为 1 的结点数为 30，总结点数为 。6. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 ，整个堆排序过程的时间复杂度为 。7. 对于 n 个记录（假设每个记录含 d 个关键字）进行链式基数排序，总共需要进行 趟分配和收集。