数据结构测验（二）一、单项选择填空题：（2*10）题号12345678910答题CABCDBBACD二、判断是非题（1*10）题号12345678910答题是是非是非是非非非是二、解答下列各题：（8+9+9+8+9+7）1.已知二叉树的先序和中序序列如下，画出该二叉树以及建立中序线索后的示意图。先序序列是：ABDHIECFG中序序列是：HDIBEAFCG(树4+线索4分）2.已知图G如右所示，试写出采用邻接表存储时的类型描述和存储结构示意图(每个顶点的各邻接边的链接顺序为所邻接到的顶点序号由小到大)，以及从顶点1为出发点，按深度和广度优先搜索策略遍历图G时所获得的顶点序列。结构0分，邻接表、深度、广度各3分）#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;DFS：123456BFS：1234653.对上图所示的带权无向图，按普里姆算法求其最小生成树(写出求解的详细过程示意图)。（表6分，画出生成树2分）12345UV-Ukadjvexlowcost02070506{0}{1，2，3，4，5}1adjvexlowcost014051506{0,1}{2，3，4，5}2adjvexlowcost00232406{0，1，2}{3，4，5}3adjvexlowcost0002433{0，1，2，3}{4，5}5adjvexlowcost000520{0，1，2，3，5}{4}4adjvexlowcost00000{0，1，2，3，4，5}{}4．已知某电文中共出现了8种不同的字母，每个字母出现的频率分别为A:8,B:2,C:3,D:2,E:6,F:15,G:9,H:13,现在对这段电文用二进制进行哈夫曼编码（要求画出哈夫曼树）。哈夫曼树6分，编码3分5．对于如下图所示的事件结点网络，求出各活动可能的最早开始时间和允许的最晚完成时间，并问哪些活动是关键活动。两张表6分，结论3分vevl10027133664585121861919717201022221-21-31-42-53-53-64-62-74-75-106-107-10e000766575121917l60313146141781819206．Next3分，过程4分123456next012311123456nextval000310五、算法设计题（先写出相应的存储结构的类型描述）：（2*10)1．假设采用邻接表来存储表示无向网G,试编写相应的深度优先搜索遍历算法。2．查找二叉树中所有值为x的结点的双亲。二叉树采用二叉链表结构。typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;voidPreOrderTraverse(BiTreeT,ElemTypex){if(T){if(T->lchild&&T->lchild->data==x)printf(T->data);if(T->rchild&&T->rchild->data==x)printf(T->data);PreOrderTraverse(T->lchild,x);PreOrderTraverse(T->rchild,x);}}或voidPreOrderTraverse(BiTreeT,ElemTypex,BiTreeparent){if(T){if(T->data==x)if(parent)printf(parent->data);elseprintf("无双亲");PreOrderTraverse(T->lchild,x,T);PreOrderTraverse(T->rchild,x,T);}}可运行的程序：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineYES1#defi