还剩25页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构应用题答案第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,1243,1324,1342,1432,2134,2143,2341,2314,2431,3214,3241,3421,
43212.如果输入序列为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先出栈,然后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,
63.假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文假设一字符序列已存入计算机,请用堆栈判断其是否为回文,简述算法答方法一使用数据结构:循环队列和顺序栈算法思路为
1.将字符串按照用户输入的顺序分别入栈和队列
2.分别从队列和栈中取出首个字符
3.比较取出的字符,若相等,继续分别从队列和栈中取首个字符;否则跳出循环,并设置标志flag=0;
4.若队列和栈中的字符都取完,则结束,设置标志flag=1;
5.flag=1表示字符从前往后和从后往前的序列完全匹配,该字符串属于回文
6.flag=0表示字符从前往后和从后往前的序列不完全匹配,该字符串不属于回文方法二使用栈将字符串的前一半入栈,再依次出栈,与后一半进行比较,若有不等则不是回文;若依次相等,则是回文注意本题要求简答算法思路,并不要求写出具体算法
4.试写出循环队列判空和判满的条件(队列最大容量为M)答假设循环队列最大存储容量为M判空Q.front==Q.rear
(1)判满(Q.rear+1)%M==Q.front
(2)评分标准给出
(1)和
(2)式分别得3分,其他酌情扣分
5.假设Q[
0..10]是一个循环队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由debgh入队;de出队;ijklm入队;nop入队答(图自己根据解答画出)debgh入队;状态1front=0,rear=5;de出队;状态2front=2,rear=5;ijklm入队;状态3front=2,rear=10;nop入队;状态4front=2,rear=1;p不能入队,因为队列已经满了评分标准状态
1、状态4各2分,状态
2、状态3各1分,状态4中状态1分,理由1分
6.若元素的进栈序列为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是栈顶元素,B和A不可能早于C出栈,故不可能得到D、B、A、C、E出栈序列
7.设输入序列为abcd试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列答借助栈结构,n个入栈元素可得到1/n+12n)!/(n!*n!)种出栈序列本题4个元素,可有14种出栈序列,abcd和dcba就是其中两种但dabc和adbc是不可能得到的两种
8.将两个栈存入数组V[
1..m]应如何安排最好?这时栈空、栈满的条件是什么?答设栈S1和栈S2共享向量V[
1..m],初始时,栈S1的栈顶指针top
[0]=0,栈S2的栈顶指针top
[1]=m+1,当top
[0]=0为左栈空,top
[1]=m+1为右栈空;当top
[0]=0并且top
[1]=m+1时为全栈空当top
[1]-top
[0]=1时为栈满
9.如果输入序列为123456试问能否通过栈结构得到以下两个序列:435612和135426;请说明为什么不能或如何才能得到答输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是12,前面4个元素
(4356)得到后,栈中元素剩12,且2在栈顶,不可能栈底元素1在栈顶元素2之前出栈得到135426的过程如下1入栈并出栈,得到部分输出序列1;然后2和3入栈,3出栈,部分输出序列变为13;接着4和5入栈,5,4和2依次出栈,部分输出序列变为13542;最后6入栈并退栈,得最终结果
13542610.假设以数组sq[
0..7]存放循环队列元素变量f指向队头元素的前一位置变量r指向队尾元素,如用A和D分别表示入队和出队操作,请给出
(1)队空的初始条件;
(2)执行操作序列A3D1A5D2A1D2A4时的状态并作必要的说明(A3表示三次入队操作,D1表示一次出队操作)答
(1)队空的初始条件f=r=0;
(2)执行操作A3后,f=0,r=3;//A3表示三次入队操作执行操作D1后,f=1,r=3;//D1表示一次出队操作执行操作A5后,f=1,r=0;执行操作D2后,f=3,r=0;执行操作A1后,f=3,r=1;执行操作D2后,f=5,r=1;执行操作A4后,按溢出处理因为执行A3后,r=4,这时队满,若再执行A操作,则出错
11.内存中一片连续空间(不妨假设地址从1到m)提供给两个栈S1和S2使用,怎样分配这部分存储空间,使得对任一个栈,仅当这部分空间全满时才发生上溢1答S1和S2共享内存中一片连续空间(地址1到m),可以将S1和S2的栈底设在两端,两栈顶向共享空间的中心延伸,仅当两栈顶指针相邻(两栈顶指针值之差的绝对值等于1)时,判断为栈满,当一个栈顶指针为0,另一个栈顶指针m+1时为两栈均空
12.设一数列的输入顺序为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在栈顶,故不可能2先出栈,得不到输出序列
15462313.设输入序列为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第二个出栈)的次序有哪几个?用S表示入栈,X表示出栈,写出可能得到次序的操作序列答三个CDEBA,CDBEA,CDBAECDEBA操作序列SSSXSXSXXX;CDBEA操作序列SSSXSXXSXX;CDBAE操作序列SSSXSXXXSX;
15.若以
1、
2、
3、4作为双端队列的输入序列,试分别求出以下条件的输出序列
(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;
(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;
(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列答
(1)4132
(2)4213
(3)
423116.设一个双端队列,元素进入该队列的次序为a,b,c,d求既不能由输入受限的双端队列得到又不能由输出受限的双端队列得到的输出序列答既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是dbca第6章树和二叉树
1.(8分)已知一棵树的边的集合表示为LNGKGLGMBEBFDGDHDIDJABACAD画出这棵树,并回答下列问题1树根是哪个结点?哪些是叶子结点?哪些是非终端结点?2树的度是多少?各个结点的度是多少?3树的深度是多少?各个结点的层数是多少?以结点G为根的子树的深度是多少?X
72.用一维数组存放的一棵完全二叉树如下表所示ABCDEFGHIJKL写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序答案HIDJKEBLFGCAX
23.(5分)对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,证明n0=n2+1X
34.叙述并证明二叉树的性质3X
35.(8分)已知一棵二叉树如下,
(1)请分别写出按前序、中序、后序和层次遍历时得到的结点序列
(2)如果此二叉树由森林转换得到,请画出原森林中的各棵树X1X
56.(8分)画出由下列序列得到的二叉树以及由此二叉树转化的森林先序EBADCFHGIKJ;中序ABCDEFGHIJKX
87.有二叉树中序序列为ABCEFGHD,后序序列为ABFHGEDC,请画出此二叉树,并写出二叉树的先序遍历序列和层次遍历序列答案根据后序序列知根结点为C,因此左子树中序序列为AB后序序列为AB右子树中序序列为EFGHD,后序序列为FHGED依次推得该二叉树结构如下图所示先序遍历序列CBADEGFH层次遍历序列CBDAEGFHX
58.(8分)二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG,试画出该二叉树,并写出二叉树的后序遍历序列和层次遍历序列X
99.(6分)二叉树的先序序列为EBADCFHGIKJ;二叉树的中序序列为ABCDEFGHIJK,请画出该二叉树,并写出二叉树的后序遍历序列和层次遍历序列X
1010.(8分)设一棵二叉树的先序、中序遍历序列分别为先序遍历序列ABDFCEGH中序遍历序列BFDAGEHC请画出该二叉树,并将这棵二叉树转换成对应的树(或森林)X
411.(8分)设一棵二叉树的前序序列为ABDGECFH,中序序列为DGBEAFHC试画出该二叉树并写出后序和层次遍历序列
12.(6分)设给定一个权值集合W=3,5,7,9,11,要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPLX
613.(8分)假设字符abcdefgh的使用频度分别是
0.
150.
190.
070.
080.
040.23,
0.13,
0.11画出哈夫曼树并写出abcdefgh的Huffman(哈夫曼)编码X
514.(8分)假设字符abcdef的使用频度分
0.
070.
090.
120.
220.
230.27,写出abcdef的Huffman(哈夫曼)编码X
715.(8分)假设字符abcdef的使用频度分别是
0.
070.
100.
120.
160.
250.30,构造哈夫曼树并写出abcdef的哈夫曼编码
16.(6分)试分别画出具有三个结点的树和三个结点的二叉树的不同形态X
617.请画出下图所示的树所对应的二叉树答案
18.(6分)请画出与下列二叉树对应的森林X10X
819.已知一棵树边的集合为{IMINEIBEBDABGJGKCGCFHLCHAC},请回答下列问题x10
(1)哪个是根结点?
(2)X8哪些是叶子结点?X10哪些是分支结点?X8
(3)哪个是结点G的双亲结点?
(4)哪些是结点G的祖先?X8
(5)哪些是结点G的孩子?X8
(6)哪些是结点E的子孙?X8
(7)哪些是结点E的兄弟?哪些是结点F的兄弟?
(8)结点B和N的层次号分别是多少?
(9)树的深度是多少?
(10)以结点C为根的子树的深度是多少?答案
(1)A;
(2)DMNFJKL;3C;4AC;5JK;6IMN;7E的兄弟是D,F的兄弟是G和H;
(8)25;95;103X
920.假设在树中,结点x是结点y的双亲时,用(x,y)来表示树边已知一棵树边的集合为{(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)叶结点m、n、d、l、h、j、k
(3)g的双亲c
(4)g的祖先a、c
(5)g的孩子j、k
(6)e的子孙i、m、n
(7)e的兄弟d
(8)b的层次2
(9)树的深度5 f的兄弟g、hn的层次;5
(10)以结点c为根的子树的深度3
(11)树的度数
321.已知一棵树边的结点为(IM),I,NE,IB,E,B,DC,BG,L,G,K,A,G,A,FH,J,A,H,C,A},试画出这棵树,并回答下列问题1哪个是根结点?2哪些是叶子结点?3树的深度是多少?答案如下图所示(图不对,缺结点H的孩子结点J,)根结点C,叶子结点F、K、L、J、D、M、N,深度5
五、应用题(每小题6分,共48分)
3.答快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序评分标准只要基本思想对就可得分
3、(8分)二叉树为AEGDCFB后序遍历序列CEDBGFA,层次遍历序列ABFCDGE评分标准得出二叉树得4分,给出后序和层次遍历序列得4分,步骤不全酌情给分
4、(8分)哈夫曼树cdehbfag哈夫曼编码a011b10c00000d0010e0001f11g001h0101评分标准得出哈夫曼树给4分,给出哈夫曼编码给4分,步骤不全酌情给分
5、(10分)
(1)邻接表存储结构ABCDEF13^0213^4^0245^1^33^
(2)深度优先遍历序列BADCEF广度优先遍历序列BACEDF评分标准画出邻接表存储结构得5分,求出深度优先和广度优先遍历序列得5分,其他情况全酌情给分
6、(8分)二叉判定树60100327238124552090平均查找长度ASL=(1+2*2+4*3+3*4)/10=
2.9评分标准得出二叉判定树给6分,求出平均查找长度给2分,步骤不全酌情给分
2、(6分)快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序评分标准只要基本思想对就可得分
3、(8分)二叉树为AEGDCFB后序遍历序列CEDBGFA,层次遍历序列ABFCDGE评分标准得出二叉树得4分,给出后序和层次遍历序列得4分,步骤不全酌情给分
4、(8分)哈夫曼树cdehbfag哈夫曼编码a011b10c00000d0010e0001f11g001h0101评分标准得出哈夫曼树给4分,给出哈夫曼编码给4分,步骤不全酌情给分
5、(10分)
(1)邻接表存储结构ABCDEF13^0213^4^0245^1^33^
(2)深度优先遍历序列BADCEF广度优先遍历序列BACEDF评分标准画出邻接表存储结构得5分,求出深度优先和广度优先遍历序列得5分,其他情况全酌情给分
6、(8分)二叉判定树60100327238124552090平均查找长度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)二叉树所对应的森林ABDGCEFH评分标准第一小题每个1分,第二小题三棵树4分,每错一个扣1分
3、(8分)二叉排序树的构造过程如下463988454688454688464646705810145398870583945884670394588465870341010166453988464670106610158453988701011058453988评分标准没有过程或过程不全酌情减分
4、(8分)1562439156243109156243109111562431091151562431091156评分标准结果正确得5分,步骤不全酌情扣分
5、(10分)
(1)(4分)哈希表012345678910111213141516173217634924401030314647
(2)(4分)若查找关键字63,需要与关键字
31、
16、
47、
32、17进行比较
(3)(2分)平均查找长度ASLsc=(6*1+2+3*3+6)/11=23/
116、(8分)
(36)2548126520
(2536)48126520
(253648)126520
(12253648)6520
(1225364865)20
(122025364865)评分标准每一趟插入得1分,步骤不全酌情扣分
三、应用题(43分)
1、(6分)对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1证明设二叉树的结点总数为n,度为1的结点个数为n1,则有n=n0+n1+n2
(1)又在二叉树中除了根结点每个结点都有一个分支指向它,这些分支是有度为1和度为2的结点发出的,由此得到n-1=n1+2*n2
(2)由式
(1)和
(2)得n0=n2+1,证毕评分标准叙述定理得2分,证明得4分,其他酌情扣分
2、(8分)哈夫曼树为efdcab0000011111由此可得哈夫曼编码分别为a000b001c100d101e01f11评分标准得出哈夫曼树给4分,给出哈夫曼编码给4分,步骤不全酌情给分
3、(8分)二叉排序树的构造过程如下45203212453212451245454520253212875202532127545203212754564502025903212875454550202590321287550202532128755分平均查找长度ASL=(1+2*2+4*3+2*4+5)/10=33分评分标准得出二叉判定树给5分,求出平均查找长度给3分,步骤不全酌情给分
4、(7分)拓扑序列构造过程BCDEF输出ACDEF输出B输出CDEF输出DEF拓扑有序序列有两种ABCDEF和ACBDEF评分标准只有结果没有过程给5分,过程不全或过程不正确酌情扣分
5、(8分)邻接矩阵为最小生成树为ABFHDHE1AB12CFAB1233DCFAB123DECFAB125343评分标准写出邻接矩阵给3分,最小生成树给5分,只有结果没有过程给3分,过程不全或过程不正确酌情扣分
6、(6分)快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序一趟快速排序的结果40,38,27,20,13,49,76,80,65评分标准写出快速排序思想给3分,给出一趟排序结果给3分
四、算法题(22分)
三、应用题(43分)
1、(6分)EFADJKCIBHG3分EFADJKCIBHG3分评分标准构造出二叉树得3分,二叉树的生成森林得3分
2、(8分)601003272381245520905分平均查找长度ASL=(1+2*2+4*3+3*4)/10=
2.93分评分标准得出二叉判定树给4分,求出平均查找长度给2分,步骤不全酌情给分
3、(7分)邻接矩阵3分深度优先序列abcdehf或abchedf或abcfdeh或abcfhed(不唯一)2分广度优先序列abfcdhe或afbcdhe或abfchde或afbchde(不唯一)2分评分标准写出图的邻接矩阵的2分,深度优先序列得2分,广度优先序列得2分,其他酌情给分
4、(8分)最短路径终点12345B6AB4ACBC2ACD∞5ACD5ACDE∞6ACE6ACE6ACEF∞∞∞8ACDF8ACDFS{A}{AC}{ACB}{ACBD}{ABCDE}评分标准最短路径给5分,过程给3分,结果正确没有过程或过程不对酌情减分
5、(8分)哈希表01234567891011121401682755192084231110平均查找长度ASLsc=(6*1+2+3*3+4)/11=21/11评分标准写出哈希表得5分,查找长度3分
6、(5分)
(1)是大顶堆
(2)不是堆,调整以后为100,98,66,85,80,60,40,77,82,10,20
(3)是小顶堆评分标准判断正确得3分,调整得3分
四、算法题(22分)
1、(5分)假设循环队列最大存储容量为M判空Q.front==Q.rear
(1)判满(Q.rear+1)%M==Q.front
(2)评分标准给出
(1)和
(2)式分别得2分,前提假设得1分,其他酌情扣分
2、(5分)对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1证明设二叉树的结点总数为n,度为1的结点个数为n1,则有n=n0+n1+n2
(1)又在二叉树中除了根结点每个结点都有一个分支指向它,这些分支是有度为1和度为2的结点发出的,由此得到n-1=n1+2*n2
(2)由式
(1)和
(2)得n0=n2+1,证毕评分标准给出
(1)和
(2)式分别得2分,得出结论得1分,其他酌情扣分
3、(7分)哈夫曼树为efdcab0000011111由此可得哈夫曼编码分别为a000b001c100d101e01f11评分标准得出哈夫曼树给4分,给出哈夫曼编码给3分,步骤不全酌情给分
4、(8分)二叉排序树JanFebMarAprJunMayJulAugSepOctNovDec平均查找长度ASL=(1+2*2+3*3+4*3+5*2+6)/12=
3.5评分标准构造出二叉排序树得5分,平均查找长度得3分,步骤不全酌情扣分
5、(7分)CADBEF由C开始的深度优先生成序列CDEABF评分标准画出原图得4分,求出深度优先生成序列得3分,其他情况酌情给分
6、(8分)最短路径求解过程终点12345B6AB4ACBC2ACD∞5ACD5ACDE∞6ACE6ACE6ACEF∞∞∞8ACDF8ACDFS{A}{AC}{ACB}{ACBD}{ABCDE}评分标准结果正确没有过程得5分,步骤不全或不正确酌情扣分
五、算法题(共20分)
1、(5分)评分标准每写对一种形态得1分
2、(5分)快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序评分标准只要基本思想对就可得分
3、(7分)
(1)前序ABDGCEFH中序DGBAECHF后序GDBEHFCA层次ABCDEFGH
(2)二叉树所对应的森林ABDGCEFH评分标准第一小题每个1分,第二小题三棵树,每个1分
4、(8分)关键路径为ACEHIa2=2a5=7a7=5a10=9求解过程vevlell-eA00a1011B56a2000C22a3055D611a4561E99a5220F1015a66115G1516a7990H1414a89101I2323a910155a1014140a1115161评分标准结果正确没有过程给5分,过程不全或过程不正确酌情扣分
5、(8分)最小生成树为ABFHDHE1AB12CFAB1233DCFAB123DECFAB125343评分标准结果正确没有过程给5分,过程不全或过程不正确酌情扣分
6、哈希表01234567891011121401682755192084231110平均查找长度ASLsc=(6*1+2+3*3+4)/11=21/11评分标准写出哈希表得5分,查找长度2分,其他情况酌情给分
五、算法题(20分)
四、应用题(40分)
1、(8分)EFADJKCIBHG4分EFADJKCIBHG4分评分标准构造出二叉树得4分,二叉树的生成森林得4分
2、(8分)二叉排序树的构造过程如下4520321245321245124545452025321287520253212754520321275456450202590321287545455020259032128755020253212875评分标准没有过程或过程不全酌情减分
3、(8分)邻接矩阵4分深度优先序列abcdehf或abchedf或abcfdeh或abcfhed(不唯一)广度优先序列abfcdhe或afbcdhe或abfchde或afbchde(不唯一)4分评分标准写出图的邻接矩阵的4分,深度优先序列得2分,其他酌情给分
4、(8分)3.1562439156243109115156243109156243109111562431091156评分标准最小生成树给4分,过程给4分,结果正确没有过程或过程不对酌情减分
5、(8分)哈希表012345678910111232920032455810010126400平均查找长度ASLsc=(7*1+2+3+3)/10=
1.5评分标准写出哈希表得5分,查找长度3分
四、算法题(20分)
三、应用题(40分)
1、(5分)评分标准每写错一种形态扣1分
2、(5分)对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1评分标准叙述不恰当酌情扣分
3、(8分)哈夫曼树为efdcab0000110111由此可得哈夫曼编码分别为a0000b0001c001d01e10f11评分标准得出哈夫曼树给4分,给出哈夫曼编码给4分,步骤不全酌情给分
4、(8分)拓扑序列构造过程BCDEF输出ACDEF输出B输出CDEF输出DEF拓扑有序序列有两种ABCDEF和ACBDEF评分标准只有结果没有过程给5分,过程不全或过程不正确酌情扣分
5、(8分)最小生成树为ABFCDHE1AB12FAB125CFAB1253DCFAB12534DECFAB125343评分标准只有结果没有过程给5分,过程不全或过程不正确酌情扣分
6、(8分)
(1)由装载因子
0.7,数据总数7个,得一维数组大小为7/
0.7=10,存储空间长度为10,采用线性探测再散列法处理冲突,所构造的散列表为
01234567893071411818.
9..
(2)查找成功的ASL=1+1+1+1+2+1+1/7=8/7评分标准构造出哈希表得6分,求出平均查找长度得2分
7、(6分)快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序快速排序的结果27,38,13,49,76,97,65,5013,27,38,49,76,97,65,5013,27,38,49,50,65,76,97评分标准写出快速排序思想给3分,给出排序结果给3分
四、算法题(22分)
三、解答下列问题(共45分)1.(5分)快速排序的思想通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序评分标准只要思想正确定就可得分2.(5分)评分标准每写对一种形态得1分3.(8分)ACDEJHGBFI6分后序序列DGJHEBIFCA层次序列ABCDEFGHIJ2分评分标准构造出二叉树得6分,后序序列和层次序列各得1分4.(8分)二叉排序树JanFebMarAprJunMayJulAugSepOctNovDec平均查找长度ASL=(1+2*2+3*3+4*3+5*2+6)/12=
3.5评分标准构造出二叉排序树得5分,平均查找长度得3分,其他情况酌情给分
三、解答下列问题(共50分)1.(5分)二叉排序树或者是一棵空树;或者是具有下列性质的二叉树
(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)它的左、右子树也分别是二叉排序树评分标准只要基本思想对就可得分2.(5分)对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1证明设二叉树的结点总数为n,度为1的结点个数为n1,则有n=n0+n1+n2
(1)又在二叉树中除了根结点每个结点都有一个分支指向它,这些分支是有度为1和度为2的结点发出的,由此得到n-1=n1+2*n2
(2)由式
(1)和
(2)得n0=n2+1,证毕评分标准叙述定理得1分,证明得4分,其他酌情扣分3.(8分)
(1)前序ABDGCEFH中序DGBAECHF后序GDBEHFCA层次ABCDEFGH
(2)二叉树所对应的森林ABDGCEFH评分标准第一小题每个1分,第二小题三棵树,每个2分4.(8分)CADBEF由C开始的深度优先生成序列CDEABF评分标准画出原图得4分,求出深度优先生成序列得4分,其他情况酌情给分5.(8分)1562439156243109156243109111562431091151562431091156评分标准结果正确得5分,步骤不全酌情扣分6.8分初始堆330122815930选出后302831215928选出后301531292815选出后301215392812选出后30915123289选出后30315129283选出后排序完成评分标准结果正确得5分,步骤不全酌情扣分7.(8分)
(1)由装载因子
0.7,数据总数7个,得一维数组大小为7/
0.7=10,存储空间长度为10,采用线性探测再散列法处理冲突,所构造的散列表为
01234567893071411818.
9..
(2)查找成功的ASL=1+1+1+1+2+1+1/7=8/7评分标准构造出哈希表得6分,求出平均查找长度得2分
四、算法题(20分)。