数据结构期末考试试题.doc

70“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1在一个单链表hl中，若要向表头插入一个由指针p指向的结点，则执行( )。 a hlps p一nexthl b p一nexthl；hlp3 c p一nexthl；phl； d p一nexthl一next;hl一nextp； 2n个顶点的强连通图中至少含有( )。 a.nl条有向边 b.n条有向边 c.n(n1)2条有向边 d.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 a.o(1) b.o(n)c.o(1ogzn) d.o(n2)4由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 a24 b48c 72 d 535当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 a.整形 b.引用型 c.指针型 d.常值引用型6向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 ao(n) bo(1) co(n2) do(10g2n)二、填空题(每空1分，共28分)1数据的存储结构被分为、和四种。 2在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。3中缀表达式 3十x*(2.456)所对应的后缀表达式为。 4在一棵高度为h的3叉树中，最多含有结点。5假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为 6在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。 7当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到位置为止。 8表示图的三种存储结构为、和。 9对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。 10从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和 11假定对长度n144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为 12一棵b树中的所有叶子结点均处在上。 13每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。 14快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。 三、运算题(每小题6分，共24分) 1假定一棵二叉树广义表表示为a(b(c，d)，c(，8)，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2已知一个带权图的顶点集v和边集g分别为： v0，1，2，3，4，5； e=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10， 则求出该图的最小生成树的权。 最小生成树的权； 3假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为。 4有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数：。四、阅读算法，回答问题(每小题8分，共16分) 1voldac(list&l) initlist(l)； insertrear(l;25)； insertfront(l，50)； intal45，8，12，15，36; for(inti0; i5; i+) if (ai20)insertfront(l，ai)； elselnsertrear(l，ai)； 该算法被调用执行后，得到的线性表l为： 2void ag(queue&q) initqueue(q)； inta56，12，5，15，8； for(int i0;i5; i+)qinsert(q，ai)； qinsert(q，qdelete(q)； qinsert(q，20)； qinsert(q，qdelete(q)十16)； while(!queueempty(q)coutqdelete(q)”； 该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1从一维数组an)中二分查找关键字为k的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。 intbinsch(elemtypea，intlow，int high，keytypek) if(lowhigh) int mid(low+high)2； if(kamid.key)； else if (kdatax)return 1; 根结点的层号为1 向子树中查找x结点 else int clnodelevel(bt一left，x)； if(cl1)return cl+1; int c2 ； if； 若树中不存在x结点则返回o else return 0； 六、编写算法(8分) 按所给函数声明编写一个算法，从表头指针为hl的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。 eiemtype maxvalue(lnode*hl);“数据结构”期末考试试题答案 一、单选题(每小题2分，共12分) 评分标准；选对者得2分，否则不得分。 1b 2b 3c 4d 5b 6a 二、填空题(每空1分，共28分) 1顺序结构 链接结构 索引结构 散列结构(次序无先后) 2值(或data) 子表指针(或sublist) 33 x 24 56一*十 4(3h一1)2 5 5 18 6小于 大于(或大于等于) 7向上 堆顶 8邻接矩阵 邻接表 边集数组(次序无先后) 9o(n2) o(e) 10 1 3 1113 o() 12同一层 13插人 选择 14o(nlog2n) o(n2) 三、运算题(每小题6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成树的权：31 6分 3(84，79，56，42，40，46，50，38) 6分 4带权路径长度：131 3分 高度：5 2分 双分支结点数：6 1分四、阅读算法，回答问题(每小题8分，共16分) 评分标准：每小题正确得8分，出现一处错误扣4分，两处及以上错误不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1feturn mid 2分 returnbinsch(a，low，mid一1，k) 2分 returnbmsch(a，mid+1，high，k) 2分 2nodelevel(bt一right，x) 3分 (c2=1)returnc2十1 3分六、编写算法(8分) 评分标准：请参考语句后的注释，或根据情况酌情给分。 elemtype maxvalue(lnodeo* hl。) if (hl=null) 2分 cerrlinked llst is empty!”data； 3分 lnode*p=hi一next； 4分 while(p!：null) 7分 if(maxdata)maxp一data； pp一next； returnmax； 8分 一、 单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。1. 算法必须具备输入、输出和 c a. 计算方法b. 排序方法c解决问题的有限运算步骤d. 程序设计方法2. 有n个节点的顺序表中，算法的时间复杂度是o(1)的操作是 a a. 访问第i个节点（1in）b. 在第i个节点后插入一个新节点（1in）c. 删除第i个节点（1in）d. 将n个节点从小到大排序3单链表的存储密度 c a大于1b. 等于1c小于1d. 不能确定4设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 b a23415b. 54132c23145 d. 154325. 循环队列sq的存储空间是数组dm，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是 d afront=front+1 b. front=(front+1)%(m-1)c. front=(front-1)%m d. front=(front+1)%m6. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 b a. o(1) b. o(n) c. o(n2) d. o(nlogn)7. 设二维数组a0.m-10.n-1按行优先顺序存储，则元素aij的地址为 b a loc(a00)+(i*m+j) bloc(a00)+(i*n+j)c. loc(a00)+(i-1)*n+j-1 d. loc(a00)+(i-1)*m+j-1 8. 一个非空广义表的表头 d a一定是子表b. 一定是原子c不能是子表d. 可以是原子，也可以是子表9具有n个节点的完全二叉树的深度为 a alog2(n+1) -1 b. log2n+1 c. log2n d. log2n10. 若要惟一地确定一棵二叉树，只需知道该二叉树的 d a前序序列b. 中序序列c前序和后序序列d. 中序和后序序列11在一个无向图中，所有顶点的度数之和等于图的边数的倍 c a1/2 b. 1c. 2 d. 412. 拓扑排序运算只能用于 c a带权有向图b. 连通无向图c有向无环图d. 无向图13在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 d a希尔排序b. 冒泡排序c插入排序d. 选择排序14下列排序算法中时间复杂度不受数据初始状态影响，恒为o(n2)的是 c a堆排序b. 冒泡排序c直接选择排序d. 快速排序15二分查找要求节点 a a有序、顺序存储b. 有序、链接存储c无序、顺序存储d. 无序、链接存储二、 填空题（本大题共10小题，每小题2分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16数据的逻辑结构分为两大类，它们是线性结构和非线性结构 。17在单链表中（假设结点指针域名称为next），删除指针p所指结点的后继结点的语句是 p-next=p-next-next 。18已知循环队列用数组datan存储元素值，用front,rear分别作为头尾指针，则当前元素个数为 (rear-front+n)%n 。19 若n为主串长，m 为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为_（n-m+1）m_ _。20 广义表(a),(b),j,(d)的表尾是_(b),j,(d)_ _。21 已知二叉树有61个叶子节点，且仅有一个孩子的节点数为45，则总节点数为_166 _。22 解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个队列 结构。23 n 个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_o(n+e)_。24 对于n个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为_o（n2）_。25在一个长度为n的顺序表中的第i个元素（1in）之前插入一个元素时，需向后移n-i+1 个元素。三、 解答题（本大题共4小题，共25分）26. 对于下面的稀疏矩阵，画出其三元组法存储表示(假设下标从0开始)。（5分）0 0 14 0 0 00 0 0 0 -6 07 0 0 0 0 240 0 0 18 0 00 15 0 0 0 0答案:021414-6207252433184115行号 列号 值012345 27. 已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。（5分）中序序列：digjlkbaechf后序序列：ilkjgdbehfca答案:abcdefhgjkil28设有一个关键码的输入序列55,31,11,37,46,73,63,02,07，（7分）（1） 从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(3分)（2） 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。(4分)29已知一个图的邻接表如下所示。（8分）（1） 画出该图的图形；(4分)（2） 根据邻接表分别画出从顶点a出发进行深度优先和广度优先遍历所生成的生成树。(4分)abcdef12555243答案：四、 算法阅读题（本大题共3小题，每小题5分，共15分）30设线性表的n个结点定义为（a0,a1,an-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最大可容纳项数为maxsize)template int seqlist:insert(type &x, int i) if (ilast+1 | last= (1) ) return 0; else last+; for(int j=last;ji;j-) dataj= (2) ; (3) ; return 1; template int seqlist:remove(type &x) int i=find(x); if(i=0) last-; for (int j= (4) ;jtop!=stacksize-1)s-data+s-top=x;datatype pop(seqstack *s)if(s-top!=-1) return s-datas-top-;void main( ) datatype i; seqstack s; s.top=-1; scanf(“%d”,&i); while(i!=-1) push(&s,i); scanf(“%d”,&i); while(s-top!=-1) i=pop(&s); printf(“%6d”,i);答案:(1)程序的功能是把输入的一串整数(用-1做结束标记) ，按照与输入相反的次序输出。用栈实现这一功能。（2）输出结果 8 7 6 5 4 3 2 1。 32. 已知二叉树的存储结构为二叉链表，阅读下面算法。说明该算法的功能。templateint binarytree:height(bintreenode *t) if(t=null) return 1; int h1=height(t-leftchild); int hr=height(t-rightchild);return 1+(h1hr?h1:hr); 答案：该算法的功能是统计二叉树的高度。五、 算法设计题（本题共10分）33设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法。（1）统计二叉树中度为1的结点个数；（5分）（2）统计二叉树中度为2的结点个数。（5分） （提示：递归算法如32题所示）解答：（1）统计二叉树中度为1的结点个数。templateint binarytree :degree1(bintreenode *t)constif(t=null) return 0;if(t-leftchild!=null &t-rightchild=null | t-leftchild=null &t-rightchild!=null) return 1+degree1(t-leftchild)+degree1(t-rightchild);return degree1(t-leftchild)+degree1(t-rightchild);(2) 统计二叉树中度为2的结点个数。templateint binarytree :degree2(bintreenode *t)constif(t=null) return 0;if(t-leftchild!=null &t-rightchild!=null ) return 1+degree2(t-leftchild)+degree2(t-rightchild);return degree2(t-leftchild)+degree2(t-rightchild);“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1在一个单链表hl中，若要向表头插入一个由指针p指向的结点，则执行( )。 a hlps p一nexthl b p一nexthl；hlp3 c p一nexthl；phl； d p一nexthl一next;hl一nextp； 2n个顶点的强连通图中至少含有( )。 a.nl条有向边 b.n条有向边 c.n(n1)2条有向边 d.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 a.o(1) b.o(n)c.o(1ogzn) d.o(n2)4由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 a24 b48c 72 d 535当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 a.整形 b.引用型 c.指针型 d.常值引用型6向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 ao(n) bo(1) co(n2) do(10g2n)二、填空题(每空1分，共28分)1数据的存储结构被分为、和四种。 2在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。3中缀表达式 3十x*(2.456)所对应的后缀表达式为。 4在一棵高度为h的3叉树中，最多含有结点。5假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为 6在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。 7当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到位置为止。 8表示图的三种存储结构为、和。 9对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。 10从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和 11假定对长度n144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为 12一棵b树中的所有叶子结点均处在上。 13每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。 14快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。 三、运算题(每小题6分，共24分) 1假定一棵二叉树广义表表示为a(b(c，d)，c(，8)，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2已知一个带权图的顶点集v和边集g分别为： v0，1，2，3，4，5； e=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10， 则求出该图的最小生成树的权。 最小生成树的权； 3假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为。 4有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数：。四、阅读算法，回答问题(每小题8分，共16分) 1voldac(list&l) initlist(l)； insertrear(l;25)； insertfront(l，50)； intal45，8，12，15，36; for(inti0; i5; i+) if (ai20)insertfront(l，ai)； elselnsertrear(l，ai)； 该算法被调用执行后，得到的线性表l为： 2void ag(queue&q) initqueue(q)； inta56，12，5，15，8； for(int i0;i5; i+)qinsert(q，ai)； qinsert(q，qdelete(q)； qinsert(q，20)； qinsert(q，qdelete(q)十16)； while(!queueempty(q)coutqdelete(q)”； 该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1从一维数组an)中二分查找关键字为k的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。 intbinsch(elemtypea，intlow，int high，keytypek) if(lowhigh) int mid(low+high)2； if(kamid.key)； else if (kdatax)return 1; 根结点的层号为1 向子树中查找x结点 else int clnodelevel(bt一left，x)； if(cl1)return cl+1; int c2 ； if； 若树中不存在x结点则返回o else return 0； 六、编写算法(8分) 按所给函数声明编写一个算法，从表头指针为hl的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。 eiemtype maxvalue(lnode*hl);“数据结构”期末考试试题答案 一、单选题(每小题2分，共12分) 评分标准；选对者得2分，否则不得分。 1b 2b 3c 4d 5b 6a 二、填空题(每空1分，共28分) 1顺序结构 链接结构 索引结构 散列结构(次序无先后) 2值(或data) 子表指针(或sublist) 33 x 24 56一*十 4(3h一1)2 5 5 18 6小于 大于(或大于等于) 7向上 堆顶 8邻接矩阵 邻接表 边集数组(次序无先后) 9o(n2) o(e) 10 1 3 1113 o() 12同一层 13插人 选择 14o(nlog2n) o(n2) 三、运算题(每小题6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成树的权：31 6分 3(84，79，56，42，40，46，50，38) 6分 4带权路径长度：131 3分 高度：5 2分 双分支结点数：6 1分四、阅读算法，回答问题(每小题8分，共16分) 评分标准：每小题正确得8分，出现一处错误扣4分，两处及以上错误不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1feturn mid 2分 returnbinsch(a，low，mid一1，k) 2分 returnbmsch(a，mid+1，high，k) 2分 2nodelevel(bt一right，x) 3分 (c2=1)returnc2十1 3分六、编写算法(8分) 评分标准：请参考语句后的注释，或根据情况酌情给分。 elemtype maxvalue(lnodeo* hl。) if (hl=null) 2分 cerrlinked llst is empty!”data； 3分 lnode*p=hi一next； 4分 while(p!：null) 7分 if(maxdata)maxp一data； pp一next； returnmax； 8分 数据结构与算法复习题四、应用简答题。1有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1）a d，r，其中：da，b，c，d，e，f，g，h，r r，r ，（2）b d，r，其中：da，b，c，d，e，f，g，h，r r，r ，（3）c d，r，其中：d1，2，3，4，5，6，r r，r （1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）2简述顺序表和链表存储方式的特点。答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点（增减结点操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问。另外，每个结点上增加指针域，造出额外存储空间增大。3对链表设置头结点的作用是什么？（至少说出两条好处）答：其好处有：（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。4对于一个栈，给出输入项a，b，c。如果输入项序列由a，b，c组成，试给出全部可能的输出序列。5设有4个元素1、2、3、4依次进栈，而栈的操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序。6现有稀疏矩阵a如图所示，要求画出三元组表示法和十字链表表示法：7设4维数组的4个下标的范围分别为-1，0，1，2，1，3，-2，-1，请分别按行序和列序列出各元素。8有一份电文中共使用5个字符：a，b，c，d，e，它们出现的频率依次为4，7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。9有如图所示的二叉树，回答如下问题。（1） 写出该树的中序遍历序列;（2） 写出该树的先序遍历序列;（3） 写出该树的后序遍历序列；（4） 画出该二叉树的中序线索二叉树；（5） 画出该二叉树的后序线索二叉树；（6） 画出该二叉树对应的森林； 10已知一棵树边的集合为, ,，画出这棵树。11假设二叉树采用顺序存储结构，如图所示。（1） 画出二叉树表示；（2） 写出先序遍历、中序遍历和后序遍历的结果；（3） 写出结点值c的双亲结点，其左、右孩子；（4） 画出把此二叉树还原成森林的图。1234567891011121314151617181920eafdgcjhib12已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。13某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其后序遍历序列。14将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。 15有一份电文中共使用8个字符：a、b、c、d、e、f、o、i，它们的出现频率依次为10，20，15，32，40，60，26，18。试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。16已知某系统在通信联络中只可能出现a,b,c,d,e,f,g,h八种字符，其频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计哈夫曼编码。17对有五个顶点v1,v2,v3,v4,v5的图的邻接矩阵如图所示，解答下列问题：（1）画出逻辑图。（2）画出该逻辑结构的邻接表。（3）基于邻接矩阵写出图的深度、广度优先遍历序列。18如图所示，解答如下问题：（1）写出从定点a出发，深度和广度优先遍历方法遍历该图的顶点序列。（2）根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构造过程。19给出如图所示的无向图g的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。20使用普里姆算法构造出如图所示的图g的一棵最小生成树。21使用克鲁斯卡尔算法构造出如图所示的图g的一棵最小生成树。22设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。 中序：1 4 3 5 6 2 后序：4 6 5 3 2 123设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。24设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。25设有如图所示的一棵树，请将其转化为二叉树。26下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题：（1）画出相应的aoe图；（2）给出各事件的最早发生时间和最晚发生时间；（3）找出关键路径，并指明完成该工程所需最短时间；（4）若把aoe网视为aov网，给出其一个拓扑序列的例子。工序代号abcdefghijklmm时间151050815409015806015302040先驱工作a,bbc,dbeg,ieif,ih