（一）数据结构部分1.已知W=组数，且表示的邻接矩阵如下图所示，如下要求（1）画出有向图（2）画出邻接表解：123456710111000200100103000111040000100500000116110000170000000aij=1代表Vi到Vj有一条有向边有向图：邻接表：1234236345645567612772.3阶B-树如图所示，分别画出插入关键字20后和150后得到的B-树B-树结点树最小不能少于M/2（取整），最大不到大于MM为阶插入20后B-树为3.给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18）写出用下列算法从小到大排序时第一趟结束时的顺序（1）希尔排序（第一趟排序的增量为5）（2）快速排序（轴元素为5）解：※希尔排序(增量为5表示位置间5为一组）（12，2，10，20，6，18，4，16，30，8，28）※快速排序（从后面找大的，从前面找小的）（6，2，10，4，8，12，28，30，20，16，18）4.画出和下列已知序列对应的树T：树的先根次序序访问序列为GFKDAIEBCHJ;后根次序访问序列为DIAEKFCJHBG※先根序列：根→δ树→δ树后根序列：α树→δ树→根判断题1.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点（X）2.在单链表中，要访问某个环节，只要知道该结点的指针即可，因此单链表是一种随机存取结构（X）3.广义表是线性表的推广，是一类线性数据结构（X）4.广义表中原子个数为广义表的长度（X）5.二叉树中用树的前序遍历和中序遍历可以到处树的后序遍历（√）6.哈夫曼树是带权路径长度最短的树，路径上树值较大的结点离根较近（√）7.若连通图上各边权值均不相同，则该图的最小生成树是唯一的（√）8.邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图（X）9.AVL树是一棵二叉树，该树上任一结点的平衡因δ绝对值不大于1（√）10.内排序的快速排序方法，在任何情况下均可得到最快的排序效果（X）三、设有一组关键字{9,01,23,14,55,20,84,27}采用哈希函数：H（key）=keyMOD7,表长为10，用开放地址法的二次探测散列方法1+i=（H(key)+di)MOD10(di=1平方，2平方，3平方...)解决冲突。要求：对该关键字序列结构哈希表，指出有哪些同义词，并计算查找成功的平均查找长度。※ki≠kj但H(ki）=H（kj）则ki和kj为同义词同义词：9和23，14和84，20，55和27查找成功时的平均查找长度为：ASL=(1+1+1+2+3+4+1+2)/8=1.875四、证明题：1.有一非空树，其度为5，已知度为i的节点数为i个，其中1<=i<=5，证明其终端节点个数为41.※证明：若n为节点总数，ni为度i的节点数则n=n0+n1+n2+n3+n4+n5①令B为分支数目，B=n-1②所有的分支是由度为1，2，3，4，5的节点所提供故B=n-1=n1+2n2+3n3+4n4+5n5③由①②③知n0+n1+n2+n3+n4+n5-1=n1+2n2+3n3+4n4+5n5n0=n2+2n3+3n4+4n5+1∵n2=2,n3=3,n4=4,n4=5∴n0=2+6+12+20+1=41假设称正读和反读都相同的字符序列为"回文"例如"abcba"是回文，"abcde"和"ababab"则不是回文，试写一个算法判别读入的一个"@"为结束符的字符序列是否为回文。※intpalindrome_Test(){Initstack(s);InitQueue(Q);while（c=getchar（）！="@"）{push（s，c）;EnQueue(Q，c);}while(!stackEmpty(s)){pop(s,a);DeQueue(Q,b));if(a!=b)returnERROR;}erturnOK;}//palindiome-Test五、试编写一个高效算法，查找未排序文件A(1...n)中得第k个最小的元素注：第k个最小的元素；若M是A（1），A(2)...A(n)中的第k个最小元素，则A(1),A(2),...A(n)中至少有k个元素小于等于M,并且最多有k-1个元素小于M思想：调用一个快速排序以后，有p-1（p：轴元素位置）个元素小于等于轴元素，且n-p个元素大于等于轴元素，若k小于p则第k个最小元素在A(1,...p-1）中；若k=p，则A(p)就是第k个最小元素，若k>p,则A(1,..n）中的第k个最小元素就是A(p+