《数据结构与算法设计期末考试试卷.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计期末考试试卷.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、试 卷（A卷）数据结构与算法设计试卷开课单位：计算机学院，考试形式：闭卷，允许带 入场身眇送世奈般笨点亳题序一二三四五六七八总分得分评卷人I.基本概念部分（第 9 小 题 1 0分,其余每小题6 分，共 7 0 分）1 在右边空白处画出下面的B ST中删除值为2 2 的结点以后的B ST的形状。郛.赭(蹴和郛蔚囹)2 请画出向下面所示的最小堆中插入一个元素值1 4 以后的堆的形状。和652632 数据结构与算法设计试 卷 第1页 共8页3 给出下图所示的树的前序遍历序列。4 下面给出了某二叉树的前序和中序访问序列，请画出该二叉树的形状。前序序列：23 54 56 89 20 76 67 90
2、78 45 31中序序列：56 54 20 89 76 23 90 78 67 45 31 数据结构与算法设计试 卷 第2页 共8页5下图所示是双链表结点的删除过程，在fence结点后面删除一个值为2 3的结点，已 知fence-next是 指 向fence的后继结点，fence-prev是 指 向fence的前驱结点，Itmp是一个值为NULL的链表结点指针，请把这一删除过程用代码表示出来：这一过程的代码:6给出下图从结点C开始的深度优先搜索树，并按搜到的顺序标上序号。密姓名:学号:封（密 封 线 内 不 答 题）.线系另U：年 级 专 业：S澄3同处.007 画出下图以相邻矩阵表示法时的相
3、邻矩阵。8 画出下图的最小支撑树。数据结构与算法设计试 卷 第4页 共8页ABCDEFABCDEF9 下图是一个表示课程之间优先关系的有向图，根据你在数据结构课程中所学的拓扑排序的有关知识，给出该图的拓扑排序序列。(此小题1 0 分)1 0 设将整数1、2、3、4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：(1)若入栈次序为 push(l),pop(),push(2),push(3),pop(),pop(),push(4),pop(),则出栈的数字序列是什么？(2)能否得到出栈序列423和 432?并说明为什么不能得到或如何得到。姓名：学号：系别：年级专业
4、:（密 封 线 内 不 答 题）密.封.线.S澄5同处8疔1 1 假设用于通信的电文是由字符集卜勒必 力口力中的字符构成，这 9个字符在电文中出现的概率分别为0.26,0.10,0.02,0.06,0.16,0.03,0.12,0.07,0.18。请画出对应的Huffman树（按左子树根结点的权小于等于右子树根结点的权的次序构造）。数据结构与算法设计试 卷 第6页 共8页I I.综合应用部分（每 小 题1（）分，共30分）1设有一个链表（u“U 2,，u）,试编写一个函数将这个链表原地逆置，即链表 为（u,.U2,U.）,并要求算法的空间复杂度为0（1）。（带头结点的实现）2设指针p指向单链表的首结点，指 针x指向单链表中的任意一个结点，写出在x前插入一个结点1的算法。（不带头结点的实现）数据结构与算法设计试 卷 第7页 共8页邦.葩(蹴和郛蔚囹)一黑版一即妙一2三和3编写一个函数，以一棵树为输入，返回树的结点数目。数据结构与算法设计试 卷 第8页 共8页