2022年《数据结构》课后习题答案 .pdf

《2022年《数据结构》课后习题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构》课后习题答案 .pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、附录 习题参考答案习题 1 参考答案1.1. 选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2. 填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（ Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). (n) 1.3 名词解释如下：数据

2、： 数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项： 数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型： 是指变量的取值范围和所能够进行的操作的总和。算法： 是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：(1) (n2) (2) (n2) (3) (n2)(

3、4) (n-1) (5) (n3) 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - else printf(%d, %d, %d,Z,X,Y); else

4、 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 参考程序：main() int i,n; float x,a,p; printf(nn=);scanf(%f,&n); printf(nx=);scanf(%f,&x); for(i=0;i=n;i+) scanf(%f,&ai); p=a0; for(i=1;inext=p-next; p-next=s ; (10). s-next 2.3. 解题思路：将顺序表A中的元素输入

5、数组a，若数组a 中元素个数为n, 将下标为0，1,2, , （n-1 ）/2 的元素依次与下标为n,n-1, , （n-1 ）/2 的元素交换，输出数组a 的元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - 参考程序如下：main() int i,n; float t,a; printf(nn=);scanf(%f,&n); for(i=0;i=n-1;i+) scanf(%f,&ai); for(i=0;i=(n-1)

6、/2;i+) t=ai; ai =an-1-i; an-1-i=t; for(i=0;i=n-1;i+) printf(%f,ai); 2.4 算法与程序：main() int i,n; float t,a; printf(nn=);scanf(%f,&n); for(i=0;in;i+) scanf(%f,&ai); for(i=1;ia0 t=ai; ai =a0; a0=t; printf(%f,a0); for(i=2;ia1 t=ai; ai =a1; a1=t; printf(%f,a0); 2.5 算法与程序：main() int i,j,k,n; float x,t,a; pr

7、intf(nx=);scanf(%f,&x); printf(nn=);scanf(%f,&n); for(i=0;in;i+) scanf(%f,&ai); /* 输入线性表中的元素*/ for (i=0; in; i+) /* 对线性表中的元素递增排序 */ k=i; for (j=i+1; jn; j+) if (ajak) k=j; if (k!=j) t=ai;ai=ak;ak=t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - -

8、- - - - for(i=0;ix) break; for(k=n-1;k=i;i-) /* 移动线性表中元素，然后插入元素x*/ ak+1=ak; ai=x; for(i=0;i=n;i+) /* 依次输出线性表中的元素 */ printf(%f,ai); 2.6 算法思路：依次扫描A和 B的元素，比较A、B当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C 即可。 C 的容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：void merge (SeqList A, SeqList B, SeqList *C) int i，

9、j ，k； i=0；j=0 ；k=0； while ( i=A.last & j=B.last ) if (A.dataidatak+=A.datai+； else C-datak+=B.dataj+；while (idatak+= A.datai+；while (jdatak+=B.dataj+；C-last=k-1； 2.7 算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性表扫描完毕，线性表C就是所求递增有序线性表。算法：void merge (SeqList A, SeqList B, SeqList *C) int i， j ，k； i=0；j=0 ；k=0

10、； while ( i=A.last) while （jdatak+=A.datai+； C-last=k-1；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 习题 3 参考答案3.1. 选择题(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D

11、(17). D (18). C (19). C (20). C 3.2. 填空题（1）FILO, FIFO （2）-1, 3 4 X * + 2 Y * 3 / - （3）stack.top, stack.sstack.top=x （4）pllink-rlink=p-rlink, p-rlink-llink=p-rlink （5）(R-F+M)%M （6）top1+1=top2 （7）F=R （8）front=rear （9）front=(rear+1)%n （10） N-1 3.3 答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在

12、线性表的一端插入（称为入栈,push ）或者读取栈顶元素或者称为“弹出、出栈”(pop) 。3.4 答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top ）删除，一端(rear)插入。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

13、， 5， 4， 2， 6， 按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。 3.7 答： stack 3.8 非递归 : int vonvert (int no,int a) /将十进制数转换为2 进制存放在a ，并返回位数 int r; SeStack s,*p; P=&s; Init_stack(p); while(no) push(p,no%2); no/=10; 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

14、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - r=0; while(!empty_stack(p) pop(p,a+r); r+; return r; 递归算法 : void convert(int no) if(no/20) Convert(no/2); Printf(“%d ”,no%2); else prin tf( “%d ”,no); 3.9 参考程序：void view(SeStack s) SeStack *p; /假设栈元素为字符型char c; p=&s; while(!e

15、mpty_stack(p) c=pop(p); printf(“%c ”,c); printf(”n”); 3.10 答： char 3.11 参考程序：void out(linkqueue q) int e; while(q.rear !=q.front ) dequeue(q,e); print(e); /打印 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 习题 4 参考答案4.1 选择题：(1). A (2). D (

16、3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空题：（1）串长相等且对应位置字符相等（2）不含任何元素的串，0 （3）所含字符均是空格，所含空格数（4）10 （5）“hello boy ”（6）13 （7）1066 （8）模式匹配（9）串中所含不同字符的个数（10） 36 4.3 StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=” STUDENT ”, SubStr(t，2，1)=”O ”,StrIndex(s,“A”)=3, StrIndex (s ， t)=0,

17、StrRep(s ， “STUDENT”，q)=” I AM A WORKER”,4.4 StrRep(s,”Y”, ”+”);StrRep(s,”+*”, ”*Y”);4.5 空串：不含任何字符；空格串：所含字符都是空格串变量和串常量: 串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值: 串变量的名字表示串值的标识符 4.6 int EQUAl(S,T) char *p,*q; p=&S; q=&T; while(*p&*q) if(*p!=*q) return *p-*q; p+; q+; r

18、eturn *p-*q; 4.7 (1)6*8*6=288 (2)1000+47*6=1282 (3)1000+(8+4)*8=1096 (4)1000+(6*7+4)*8=1368 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - 4.8 习题 5 参考答案5.1 选择（1）C（2） B（3）C（4） B（5）C（6）D（7）C （ 8）C（9）B（10）C （11）B（12）C（ 13）C（ 14）C（ 15）C（ 16）B

19、 5.2 填空（1）1 （2）1036； 1040 （3）2i （4） 1 ； n ; n-1 ; 2 （5）2k-1；2k-1 （6）ACDBGJKIHFE （7）p!=NULL （8）Huffman 树（9）其第一个孩子; 下一个兄弟（10）先序遍历；中序遍历5.3 叶子结点 :C、F、G、L、I 、M 、K ；非终端结点： A、B、D、E、J；各结点的度：结点： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0 树深： 4 5.4 无序树形态如下：i j v 1 1 2 1 2 1 5 -1 3 2 1 4 4 3 4 7 5 4 2

20、6 6 5 1 8 7 5 3 9矩阵的三元组表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 二叉树形态如下：5.5 二叉链表如下 : 三叉链表如下 : A B C D E F G H I J A B C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 5.

21、6 先序遍历序列 :ABDEHICFJG 中序遍历序列 :DBHEIAFJCG 后序遍历序列 :DHIEBJFGCA 5.7 (1) 先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。5.8 这棵二叉树为 : 5.9 先根遍历序列 :ABFGLCDIEJMK 后根遍历序列 :FGLBCIDMJKEA 层次遍历序列 :ABCDEFGLIJKM 5.10 证明：设树中结点总数为n，叶子结点数为n0，则n=n0 + n1 + , + nm （ 1）再设树中分支数目为B，则B=n1 + 2n

22、2 + 3n3+ , + m nm （ 2）D E F G H I J 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 （ 3）将（ 1）和（ 2）代入（ 3） ，得n0 + n1 + , + nm = n1 + 2n2 + 3n3+ , + m nm + 1 从而可得叶子结点数为：n0 = n2 + 2n3+ , + (m-1)nm + 1 5.11

23、由 5.10 结论得， n0 = (k-1)nk + 1 又由 n=n0 + nk，得 nk= n-n0，代入上式，得n0 = (k-1)（ n-n0）+ 1 叶子结点数为：n0 = n (k-1) / k 5.12 int NodeCount(BiTree T) /计算结点总数if(T) if (T- lchild=NULL )&( T - rchild=NULL ) return 1; else return NodeCount(T- lchild ) +Node ( T - rchild )+1; else return 0; 5.13 void ExchangeLR(Bitree bt

24、) /* 将 bt 所指二叉树中所有结点的左、右子树相互交换 */ if (bt & (bt-lchild | bt-rchild) bt-lchildbt-rchild; Exchange-lr(bt-lchild); Exchange-lr(bt-rchild); /* ExchangeLR */ 5.14 int IsFullBitree(Bitree T) /* 是则返回 1，否则返回0。*/ Init_Queue(Q); /* 初始化队列 */ flag=0; In_Queue(Q ，T); /* 根指针入队列，按层次遍历*/ while(!Empty_Queue (Q) Out_Q

25、ueue(Q,p); if(!p) flag=1; /* 若本次出队列的是空指针时，则修改flag值为 1。若以后出队列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 的指针存在非空，则可断定不是完全二叉树 */ else if (flag) return 0; /*断定不是完全二叉树 */ else In_Queue(Q，p-lchild); In_Queue(Q，p-rchild); /* 不管孩子是否为空，都入队列。*

26、/ /* while */ return 1; /* 只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树 */ /* IsFullBitree */ 5.15 转换的二叉树为：5.16 对应的森林分别为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 5.17 typedef char elemtype; typedef struct elemtype data; int parent; NodeType;

27、 (1) 求树中结点双亲的算法: int Parent(NodeType t , elemtype x) /* x不存在时返回 -2, 否则返回 x 双亲的下标 ( 根的双亲为 -1 */ for(i=0;iMAXNODE;i+) if(x=ti.data) return ti.parent; return -2; /*Parent*/ (2) 求树中结点孩子的算法: void Children(NodeType t , elemtype x) for(i=0;i=MAXNODE) printf(“x 不存在 n ”); else flag=0; for(j=0;jMAXNODE;j+) if

28、(i=tj.parent) printf(“ x 的孩子 :%cn ”,tj.data); flag=1; if(flag=0) printf(“x 无孩子 n ” ); /*Children*/ 5.18 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - typedef char elemtype; typedef struct ChildNode int childcode; struct ChildNode *nextc

29、hild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; (1) 求树中结点双亲的算法: int ParentCL(NodeType t , elemtype x) /* x不存在时返回-2, 否则返回x 双亲的下标 */ for(i=0;i=MAXNODE) return -2; /* x不存在 */ /*搜索 x 的双亲 */ for(i=0;inextchild) if(loc=p-childcode) return i; /*返回 x 结点的双亲下标*/ /* ParentL */ (2) 求

30、树中结点孩子的算法: void ChildrenCL(NodeType t , elemtype x) for(i=0;inextchild) printf(“ x 的孩子 :%cn ”,tp- childcode.data); flag=1; if(flag=0) printf(“x 无孩子 n ”); return; /*if*/ printf(“x 不存在 n ”); return; /* ChildrenL */ 5.19 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14

31、 页，共 29 页 - - - - - - - - - typedef char elemtype; typedef struct TreeNode elemtype data; struct TreeNode *firstchild; struct TreeNode *nextsibling; NodeType; void ChildrenCSL(NodeType *t, elemtype x) /* 层次遍历方法 */ Init_Queue(Q); /* 初始化队列 */ In_Queue(Q,t); count=0; while(!Empty_Queue (Q) Out_Queue(Q,

32、p); if(p-data=x) /*输出 x 的孩子 */ p=p-firstchild; if(!p) printf(“无孩子 n ”); else printf(“x 的第 %i 个孩子 :%cn ”,+count, p-data);/*输出第一个孩子*/ p=p-nextsibling; /*沿右分支 */ while(p) printf(“x 的第 %i 个孩子 :%cn ” , +count, p-data); p=p- nextsibling; return; if(p- firstchild) In_Queue(Q,p- firstchild); if(p- nextsibli

33、ng) In_Queue(Q,p- nextsibling); /* ChildrenCSL */ 5.20 (1) 哈夫曼树为 : (2) 在上述哈夫曼树的每个左分支上标以1，右分支上标以0，并设这 7 个字母分别为A、B、69 28 16 9 41 19 22 10 5 12 7 4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - C、D、E、F 和 H，如下图所示：则它们的哈夫曼树为分别为: A：1100 B：11

34、01 C：10 D：011 E：00 F：010 H：111 习题 6 参考答案6.1 选择题（1）C （2）A （ 3）B（4）C（5）B_条边。 （6）B（7）A（8）A（9）B（10）A （11）A（12）A（ 13）B（ 14）A（ 15）B（ 16）A （17）C 6.2 填空（1） 4 （2） 1对多 ; 多对多（3） n-1 ; n （4） 0_ （5）有向图（6） 1 （7）一半（8）一半（9）_第 i 个链表中边表结点数_ （10）_第 i 个链表中边表结点数_ （11）深度优先遍历；广度优先遍历（12）O （n2）（13）_无回路6.3 名师资料总结 - - -精品资料欢迎

35、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - （1）邻接矩阵 : （2）邻接链表：（3）每个顶点的度：顶点度 V1 3 V2 3 V3 2 V4 3 V5 3 6.4 （1）邻接链表：（2）逆邻接链表：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - （3）顶点入度出度 V1 3 0 V2

36、2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3 6.5 （1）深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2 （1）广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5 6.6 有两个连通分量：6.7 顶点（1）（2）（3）（4）（5）Low Close Low Close Low Close Low Close Low Close V1 0 0 0 0 0 0 0 0 0 0 V2 1 0 0 0 0 0 0 0 0 0 V3 1 0 1 0 0

37、0 0 0 0 0 V4 3 0 2 1 2 1 0 1 0 1 V5 0 5 1 3 2 2 3 0 3 U v1 v1,v2 v1,v2,v3 v1, v2, v3, v4 v1, v2, v3, v4, v5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - T (v1,v2) (v1,v2), (v1,v3) (v1,v2), (v1,v3), (v2,v4) (v1,v2), (v1,v3), (v2,v4), (v

38、4,v5) 最小生成树的示意图如下：6.8 拓扑排序结果： V3 V1 V4 V5 V2 V6 6.9 （1）建立无向图邻接矩阵算法：提示：参见算法6.1 因为无向图的邻接矩阵是对称的，所以有for (k=0; ke; k+) /*输入 e 条边，建立无向图邻接矩阵*/ scanf(n%d,%d,&i,&j); G -edgesij= G -edgesji=1; (2) 建立无向网邻接矩阵算法: 提示：参见算法6.1 。初始化邻接矩阵：#define INFINITY 32768 /* 表示极大值 */ for(i=0;in;i+) for(j=0;jn;j+) G-edgesij= INFI

39、NITY; 输入边的信息：不仅要输入边邻接的两个顶点序号，还要输入边上的权值for (k=0; ke; k+) /*输入 e 条边，建立无向网邻接矩阵*/ scanf(n%d,%d,%d,&i,&j,&cost); /*设权值为int型*/ G -edgesij= G -edgesji=cost;/*对称矩阵 */ (3) 建立有向图邻接矩阵算法: 提示：参见算法6.1 。6.10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - -

40、 - (1) 建立无向图邻接链表算法：typedef VertexType char; int Create_NgAdjList(ALGraph *G) /* 输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表 */ scanf(%d,&n); if(nn=n; scanf(%d,&e); if(ee=e; for(m=0;mn ;m+) G- adjlist m.firstedge=NULL; /*置每个单链表为空表*/ for(m=0;mn;m+) G-adjlistm.vertex=getchar(); /*输入各顶点的符号*/ for(m=1;me; m+) scanf(“n%d,

41、 %d ”,&i,&j); /* 输入一对邻接顶点序号*/ if(i0 | jadjvex=j;p-next= G- adjlist i.firstedge; G- adjlist i.firstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode);/*在第 j+1 个链表中插入一个边表结点*/ p-adjvex=i;p-next= G- adjlist j.firstedge; G- adjlist j.firstedge=p; /* for*/ return 0; /*成功 */ /Create_NgAdjList (2) 建立有向图逆邻接链表算法：ty

42、pedef VertexType char; int Create_AdjList(ALGraph *G) /* 输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表 */ scanf(%d,&n); if(nn=n; scanf(%d,&e); if(ee=e; for(m=0;mn; m+) G- adjlist m.firstedge=NULL; /*置每个单链表为空表*/ for(m=0;mn;m+) G-adjlistm.vertex=getchar(); /*输入各顶点的符号*/ for(m=1;me ; m+) scanf(“n%d, %d ”,&t,&h); /* 输入弧

43、尾和弧头序号*/ if(t0 | hadjvex=t;p-next= G- adjlist h.firstedge; G- adjlist h.firstedge=p; /* for*/ return 0; /*成功 */ /Create_AdjList 6.11 void Create_AdjM(ALGraph *G1， MGraph *G2) /*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/ G2-n=G1-n; G2-e=G1-e; for(i=0;in;i+) /* 置 G2每个元素为0 */ for(j=0;jn;j+) G2-edgesij= 0; for(m=0;mn;m

44、+) G2-vexsm=G1-adjlistm.vertex; /*复制顶点信息 */ num= （G1-n/2=0?G1-n/2:G1-n/2+1）; /*只要搜索前n/2 个单链表即可 */ for(m=0;madjlistm.firstedge; while(p) /* 无向图的存储具有对称性*/ G2-edgesm p-adjvex = G2-edgesp-adjvex m =1; p=p-next; /* for */ /*Create_AdjM */ 6.12 void Create_AdjL(ALGraph *G1， MGraph *G2) /*通过无向图的邻接矩阵G1 ，生成无

45、向图的邻接链表G2*/ G2-n=G1-n; G2-e=G1-e; for(i=0;in;i+) /* 建立每个单链表 */ G2-vexsi=G1-adjlisti.vertex; G2-adjlisti.firstedge=NULL；for(j=i; jn; j+) /*对称矩阵，只要搜索主对角以上的元素即可*/ if(G1-edgesij= 1) p=(EdgeNode*)malloc(sizeof(EdgeNode);/*在第 i+1 个链表中插入一个边表结点*/ p-adjvex=j;p-next= G- adjlist i.firstedge; G- adjlist i.first

46、edge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode);/*在第j+1个链表中插入一个边表结点 */ p-adjvex=i;p-next= G- adjlist j.firstedge; G- adjlist j.firstedge=p; /*if*/ /* for*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 29 页 - - - - - - - - - /* for*/ /* Create_AdjL */ 6.13 (1) 邻

47、接矩阵中1 的个数的一半 ; (2) 若位于 i-1,j-1或j-1,i-1位置的元素值等于1，则有边相连，否则没有。(3) 顶点 i 的度等于第i-1行中或第 i-1列中 1的个数。6.14 (1) 邻接链表中边表结点的个数的一半; (2) 若第 i-1 （或 j-1 ）个单链表中存在adjvex 域值等于j-1 （或 i-1 ）的边表结点，则有边相连，否则没有。(3) 顶点 i 的度等于第i-1个单链表中边表结点的个数。6.15 提示：参见算法6.2 和 6.3 。习题 7参考答案7.1 选择题（1）C (2)C (3) C (4)B (5) A (6)A (7) D (8)B (9)D

48、(10) B (11)B (12)A (13)C (14)C (15)A (16)D (17)C (18)B,C (19)B (20)A 7.2 填空题（1）O(n),O(log2n) （2）1,2,4,8,5, log2(n+1)-1 （3）小于，大于（4）增序序列（5）2/n ,m-1 （6）70; 34,20,55 （7）n/m （8）开放地址法，链地址法（9）产生冲突的可能性就越大，产生冲突的可能性就越小（10） 关键码直接（11） , , （12） 16,16,8,21 （13） 直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法（14） 开放地址法，再哈希法，链地址法

49、，建立一个公共溢出区（15） 装满程度（16） 索引，快（17） 哈希函数，装填因子（18） 一个结点（19） 中序（20） 等于名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 29 页 - - - - - - - - - 7.3 一棵二叉排序树( 又称二叉查找树) 或者是一棵空树，或者是一棵同时满足下列条件的二叉树： (1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。 (2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。 (3)它的左

50、、右子树也分别为二叉排序树。7.4 对地址单元d=H(K) ，如发生冲突，以d 为中心在左右两边交替进行探测。按照二次探测法，键值K的散列地址序列为： do=H(K)， d1=(d0+12)mod m， d2=(d0-12)mod m， d3=(d0+22)mod m，d4=(d0-12)mod m，,7.5 衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而