数据结构应用题答案

1、数据结构应用题答案第2章线性表1.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点 B,要求给出在结点 A的后面插入结点 B的操作序列设双向链表中结点的两个指针域分别为llink 和rlink .答：操作序列如下：q->rlink = p->rlink ; p->rlink = q ;q->rlink->llink = q ; q->llink = p ;注意答案不唯一第3章栈和队列1 .设有编号为1, 2, 3, 4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列 车开出车站的所有可能的顺序.答：共计 14 种,分别是：1234, 124

2、3 , 1324 , 1342 , 1432 , 2134 , 2143 , 2341 , 2314 ,243132143241342143212 .如果输入序列为1, 2, 3, 4, 5, 6,试问能否通过栈结构得到以下两个序列：4, 3, 5,6, 1, 2和1, 3, 5, 4, 2, 6;请说明为什么不能或如何才能得到.答：1不能得到4, 3, 5, 6, 1, 2 ;由于1, 2, 3, 4入栈后；4, 3出栈；得到序列 4, 3;栈中还有1, 2； 5入栈后即出栈,得到序列 4, 3, 5； 6入栈后即出栈,得到序列 4, 3, 5, 6；此时,栈中还有1, 2；必须2先出栈,然

3、后1再出栈,1不可能在2之前出栈.故而 得不到该序列.2能得到输出顺序为 1, 3, 5, 4, 2, 6的序列.得到的操作如下：1入栈后即出栈,得 到序列1; 2, 3入栈后3即出栈,得到序列1 , 3; 4, 5入栈后,5出栈,4出栈,得到序列 1 , 3,5,4; 2出栈,得到序列1,3,5,4,2; 6入栈后即出栈,得到序列1,3,5, 4,2,6.3.假设正读和反读都相同的字符序列为“回文",例如,abba'和'abcba'是回文,'abcde'和ababab'那么不是回文.假设一字符序列已存入计算机,请用堆栈判断其是否为回文

4、,简述算法.答：方法一：使用数据结构：循环队列和顺序栈.算法思路为：1 .将字符串根据用户输入的顺序分别入栈和队列2 .分别从队列和栈中取出首个字符3 .比拟取出的字符,假设相等,继续分别从队列和栈中取首个字符；否那么跳出循环,并设置标志 flag=0;4 .假设队列和栈中的字符都取完,那么结束,设置标志flag=1;5 .flag=1,表示字符从前往后和从后往前的序列完全匹配,该字符串属于回文6 .flag=0,表示字符从前往后和从后往前的序列不完全匹配,该字符串不属于回文方法二：使用栈.将字符串的前一半入栈,再依次出栈,与后一半进行比拟,假设有不等那么不是回文；假设依次相等,那么是回文.注

5、意：此题要求简答算法思路,并不要求写出具体算法.7 .试写出循环队列判空和判满的条件队列最大容量为M.答：假设循环队列最大存储容量为M判空：Q.front=Q.rear1判满：Q.rear+1 %M=Q.front2评分标准：给出1和2式分别得3分,其他酌情扣分.8 .假设Q0.10是一个循环队列,初始状态为front=rear=0 ,画出做完以下操作后队列的头尾指针的状态变化情况,假设不能入队,请指出其元素,并说明理由.d,e,b,g,h 入队；d,e 出队；i,j,k,l,m入队；n,o,p 入队答：图自己根据解答画出d,e,b,g,h 入队；状态1: front=0 , rear=5 ;

6、d,e 出队；状态 2： front=2 , rear=5 ;i,j,k,l,m 入队；状态 3: front=2 , rear=10 ;n,o,p入队；状态4： front=2 , rear=1 ; p不能入队,由于队列已经满了.评分标准：状态1、状态4各2分,状态2、状态3各1分,状态4中状态1分,理由1分.9 .假设元素的进栈序列为： A、B、C、D、E,运用栈操作,能否得到出栈序列B、C、A、E、D和D、B、A、C、E?为什么？答：能得到出栈序列B、C、A、E、D,不能得到出栈序列D、B、A、C、E.其理由为：假设出栈序列以D开头,说明在D之前的入栈元素是 A、B和C,三个元素中C是栈

7、顶元素, B和A不可能早于C出栈,故不可能得到 D、B、A、C、E出栈序列.10 设输入序列为 a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出 序列.答：借助栈结构,n个入栈元素可得到1/(n+1)(2n )! / (n!*n!)种出栈序列.此题4个元素, 可有14种出栈序列,abcd和dcba就是其中两种.但 dabc和adbc是不可能得到的两种.11 将两个栈存入数组 V1.m应如何安排最好？这时栈空、栈满的条件是什么？答：设栈S1和栈S2共享向量V1.m,初始时,栈S1的栈顶指针top0=0 ,栈S2的栈顶 指针 top1=m+1,当 top0=0 为左栈空,t

8、op1=m+1 为右栈空；当 top0=0 并且 top1=m+1 时为全栈空.当top1-top0=1 时为栈满.12 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2 和1 35 4 2 6 ;请说明为什么不能或如何才能得到.答：输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是 12,前面4 个元素(4356)得到后,栈中元素剩 12,且2在栈顶,不可能栈底元素 1在栈顶元素2之 前出栈.得到135426的过程如下：1入栈并出栈,得到局部输出序列 1;然后2和3入栈,3出 栈,局部输出序列变为：13;接着4和5入栈

9、,5, 4和2依次出栈,局部输出序列变为13542; 最后6入栈并退栈,彳#最终结果 135426.10 .假设以数组sq0.7存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素,如用A和D分别表示入队和出队操作,请给出:(1)队空的初始条件;(2)执行操作序列 A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明.(A3表示三次入队操 作,D1表示一次出队操作)答：(1)队空的初始条件： (2)执行操作A3后,f=0 ,执行操作D1后,f=1 , 执行操作A5后,f=1 , 执行操作D2后,f=3 , 执行操作A1后,f=3 , 执行操作D2后,f=5 ,f=r=

10、0 ;r=3; /A3表示三次入队操作 r=3; /D1表示一次出队操作 r=0 ;r=0 ;r=1 ;r=1 ;执行操作A4后,按溢出处理.由于执行 A3后,r=4,这时队满,假设再执行 A操作,那么出错.11 .内存中一片连续空间(不妨假设地址从1到m)提供应两个栈 si和S2使用,怎样分配这局部存储空间,使得对任一个栈,仅当这局部空间全满时才发生上溢1答：S1和S2共享内存中一片连续空间(地址 1到城,可以将S1和S2的栈底设在两端, 两栈顶向共享空间的中央延伸,仅当两栈顶指针相邻(两栈顶指针值之差的绝对值等于1)时,判断为栈满,当一个栈顶指针为0,另一个栈顶指针 m+1时为两栈均空.1

11、2,设一数列的输入顺序为123456,假设采用堆栈结构,并以A和D分别表示入栈和出栈操作,试问通过入出栈操作的合法序列.(1)能否得到输出顺序为325641的序列.(2)能否得到输出顺序为154623的序列.答：(1)能得到325641.在123依次进栈后,3和2出栈,得局部输出序列 32;然后4, 5入栈,5出栈,得局部出栈序列325; 6入栈并出栈,得局部输出序列3256;最后退栈,直到栈空.得输出序列 325641.其操作序列为 AAADDAADADDD(2)不能得到输出顺序为 154623的序列.局部合法操作序列为ADAAAADDAD导到局部输出序列1546后,栈中元素为 23, 3在

12、栈顶,故不可能 2先出栈,得不到输出序列 154623.13,设输入序列为2, 3, 4, 5, 6,利用一个栈能得到序列2, 5, 3, 4, 6吗？为什么？栈可以用单链表实现吗？答：不能得到序列 2, 5, 3, 4, 6；其理由是,输出序列第三四位两元素是3, 4,前面2个元素(2, 5)得到后,栈中元素剩 3, 4,且4在栈顶,栈底元素 3不可能在栈顶元素 4 之前出栈.栈可以用单链表实现,这就是链栈.由于栈只在栈顶操作,所以链栈通常不设头结点.14,有5个元素,其入栈次序为：A, B, C, D, E,在各种可能的出栈次序中,以元素 C, D最先出栈(即C第一个且D第二个出栈)的次序

13、有哪几个？用S表示入栈,X表示出栈,写出可能得到次序的操作序列.答：三个：CDEBA CDBEA CDBAECDEB斓作序歹 U: SSSXSXSXXXCDBE斓作序歹 U: SSSXSXXSXXCDBA映作序歹 U: SSSXSXXXSX15.假设以1、2、3、4作为双端队列的输入序列,试分别求出以下条件的输出序列：(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列；(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列；(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列.答：(1) 4132(2) 4213(3) 42

14、3116,设一个双端队列,元素进入该队列的次序为a, b, c, do求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列.答：既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是 dbca.第6章树和二叉树1. (8 分)一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D)画出这棵树,并答复以下问题：(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？(2)树的度是多少？各个结点的度是多少？(3)树的深度是多少？各个结点

15、的层数是多少？以结点G为根的子树的深度是多少？X72,用一维数组存放的一棵完全二叉树如下表所示ABCDEFGHIJKL写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序.答案 HIDJKEBLFGCAX23. (5分)对任何一棵二叉树 T,如果其终端结点数为 n.,度为2的结点数为止,证实: nc=n2+1oX34.表达并证实二叉树的性质3.X35. (8分)一棵二叉树如下,(1)请分别写出按前序、中序、后序和层次遍历时得到的结点序列.(2)如果此二叉树由森林转换得到,请画出原森林中的各棵树.IX1X56. 8分画出由以下序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIK

16、J 中序：ABCDEFGHIJKX87.有二叉树中序序列为： ABCEFGHD后序序列为：ABFHGEDC请画出此二叉树,并写出二 叉树的先序遍历序列和层次遍历序列.答案根据后序序列知根结点为 C,因此左子树：中序序列为 AB后序序列为AB右子树：中 序序列为EFGHD,后序序列为：FHGED次推得该二叉树结构如以下图所示先序遍历序列:层次遍历序列:CBADEGFHCBDAEGFHX5 8. 8分二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG口 CBEDAFG试画出该二叉树,并写出二叉树的后序遍历序列和层次遍历序列.X99. 6分二叉树的先序序列为EBADCFHGI代J二叉树的中序序

17、列为 ABCDEFGHIJK请画出该二叉树,并写出二叉树的后序遍历序列和层次遍历序列.X1010. 8分设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：A B D F C E G H 中序遍历序列： B F D A G E H C请画出该二叉树,并将这棵二叉树转换成对应的树或森林X411. 8分设一棵二叉树的前序序列为 叉树.并写出后序和层次遍历序列.12. 6分设给定一个权值集合W=3 ,哈夫曼树并计算哈夫曼树的带权路径长度 X613. 8 分假设字符 a,b,c,d,e,f,g,hABDGECFH中序序歹U为：DGBEAFHC试画出该二5, 7, 9, 11,要求根据给定的权值集合构造

18、一棵WPL.的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23Huffman 哈夫曼编码.X514. 8 分假设字符 a,b,c,d,e,f a,b,c,d,e,f 的 Huffman 哈夫曼 X715. 8 分假设字符 a,b,c,d,e,f 构造哈夫曼树并写出 a,b,c,d,e,f,0.13, 0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h 的的使用频度分 0.07,0.09,0.12,0.22,0.23,0.27 编码.的使用频度分另 I是0.07,0.10,0.12,0.16,0.25,0.30的哈夫曼编码.16. 6分试分别画出具有三个结点的树和三

19、个结点的二叉树的不同形态.X617.请画出以下图所示的树所对应的二叉树.0s答案：18. (6分)请画出与以下二叉树对应的森林.X10X819.一棵树边的集合为<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>, <C,F>,<H,L>,<C,H>,<A,C>,请答复以下问题：x10 (1)哪个是根结点？ ( 2) X8哪些是叶子结点？ X10哪些是分支结点？ X8 (3)哪个是结 点

20、G的双亲结点？ ( 4)哪些是结点 G的祖先？ X8 (5)哪些是结点 G的孩子？ X8 (6)哪些是结点E的子孙？ X8 (7)哪些是结点E的兄弟？哪些是结点F的兄弟？(8)结点B和N的层次号分别是多少？ ( 9)树的深度是多少？ (10)以结点C为根的子树的深度是多少？答案(1) A;(2) D, M, N, F, J, K, L ; (3) C ; (4) A, C ; (5) J,K ; (6) I, M, N ;E 的兄弟是 D, F的兄弟是 G和H; (8) 2, 5 ; (9) 5 ; (10) 3 .X920.假设在树中,结点 x是结点y的双亲时,用(x, y)来表示树边.一棵

21、树边的集 合为： (i,m),(i,n),(e,i), (b, e), (b, d), (a, b), (g, j), (g,k), (c, g),(c, f), (h,l),(c,h),(a,c) .用树形表示法画出此树,并答复以下问题：(1)哪个是根结点：(2)哪些是叶结点？ ( 3)哪个是g的双亲？ (4)哪些是g的祖先？ ( 5)哪些是g的孩子？ ( 6)哪些是e的子孙？ (7)哪些是e的兄弟？哪些是f的兄弟？ ( 8)结点b和n的层次各是多少？ (9)树的深度是多少？ ( 10)以结点c为根的子树的深度是多少？ (11)树的度数是多少？ 青案： (1)根结点：a(2)叶结点： rn

22、n、d、l、h、j、k (3) g的双亲：c(4) g的祖先：a、c(5)g的孩子：j、k(6)e的子孙：i、mrn(7) e的兄弟：d (8) b的层次：2(9)树的深度：5 f的兄弟：g、hn的层次；5(10)以结点c为根的子树的深度：21.一棵树边的结点为(I,M ),K), (A, G), (A , F),(H , J), (A ,(1)哪个是根结点？(2)哪些是叶子结点？(3)树的深度是多少？答案如以下图所示.(图不对,缺结点3(11)树的度数：3(I , N),(E , I),(B , E) , (B , D),(C , B),(G , L) , (G , H), (C , A),

23、试画出这棵树,并答复以下问题：H的孩子结点J,)根结点C,叶子结点F、K、L、J、D M N,深度5五、应用题(每题 6分,共48分)3.答：快速排序的思想：通过一趟排序将待排序记录分割成独立的两局部,其中一局部记录的关键字均比另一局部记录的关键字小, 那么可分别对这两局部记录继续进行排序, 以到达整 个序列有序.评分标准：只要根本思想对就可得分.3、(8分)二叉树为：后序遍历序列：CEDBGFA ,层次遍历序列： ABFCDGE评分标准：得出二叉树得4分,给出后序和层次遍历序列得4分,步骤不全酌情给分.4、(8分)哈夫曼树：哈夫曼编码:a： 011e： 0001b：f：1011评分标准：得出

24、哈夫曼树给5、10 分1邻接表存储结构c： 00000g： 0014分,给出哈夫曼编码给d： 0010h： 01014分,步骤不全酌情给分.2深度优先遍历序列：BADCEF广度优先遍历序列：BACEDF评分标准：画出邻接表存储结构得 他情况全酌情给分.6、8分二叉判定树5分,求出深度优先和广度优先遍历序列得平均查找长度:ASL= (1+2*2+4*3+3*4 ) /10=2.9评分标准：得出二叉判定树给 6分,求出平均查找长度给 2分,步骤不全酌情给分.以达2、6分快速排序的思想：通过一趟排序将待排序记录分割成独立的两局部,其中一局部 记录的关键字均比另一局部记录的关键字小, 那么可分别对这两

25、局部记录继续进行排序, 到整个序列有序.评分标准：只要根本思想对就可得分.3、8分二叉树为：后序遍历序列：CEDBGFA ,层次遍历序列:ABFCDGE评分标准：得出二叉树得4分, 4、4分,步骤不全酌情给分.给出后序和层次遍历序列得哈夫曼编码:a： 011e： 0001b:f:1011评分标准：得出哈夫曼树给5、10 分1邻接表存储结构c： 00000g： 0014分,给出哈夫曼编码给d： 0010h： 01014分,步骤不全酌情给分.2深度优先遍历序列：BADCEF广度优先遍历序列：BACEDF评分标准：画出邻接表存储结构得 5分,求出深度优先和广度优先遍历序列得5分,其他情况全酌情给分.

26、6、8分二叉判定树38127252045901003260平均查找长度:ASL= (1+2*2+4*3+3*4 ) /10=2.9评分标准：得出二叉判定树给 6分,求出平均查找长度给 2分,步骤不全酌情给分. 四、算法题22分1、6 分评分标准：每写错一种形态扣 1分.2、8 分(1)前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH(2)二叉树所对应的森林：评分标准：第一小题每个1分,第二小题三棵树 4分,每错一个扣1分.评分标准：没有过程或过程不全酌情减分4、(8 分)评分标准：结果正确得5分,步骤不全酌情扣分.5、(10 分)(1) (4分)哈

27、希表:012345678910111213141516173217634924401030314647(2) (4分)假设查找关键字 63,需要与关键字 31、16、47、32、17进行比拟.(3) (2分)平均查找长度：ASLc= (6*1+2+3*3+6 ) /11=23/116、(8 分)(36) 25 48 12 65 20(25 36 ) 48 12 65 20(25 36 48 ) 12 65 20(12 25 36 48) 65 20(12 25 36 48 65) 20(12 20 25 36 48 65)评分标准：每一趟插入得1分,步骤不全酌情扣分.三、应用题(43分)1、(

28、6分)对任何一棵二叉树,如果其终端结点数为n.,度为2的结点数为n2,那么怵=m+1.证实：设二叉树白结点总数为n,度为1的结点个数为nb那么有：n=n0+m+n2(1)又在二叉树中除了根结点每个结点都有一个分支指向它,这些分支是有度为1和度为2的结点发出的,由此得到：n-1=n1+2*n 2(2)由式(1)和(2)得n0=n2+1,证毕.评分标准：表达定理得2分,证实得4分,其他酌情扣分.2、(8分)哈夫曼树为：评分标准：得出哈夫曼树给4分,给出哈夫曼编码给4分,步骤不全酌情给分.由此可得哈夫曼编码分别为：a：000b： 001c： 100d：101e： 01f: 113、(8分)二叉排序树

29、的构造过程如下:45121232322012 75 1232320 208 32 50 8 3220 2025 125平均查找长度：ASL= (1+2*2+4*3+2*4+5 )5 75 12 75,283220节 25石 4575 12 755090832509020645分/10=33分评分标准：得出二叉判定树给 54、7分拓扑序列构造过程B输出 A, D E E/、亭1c输出C D-E拓扑有序序列后两种： ABCDEF评分标准：只有结果没有过程给5、8分邻接矩阵为,010001<0分,求出平均查找长度给 3分,步骤不全酌情给分. F 输出 BD< E： F_Z9F输出D i；

30、E-F和 ACBDEF5分,过程不全或过程/、止确酌情扣分.100010、0 10 0 1010 11110 10 10 00 110 0 01 1 0 0 0 00 10 10 0最小生成树为:3分,过程评分标准：写出邻接矩阵给3分,最小生成树给5分,只有结果没有过程给 不全或过程不正确酌情扣分.6、6分快速排序的思想：通过一趟排序将待排序记录分割成独立的两局部,其中一局部记录的关键字均比另一局部记录的关键字小,那么可分别对这两局部记录继续进行排序,以达到整个序列有序.一趟快速排序的结果：40, 38, 27, 20, 13, 49, 76, 80, 65评分标准：写出快速排序思想给 3分,

31、给出一趟排序结果给 3分.四、算法题22分三、应用题43分1、6 分3分C评分标准:2、8 分3分.平均查找长度:构造出二叉树得3分,二叉树的生成森林得ASL=(5 分分评分标准:得出二叉判定树给步骤不全酌情给分.3、7分邻接矩阵:金1O08002001Q05Q0Q0Q0Q0O05od3867O0Q03Q08Q0Q0od00od88832Q06Q0Q0Q0Q0007Q03Q0Q0求出平均查找长度给 2分,3分或 abchedf或 afbcdheabcfhed afbchde或 abcfdeh 或或 abfchde 或深度优先序列:广度优先序列:abcdehfabfcdhe不唯一不唯一评分标准:

32、写出图的邻接矩阵的2分,深度优先序列得2分,广度优先序列得 2分,其他酌情给分.4、8分最短路径:终 点12345B6 (A,B)4(A,C,B)C2 (A,C)Doo5 (A,C,D)5 (A,C,D)Eoo6 (A,C,E)6 (A,C,E)6 (A,C,E)Foooooo8 (A,C,D,F)8 (A,C,D,F)SAA,CA,C,BA,C,B,DA,B,C,D,E评分标准：最短路径给5分,过程给3分,结果正确没有过程或过程不对酌情减分.5、8分哈希表:01234567891011121401682755192084231110平均查找长度：ASbc= 6*1+2+3*3+4 /11=2

33、1/11评分标准：写出哈希表得5分,查找长度3分6、5 分1是大顶堆2不是堆,调整以后为 100, 98, 66, 85, 80, 60, 40, 77, 82, 10, 203是小顶堆评分标准：判断正确得3分,调整得3分四、算法题22分1、5分假设循环队列最大存储容量为 M判空：Q.front=Q.rear1判满：Q.rear+1 %M=Q.front2评分标准：给出1和2式分别得2分,前提假设得1分,其他酌情扣分.2、5分对任何一棵二叉树,如果其终端结点数为n.,度为2的结点数为n2,那么怵=m+1.证实：设二叉树白结点总数为n,度为1的结点个数为 m,那么有：n=n0+m+n21又在二叉

34、树中除了根结点每个结点都有一个分支指向它,这些分支是有度为1和度为2的结点发出的,由此得到：n-1=n1+2*n 22由式1和2得n0=n2+1,证毕.评分标准：给出1和2式分别得2分,得出结论得1分,其他酌情扣分.3、7分哈夫曼树为：由此可得哈夫曼编码分别为：a： 000 b ： 001 c ： 100d： 101 e ： 01 f: 11评分标准：得出哈夫曼树给4分,给出哈夫曼编码给 3分,步骤不全酌情给分.4、8分二叉排序树：JanFebMarAprJunMaySepAugJulOctDecNovASL= (1+2*2+3*3+4*3+5*2+6 ) /12=3.5平均合找长度:评分标准

35、：构造出二叉排序树得 5分,平均查找长度得 3分,步骤不全酌情扣分.5、7 分由C开始的深度优先生成序列：CDEABF评分标准：画出原图得4分,求出深度优先生成序列得3分,其他情况酌情给分.6、8分最短路径求解过程：终点12345B6 (A,B)4(A,C,B)C2 (A,C)Doo5 (A,C,D)5 (A,C,D)Eoo6 (A,C,E)6 (A,C,E)6 (A,C,E)Foooooo8 (A,C,D,F)8 (A,C,D,F)SAA,CA,C,BA,C,B,DA,B,C,D,E评分标准：结果正确没有过程得 5分,步骤不全或不正确酌情扣分.五、算法题共20分1、5 分评分标准：每写对一种

36、形态得 1分.以达2、5分快速排序的思想：通过一趟排序将待排序记录分割成独立的两局部,其中一局部 记录的关键字均比另一局部记录的关键字小, 那么可分别对这两局部记录继续进行排序, 到整个序列有序.评分标准：只要根本思想对就可得分.3、7 分(1)前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH2二叉树所对应的森林:评分标准：第一小题每个1分,第二小题三棵树,每个 1分.4、8分关键路径为:求解过程:vevlell-eA00a1011B56r a2000C22a3055D611a4561E99P a5220F1015a66115G1516a7990H

37、1414a89101I2323a910155a1014140a1115161评分标准：结果正确没有过程给 5分,过程不全或过程不正确酌情扣分.5、8分最小生成树为：6、哈希表:01234567891011121401682755192084231110平均查找长度：ASLsc= 6*1+2+3*3+4 /11=21/11评分标准：写出哈希表得5分,查找长度2分,其他情况酌情给分.五、算法题20分四、应用题40分4分评分标准：构造出二叉树得4分,二叉树的生成森林得 4分.2、8分二叉排序树的构造过程如下：评分标准：没有过程或过程不全酌情减分 3、8分邻接矩阵：1odQ0Q02od、1OO500Q

38、0Q000od5od3Q06700003008Q0004分O0oOO08OOOO32Q06Q0Q0Q0Q0产oO7OO3OO深度优先序列:广度优先序列:abcdehf 或 abchedf 或 abcfdeh 或 abcfhed 不唯一abfcdhe 或 afbcdhe 或 abfchde 或 afbchde 不唯一 4 分评分标准：写出图的邻接矩阵的 4分,深度优先序列得 2分,其他酌情给分.4、8 分3.程不对酌情减分.4分,过程给4分,结果正确没有过程或过5、8分哈希表:012345678911112322034510011240平均查找长度:ASLsc= 7*1+2+3+3 /10=1.

39、5评分标准：写出哈希表得5分,查找长度3分1fde1c1baEFC评分标准：每写错一种形态扣 1分.011、算法题20分 应用题40分 5分0 C为 n2,那么 n0=n2+1.评分标准：表达不恰当酌情扣分.00100由此可得哈夫曼编码分别为:a： 0000 b : 0001 c : 001d： 01 e ： 10 f ： 114、8分拓扑序列构造过程n0,度为2的结点数3、8分哈夫曼树为:评分标准：得出哈夫曼树给 酌情给分.4分,给出哈夫曼编码给 4分,步骤不全2、5分对任何一棵二叉树,如果其终端结点数为输出A输出BDE 声小一ZC输出CD：E,输出DE 拓扑有序序列后两种：ABCDEF评分标准：只有结果没有过程给 分.5、8分最小生成树为：A： 5J 4 E评分标准：只有结果没有过程给 分.X1- ,FFF和 ACBDEF5分,过程不全或过程/、止确酌情扣5C A1 B 5C3 D父一5分,过程不全或过程/、止确酌情扣6、8 分1由装载因子0.7,数据总数7个,得一维数组大小为7/0,7=10储空间长度为10,采用线性探测再散列法处理冲突,所构造的散列表为：01234567893071411818.9.2查找成功的 ASL=1 + 1 + 1+1+2+1 +