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

附录 习题参考答案习题 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 名词解释如下：数据： 数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项： 数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型： 是指变量的取值范围和所能够进行的操作的总和。算法： 是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：(1) (n2) (2) (n2) (3) (n2)(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 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中的元素输入数组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)/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; printf(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 页 - - - - - - - - - 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， 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； 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(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 答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入（称为入栈,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， 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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(!empty_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 (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, 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+; return *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 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 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.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 + 2n2 + 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 由 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) /* 将 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_Queue(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); /* 不管孩子是否为空，都入队列。*/ /* while */ return 1; /* 只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树 */ /* IsFullBitree */ 5.15 转换的二叉树为：5.16 对应的森林分别为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 5.17 typedef char elemtype; typedef struct elemtype data; int parent; NodeType; (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(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 *nextchild; 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) 求树中结点孩子的算法: 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 页，共 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,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- nextsibling) 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：1101 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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 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 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), (v4,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= INFINITY; 输入边的信息：不仅要输入边邻接的两个顶点序号，还要输入边上的权值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 页 - - - - - - - - - (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, %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) 建立有向图逆邻接链表算法：typedef 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); /* 输入弧尾和弧头序号*/ 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+) 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 ，生成无向图的邻接链表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.firstedge=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) 邻接矩阵中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 (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） 开放地址法，再哈希法，链地址法，建立一个公共溢出区（15） 装满程度（16） 索引，快（17） 哈希函数，装填因子（18） 一个结点（19） 中序（20） 等于名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 29 页 - - - - - - - - - 7.3 一棵二叉排序树( 又称二叉查找树) 或者是一棵空树，或者是一棵同时满足下列条件的二叉树： (1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。 (2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。 (3)它的左、右子树也分别为二叉排序树。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 衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而