malloc(p): p->data=x; p->next=NULL: 四、应用题(共26分) 1.有向图G的邻接表如下图所示,若删去图G中的边<V3,V6>和<V4,V5>,试 画出修改后图的邻接表。(4分) 顶点入度 V5 2.有向图如下图所示,写出以V1为出发点对图进行深度优先搜索所得到的所有可能 的访问序列。(4分) 3.对于键值序列(49,38,65,97,76,13,27,50),使用堆排序算法完成排序过程。要 求 (1)画出初始堆(用二叉树表示) (2)画出分别输出13,27后重建的两个堆。(5分) 4.一个深度为d(根的层次号为1)的满K叉树有如下性质:第d层上的结点都是叶 子结点,其余各层上的每个结点都有K棵非空子树。如果从根这一层开始从左到右顺序逐 层对全部结点编号,且根结点的编号为1,问编号为n的结点有右兄弟的条件是什么?其 右兄弟的编号是多少?(3分) 5.给定权值{5,10,12,15,30,40},构造相应的哈夫曼树,要求写构造步骤。(4分) 6.已知一表为(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),按表中顺 序依次插入初始为空的二叉排序树,要求 (1)画出建立的二叉排序树。(4分) (2)求出在等概率情况下查找成功的平均查找长度。(2分) 五、设计题(共14分) 设有一单链表L,结点结构为[ ata next结点个数至少3个,试画出链表L的结 构图,并编写算法判断该单链表L中的元素是否成等差关系,即:设各元素值次为 a,a2,as,,an,判断a1-a:=a:-a1是否成立,其中i满足2<=i<=n-1.(8分) 2.设有一棵二叉树以二又链表作为存储结构,结点结构为[ childldatalrchild其中 data域中存放一个字符,设计一个算法按前根遍历顺序仅打印出data域为数字的字符(即 0<=data<=9′)(6分) 33 malloc(p)；p->data=x; p->next=NULL； ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、应用题（共 26 分） 1．有向图 G 的邻接表如下图所示，若删去图 G 中的边＜V3，V6＞和＜V4，V5＞，试 画出修改后图的邻接表。（4 分） 顶点 入度 2．有向图如下图所示，写出以 V1 为出发点对图进行深度优先搜索所得到的所有可能 的访问序列。（4 分） 3．对于键值序列（49,38,65,97,76,13,27,50），使用堆排序算法完成排序过程。要 求： ⑴画出初始堆（用二叉树表示）。 ⑵画出分别输出 13,27 后重建的两个堆。（5 分） 4.一个深度为 d（根的层次号为 1）的满 K 叉树有如下性质：第 d 层上的结点都是叶 子结点，其余各层上的每个结点都有 K 棵非空子树。如果从根这一层开始从左到右顺序逐 层对全部结点编号，且根结点的编号为 1，问编号为 n 的结点有右兄弟的条件是什么？其 右兄弟的编号是多少？（3 分） 5．给定权值｛5,10,12,15,30,40｝，构造相应的哈夫曼树，要求写构造歩骤。（4 分） 6．已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺 序依次插入初始为空的二叉排序树，要求： ⑴画出建立的二叉排序树。（4 分） ⑵求出在等概率情况下查找成功的平均查找长度。（2 分） 五、设计题（共 14 分） 1．设有一单链表 L，结点结构为 data|next，结点个数至少 3 个，试画出链表 L 的结 构图，并编写算法判断该单链表 L 中的元素是否成等差关系，即：设各元素值次为 a1,a2,a3,…,an，判断 ai+1-ai=ai-ai-1 是否成立，其中 i 满足 2<=i<=n-1.(8 分) 2．设有一棵二叉树以二叉链表作为存储结构，结点结构为 lchild|data|rchild,其中 data 域中存放一个字符，设计一个算法按前根遍历顺序仅打印出 data 域为数字的字符（即 ‘0’<=data<=‘9’）（6 分） V1 0 V2 1 V3 4 V4 0 V5 1 V6 1 ∧ 2 3 ∧ 6 3 3 1 ∧ 5 ∧ 1 3 2 5 4 6