数据结构(第4版)习题及实验参考答案-数据结构复习资料(c语言版).docx

数据结构基础及深入及考试
复习资料
习题及实验参考答案见附录
结论
1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据 的存储无关，是独立于计算机的。
2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。 它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列
3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构 成，并包括•组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使 用与实现分离，实行封装和信息隐蔽（独立于计算机）。
4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换 为输出的计算步骤。
5、在数据结构中，从逻辑上可以把数据结构分成（C ）
A、动态结构和表态结构B、紧凑结构和非紧凑结构
C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A ）
A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态线性表
1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时， 插入一个元素所需移动元素的平均次数为（E ）,删除一个元素需要移动的元素的个数 为（A ）o
A、（n-l）/2 B、n C、n+1 D、n-1 E、n/2 F、（n+l）/2 G、（n-2）/2
3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ）
A、正确的B、错误的C、不一定，与具体的结构有关
4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）
A、必须是连续的B、部分地址必须是连续的C 一定是不连续的D连续或不连续都可 以
5、带头结点的单链表为空的判定条件是（B ）
A、hcad==NULL B、hcad->ncxt==NULL C、hcad->next=hcad D、hcad!=NULL
6、不带头结点的单链表head为空的判定条件是（A ）A、hcad==NULL B、hcad->ncxt==NULL C、hcad->ncxt=hcad D、head!二NULL
7、非空的循环单链表head的尾结点P满足（C ）
A、p->ncxt==NULL B、p==NULL C、p->ncxt==hcad D、p==hcad
8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 （B ）附录习题及实验参考答案习题1参考答案1.1.选择题
(1). A.⑵.A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). C. (9). B. (10.) A.
12填空题.数据关系.逻辑结构物理结构.线性数据结构树型结构图结构
(1) .顺序存储链式存储索引存储散列表(Hash)存储.变量的取值范围操作的类别.数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系.关系网状结构树结构
(2) .空间复杂度和时间复杂度.空间时间. O(n)1.3名词解释如下：
数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。 数据元素:数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理, 一个数据元素可由若干个数据项组成。
数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。
数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。
数据类型：是指变ht的取值范围和所能够进行的操作的总和。
算法：是对特定问题求解步骤的•种描述，是指令的有限序列。
1.4语句的时间复杂度为：
⑴。(的⑵。(盼。(殆O(n-l)
(3) 。(砖1.5参考程序：
main。
{int X,Y,Z；scanf( “％d,%d,%d”，&X,&Y,Z);if(X>=Y)
if(X>=Z)if(Y>=Z){ printf( “％d,%d,%d”，X,Y,Z);}else
( printf( “％d,%d,%d”，X,Z,Y);} else{ printf( “％d,%d,%d" ,Z,X,Y);} else
if(Z>=X)if(Y>=Z){ printf( “％d, %d, %d”，Y,Z,X);} else{ printf( “％d, %d, %d”，Z,Y,X);}
else{ printf( "％d, %d, %d”，Y,X,Z);}1.6参考程序：
mainQ{int i,n;float x,a|J,p;
printf( "\nn=" );scanf( ，&n); printf( "\nx=" );scanf( "%f” ,&x); for(i=0;i<=n;i++)scanf( "%f” ,&a[i]);P=a[0]; for(i=1;i<=n;i++)( p=p+a[i]*x;
x=x*x;}printf( "％f”，p)'习题2参考答案2.1选择题
(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.
22填空题.有限序列.顺序存储和链式存储, s->next=p->next; p->next=s;
⑶.
O(n)
O(n)
(4).
n-i+1
n-i
(5).
链式

(6).
数据
指针
⑺.
前驱
后继
(8).
0(1)
。⑥
(9) . s->next解题思路:将顺序表A中的元素输入数组a,若数组a中元素个数为n,将下标为0,1,2，…, (n-1) /2的元素依次与下标为…，(n-1) /2的元素交换，输出数组a的元素。
参考程序如下：
main。
(int i,n;floatprintf( "\nn=" );scanf( "%「'，&n);
for(i=0;i <=n-1 ;i++)scanf( "％f”，&a[i]);for(i=0;i<=(n-l)/2;i++){ t=a[i]; a[ij =a[n-l-i]; a[n-l-ij=t;}
for(i=0;i<=n-l ;i++)printf( "%「'，a[i])；}2.4算法与程序：
mainQ{int i,n;float t,aQ；
printf( "\nn=" );scanf( "%f” ，&n);for(i=0;i<n;i++)scanf( "%f " ,&a国)；for(i=l;i<n;i++)
{ t=a[i]; a[i] =a[0];a[0]=t;}printf( "％f" ,a[0]);fbr(i=2;i<n;i++){t=a[i]; a[i] =a[l];a[l]=t;}
printf( "%f” ,a[0]);2.5算法与程序: mainQint i,j,k,n;float x,t,a[]；
printf( "\nx=" );scanf( "%广，&x);printf( "\nn=" );scanf( "%f" ，&n); fbr(i=O;iVn;i++)scanf( "％f”，&a[i]);//输入线性表中的元素tor (i=0; i<n; i++) {//对线性表中的元素递增排序
k=i；
for (j=i+l; jvn; j++) if (a[j]<a[k]) k=j;
if (k<>j) (t=a[i];a[i]=a[k];a[k]=t;)for(i=0;i<n;i++)//在线性表中找到合适的位置
//移动线性表中元素，然后插入元素x
//依次输出线性表中的元素
if(a[i]>x) break; for(k=n-l;k>=i;i-)
a[k+l]=a[k];
a[i]=x;
for(i=0;i<=n;i++)printf( ,a[i]);2.6算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给 C,如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的 容量要能够容纳A、B两个线性表相加的长度。
有序表的合并算法：
void merge (SeqList A, SeqList B, Seql Jst *Q｛际 i, j, k；
i=0； j=0； k=0；
while (i<=A.last && j<=B.last)
if (A.data[i]<=B.data[jl)C->data[k++]=A.data[i++]；
elseC->data[k++]=B.data[j++]；while (i<=A.last)
C->data[k++] = A.data[i++]；while (j<=B.last)
C->data[k++]=B.data[j++]；C->last=k-l ；2.7算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C,如此直到线性 表扫描完毕，线性表C就是所求递增有序线性表。
算法：
void tnerge (SeqList A, SeqList B, SeqList *C)｛血 i, j, k；
i=0; j=0; k =0;
while (i<=A.last)while (jv=B.last)if (A.data[i]=B.data[jDC->data[k++]=A.data[i++]；
C->last = k-1;习题3参考答案3.1.选择题. D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB
(I) . D (12). B (13). D (14). C (15). C (16). D(17). B (18). C (19). C (20). C 32填空题3.3答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表
(1)
FILO, FIFO
(2)
-1,34X* + 2Y*3/-
(3)
srack.top++, stack.s[stack.top]=x
(4)
p>llink->rlink=p->rlink, p->dink->llink=p->rlink
(5)
(R-F+M)%M
(6)
top! +I=top2
(7)
F==R
(8)
front==rcar
(9)
front==(rcar+l)%n
(10)
N-l
栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出 栈”（pop）。
3.4答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。
不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（砰）删除，一端（「河）插 入。
3.5 答:可能序列有 14 种:ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。
3.6答：不能得到4, 3, 5, 6, 1, 2,最先出栈的是4,则按321的方式出，不可能得到1 在2前的序列，可以得到1, 3, 5, 4, 2, 6,按如下方式进行push(l),
popO, push(2), push(3), pop。, push(4), push(5), popO, popO, pop。, push(6), pop。。
3.7 答：stack3.8非递归：
int vonvcrt (int no,int a[]) 〃将十进制数转换为2进制存放在a[],并返回位数 {int r;SeStack s,*p;P=&s;
Init_stack(p);while(no)(push(p,no%2);
no/=10;}r=0;whilc(!empty_stack(p))
{pop(p,a+r);r++;}
return r;}
递归算法：
void convert(in t no)(if(no/2>0){
Convert(no/2);Printf( "％d” ,no%2);}else
printf( ,no);
}3.9参考程序：
void view(SeStack s){SeStack *p; 〃假设栈元素为字符型char c;
p=&s;while(!empty_stack(p)){c=pop(p);
printf( "%c” ,c);printff \nw );}3.10 答：char
3.11参考程序：
void outflinkqucuc q){
int c;
while(q.rear !=q.front) {dcqucuc(q,c);print(e); 〃打印
}
}习题4参考答案4.1选择题：
⑴.A (2). D (3). C (4). C (5). B (6). B 4.2填空题：
(7). D (8). A (9). B (10). D
(1) 串长相等且对应位置字符相等不含任何元素的串，0所含字符均是空格，所含空格数10
(2) "hclloboy”181066由零个或多个任意字符组成的字符序列
(3) 串中所含不同字符的个数36StrLcngth (s)=14, StrLcngth (t)=4, SubStr( s, 8,7)=" STUDENT”，SubStr(t, 2, 1)=” O”， Strlndcx(s, “A” )=3, Strindex (s, t)=0, StrRcp(s, “STUDENT”，q)=” I AM A WORKER",StrRcp(s," Y” +" );StrRcp(s,"*Y” );
4.5空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过 程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符
4.6int EQUA1(S；O{char *p,*q;
p=&S;q=&T； while(*p&&*q){if(*P=*q) rcuirn *p-*q;
])++；q++；}return *p-*q;
}
4.76*8*6=2881000+47*6=12821000+(8+4)*6=1072
(1) 1000+(6*7+4)*6=12764.8矩阵的三元组表

i
j
V
i
1
2
1
2
1
5
-I
3
2
1
4
4
3
4
7
5
4
2
6
6
5
1
8
7
5
3
9
习题5参考答案5.1选择
(1) C (2) B (3) C (4) B (5) C (6) D (7) C (8) C (9) B (10) C
(4) B (12) C (13) C (14) C (15) C5.2填空
(1) 1
(2) 1036； 1040
(3) 2i
(4) [； n ;n-1;2
(5) 坦；2M
(6)
(7)
(8)
(9)
ACDBGJKIHFE
p!=NULL
Huffrnan 树
其第一个孩子;下一个兄弟
(10) 先序遍历;中序遍历
5.3
叶子结点:C、F、G、L、I、M、K; 非终端结点：A、 各结点的度： 结点： 度：
B、D、E、J;
L I J K M
0100
树深:
5.4
无序树形态如下:
OAYO
二叉树形态如下:

5.5二叉链表如下:
A、0（1） B、O（n） C、OS2） D、O（nlogjn）
9、在一个单链表中，若删除p所指结点的后继结点，则执行（A ）A、p->next=p->next->next;B、p=p->next;p->ncxt=p->next->ncxt;C、p->next=p->next;
D、p= p->next->next;
10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（B ）
A、s->next=p;p->next=s;
B、s->ncxt=p->ncxt;p->ncxt=s;
C、s->next=p->next;p=s;
D、p->ncxt=s;s->ncxt=p;
11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s,则执行（C ）
A、s->next=p->ncxt;p->ncxt=s;
13、p->next=s->next;s->next=p;
C、q->next=s;s->next=p;
D、p->ncxt=s;s->ncxt=q;12、在线性结构中，第一•个结点没有前趋结点，其余每个结点有且只有1 个前趋结点。
栈和队列1、在栈操作中，输入序列为（A, B, C, D）,不可能得到的输出数列是（D ）
A、（A, B, C, D）B、（D, C, B, A）
C、（A, C, D, B）D、（C, A, D, B）2、设栈ST用顺序存储结构表示，则栈ST为空的条件（B ）
A、ST.top=ST.basc<>0B、Sl'.top=ST.basc==0C、ST.top=ST.base<>nD、ST.top=ST.base==n3、向一个栈顶指针为HS的链栈中插入一个s结点时，执行（C ）
A、HS->next=s;s->next=HS->next;HS->next=s;
C、s->next=HS;HS=S;D、s->next=HS;HS=HS->next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删结点的值，则执行（C ）
A、x=HS;HS=HS->next;HS=HS->next;x=HS->data;
C、x=HS->data;HS=HS->ncxt; D、s->ncxt=HS;HS=HS->ncxt;5、用单链表表示的链示队列的队头在链表的（ A ）位置。
A、链头 B、链尾 C、链中6、判定一个链队列Q （最多元素个数为n）为空的条件是（ A ）
A、Q.front==Q.rearB、Q.front!=Q.rcar
C、Q.front==（Q.rear+ l）%nD、Q.front!=（Q.rear+l）%n7、在链队列Q中，插入要所指结点需顺序执行的指令是（B ）
A、Q.front->ncxt=s;f=s;
Bn Q.rear->next=s;Q.rear=s;
C、s->ncxt=Q.rcar;Q.rcar=s;
D、s->next=Q.front;Q.front=s;5.6
先序遍历序列:ABDEM1CIJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DIUE BJFGCA 5.7
(1) 先序序列和中序序列相同：空树或缺左子树的单支树；
(2) 后序序列和中序序列相同：空树或缺右子树的单支树；
(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。
5.8这棵二叉树为:

5.9先根遍历序列:ABi'GLCDlEJMK后根遍历序列:FGLBCIDMJKEA
层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n,叶子结点数为n。，则n=n0 + rij ++nm(1)
再设树中分支数目为B,则B=ri| + 2。2 + 3r)3 ++ m nm(2)因为除根结点外，每个结点均对应一个进入它的分支，所以有 n=B + 1(3)将⑴和(2)代入(3),得
rin + n】++ nm = rij + 2。2 + 3由 ++m nm + 1从而可得叶子结点数为：
n0 = n2 + 2n.3 ++(m-l)nrn + 15.11由5.10结论得，山二«-1加+1乂由 n=n0+ nk , nk= n-n0,代入上式，得
n(l= (k-1) (n-no) + 1叶子结点数为：ntl=n(k-l)/k5.12int NodeCount(BiTrec T)
{〃计算结点总数
if (T-> lchild==NULL)&&(T-> rchikl==NULL)
return 1;
elsereturn NodeCount(T-> Ichild ) +Node (T —> rchild )+1;elsereturn 0;
5.13void ExchangeLR(Bitree bt)(/*将bt所指二叉树中所有结点的左、右子树相互交换*/if (bt && (bt->lchild | | bt->rchild)) (
bt->lchild<->bt->rchild;
Exchangc-lr(bt->lchild);
Exchange-lr(bt->rchild);}}/* ExchangeLR */5.14
int IsFullBitrec(Birree T)(/*是则返回1,否则返回Oo */
Init_Qucue(Q); /* 初始化队列*/
flag=0;
In_Queue(Q, T);/*根指针入队列，按层次遍历*/
while(!Empty_Queuc (Q))
(
Out_Queue(Q,p);
if(!p) flag=1; /*若本次出队列的是空指针时，则修改flag值为1。若以后出队列的指针 存在非空，则可断定不是完全二叉树*/
else if (fl疫)return 0; /*断定不是完全二叉树*/
else
{
In_Queue(Q, p->lchild);
In_Queue(Q, p->rchild);/*不管孩子是否为空，都入队列。*/
}
}/* while */
return 1; /*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉 树*/}/* IsFullBitree */5.15转换的二叉树为：
BG乙O (S) O
(c)B<e)@(a)
5.16对应的森林分别为:
B
(d)

5.17
typedeF char elemtype;
typcdcf struct{ elemtype data;int parent;} NodeType;
⑴求树中结点双亲的算法：
inr Parent(NodcType t[], elemtype x){/* x不存在时返回2否则返回x双亲的下标(根的双亲为-1 */ for(i=0;i<MAXN()DE;i++)
if(x==t[i].data) return t(i].parent;
return -2;}/*Parent*/求树中结点孩子的算法：
void Childrcn(NodcTypc t[], elemtype x)( for(i=0;i<MAXNODE;i++) {
if(x==t[i].data)break;/*找到x,退出循环*/
}/*for*/
if(i>=MAXNODE) printf( “x 不存在\n” );
else {flag=0；fbrO=0;j<MAXNODE;j++)if(i==t|j].parent)
{ printf( "x 的孩子:%c\n” ,t[j].data);flag=1;}if(flag==0) printf( "x 无孩子\n” )；
}(/♦Children*/5.18
typedef char elemtype;typedef struct ChildNode{ int childcode;
struct ChildNodc *nextchild;}typedef struct{ elemtype data;
struct ChildNode *firstchild;} NodeType;⑴求树中结点双亲的算法：
int ParentCL(NodeType t[], elemtype x){/* x不存在时返回-2,否则返回x双亲的下标*/ fbr(i=O;ivMAXN()DE;i++)
if(x==t[i].data) (loc=i;/*记下x的下标*/
break;
if(i>=MAXNODE) return -2; /* x 不存在 */
/*搜索x的双亲*/
for(i=0;i<MAXN()DE;i++)
fbr(p=t[i].firstchild;p!=NULL;p=p->nextchild)if(loc==p->childcode)return i; /*返回x结点的双亲下标*/
} /* ParentL */(2)求树中结点孩子的算法：
void ChildrenCL(NodeT\pe t[ ], clcmtypc 对{
for(i=0;i<MAXNODE;i++)if(x==t[il.data) /*依次打印x的孩子*/{flag=0; /* x 存在 */
fbr(p=t[i].firstchild;p;p=p->nextchild)( printf( "x 的孩子:%c\nw ,t[p-> childcodc].data);
flag=l;}if(flag==0) printf( "x 无孩子\n")； return;
)/*if*/
printF( "x 不存在\n” )；
return;}/* ChildrcnL */5.19
typedef char el cm type;typedef struct TreeNode{ el em type data;struct TrccNodc *firstchild;
struct TreeNode *nextsibling;
} NodcTypc;void ChildrenCSL(NodeType *t, elemtype 对{/* 层次遍历方法 */
Init_Queue(Q); /* 初始化队列 */ln_Queue(Q,t);
count=0;\vhile(!Empty_Qucuc (Q)) {()ut_Queue(Q,p);if(p->data==x)
{ /*输出x的孩子*/p=p->firstchild;if(!p) printf("无孩子\n")；else
{ printf( "x 的第％i 个孩子:％c\n" ,++count, p->data);/*输出第一个孩子*/ p=p->nextsibling; /*沿右分支*/whilc(p) {printf( "x 的第％i 个孩子:%c\n” , ++count, p->data);p=p-> nextsibling;
}}return;
}if(p-> firstchild) ln_Qucuc(Q,p-> firstchild);if(p-> nextsibling) ln_Qucuc(Q,p-> nextsibling);}
}/* ChildrenCSL */5.20⑴哈夫曼树为:
(2)在上述哈夫曼树的每个左分支上标以1,右分支上标以0,并设这7个字母分别为A、B、C、D、E、F和H,如下图所示：
则它们的哈夫曼树为分别为:
A: 1100B: 1101C: 10D: Oil
E: 00F: 010H: 111习题6参考答案
条边。(6) B (7) A (8) A (9) B (10) A 6) A (17) C
6.1选择题
(I) C (2) A (3) B (4) C (5) B—
(II) A (12) A (13) B (14) A (15) B6.2填空
(1) 4
(2) 1对多 ； 多对多
(3) n-1; n
(4) _J
(5) 有向图
(6) _J
(7) 一半
(8) 一半
(9) ―第i个链表中边表结点数—
(10) _第i个链表中边表结点数_
(10深度优先遍历;广度优先遍历
(5) C (/)
(6) ―无回路6.3
(1)邻接矩阵：
0
1
1
1
0
1
0
0
1
1
1
0
0
0
1
1
1
0
0
1
0
1
1
1
0

(2)邻接链表:
0123
4每个顶点的度:
顶点
度
VI
3
V2
3
V3
2
V4
3
V5
3
6.4
(1)邻接链表:
VI
A
V2

V3

V4

V5

V6

123
450
3

| 5
-
| 5
-
L 2.
A_

-4

-L_i_

逆邻接链表:
1234
52/\(3)顶点 入度
出度VIV2V3
V4321
1022
3

8、在一个链队列Q中，删除一个结点需要执行的指令是（C ）A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->ncxt=Q.front->next->ncxt;
D、Q. fron t=Q.rear->next;9、栈和队列的共同点（C ）A、都是先进后出B、都是先进先出
C、只允许在端点处插入和删除元素D、没有共同点10、栈的特点是—先进后出，队列的特点是先进先出11、线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只 能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。
串和数组1、设串 si='ABCDEFG' ,s2='PQRST'，函数Concat（x,y）返回 x和y 串的连接串,Substr（s,l,j） 返回串s从序号i开始的j个字符组成的子串，length（s）返Is!串s的长度，则Concat（Substr（sl,2, length（s2）, Substr（slJength（s2）,2））的结果串是（D ）A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF2、串是一种特殊的线性表，其特殊性体现在（D ）
A、可以顺序存储 B、数据元素是一个字符C、可以链接存储 D、数据元素可以是多个字符3、设有两个串p和q,求q在p中首次出现的位置的运算称作（B ）A、连接 B、模式匹配C、求子串联 D、求串长
4、串的两种最基本的存储方式是顺序存储方式和链接存储方式。
树和二叉树1、树最合适用来表示（B ）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据
2、按照二叉树的定义，具有3个结点的二叉树有（ C ）种。
A、3 B、4 C、5 D、63、在一棵有n个结点的二叉树中，若度为2的结点数为n2,度为1的结点数为n】，度为0 的结点数为所，则树的最大高度为（E ），其叶结点数为（ G ）；树的最小高 度为（B ）,其叶结点数为（ G ）;若采用链表存储结构，则有（I ） 个空链域。
A、n/2 B、[logjn] + lC、logjn D、n E、n（）+ni + ri2 F、n】+ n?
G、n2 +1 H、1 I、n+1 J、n】 K、n? L、n】+14、在一棵二叉树上第5层的结点数最多为（B ）。（假设根结点的层数为0）A、8 B、16 C、15 D、325、深度为5的二叉树至多有（C ）个结点。
A、16 B、32 C、31 D、106、在一非空二叉树的中序遍历序列中，根结点的右边（ A ）A、只有右子树上的所有结点 B、只有右子树上的部分结点
V5V66.5
(1) 深度优先查找遍历序列:VI V2 V3 V4 V5; VI V3 V5 V4 V2; VI V4 V3 V5 V2
(1) 广度优先查找遍历序列:VI V2 V3 V4 V5; VI V3 V2 V4 V5; VI V4 V3 V2 V56.6
6.6

6.6
<s>—

6.7最小生成树的示意图如下:

最小生成树的示意图如下:
6.8

顶 点
(1)
(2)
(3)
(4)
(5)
Low Close
I -ow Close
Low Close
Ix>w Close
Low Close
VI
01
01
01
01
01
V2
1 1
01
01
01
01
V3
1 1
1 1
01
01
01
V4
31
22
22
02
02
V5
co 1
52
33
24
04

U
{vl}
{vl,v2}
(vl,v2,v3}
{vl, v2, v3, v4)
(vl, v2, v3, v4, v5}
T
(}
{ (vl,v2) }
"2),
(vl,v3) }
((vl,v2),
(vl,v3), (v2,v4) }
((v1,v2),
(vl,v3), (v2,v4), (v4,v5) }

拓扑排序结果：V3 V1 V4 V5 V2 V66.9建立无向图邻接矩阵算法：
提示：参见算法6.1因为无向图的邻接矩阵是对称的，所以有for (k=0; k<G ->e; k++) /*输入e条边，建立无向图邻接矩阵*/{ scanf("\n%d,%d”,&i,&j);
G->edges[i][j]= G->edgps[j][i]= 1;}⑵建立无向网邻接矩阵算法：
提示：参见算法6.1 o初始化邻接矩阵：
#dcfinc INFINITY 32768 /* 表示极大值*/for(i=03<G->n;i++)for(j=0;j<G->n;j++) G->cdges[i][j]= INFINITY;输入边的信息：
不仅要输入边邻接的两个顶点序号，还要输入边上的权值for (k=0; k<G ->c; k++) /*输入c条边，建立无向网邻接矩阵*/{ scanf(”\n%d,%d,%d”,&i,&j,&ccst); /* 设权值为 int 型*/
G ->cdgcs[i][j]= G ->cdgcs[j](i]=cost;/*对称矩阵*/}(3)建立有向图邻接矩阵算法：
提示：参见算法6.1。
6.10⑴建立无向图邻接链表算法：
typcdef VcrtexType char;int Create_NgAdjList(ALGraph *G){/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/scanfC'%d",&n); if(n<0) return -1; /* 顶点数不能为负 */
G->n=n;scanfCWdC&e); if(e<0) return =1; /*边数不能为负 */G->e=e;for(m=0;m< G->n ;m++)
G-> adjlist lm].firstcdgc=NULL; /*置每个单链表为空表*/fc)r(m=0;m< G->n;m++)
G->adjlist[m].vcrtcx=gctchar(); /*输入各顶点的符号*/ fc)r(m=l;m<= G->e; m++){
scanf( "\n%d, %d" ,&i,&j);/* 输入一•对邻接顶点序号*/if((ivO | | j<0) return -1;p=(EdgeNode*)malloc(sizeof(EdgeNocle));/*在第 i+1 个链表中插入一个边表结点*/ p->adjvex=j;p->next= G-> adjlist [i].firstedge;G-> adjlist [i