数据结构应用题答案2014-7-6.doc

数据结构应用题答案
第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， 4321

2.如果输入序列为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，6。

3.假设正读和反读都相同的字符序列为“回文”，例如，‘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，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。
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；
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分。

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.设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。
答：借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（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.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6；请说明为什么不能或如何才能得到。
答：输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

10.假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出：
（1）队空的初始条件；
（2）执行操作序列A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明。（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先出栈，得不到输出序列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第二个出栈）的次序有哪几个？用S表示入栈，X表示出栈，写出可能得到次序的操作序列。
答：三个：CDEBA，CDBEA，CDBAE
CDEBA操作序列：SSSXSXSXXX；CDBEA操作序列：SSSXSXXSXX；CDBAE操作序列：SSSXSXXXSX；

15.若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
答：（1）4132 （2）4213 （3）4231
16.设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。
答：既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是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)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？
X72.用一维数组存放的一棵完全二叉树如下表所示
A
B
C
D
E
F
G
H
I
J
K
L
写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。
答案 HIDJKEBLFGCA
X23.（5分）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，证明：n0=n2+1。
X34.叙述并证明二叉树的性质3。
X35.（8分）已知一棵二叉树如下，
（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。
（2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。

X1X56.（8分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJK。
X87.有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。
答案根据后序序列知根结点为C，因此左子树：中序序列为AB 后序序列为AB 右子树：中序序列为EFGHD ，后序序列为：FHGED 依次推得该二叉树结构如下图所示

先序遍历序列：CBADEGFH
层次遍历序列：CBDAEGFH
X58.（8分）二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
X99.（6分）二叉树的先序序列为EBADCFHGIKJ；二叉树的中序序列为ABCDEFGHIJK，请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
X1010.（8分）设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。
X411.（8分）设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。
12.（6分）设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
X613.（8分）假设字符a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。
X514.（8分）假设字符a,b,c,d,e,f的使用频度分0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
X715.（8分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30，构造哈夫曼树并写出a,b,c,d,e,f的哈夫曼编码。
16.（6分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。
X617.请画出下图所示的树所对应的二叉树。
答案：
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）哪个是结点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； (7) E的兄弟是D，F的兄弟是G和H；（8）2, 5； (9) 5； (10) 3。
X920.假设在树中，结点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）树的度数：3
21.已知一棵树边的结点为（I,M），(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)}，试画出这棵树，并回答下列问题：
(1)哪个是根结点？
(2)哪些是叶子结点？
(3)树的深度是多少？
答案如下图所示。（图不对，缺结点H的孩子结点J，）

根结点C，叶子结点F、K、L、J、D、M、N，深度5

五、应用题（每小题6分，共48分）

3.答：快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（8分）二叉树为：

后序遍历序列：CEDBGFA，层次遍历序列：ABFCDGE
评分标准：得出二叉树得4分，给出后序和层次遍历序列得4分，步骤不全酌情给分。
4、（8分）哈夫曼树：

哈夫曼编码：
a：011 b：10 c：00000 d：0010
e：0001 f：11 g：001 h：0101
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
5、（10分）
（1）邻接表存储结构

（2）深度优先遍历序列：BADCEF
广度优先遍历序列：BACEDF
评分标准：画出邻接表存储结构得5分，求出深度优先和广度优先遍历序列得5分，其他情况全酌情给分。
6、（8分）二叉判定树

平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9
评分标准：得出二叉判定树给6分，求出平均查找长度给2分，步骤不全酌情给分。

2、（6分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（8分）二叉树为：

后序遍历序列：CEDBGFA，层次遍历序列：ABFCDGE
评分标准：得出二叉树得4分，给出后序和层次遍历序列得4分，步骤不全酌情给分。
4、（8分）哈夫曼树：

哈夫曼编码：
a：011 b：10 c：00000 d：0010
e：0001 f：11 g：001 h：0101
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
5、（10分）
（1）邻接表存储结构

（2）深度优先遍历序列：BADCEF
广度优先遍历序列：BACEDF
评分标准：画出邻接表存储结构得5分，求出深度优先和广度优先遍历序列得5分，其他情况全酌情给分。
6、（8分）二叉判定树

平均查找长度：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分。
3、（8分）二叉排序树的构造过程如下：

评分标准：没有过程或过程不全酌情减分
4、（8分）

评分标准：结果正确得5分，步骤不全酌情扣分。
5、（10分）
（1）（4分）哈希表：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49

24
40
10

30
31
46
47
（2）（4分）若查找关键字63，需要与关键字31、16、47、32、17进行比较。
（3）（2分）平均查找长度：
ASLsc=（6*1+2+3*3+6）/11=23/11
6、（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、（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分）哈夫曼树为：

由此可得哈夫曼编码分别为：
a：000 b：001 c：100
d：101 e：01 f：11
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
3、（8分）二叉排序树的构造过程如下：

5分
平均查找长度：ASL=（1+2*2+4*3+2*4+5）/10=3 3分

评分标准：得出二叉判定树给5分，求出平均查找长度给3分，步骤不全酌情给分。
4、（7分）拓扑序列构造过程

拓扑有序序列有两种：ABCDEF和ACBDEF

评分标准：只有结果没有过程给5分，过程不全或过程不正确酌情扣分。
5、（8分）邻接矩阵为

最小生成树为：

评分标准：写出邻接矩阵给3分，最小生成树给5分，只有结果没有过程给3分，过程不全或过程不正确酌情扣分。
6、（6分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序的结果：40，38，27，20，13，49，76，80，65
评分标准：写出快速排序思想给3分，给出一趟排序结果给3分。
四、算法题（22分）
三、应用题（43分）
1、（6分）

3分

3分

评分标准：构造出二叉树得3分，二叉树的生成森林得3分。
2、（8分）
5分
平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9 3分

评分标准：得出二叉判定树给4分，求出平均查找长度给2分，步骤不全酌情给分。
3、（7分）邻接矩阵：
3分
深度优先序列：abcdehf或abchedf或abcfdeh或abcfhed（不唯一）2分
广度优先序列：abfcdhe或afbcdhe或abfchde或afbchde（不唯一）2分

评分标准：写出图的邻接矩阵的2分，深度优先序列得2分，广度优先序列得2分，其他酌情给分。
4、（8分）最短路径：

终点
1
2
3
4
5
B
6
(A,B)
4
(A,C,B)

C
2
(A,C)

D
∞
5
(A,C,D)
5
(A,C,D)

E
∞
6
(A,C,E)
6
(A,C,E)
6
(A,C,E)

F
∞
∞
∞
8
(A,C,D,F)
8
(A,C,D,F)
S
{A}
{A,C}
{A,C,B}
{A,C,B,D}
{A,B,C,D,E}

评分标准：最短路径给5分，过程给3分，结果正确没有过程或过程不对酌情减分。
5、（8分）哈希表：
0
1
2
3
4
5
6
7
8
9
10
11
12

14
01
68
27
55
19
20
84

23
11
10
平均查找长度：
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分）哈夫曼树为：

由此可得哈夫曼编码分别为：
a：000 b：001 c：100
d：101 e：01 f：11
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给3分，步骤不全酌情给分。
4、（8分）二叉排序树：

平均查找长度：ASL=（1+2*2+3*3+4*3+5*2+6）/12=3.5
评分标准：构造出二叉排序树得5分，平均查找长度得3分，步骤不全酌情扣分。
5、（7分）

由C开始的深度优先生成序列：CDEABF
评分标准：画出原图得4分，求出深度优先生成序列得3分，其他情况酌情给分。
6、（8分）最短路径求解过程：
终点
1
2
3
4
5
B
6
(A,B)
4
(A,C,B)

C
2
(A,C)

D
∞
5
(A,C,D)
5
(A,C,D)

E
∞
6
(A,C,E)
6
(A,C,E)
6
(A,C,E)

F
∞
∞
∞
8
(A,C,D,F)
8
(A,C,D,F)
S
{A}
{A,C}
{A,C,B}
{A,C,B,D}
{A,B,C,D,E}
评分标准：结果正确没有过程得5分，步骤不全或不正确酌情扣分。
五、算法题（共20分）
1、（5分）

评分标准：每写对一种形态得1分。
2、（5分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（7分）
（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH
（2）二叉树所对应的森林：

评分标准：第一小题每个1分，第二小题三棵树，每个1分。
4、（8分）关键路径为：

求解过程：

ve
vl

e
l
l-e
A
0
0
a1
0
1
1
B
5
6
a2
0
0
0
C
2
2
a3
0
5
5
D
6
11
a4
5
6
1
E
9
9
a5
2
2
0
F
10
15
a6
6
11
5
G
15
16
a7
9
9
0
H
14
14
a8
9
10
1
I
23
23
a9
10
15
5

a10
14
14
0

a11
15
16
1
评分标准：结果正确没有过程给5分，过程不全或过程不正确酌情扣分。
5、（8分）最小生成树为：

评分标准：结果正确没有过程给5分，过程不全或过程不正确酌情扣分。
6、哈希表：
0
1
2
3
4
5
6
7
8
9
10
11
12

14
01
68
27
55
19
20
84

23
11
10
平均查找长度：
ASLsc=（6*1+2+3*3+4）/11=21/11
评分标准：写出哈希表得5分，查找长度2分，其他情况酌情给分。
五、算法题（20分）
四、应用题（40分）
1、（8分）

4分

4分

评分标准：构造出二叉树得4分，二叉树的生成森林得4分。
2、（8分）二叉排序树的构造过程如下：

评分标准：没有过程或过程不全酌情减分
3、（8分）邻接矩阵：
4分
深度优先序列：abcdehf或abchedf或abcfdeh或abcfhed（不唯一）
广度优先序列：abfcdhe或afbcdhe或abfchde或afbchde（不唯一）4分
评分标准：写出图的邻接矩阵的4分，深度优先序列得2分，其他酌情给分。
4、（8分）
3．

评分标准：最小生成树给4分，过程给4分，结果正确没有过程或过程不对酌情减分。
5、（8分）哈希表：
0
1
2
3
4
5
6
7
8
9
10
11
12

3
29
200
32
45
58
100
10
126
400
平均查找长度：
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分）哈夫曼树为：

由此可得哈夫曼编码分别为：
a：0000 b：0001 c：001
d：01 e：10 f：11
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
4、（8分）拓扑序列构造过程

拓扑有序序列有两种：ABCDEF和ACBDEF

评分标准：只有结果没有过程给5分，过程不全或过程不正确酌情扣分。
5、（8分）最小生成树为：

评分标准：只有结果没有过程给5分，过程不全或过程不正确酌情扣分。
6、（8分）
（1）由装载因子0.7，数据总数7个，得一维数组大小为7/0.7=10，存储空间长度为10，采用线性探测再散列法处理冲突，所构造的散列表为：

0
1
2
3
4
5
6
7
8
9
30
7
14
11
8
18
.
9
.
.
（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7
评分标准：构造出哈希表得6分，求出平均查找长度得2分。
7、（6分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序的结果：27，38，13，49，76，97，65，50
13，27，38，49，76，97，65，50
13，27，38，49，50，65，76，97
评分标准：写出快速排序思想给3分，给出排序结果给3分。
四、算法题（22分）
三、解答下列问题（共45分）
1．（5分）
快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要思想正确定就可得分。
2．（5分）

评分标准：每写对一种形态得1分。
3．（8分）

6分
后序序列：DGJHEBIFCA 层次序列：ABCDEFGHIJ 2分
评分标准：构造出二叉树得6分，后序序列和层次序列各得1分。
4．（8分）二叉排序树：。

平均查找长度：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）二叉树所对应的森林：

评分标准：第一小题每个1分，第二小题三棵树，每个2分。
4．（8分）

由C开始的深度优先生成序列：CDEABF
评分标准：画出原图得4分，求出深度优先生成序列得4分，其他情况酌情给分。
5．（8分）

评分标准：结果正确得5分，步骤不全酌情扣分。

6．(8分)

初始堆

30选出后

28选出后

15选出后

12选出后

9选出后

3选出后排序完成

评分标准：结果正确得5分，步骤不全酌情扣分。
7．（8分）
（1）由装载因子0.7，数据总数7个，得一维数组大小为7/0.7=10，存储空间长度为10，采用线性探测再散列法处理冲突，所构造的散列表为：

0
1
2
3
4
5
6
7
8
9
30
7
14
11
8
18
.
9
.
.
（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7
评分标准：构造出哈希表得6分，求出平均查找长度得2分。
四、算法题（20分）