《数据结构(C语言版)》习题指导与解答.docx 28页

'数据结构（C语言版）附录2习题指导与解答附录2习题指导与解答习题一解答1．数据是人们利用文字符号、数字符号以及其他规定的符号对客观现实世界的事物及其活动所做的抽象描述。它是计算机程序加工的“原料”。表示一个事物的一组数据称为一个数据元素，它是数据的基本单位，在计算机中通常作为一个整体来进行考虑和处理。一般情况下，一个数据元素由若干个数据项构成。数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：描述N个学生的有关信息的N个数据元素构成了一个数据对象。2．数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。具体来说，数据结构包含三个方面的内容，既数据的逻辑结构、数据的存储结构（或称物理结构）和对数据所施加的一组操作。3．数据的逻辑结构是数据元素之间本身所固有的独立于计算机的一种结构，这种结构可以用数据元素之间固有的关系的集合来描述。数据的存储结构（或物理结构）是逻辑结构在计算机存储器中的具体存放方式的体现，是逻辑结构在计算机存储器中的映像。4．根据数据元素之间存在的关系的不同特性，数据结构通常可以分为如下4类基本结构：（1）线性结构。元素之间存在一个一对一的线线关系，即除了第一个元素和最后一个元素外，每个元素都有一个直接前驱和一个直接后继，第一个元素有一个后继，最后一个元素有一个直接前驱。例如学生档案管理系统中学生记录之间的关系即为线性关系；（2）树形结构。数据元素之间存在着一个对多个的关系。例如，老师T指导3个硕士研究生G1，G2，G3；每个研究生Gi（i=1,2,3）又分别指导3个本科生Si1，Si2，Si3；则数据元素之间的呈现树形结构。(3)图形结构或网状结构。数据元素之间存在多个对多个的关系。如城市交通网络中城市之间的交通道路的连接关系就是一个网状结构。（4）集合结构。数据元素之间无任何关系。5．抽象数据类型通常是指由用户定义，用以表示实际应用问题的数据模型，一般由基本数据类型或其他已定义的抽象数据类型以及定义在该模型上的一组操作组成。在C或C++语言中，一般可用struc或直接用“类”来定义抽象数据类型。6．算法（Algorithm）是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法分析（Algorithmanalysis）的主要工作是从“时间”和“空间”两个方面来分析算法的效率。7．算法应具有如下5个重要特性：（1）输入性；（2）输出性；（3）有限性；（4）确定性；（5）可行性；算法设计应满足以下5个基本要求： 数据结构（C语言版）附录2习题指导与解答（1）正确性；（2）可读性；（3）健壮性；（4）高时间效率；（5）高空间效率。8．（1）当n=10的时候有210>103，而29<93，故当n≥10时，有2n>n3。（2）O(n)。（3）因为当n趋向于无穷大时有lim((2n+n3)/2n)=1，2n+n3的同阶数量级是O(2n)。第2大题略习题二解答1.填空⑴表长的一半，表长，该元素在表中的位置⑵144第5个元素的存储地址=第1个元素的存储地址＋(7－1)×4=144⑶p->next=(p->next)->next⑷为了运算方便⑸Ο(1)，Ο(n)在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。(6)两个,直接后继,直接前驱,尾结点,头结点.（7）顺序2.选择题数据结构（C语言版）附录2习题指导与解答⑴A顺序存储的特点是“逻辑上相邻，物理上也相邻”，所以无需存储元素间的关系，故存储密度大。⑵D线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。⑶C因为有prior指针⑷A因为单链表属于顺序存储结构⑸B⑹B（7）B（8）B（9）B（10）BLoc(a6)=Loc(a1)+(6-1)*5=90+10=100数据结构（C语言版）附录2习题指导与解答3.简答题(1)顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：a.在做插入和删除操作时，需移动大量元素；b.由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；c.表的容量难以扩充。 数据结构（C语言版）附录2习题指导与解答链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。(2)带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。4．算法设计⑴从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：voidadjust(intA[],n){i=0;j=n-1;while(inext=C;//创建空循环链表C存放字符D=(Linklist)malloc(sizeof(Lnode));D->next=D;//创建空循环链表D存放数字p=A;q=p->next;while(q){if((q->data>=’A’)&&(q->data<=’Z’)||(q->data>=’a’)&&(q->data<=’z’)){p->next=q->next;q->next=C->next;C->next=q;}elseif((q->data>=’0’)&&(q->data<=’9’)){p->next=q->next;q->next=D->next;D->next=q;}elsep=q;q=p->next;}p->next=A;R=A；}⑷从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：voiddel(LinklistA){p=A->next;while(p->next)if(p->data==p->next->data){q=p->next;p->next=q->next;deleteq;}elsep=p->next;}⑸因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。voiddelbtween(LinklistA,intmink,intmaxk){p=A;while(p->next&&p->next->data<=mink)p=p->next;if(p->next) 数据结构（C语言版）附录2习题指导与解答{q=p->next;while(q->datanext;p->next=q->next;deleteq;q=x;}}}习题三解答1.填空⑴23，1003H⑵顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶后进先出，先进先出，对插入和删除操作限定的位置不同⑷假溢出⑸Ｏ(1)，Ｏ(n)在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。2.选择题⑴D此时，输出序列一定是输入序列的逆序。⑵C解题技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。⑶B每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。⑷C栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。⑸A两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。(6)C队列长度为（rear-front+20）mod20=15(7)B(8)C(9)A递归算法里会用到递归工作栈(10)B先进先出的特性3.问答题(1)栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行,队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线 数据结构（C语言版）附录2习题指导与解答性表可以在线性表的任何位置进行插入和删除操作。(2)因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。4.算法设计(1)出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。入队算法如下：voidEnqueue(*rear,Elemtypex){s=new;S->data=x;if(rear=NULL){rear=s;rear->next=s;}else{s->next=rear->next;rear->=s;rear=s;}}出队算法如下：ElemtypeDequeue(*rear){if(rear==NULL)throw”underflow”;else{s=rear->next;if(s==rear)resr=NULL;elserear->next=s->next;free(s);}}(2)算法思想：利用栈和队列的操作特点，可以先将队列中所有元素出队并入栈，然后再将栈中所有元素出栈并入队即可。voidInverse(StackS,QueueQ){while(!EmptyQueue(Q)){a=DeQueue(Q);Push(S,a);}while(!EmptyStack(S)){a=Pop(S);EnQueue(Q,a);} 数据结构（C语言版）附录2习题指导与解答}习题四解答1.填空⑴数据元素的类型是一个字符⑵长度相同且对应位置的字符相等例如"abc"≠"abc"，"abc"≠"bca"。⑶14⑷模式匹配(5)由空格字符（ASCII值32）所组成的字符串，空格个数(6)该串所包含的的字符的个数(7)a.21b.1c.DataBaseStructureCoursed.DataCoursee.Structuref.6g.DataBaseCourse2.简答题（1）不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，其串值是常量。串值可以变化的量称为串变量。串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现时的第一个字符的位置称子串在主串中的位置。串变量与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。(2)concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4，index(S2,‘8’),length(S2)))=concat(replace(S1,substr(S1,4,3),S3),substr(S4,2,4))=concat(replace(S1,’DEF’,S3),’1234’)=concat(‘ABC###G’,’1234’)=‘ABC###G1234’(3)j123456789101112串ababaaababaa 数据结构（C语言版）附录2习题指导与解答next[j]0112342234563.算法设计⑴先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。voidDele(chars[],inti,intj)/*数组s的0号单元存放串的长度*/{if(i+j0;i--)if(s[i]==ch){for(j=i+1;j<=s[0];j++)s[j-1]=s[j];s[0]--;}}(3)两个指针，一个从头开始，一个从为开始依次交换直至开头小于结尾时候停止。算法如下：#include#includevoidmain(){intstrbegin,strend;stringstr;chartmp;charname[100]="abcdeabc";str=name;printf(“%sn”,str);strbegin=0; 数据结构（C语言版）附录2习题指导与解答strstrend=str.size()-1;while(strbegin=’0’&&ch<=’9’)/*是数字字符*/｛num=０;/*数初始化*/while（ch>=’0’&&ch<=’9’）/*拼数*/｛num=num＊10+‘ch’-‘０’;scanf(“％c”，&ch）;｝a[i++]=num；if（ch!=‘#’）/*若拼数中输入了‘#’，则不再输入*/scanf（“%c”，&ch）;｝elsescanf（“%c”，&ch）；/*输入非数字且非＃时，继续输入字符*/printf（“共有%d个整数，它们是：n”,i）； 数据结构（C语言版）附录2习题指导与解答for（j=０；jlchild);n++;count(root->rchild);}}⑵本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：voidprintleaf(BiNode*root){if(root){if(!root->lchild&&!root->rchild)printf(“%d“,root->data);printleaf(root->lchild);printleaf(root->rchild);}}⑶当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下：intDepth(BiNode*root){if(!root)return0;else{Dl=Depth(root->lchild);Dr=Depth(root->rchild);returnmax(Dl,Dr)+1;}}⑷要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：voidPostPrder(BiNode*root){if(root){ 数据结构（C语言版）附录2习题指导与解答printf(“%d“,root->data);PostOrder(root->rchild);PostOrder(root->lchild);}}⑸对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。具体算法如下：voidExchange(BiNode*root){if(root){Exchange(root->lchild);Exchange(root->rchild);Root->lchildß->root-rchild;}}⑹对二叉链表进行遍历，在遍历的过程中查找结点a并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下：voidDelete(BiNode*root,ElemTypea){if(root){if(root->data==a)if(!p)root=NULL;elseif(p->lchild==root)p->lchild=NULL;elsep->rchild=NULL;else{p=root;Delete(root->lchild,a);Delete(root->rchild,a);}}}(7)在一棵完全二叉树中，若某结点无左孩子的话，那么它一定也没有右孩子；若某结点没有右孩子的话，那么按层序编号比它大的结点一定没有孩子。boolComBiTree(BiNode*root) 数据结构（C语言版）附录2习题指导与解答{front=rear=-1;a=1;b=1;if(root){Q[++rear]=root;while(front!=rear&&b){p=Q[++front];if(!p->lchild){a=0;if(p->rchild)b=0;}else{b=a;Q[++rear]=p->lchild;if(!p->rchild)a=0;elseQ[++rear]=p->rchild;}}}returnb;}(8)①找结点p的前序后继：BiThrNode*PreorderSucc(BiThrNode*p){BiThrNode*q;if(p->rtag==1)/*右子树为空，rchild域指的就是后继*/q=p->rchild;else/*右子树非空*/{if(p->ltag==0)/*左子树非空，左孩子就是后继*/q=p->lchild；if(p->ltag==1)/*左子树为空，右孩子就是后继*/q=p->rchild;} 数据结构（C语言版）附录2习题指导与解答return(q);}②找结点p的后序前驱：BiThrNode*PostorderSucc(BiThrNode*p){BiThrNode*q;if(p->ltag==1)/*左子树为空，lchild域指的就是前驱*/q=p->lchild;else/*左子树非空*/{if(p->rtag==0)/*右子树非空，右孩子就是前驱*/q=p->rchild;if(p->rtag==1)/*右子树为空，左孩子就是前驱*/q=p->lchild;}return(q);}习题七解答1.填空题⑴0，n(n-1)/2，0，n(n-1)图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。⑵邻接矩阵，邻接表这是最常用的两种存储结构，此外，还有十字链表、邻接多重表等。⑶Ｏ(n+e)在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。⑷求第i行的所有元素之和⑸前序，栈，层序，队列⑹回路⑺2000⑻从源点到汇点的最长路径⑼m顶点所代表的事件要优先于n顶点所代表的事件完成(10)n-1（11）全部（n0n-1(12)有向 数据结构（C语言版）附录2习题指导与解答(13)稠密稀疏(14)O（n2），O（n+e）(15)m=2e2.选择题⑴B设无向图中含有n个顶点e条边，则。⑵D⑶C若超过n-1，则路径中必存在重复的顶点。⑷Dn个顶点的无向图中，边数e≤n(n-1)/2，将e=41，有n≥9，现已知无向图非连通，则n=10。⑸D⑹D当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。⑺C，D⑻A(9)B(10)B(11)A邻接矩阵的存储空间为O(n2)，邻接表的存储空间为O(n+e)(12)D3.判断题⑴对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。⑵对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。⑶错。有向图的邻接矩阵不一定不对称，例如有向完全图的邻接矩阵就是对称的。⑷错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。⑸错。只能说明从顶点a到顶点b有一条路径。⑹错。只有在仍旧保持关键活动所在路径仍是关键路径的前提下才可以。4．（1）链接矩阵：⑴邻接矩阵中非零元素个数的总和除以2。⑵当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。⑶计算邻接矩阵上该顶点对应的行上非零元素的个数。 数据结构（C语言版）附录2习题指导与解答邻接表：⑴边表中的结点个数之和除以2。⑵第i个边表中是否含有结点j。⑶该顶点所对应的边表中所含结点个数。（2）邻接矩阵表示如下：邻接表表示如下：各顶点的度：TD(v1)=3TD(v2)=4TD(v3)=2TD(v4)=4TD(v5)=3TD(v6)=2深度优先遍历序列为：v1v2v3v5v4v6广度优先遍历序列为：v1v2v4v6v3v5（3）按Prim算法求最小生成树的过程如下： 数据结构（C语言版）附录2习题指导与解答按Kruskal算法求最小生成树的过程如下：（4）拓扑序列为：v0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4、v0v5v1v2v3v6v4、v0v5v1v2v6v3v4、v0v5v1v6v2v3v4、v1v0v5v2v3v6v4、v1v0v5v2v6v3v4、v1v0v5v6v2v3v4、v1v5v0v2v3v6v4、v1v5v0v2v6v3v4、v1v5v0v6v2v3v4、v5v0v1v2v3v6v4、v5v0v1v2v6v3v4、v5v0v1v6v2v3v4、v5v1v0v2v3v6v4、v5v1v0v2v6v3v4、v5v1v0v6v2v3v4（5）所有事件的最早发生时间ve[k]：ve(1)=0ve(2)=3ve(3)=max{ve(1)+2,ve(2)+6,ve(4)+2}=9ve(4)=5ve(5)=max{ve(2)+5,ve(3)+8}=17ve(6)=max{ve(3)+4,ve(4)+8}=13ve(7)=max{ve(3)+9,ve(5)+8,ve(6)+7}=25所有事件的最晚发生时间vl[k]：vl(7)=ve(7)=25vl(6)=vl(7)-7=18 数据结构（C语言版）附录2习题指导与解答vl(5)=vl(7)-8=17vl(4)=min{vl(3)-2,vl(6)-8}=7vl(3)=min{vl(7)-9,vl(5)-8,vl(6)-4}=9vl(2)=min{vl(5)-5,vl(3)-6}=3vl(1)=min{vl(4)-5,vl(3)-2,vl(2)-3}=0所有活动ai的最早开始时间e[i]和最晚开始时间l[i]：活动a1e(1)=ve(1)=0l(1)=vl(2)-3=0活动a2e(2)=ve(1)=0l(2)=vl(3)-2=7活动a3e(3)=ve(2)=0l(3)=vl(4)-5=2活动a4e(4)=ve(2)=3l(4)=vl(5)-5=12活动a5e(5)=ve(3)=3l(5)=vl(3)-6=3活动a6e(6)=ve(3)=5l(6)=vl(3)-2=7活动a7e(7)=ve(4)=5l(7)=vl(6)-8=10活动a8e(8)=ve(5)=9l(8)=vl(5)-8=9活动a9e(9)=ve(5)=9l(9)=vl(7)-9=16活动a10e(10)=ve(6)=9l(10)=vl(6)-4=14活动a11e(11)=ve(7)=17l(11)=vl(7)-8=17活动a12e(12)=ve(8)=13l(12)=vl(7)-7=18最后，比较e[i]和l[i]的值可判断出a1,a5,a8,a11这些活动的e[i]和l[i]的值相等，没有时间余量，所以它们是关键活动，关键路径如下图所示。v2v5a1=3a5=6a11=8v7v3v1a8=8（6）注：从V0到其余点的最短路径10060V5∞∞10∞30100∞∞5∞∞∞30V4V0∞∞∞50∞∞201010∞∞∞∞∞10V3V1∞∞∞20∞60 数据结构（C语言版）附录2习题指导与解答505V2∞∞∞∞∞∞终点从V0到各终点的Dist值和最短路径的求解过程i=1i=2i=3i=4i=5V1∞∞∞∞∞无V210(V0,V2)V3∞60(V0,V2,V3)50(V0,V4,V3)V430(V0,V4)30(V0,V4)V5100(V0,V5)100(V0,V5)90(V0,V4,V5)60(V0,V4,V3,V5)VjV2V4V3V5S{V0,V2}{V0,V2,V4}{V0,V2,V3,V4}{V0,V2,V3,V4,V5}从源点v0到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度V0V2V0V210V0V4V0V430V0V3V0V4V350V0V5V0V4V3V560V0V1无∞5．算法设计⑴先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对 数据结构（C语言版）附录2习题指导与解答应单链表中插入相应的边表结点。邻接矩阵存储结构定义如下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组intvertexNum,arcNum;//图的顶点数和边数};邻接表存储结构定义如下：constintMaxSize=10;structArcNode//定义边表结点{intadjvex;//邻接点域ArcNode*next;};templatestructVertexNode//定义顶点表结点{Tvertex;ArcNode*firstedge;};structAdjList{VertexNodeadjlist[MaxSize];intvertexNum,arcNum;//图的顶点数和边数};具体算法如下：voidMatToList(AdjMatrix&G,AdjList&A){A.vertexNum=G.vertexNum;A.arcNum=G.arcNum; 数据结构（C语言版）附录2习题指导与解答for(i=0;iadjvex=j;p->next=A.adjlist[i].firstedge;A.adjlist[i].firstedge=p;}}⑵在邻接表上顺序地取每个边表中的结点，将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下：voidListToMat(AdjMatrix&G,AdjList&A){A.vertexNum=G.vertexNum;A.arcNum=G.arcNum;for(i=0;iadjvex;a[i][j]=1;p=p->next;}}}⑶在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下：intCountODZero(AdiMatrixG) 数据结构（C语言版）附录2习题指导与解答{count=0;for(i=0;iadjlist;p2=newArcNode;p2->adjlist=I;p2-next=A.adjlist[j].firstedge;A.adjlist[j].firstedge=p2;p1=p1->next;}}}习题八解答1、填空题（1）主关键字（2）2、4、3（4）(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单（5）AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。（6）比数据元素个数稍大的质数（7）ë㏒2n」+1（8）k(k+1)/2（9）(1)顺序存储或链式存储(2)顺序存储且有序(3)块间有序(4)散列存储（10）结点的左子树的高度减去结点的右子树的高度（11）直接定址法（12）54计算公式：A(n+2)=A(n+1)+A(n)+1（14）42、选择题数据结构（C语言版）附录2习题指导与解答（1）C（2）D（3）C（4）D（5）C（6）C（8）C（9）D（10）D、C（11）B（12）D、C数据结构（C语言版）附录2习题指导与解答数据结构（C语言版）附录2习题指导与解答3．(1)散列表存储的基本思想是用关键字的值决定数据元素的存储地址（2）散列表存储中解决冲突的基本方法： 数据结构（C语言版）附录2习题指导与解答（1）开放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表长，di是增量。根据di取法不同，又分为三种：a．di=1，2，…，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。b．di=12，-12，22，-22，…，±k2（k≤m/2）称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。c．di=伪随机数序列，称为随机探测再散列。（2）二次探测再散列法Hi=RHi（key）i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。（3）链表法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。4（1）.散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+32）%10=5所以比较了4次。（2）散列地址0123456789101112关键字13225314167465130比较次数111212111装填因子=9/13=0.7（4） 数据结构（C语言版）附录2习题指导与解答ASLsucc=（1+2*2+3*3+4*2+5*2）/10=32/10（5）1）2）10,12,15,20,24,28,30,35,46,50,55,683）ASLsucc=（1+2*2+3*4+4*5）/12=37/12习题九解答1、填空题数据结构（C语言版）附录2习题指导与解答（1）n-1，n-j（2）n-1（3）4,8（4）冒泡排序，快速排序（5）希尔排序、快速排序、堆排序（6）插入排序，选择排序（7）堆排序，快速排序，归并排序，归并排序，快速排序，堆排序（8）快速排序，归并排序数据结构（C语言版）附录2习题指导与解答2、选择题数据结构（C语言版）附录2习题指导与解答（1）C（2）A（3）C（4）C（5）D（6）C（7）A（8）D（9）C（10）D数据结构（C语言版）附录2习题指导与解答'