考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一 单项选择题(每题2分，共30分)1. 在线索化二叉树中，T所指结点没有左子树的充要条件是（）。A.T->lchild=NULLB.T->ltag=1C.t->ltag=1且t-> lchild=NullD. 以上都不对2. 一个带有头结点的单链表为空的判定条件是()。A. head == NULLB. head->next == NULLC. head->next == headD. head != NULL3. 线性链表不具有的特点是（）。A.随机访问B. 不必预估所需存储空间大小C.插入与删除时不必移动元素D. 所需空间与线性表长度成正比4. 在下面的排序方法中，稳定的是（）。A. 希尔排序B.堆排序C.插入排序D.快速排序5.设有n个待排序的记录关键字，则在堆排序中需要（）辅助记录空间。A．O(1)B. O(n)C. O(nlog2n)D. O(n2)6. 数组A［５］［６］的每个元素占5个字节，将其按行优先次序存储。假设A[1][1]元素的存储地址为1000，则元素A［５，５］的存储地址为()。A. 1140B. 1145C. 1120D. 11257. 高度为n的完全二叉树的结点数至少为（　　）。A.2n-1B. 2n-1+1C.2nD.2n+18.设有一个无向图G=（V，E）和G’=（V’，E’），如果G’为G的生成树，则下面不正确的说法是（）。A．G’为G 的子图B．G’为G 的连通分量C．G’为G的极小连通子图且V’=VD．G’为G的一个无环子图9. 在有向图的邻接表存储结构中，顶点V在表结点中出现的次数是（）。A.顶点V的度B. 顶点V的出度C. 顶点V的入度D. 依附于顶点V的边数10. 关键路径是事件结点网络中()。A．最短的回路B．从源点到汇点的最短路径C．最长的回路D．从源点到汇点的最长路径11. 一个有n个结点的无向图最多有（）条边。A.nB.n-1C. 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,1B. 1,5,4,6,2,3C. 6,4,3,2,5,1D. 3,5,6,2,4,1二．填空题(每空2分，共20分)1. 在一个长度为n的顺序表中删除第i个元素时，需向前移动个元素。2.设数组Data[0..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，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为。三．判断题（每题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分）半岛在线注册高分咨询罗老师电话/微信：**咨询QQ：**
一 单项选择题(每题2分，共30分)1. 在线索化二叉树中，T所指结点没有左子树的充要条件是（）。A.T->lchild=NULLB.T->ltag=1C.t->ltag=1且t-> lchild=NullD. 以上都不对2. 一个带有头结点的单链表为空的判定条件是()。A. head == NULLB. head->next == NULLC. head->next == headD. head != NULL3. 线性链表不具有的特点是（）。A.随机访问B. 不必预估所需存储空间大小C.插入与删除时不必移动元素D. 所需空间与线性表长度成正比4. 在下面的排序方法中，稳定的是（）。A. 希尔排序B.堆排序C.插入排序D.快速排序5.设有n个待排序的记录关键字，则在堆排序中需要（）辅助记录空间。A．O(1)B. O(n)C. O(nlog2n)D. O(n2)6. 数组A［５］［６］的每个元素占5个字节，将其按行优先次序存储。假设A[1][1]元素的存储地址为1000，则元素A［５，５］的存储地址为()。A. 1140B. 1145C. 1120D. 11257. 高度为n的完全二叉树的结点数至少为（　　）。A.2n-1B. 2n-1+1C.2nD.2n+18.设有一个无向图G=（V，E）和G’=（V’，E’），如果G’为G的生成树，则下面不正确的说法是（）。A．G’为G 的子图B．G’为G 的连通分量C．G’为G的极小连通子图且V’=VD．G’为G的一个无环子图9. 在有向图的邻接表存储结构中，顶点V在表结点中出现的次数是（）。A.顶点V的度B. 顶点V的出度C. 顶点V的入度D. 依附于顶点V的边数10. 关键路径是事件结点网络中()。A．最短的回路B．从源点到汇点的最短路径C．最长的回路D．从源点到汇点的最长路径11. 一个有n个结点的无向图最多有（）条边。A.nB.n-1C. 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,1B. 1,5,4,6,2,3C. 6,4,3,2,5,1D. 3,5,6,2,4,1二．填空题(每空2分，共20分)1. 在一个长度为n的顺序表中删除第i个元素时，需向前移动个元素。2.设数组Data[0..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，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为。三．判断题（每题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分）半岛在线注册高分咨询罗老师电话/微信：**咨询QQ：**