数据结构形成性考核册答案 专课的
第å
«ç« çæ¡
ä¸ã 填空é¢ï¼
ï¼1ï¼ ï¼n+1ï¼/2 O(n)
ï¼2ï¼ O(log2n)
ï¼3ï¼ 37/12
ï¼4ï¼ é¡ºåº æåº
ï¼5ï¼ 1 3
ï¼6ï¼ äºåæç´¢æ çæ³å¹³è¡¡æ
ï¼7ï¼ 6 31 19
ï¼8ï¼ ç´¢å¼å¼ å表å¼å§å
ï¼9ï¼ ï¼12ï¼63ï¼36ï¼ ï¼55ï¼40ï¼82ï¼ ï¼23ï¼74ï¼
ï¼10ï¼ 3 3 2
ï¼11ï¼ ç¨ å¯ ç¨ç
ï¼12ï¼ ä¸éå¼ï¼å³lowå¼ï¼
ï¼13ï¼ 11 Oï¼ ï¼
ï¼14ï¼ 500 25
ï¼15ï¼ æ£å
ï¼16ï¼ é¾æ¥
ï¼17ï¼ 2 1.4
ï¼18ï¼ 5
ï¼19ï¼ n/m
ï¼20ï¼ å¼æ¾å®åæ³ é¾æ¥æ³
ï¼21ï¼ 3 2
ï¼22ï¼
ï¼23ï¼ 4 5
ï¼24ï¼ 4 8
ï¼25ï¼ m-1 m
ï¼26ï¼ åä¸å± å ³é®å
ï¼27ï¼ m 两
ï¼28ï¼
ï¼29ï¼ å¢å 1
ï¼30ï¼ åå°1
äºã æ®éé¢ï¼
ï¼1ï¼ é¡ºåºæ¥æ¾ï¼ASL=13
äºåæ¥æ¾ï¼ASL=99/25
ååæ¥æ¾ï¼ASL=6
ï¼3ï¼ 32 75 29 63 48 94 25 46 18 70
æ£åå°åï¼ 6 10 3 11 9 3 12 7 5 5 æ£ å 表ï¼
0 1 2 3 4 5 6 7 8 9 10 11 12
29 94 18 32 46 70 48 75 63 25
ASL=1.4
ï¼4ï¼ASL=1.3 ï¼é¾æ¥æ³æ£å表ä»ç¥ï¼
第ä¹ç« çæ¡
ä¸ã 填空é¢ï¼
ï¼1ï¼ æå ¥ éæ©
ï¼2ï¼ äº¤æ¢ äºè·¯å½å¹¶
ï¼3ï¼ Oï¼n2ï¼ Oï¼nï¼
ï¼4ï¼ n-1
ï¼5ï¼ Oï¼log2nï¼ Oï¼n*log2nï¼
ï¼6ï¼ ï¼84,79,56,38,40,46ï¼
ï¼7ï¼ Oï¼n*log2nï¼ Oï¼n2ï¼
ï¼8ï¼ Oï¼log2nï¼ Oï¼nï¼
ï¼9ï¼ ä¸¤ç«¯ ä¸é´
ï¼10ï¼ [38 40 ] 46 [56 79 80 ]
ï¼11ï¼ 4 4
ï¼12ï¼
ï¼13ï¼ Oï¼nï¼ Oï¼n*log2nï¼ Oï¼nï¼
ï¼14ï¼ 5 4 8
ï¼15ï¼ [ 38 46 56 79 ] [ 40 84 ]
äºã æ®éé¢ï¼
ï¼1ï¼è§å æåºæ¹æ³æ¯è¾
ï¼2ï¼
3ãå æåºï¼å¨ææåå§åçè¿ç¨ä¸ï¼æ¯æ¬¡çè¿ç®åçæ°æ®æå为ï¼
1 46 74 16 53 14 34 40 38 86 65 27 26
2 46 74 16 53 65 34 40 38 86 14 27 26
3 46 74 16 86 65 34 40 38 53 14 27 26
4 46 74 40 86 65 34 16 38 53 14 27 26
5 46 86 40 74 65 34 16 38 53 14 27 26
6 86 74 40 53 65 34 16 38 46 14 27 26
å®å ¨äºåæ ï¼ç¥ï¼
å¨å©ç¨å æåºçè¿ç¨ä¸ï¼æ¯æ¬¡çè¿ç®åçæ°æ®æå为ï¼
1 74 65 40 53 27 34 16 38 46 14 26 86
2 65 53 40 46 27 34 16 38 26 14 74 86
3 53 46 40 38 27 34 16 14 26 65 74 86
4 46 38 40 26 27 34 16 14 53 65 74 86
5 40 38 34 26 27 14 16 46 53 65 74 86
6 38 27 34 26 16 14 40 46 53 65 74 86
7 34 27 14 26 16 38 40 46 53 65 74 86
8 27 26 14 16 34 38 40 46 53 65 74 86
9 26 16 14 27 34 38 40 46 53 65 74 86
10 16 14 26 27 34 38 40 46 53 65 74 86
11 14 16 26 27 34 38 40 46 53 65 74 86
4ã å¿«éæåºæ¯å±ååå¾å°çæ°æ®æåç»æå¦ä¸ï¼
1 [38 34 16 27 14 26 40] 46 [86 65 53 74]
2 [26 34 16 27 14] 38 40 46 [74 65 53] 86
3 [16 14] 26 [27 34] 38 40 46 [53 65] 74 86
4 14 16 26 27 34 38 40 46 53 65 74 86
5ãæ¯ä¸è¶äºè·¯å½å¹¶æåºç»æåçæ°æ®æå为ï¼
1 [46 74] [16 53] [14 26] [40 38] [86 65] [27 34]
2 [16 46 53 74] [14 26 38 40] [27 34 65 86]
3 [14 16 26 38 40 46 53 74] [27 34 65 86]
4 14 16 26 27 34 38 40 46 53 65 74 86
ï¼3ï¼
1 ç´æ¥éæ©æåº
2 ç´æ¥æå ¥æåº
3 å¿«éæåº
4 å½å¹¶æåº
5 å æåº
ä¸ã 填空é¢ï¼
ï¼1ï¼ ï¼n+1ï¼/2 O(n)
ï¼2ï¼ O(log2n)
ï¼3ï¼ 37/12
ï¼4ï¼ é¡ºåº æåº
ï¼5ï¼ 1 3
ï¼6ï¼ äºåæç´¢æ çæ³å¹³è¡¡æ
ï¼7ï¼ 6 31 19
ï¼8ï¼ ç´¢å¼å¼ å表å¼å§å
ï¼9ï¼ ï¼12ï¼63ï¼36ï¼ ï¼55ï¼40ï¼82ï¼ ï¼23ï¼74ï¼
ï¼10ï¼ 3 3 2
ï¼11ï¼ ç¨ å¯ ç¨ç
ï¼12ï¼ ä¸éå¼ï¼å³lowå¼ï¼
ï¼13ï¼ 11 Oï¼ ï¼
ï¼14ï¼ 500 25
ï¼15ï¼ æ£å
ï¼16ï¼ é¾æ¥
ï¼17ï¼ 2 1.4
ï¼18ï¼ 5
ï¼19ï¼ n/m
ï¼20ï¼ å¼æ¾å®åæ³ é¾æ¥æ³
ï¼21ï¼ 3 2
ï¼22ï¼
ï¼23ï¼ 4 5
ï¼24ï¼ 4 8
ï¼25ï¼ m-1 m
ï¼26ï¼ åä¸å± å ³é®å
ï¼27ï¼ m 两
ï¼28ï¼
ï¼29ï¼ å¢å 1
ï¼30ï¼ åå°1
äºã æ®éé¢ï¼
ï¼1ï¼ é¡ºåºæ¥æ¾ï¼ASL=13
äºåæ¥æ¾ï¼ASL=99/25
ååæ¥æ¾ï¼ASL=6
ï¼3ï¼ 32 75 29 63 48 94 25 46 18 70
æ£åå°åï¼ 6 10 3 11 9 3 12 7 5 5 æ£ å 表ï¼
0 1 2 3 4 5 6 7 8 9 10 11 12
29 94 18 32 46 70 48 75 63 25
ASL=1.4
ï¼4ï¼ASL=1.3 ï¼é¾æ¥æ³æ£å表ä»ç¥ï¼
第ä¹ç« çæ¡
ä¸ã 填空é¢ï¼
ï¼1ï¼ æå ¥ éæ©
ï¼2ï¼ äº¤æ¢ äºè·¯å½å¹¶
ï¼3ï¼ Oï¼n2ï¼ Oï¼nï¼
ï¼4ï¼ n-1
ï¼5ï¼ Oï¼log2nï¼ Oï¼n*log2nï¼
ï¼6ï¼ ï¼84,79,56,38,40,46ï¼
ï¼7ï¼ Oï¼n*log2nï¼ Oï¼n2ï¼
ï¼8ï¼ Oï¼log2nï¼ Oï¼nï¼
ï¼9ï¼ ä¸¤ç«¯ ä¸é´
ï¼10ï¼ [38 40 ] 46 [56 79 80 ]
ï¼11ï¼ 4 4
ï¼12ï¼
ï¼13ï¼ Oï¼nï¼ Oï¼n*log2nï¼ Oï¼nï¼
ï¼14ï¼ 5 4 8
ï¼15ï¼ [ 38 46 56 79 ] [ 40 84 ]
äºã æ®éé¢ï¼
ï¼1ï¼è§å æåºæ¹æ³æ¯è¾
ï¼2ï¼
3ãå æåºï¼å¨ææåå§åçè¿ç¨ä¸ï¼æ¯æ¬¡çè¿ç®åçæ°æ®æå为ï¼
1 46 74 16 53 14 34 40 38 86 65 27 26
2 46 74 16 53 65 34 40 38 86 14 27 26
3 46 74 16 86 65 34 40 38 53 14 27 26
4 46 74 40 86 65 34 16 38 53 14 27 26
5 46 86 40 74 65 34 16 38 53 14 27 26
6 86 74 40 53 65 34 16 38 46 14 27 26
å®å ¨äºåæ ï¼ç¥ï¼
å¨å©ç¨å æåºçè¿ç¨ä¸ï¼æ¯æ¬¡çè¿ç®åçæ°æ®æå为ï¼
1 74 65 40 53 27 34 16 38 46 14 26 86
2 65 53 40 46 27 34 16 38 26 14 74 86
3 53 46 40 38 27 34 16 14 26 65 74 86
4 46 38 40 26 27 34 16 14 53 65 74 86
5 40 38 34 26 27 14 16 46 53 65 74 86
6 38 27 34 26 16 14 40 46 53 65 74 86
7 34 27 14 26 16 38 40 46 53 65 74 86
8 27 26 14 16 34 38 40 46 53 65 74 86
9 26 16 14 27 34 38 40 46 53 65 74 86
10 16 14 26 27 34 38 40 46 53 65 74 86
11 14 16 26 27 34 38 40 46 53 65 74 86
4ã å¿«éæåºæ¯å±ååå¾å°çæ°æ®æåç»æå¦ä¸ï¼
1 [38 34 16 27 14 26 40] 46 [86 65 53 74]
2 [26 34 16 27 14] 38 40 46 [74 65 53] 86
3 [16 14] 26 [27 34] 38 40 46 [53 65] 74 86
4 14 16 26 27 34 38 40 46 53 65 74 86
5ãæ¯ä¸è¶äºè·¯å½å¹¶æåºç»æåçæ°æ®æå为ï¼
1 [46 74] [16 53] [14 26] [40 38] [86 65] [27 34]
2 [16 46 53 74] [14 26 38 40] [27 34 65 86]
3 [14 16 26 38 40 46 53 74] [27 34 65 86]
4 14 16 26 27 34 38 40 46 53 65 74 86
ï¼3ï¼
1 ç´æ¥éæ©æåº
2 ç´æ¥æå ¥æåº
3 å¿«éæåº
4 å½å¹¶æåº
5 å æåº
温馨提示：答案为网友推荐，仅供参考
第1个回答 2014-01-02
第一章答案
一、 单选题：
A C B C D B
二、 填空题：
1、集合 线性关系 树 图
2、顺序 链接 索引 散列、
3、1：1 1：N M：N
4、数据 操作
5、引用
6、引用
7、实参 值
8、iostream.h fstream.h
9、stdlib.h rand()%21
10、长度之和 sizeof(r)
11、sizeof(a) a+i (char *)a+i*sizeof(a[i])
12、参数类型 参数个数 排列次序
13、2 用户定义
14、= = ra rb
15、O(n) O(m*n)
16、n n(n+1)/2 O(n2)
17、O(n)
18、35/12
三、 普通题：
4、 (1) O( ) (2) O(n) (3) O(n2)
(4) O( ) (5) O(n) (6) O(n2)
(7) O(M*N) (8) O(M*N*L)
第二章答案
一、单选题：
B A C B D C
填空题：
1、值 指针
2、（38，56，25，60，42，74）
3、O（n） O(1)
4、O(1) O(n)
5、i-1 i+1
6、p->next a[p].next
7、表头
8、前驱 后继
9、表尾 表头
10、HL->next==NULL HL->next==HL
11、a[i].next=a[1].next;a[1].next=i;
12、i=a[1].next;a[1].next=a[i].next;
13、p=a[i].next;a[i].next=a[p].next;i=p;
14、a[j].next=a[i].next;a[i].next=j;
普通题：
1、 （1）（79，62，34，57，26，48）
（2）（26，34，48，57，62，79）
（3）（48，56，57，62，79，34）
（4）（56，57，79，34）
（5）（26，34，39，48，57，62）
3、
（2）ElemType Delete(List &L , int i)
{
if (i<1 || i>L.size || L.size==0) {
cerr<<”Error”<<endl;
exit(1);
}
ElemType temp=L.list[i-1];
for (int j=i ; j<L.size ; j++)
L.list[j-1]=L.list[j];
L.size--;
return temp;
}
（3）void Insert(List & L , int i , ElemType item)
{
if (i<1 || i>L.size+1 || L.size==MaxSize) {
cerr<<”Error!”<<endl;
exit(1);
}
for (int j=L.size-1 ; j>=i-1 ; j--)
L.list[j+1]=L.list[j];
L.list[i-1]=item;
L.size++;
}
4、
（1）void Contrary(LNode * & HL)
{
LNode *p=HL;
HL=NULL;
while (p!=NULL) {
LNode *q=p;
p=p->next;
q->next=HL;
HL=q;
}
}
（3）ElemType MaxValue(LNode *HL)
{
if (HL==NULL) {
cerr<<”Empty!”<<endl;
exit(1);
}
ElemType max=HL->data;
LNode *p=HL->next;
while (p!=NULL) {
if (max<p->data) max=p->data;
p=p->next;
}
return max;
}
（4）int Count(LNode *HL , ElemType item)
{
int n=0;
while (HL!=NULL) {
if (HL->data==item) n++;
HL=HL->next;
}
return n;
}
一、 单选题：
A C B C D B
二、 填空题：
1、集合 线性关系 树 图
2、顺序 链接 索引 散列、
3、1：1 1：N M：N
4、数据 操作
5、引用
6、引用
7、实参 值
8、iostream.h fstream.h
9、stdlib.h rand()%21
10、长度之和 sizeof(r)
11、sizeof(a) a+i (char *)a+i*sizeof(a[i])
12、参数类型 参数个数 排列次序
13、2 用户定义
14、= = ra rb
15、O(n) O(m*n)
16、n n(n+1)/2 O(n2)
17、O(n)
18、35/12
三、 普通题：
4、 (1) O( ) (2) O(n) (3) O(n2)
(4) O( ) (5) O(n) (6) O(n2)
(7) O(M*N) (8) O(M*N*L)
第二章答案
一、单选题：
B A C B D C
填空题：
1、值 指针
2、（38，56，25，60，42，74）
3、O（n） O(1)
4、O(1) O(n)
5、i-1 i+1
6、p->next a[p].next
7、表头
8、前驱 后继
9、表尾 表头
10、HL->next==NULL HL->next==HL
11、a[i].next=a[1].next;a[1].next=i;
12、i=a[1].next;a[1].next=a[i].next;
13、p=a[i].next;a[i].next=a[p].next;i=p;
14、a[j].next=a[i].next;a[i].next=j;
普通题：
1、 （1）（79，62，34，57，26，48）
（2）（26，34，48，57，62，79）
（3）（48，56，57，62，79，34）
（4）（56，57，79，34）
（5）（26，34，39，48，57，62）
3、
（2）ElemType Delete(List &L , int i)
{
if (i<1 || i>L.size || L.size==0) {
cerr<<”Error”<<endl;
exit(1);
}
ElemType temp=L.list[i-1];
for (int j=i ; j<L.size ; j++)
L.list[j-1]=L.list[j];
L.size--;
return temp;
}
（3）void Insert(List & L , int i , ElemType item)
{
if (i<1 || i>L.size+1 || L.size==MaxSize) {
cerr<<”Error!”<<endl;
exit(1);
}
for (int j=L.size-1 ; j>=i-1 ; j--)
L.list[j+1]=L.list[j];
L.list[i-1]=item;
L.size++;
}
4、
（1）void Contrary(LNode * & HL)
{
LNode *p=HL;
HL=NULL;
while (p!=NULL) {
LNode *q=p;
p=p->next;
q->next=HL;
HL=q;
}
}
（3）ElemType MaxValue(LNode *HL)
{
if (HL==NULL) {
cerr<<”Empty!”<<endl;
exit(1);
}
ElemType max=HL->data;
LNode *p=HL->next;
while (p!=NULL) {
if (max<p->data) max=p->data;
p=p->next;
}
return max;
}
（4）int Count(LNode *HL , ElemType item)
{
int n=0;
while (HL!=NULL) {
if (HL->data==item) n++;
HL=HL->next;
}
return n;
}
第2个回答 2014-01-02
第三章答案
一、 选择题：
A D B
二、 填空题：
（1） 行号 列号 元素值
（2） 行号 列号
（3） 引用
（4） 大于等于
（5） 4 5
（6） 列号 行号
（7） 单 表
（8） 括号
（9） 3
（10） data sublist
（11） true NULL
三、 普通题：
1、（1） ((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6))
（2）((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
3、
长度 深度
（1） 1 2
（2） 3 1
（3） 2 3
（4） 2 2
（5） 3 3
（6） 1 4
第四章答案
参考答案：
一、 单选题：
A B C A B B D D
二、 填空题：
（1） 队尾 队首
（2） 后进先出 先进先出
（3） 栈顶指针 写入
（4） 栈顶元素 栈顶指针
（5） Q.front==Q.rear Q.front==(Q.rear+1)%QueueMaxSize
（6） -1 StackMaxSize-1
（7） 空栈 空 只含有一个结点
（8） 新结点的指针域 栈顶指针
（9） 指针域 栈顶指针
（10） 队尾指针 写入
（11） top==0
（12） p->next=HS ; HS=p;
（13） HS=HS->next;
（14） (front==rear) && (front!=NULL)
或(front==rear) && (rear!=NULL)
（15） 3 x 2 + 8 5 -
（16） 15
（17） 相反次序
（18） 返回地址
（19） 返回地址
三、 普通题：
（1）ABCD ABDC ACBD ACDB ADCB BACD BADC
BCAD BCDA BDCA CBAD CBDA CDBA DCBA
（5）3 4 25 6 15 + - / 8 * + @
（6）（24+8）*3/（4*（10-7））@
（15）（N+rear-front）%N
第五章答案
一、 填空题：
（1） n-1
（2） 5 50
（3） （4h-1）/3
（4） 6
（5） 31 21
（6） 10 4 3
（7） 2 1 1 6
（8） B I和J
（9） 6
（10） 2i 2i+1 i/2或
（11） 16
（12） 5 18
（13） a f 空
（14） 2 2 3
（15） 6
（16） a[2*i] a[2*i+1] a[i/2]
（17） 2i-1 2j+1
（18） a[2*i+1] a[2*i+2] a[(i-1)/2]
（19） 2n n-1 n+1
（20） 10 5
（21） 16 31
（22） 2h-1 2h-1
（23） a b c d e f c b a e d f c b e f d a a b d c e f
（24） a b e c f h I j g d a b c d e f g h i j
二、 普通题：
（7） 先序：25，16，8，37，30，28，26，29，32，35，48，60
中序：8，16，25，26，28，29，30，32，35，37，48，60
后序：8，16，26，29，28，35，32，30，60，48，37，25
一、 选择题：
A D B
二、 填空题：
（1） 行号 列号 元素值
（2） 行号 列号
（3） 引用
（4） 大于等于
（5） 4 5
（6） 列号 行号
（7） 单 表
（8） 括号
（9） 3
（10） data sublist
（11） true NULL
三、 普通题：
1、（1） ((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6))
（2）((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
3、
长度 深度
（1） 1 2
（2） 3 1
（3） 2 3
（4） 2 2
（5） 3 3
（6） 1 4
第四章答案
参考答案：
一、 单选题：
A B C A B B D D
二、 填空题：
（1） 队尾 队首
（2） 后进先出 先进先出
（3） 栈顶指针 写入
（4） 栈顶元素 栈顶指针
（5） Q.front==Q.rear Q.front==(Q.rear+1)%QueueMaxSize
（6） -1 StackMaxSize-1
（7） 空栈 空 只含有一个结点
（8） 新结点的指针域 栈顶指针
（9） 指针域 栈顶指针
（10） 队尾指针 写入
（11） top==0
（12） p->next=HS ; HS=p;
（13） HS=HS->next;
（14） (front==rear) && (front!=NULL)
或(front==rear) && (rear!=NULL)
（15） 3 x 2 + 8 5 -
（16） 15
（17） 相反次序
（18） 返回地址
（19） 返回地址
三、 普通题：
（1）ABCD ABDC ACBD ACDB ADCB BACD BADC
BCAD BCDA BDCA CBAD CBDA CDBA DCBA
（5）3 4 25 6 15 + - / 8 * + @
（6）（24+8）*3/（4*（10-7））@
（15）（N+rear-front）%N
第五章答案
一、 填空题：
（1） n-1
（2） 5 50
（3） （4h-1）/3
（4） 6
（5） 31 21
（6） 10 4 3
（7） 2 1 1 6
（8） B I和J
（9） 6
（10） 2i 2i+1 i/2或
（11） 16
（12） 5 18
（13） a f 空
（14） 2 2 3
（15） 6
（16） a[2*i] a[2*i+1] a[i/2]
（17） 2i-1 2j+1
（18） a[2*i+1] a[2*i+2] a[(i-1)/2]
（19） 2n n-1 n+1
（20） 10 5
（21） 16 31
（22） 2h-1 2h-1
（23） a b c d e f c b a e d f c b e f d a a b d c e f
（24） a b e c f h I j g d a b c d e f g h i j
二、 普通题：
（7） 先序：25，16，8，37，30，28，26，29，32，35，48，60
中序：8，16，25，26，28，29，30，32，35，37，48，60
后序：8，16，26，29，28，35，32，30，60，48，37，25
第3个回答 2014-01-02
第六章答案
一、 选择题：
C B D C A D（D改为53）
二、 填空题：
（1） 小于 大于
（2） 有序序列
（3） 查找成功 左子树 右子树
（4） 2i+1 2i+2
（5） 最小值 最大值
（6） 向上 堆顶
（7） 堆尾 堆顶 向下
（8） 4
三、 普通题：
（1） 见例6.1
（2） 见例6.2
（4） ElemType FindMax(BTreeNode * BST)
{
if (BST==NULL){
cerr<<”这是一棵空树！”<<endl;
exit(1);
}
BTreeNode *t=BST;
while (t->right!=NULL)
t=t->rignt;
return t->data;
}
（7） 见例6.3
（8） 见例6.4
（9） 见例6.5
第七章答案
一、 填空题：
（1） 2
（2） n(n-1)/2 n(n-1)
（3） n-1
（4） 邻接矩阵 邻接表 边集数组
（5） n2
（6） e 2e
（7） 出边 入边
（8） e e
（9） O(n) O(e/n) O(e)
（10） O(n2) O(n+e) O(e)
（11） O(n2) O(e)
（12） 0,1,4,2,5,3 0,1,2,3,4,5
（13） A,B,C,D,E A,B,C,E,D
（14） n n-1
（15） 22
（16） (0,1)5 (1,3)3 (3,2)6 (1,4)8
（17） (1,3)3 (0,1)5 (2,3)6 (1,4)8
（18） 栈
二、 普通题：
（3）
1、
图 DFS BFS
（a） 0,1,2,8,3,4,5,6,7,9 0,1,4,2,7,3,8,6,5,9
（b） 0,1,2,5,8,4,7,3,6 0,1,3,4,2,6,7,5,8
2、
图 DFS BFS
（a） 0,4,3,8,9,5,6,7,1,2 0,4,1,3,7,2,8,6,9,5
（b） 0,4,7,5,8,3,6,1,2 0,4,3,1,7,5,6,2,8
（6）
1、权为46
2、 （0,1）6，（1,6）4，（6,2）9，（2,3）5，（3,4）10，（0,5）12
3、 （1,6）4，（2,3）5，（0,1）6，（2,6）9，（3,4）10，（0,5）12
（7）拓扑序列为：1，4，0，2，3，5，7，6，8，9
一、 选择题：
C B D C A D（D改为53）
二、 填空题：
（1） 小于 大于
（2） 有序序列
（3） 查找成功 左子树 右子树
（4） 2i+1 2i+2
（5） 最小值 最大值
（6） 向上 堆顶
（7） 堆尾 堆顶 向下
（8） 4
三、 普通题：
（1） 见例6.1
（2） 见例6.2
（4） ElemType FindMax(BTreeNode * BST)
{
if (BST==NULL){
cerr<<”这是一棵空树！”<<endl;
exit(1);
}
BTreeNode *t=BST;
while (t->right!=NULL)
t=t->rignt;
return t->data;
}
（7） 见例6.3
（8） 见例6.4
（9） 见例6.5
第七章答案
一、 填空题：
（1） 2
（2） n(n-1)/2 n(n-1)
（3） n-1
（4） 邻接矩阵 邻接表 边集数组
（5） n2
（6） e 2e
（7） 出边 入边
（8） e e
（9） O(n) O(e/n) O(e)
（10） O(n2) O(n+e) O(e)
（11） O(n2) O(e)
（12） 0,1,4,2,5,3 0,1,2,3,4,5
（13） A,B,C,D,E A,B,C,E,D
（14） n n-1
（15） 22
（16） (0,1)5 (1,3)3 (3,2)6 (1,4)8
（17） (1,3)3 (0,1)5 (2,3)6 (1,4)8
（18） 栈
二、 普通题：
（3）
1、
图 DFS BFS
（a） 0,1,2,8,3,4,5,6,7,9 0,1,4,2,7,3,8,6,5,9
（b） 0,1,2,5,8,4,7,3,6 0,1,3,4,2,6,7,5,8
2、
图 DFS BFS
（a） 0,4,3,8,9,5,6,7,1,2 0,4,1,3,7,2,8,6,9,5
（b） 0,4,7,5,8,3,6,1,2 0,4,3,1,7,5,6,2,8
（6）
1、权为46
2、 （0,1）6，（1,6）4，（6,2）9，（2,3）5，（3,4）10，（0,5）12
3、 （1,6）4，（2,3）5，（0,1）6，（2,6）9，（3,4）10，（0,5）12
（7）拓扑序列为：1，4，0，2，3，5，7，6，8，9
