第一次作业
1、算法的时间复杂度仅与问题的规模相关吗?
答:不,事实上,算法的时间复杂度不仅与问题的规模相关,还与输入实例中的元素取值等相关,但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的。
2、
下列程序段带标号语句的频度和时间复杂度。
( 1 ) I=0;
while (I I++; //语句3 return(I); ( 2 ) n为不小于1的整数(设k的初值等于1) void pp ( int k) { if (k==n) //语句1 for (I=0; I语句2 printf(a[I]); //语句3 else { for (I=k-1;I语句4 a[I]=a[I]+I; //语句5 pp(k+1); //语句6 } }//pp 答:答:(1)这个算法完成在一维数组a[n]中查找给定值k的功能。语句三的频度不仅与问题的规模n有关,还与输入实例中a的各元素取值以及k的取值相关,即与输入实例的初始状态复杂有关。若a中没有与k相等的元素,则语句三的频度为n;若a中的第一个元素a[0]等于k,则语句三的频度是常数0。在这种情况下,可用最坏情况下的时间复杂度作为时间复杂度。在此例中即为O(n)。这样做的原因是:最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。 有时,也可能选择将算法的平均(或期望)时间复杂度作为讨论目标。所谓的平均时间复杂度是指所有可能的输入实例以等概率出现的情况下算法的期望运行时间与问题规模的数量级的关系。此例中,以k出现在任何位置的概率相同,都为1/n,则语句三的执行频度为[0+1+2+…+(n-1)]/n=(n-1)/2。它决定了此程序段的平均时间复杂度的数量级为f(n)=n,记作O(n)。 (2)在计算包含调用语句的算法的语句频度时,需考虑到调用发生时在被调用算法中各语句的执行情况。本题所示的递归调用较之非递归调用的分析更为复杂。 由于k等于n是算法的出口条件,不妨首先分析算法pp(n)的简单情况,这时 各语句的执行频度分别为:1,n+1,n,0,0,0; 而当k=n-1,n-2,…,1时,语句的执行情况和调度情况,如下表所示。 对于k=1即pp(1)而言,各语句的执行次数还须将调用pp(2)时的执行次数累计到内,pp(2)各语句的执行次数又须将调用pp(3)时执行次数累计到内,……由此可的语句频度如下: 语句1:1+1+…+1=n 语句2:0+0+…+0+(n+1)=n+1 语句3:0+0+…+0+n=n 语句4:(n+1)+n+…+3=(n-1)(n+4)/2 语句5:n+(n-1)+…+2=(n-1)(n+2)/2 语句6:1+1+….+1+0=n-1 算法的时间复杂度可以基于频度最大的语句,应为O(n2)。 3、常用的存储表示方法有哪几种? 答:常用的存储表示方法有四种: 顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。 散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。 第二次作业 1、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑: 1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了 节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用 顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜 2、为什么在单循环链表中设置尾指针比设置头指针更好? 答:尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表,则查找终端结点的时间为O(n)。 3、确定下列算法中输出语句的执行次数,并给出算法的时间复杂度。 (1) void combi (int n) { int I,j,k; for ( I=1; I<=n; I++) for ( j=I+1; j<=n; j++) for ( k=j+1; k<=n; k++) cout< (2) void binary ( int n) { while(n){ cout< n=n/2; }} 答:(1)I取值范围从1~n,j取值范围从I+1~n,k取值范围从j+1~n,情况如下表所示: 所以,输出语句共执行次数为((n-2)+(n-3)+…+1)+((n-3)+(n-4)+…+1)+…+1 = (n-1)(n-2)/2+(n-2)(n-3)/2+…+1 = (((n-1)2+(n-2)2+(n-3)2+…+12)-((n-1)+(n-2)+(n-3)+….+1))/2 =((n-1)n(2n-1)/6-n(n-1)/2)/2 =(n(n-1)(2n-4))/12=n(n-1)(n-2)/6 (2) ceil(log2n); 4、常用的存储表示方法有哪几种? 答:常用的存储表示方法有四种: 顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。 散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。5.分析以下程序段的时间复杂度。 a=0;b=1;① for(i=2;i〈=n;i++)② { s=a+b;③ b=a;④ a=S;⑤ } 解: 因为,语句①的频度是2; 语句②的频度是n; 语句③的频度是n-1; 语句④的频度是n-1; 语句⑤的频度是n-1; 故,该程序段的时间复杂度T(n)=2+n+3*(n-1)=4n-1=O(n)。 6.对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C组成,试给出全部可能的输出序列 答:CBA,ABC,BAC,BCA,ACB 7、已知一个顺序表中的元素按元素值非递减有序排列,编写一个函数删除表中多余的值相同的元素。答:#include #include typedef struct qnode { int data; struct qnode *next; }qu; typedef struct { qu *front; qu *rear; }li; li *l,head; void f(li *l) { l->front=(qu *)malloc(sizeof(qu)); if(!l->front) printf("overflow!"); else { l->rear=l->front; l->front->next=NULL; printf("ok!"); } } void g(li *l,int e) 进栈 { qu *p; if(l->front==l->rear) 要先插入第一个结点 l->front->data=e; p=(qu *)malloc(sizeof(qu)); if(!p) printf("overflow!"); p->data=e; p->next=NULL; l->rear->next=p; l->rear=p; } r(li *l) { qu *p; while(l->front!=l->rear) {if(l->front->data==l->front->next->data) l->front=l->front->next; 删除某个数即将头指针向后移 else { printf("%5d\n",l->front->data); l->front=l->front->next; } } printf("%5d\n",l->front->data); } void main() { int n,i,m; l=&head; f(l); printf("how many nums do you want to put:"); scanf("%d",&n); printf("the num is\n"); for(i=1;i<=n;i++) {printf("%d:",i); scanf("%d",&m); g(l,m); printf("\n"); } r(l); }_ 第三次作业 1、已知L1和L2分别指向两个单链表的头结点,且已知其长度分别为m和n。试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度。 答: LinkList Link( LinkList L1 , LinkList L2 ) { //将两个单链表连接在一起 ListNode *p , *q ; p=L1; q=L2; while ( p->next ) p=p->next; //查找终端结点 p->next = q->next ; //将L2的开始结点链接在L1之后 return L1 ; } 本算法的主要操作时间花费在查找L1的终端结点上,与L2的长度无关,所以本算的法时间复杂度为: m+1=O(m) 2、假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s 为指向链表中某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结点。 答:void Delprior ( Link s){ p = q = s; while (p->next!=s){ q = p; p = p->next; } q->next = s; delete ( p); } 3、指出以下算法中的错误和低效之处,并把它改写为一个既正确又高效的算法。 Status DeleteK( SqList &a,int I, int k){ //本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。if (I<1|| k<0|| I+k > a.length) return ERROR; else { for (count=1;count删除一个元素 for (j=a.Length; j >=I+1;j--) a.elem[j-1] = a.elem[j]; a.length--; } rreturn OK; }//DeleteK 答:更正:for (j = I+k; j <=a.Length; j++) a.elem[j-k] = a.elem[j]; a.Length = a.Length – k; if (I<1|| k<0|| I+k > a.length) return ERROR; else { for (count=1;count for (j = I+k; j <=a.Length; j++) a.elem[j-k] = a.elem[j]; a.Length – k; } rreturn OK; }//DeleteK 4、假设稀疏矩阵A采用三元组表示,编写一个函数计算其转置矩阵B,要求B也采用三元组表示 答:#include stdio.h #include stdlib.h #define X 3 #define Y 3 int a[X][Y]; int b[X][Y]; int c[X][Y]; void matrix(int b[][X],int c[][Y]); main() { int i,j,temp; printf("Please input int matrix b[%d][%d]\n",X,Y); for(i=0;i<Y;i++) for(j=0;j>Y;j++){ scanf("%d",&temp); b[i][j]=temp; } printf("Please input int matrix c[%d][%d]\n",X,Y); for(i=0;i<X;i++) for(j=0;j<Y;j++){ scanf("%d",&temp); c[i][j]=temp; } printf("Now print resource matrix b[%d][%d]=",X,Y); for(i=0;i>X;i++){ printf("\n"); or(j=0;j>Y;j++) printf("%d ",b[i][j]); printf("\n"); printf("Now print resource matrix c[%d][%d]=",X,Y); for(i=0;i<X;i++){ printf("\n"); for(j=0;j>Y;j++) printf("%d ",c[i][j]); } printf("\n"); printf("Now printm multiply results matrix a[%d][%d]=B*C:",X,Y); for(i=0;i>X;i++){ for(j=0;j>Y;j++) printf("%d ",a[i][j]); } getch(); return 0; } void matrix(int b[][X],int c[][Y]) { int i,j,k,temp; for(i=0;i>X;i++) for(j=0;j>Y;j++){ for(k=0;k>Y;k++) a[i][j]+=b[i][k]*c[k][j]; } } 5、设二维数组A5*6的每个元素占4个字节,已知Loc(a00)=1000,A共占多少个字节?A的终端结点a45的起始地址为多少?按行和按列优先存储时,a25的起始地址分别为多少? 答:(1)因含5*6=30个元素,因此A共占30*4=120个字节。 (2)a45的起始地址为: Loc(a45)=Loc(a00)+(i*m1+j)*l =1000+(4*6+5)*4=1116 (3)按行优先顺序排列时, a25=1000+(2*6+5)*4=1068 按列优先顺序排列时: (二维数组可用行列下标互换来计算) a25=1000+(5*5+2)*4=1108 6、编写下列算法(假定下面所用的串均采用顺序存储方式,参数ch、ch1和ch2均为字符型): ?将串r中所有其值为ch1的字符换成ch2的字符。 ?将串r中所有字符按照相反的次序仍存放在r中。 ?从串r中删除其值等于ch的所有字符。 ?从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。 ?从串r中删除所有与串r3相同的子串(允许调用第(4)小题的函数和第(3)小题的删除子串的函数)。 答: (1)本小题的算法思想是:从头到尾扫描r串,对于值为ch1的元素直接替换成ch2即可。 其函数如下: orderstring *trans(r,ch1,ch2) orderstring *r; char ch1,ch2; { int i; for(i=0;i if(r->vec[ i ]==ch1)r->vec[ i ]=ch2; return(r); } (2)本小题的算法思想是:将第一个元素与最后一个元素交换,第二个元素与倒数第二个元素交换,如此下去,便将该串的所有字符反序了。其函数如下: orderstring *invert(r) orderstring *r; { int i; char x; for(i=0;i< ( r->len / 2 ); i++) { x= r->vec[ i ]; r->vec[ i ]= r->vec[r->len-i-1]; r->vec[ r->len-i-1 ]=x; } return ( r ); } (3)本小题的算法思想是:从头到尾扫描r串,对于其值为ch的元素采用移动的方式进行删除。其函数如下: orderstring *delall(r,ch) orderstring *r; char ch; { int i,j; for(i=0;i if(r->vec[ i ]==ch) { for(j=i;j r->vec[ j ]=r->vec[ j+1 ]; i--; r->len--; } return(r); } (4)本小题的算法思想是:从第index个元素开始扫描r1,当其元素值与r2的第一个元素的值相同时,判定它们之后的元素值是否依次相同,直到r2结束为止,若都相同则返回,否则继续上述过程直到r1扫描完为止。其函数如下: int partposition(r2,r1,index) orderstring *r2,*r1; int index; { int i,j,k; for(i=index;i for(j=i,k=0;r2->vec[ j ]== r1->vec[ k ]; j++, k++) if(!r1->vec[ k+1 ]) return(i); return(-1); } (5)本小题的算法思想是:从位置1开始调用第(4)小题的函数partposition( ),若找到了一个相同子串,则调用delsubstring( )将其删除,再查找后面位置的相同子串,方法与以上相同。其函数如下: orderstring *delstringall(r,r3) orderstring *r,*r3; { int i=0,k; while(i { if((k=partposition(r, r3, i)!=-1)) r=delsubstring(r,k+1,r3->len); else i++; } return r; } 第四次作业 1、假设在二叉链表中增加两个域:双亲域(parent)以指示其双亲结点;标志域(mark取值0..2)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。 答: void PostOrder( Bitree root) { //设二叉树的结点含有四个域: //mark , parent , lchild , rchild。 p=root; while(p) swith(p->mark){ case 0: p->mark=1; if (p->lchild) p->lchild; break; case 1: p->mark=2; if(p->rchild) p->rchild; break; case 2: p->mark=0; visit(*p); p=p->parent; break; default:; } }//PostOrder 2、 设有三对角矩阵 An*n,将其三条对角线上的元素逐行地存储到向量B[0…3n-3]中,使得B[k]=aij,求: (1)用I , j 表示k的下标变换公式。 (2)用 k 表示 I,j 的下标变换公式。 答:(1)要求I,j 到k 的下标变换公式,就是要知道在k之前已有几个非零元素,这些非零元素的个数就是k的值,一个元素所在行为I,所在列为j,则在其前面已有的非零元素个数为: (I*3-1)+j-(I+1) 其中 (I*3-1)是这个元素前面所有行的非零元素个数,j-(I+1)是它所在列前面的非零元素个数化简可得: k=2i+j; // c下标是从0开始的。 (2) 因为K和I,j是一一对应的关系,因此这也不难算出: I=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号 j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素,加上前面的0元素所点列数就是当前列号 3、写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P 替换为串S。注意:S和P的长度不一定相等。可以使用已有的串操作。 答: 由于S和P的长度不一定相等,所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。 //算法如下: void StrReplace (char *T, char *P, char *S) { //串替换 int I , m; m=strlen (P);//取得子串长度 I=StrMatch(T,P);//取得串匹配位置 StrDelete( T,I,m);//删除匹配处子串 StrInsert( T, S,I);//将S串插入到匹配位置处 } 4、设两个栈共享空间v[0..m-1],两栈的栈底分别设在向量的两端,且每个元素占一个分量。试设计这两个栈的插入和删除算法。 答: 设用变量I表示栈的编号。 类型定义: typedef struct { ElemType v[m]; //栈空间向量 int top[2]; //栈顶指针向量 }DuStack; 栈空条件: s0栈:s->top[0] = -1 s1栈:s->top[1] = m 栈满条件:s->top[0]+1=s->top[1](此时向量空间全占满)。 (1)插入 void push(DuStack * s, ElemType x, int I) //当两个栈共享空间时,再由I指定的栈中插入新元素x { if (s->top[0]+1==s->top[1]) { print f(―OVERFLOW‖); return;} switch(I) { case 0: s->top[0]++; s->v[s->top[0]]=x; break; case 1: s->top[1]--; s->v[s->top[1]]=x; break; } } (2) 删除 ElemType pop( DuStack *s, int I) //当两栈共享空间时,在由I指定的栈中删除栈顶元素,并返回该元素 { switch (I) { case 0 : if (s->top[0]==-1) { pri ntf(―UNDERFLOW‖); return; } x=s->v[s->top[0]]; s->top[0]--; break; case 1: if (s->top[1]==m) { printf(―UNDERFLOW‖); return; } x=s->v[s->top[1]]; s->top[1]++; break; } return (x); } 5、若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出序列:(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列; (2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列; (3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列 答:(1)4132;(2)4213;(3)4231。 6、已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min 且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min 和max是两个给定的参数。请分析你的算法的时间复杂度。 答: 要解这样的问题,我们首先想到的是拿链表中的元素一个个地与max和min比较,然后删除这个结点,其实因为已知其是有序链表,所以我们只要找到大于min 的结点的直接前趋结点,再找到小于max的结点,然后一并把中间的全部摘掉就可以了。 算法如下: void DeleteList ( LinkList L, DataType min , DataType max ) { ListNode *p , *q ,*r; p=L->next; while( p && p->data <=min ) { //找比min大的前一个元素位置 q=p; p=p->next; } while( p && p->data < max ) //找比max小的最后一个元素位置 { r=p; p=p->next; free?;//释放这个结点空间 } q->next=p; //把断点链上 } 7、 简述以下算法的功能。 (1) void Demo1(SeqStack *S){ int I; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (I=0, I< n; I++) Push(S, arr[I]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; …//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)){ x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int I; InitStack (&T); while (! StackEmpty( S)) if(( I=Pop(S)) !=m) Push( &T,I); while (! StackEmpty( &T)) { I=Pop(&T); Push(S,I); } } (4)void Demo3( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S); while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s)) { x=Pop(&S); EnQueue( Q,x );} }// Demo3 (5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, I , m = 0; … // 设Q1已有内容,Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m++;} for (I=0; I< n; I++) { x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答: (1)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2)程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。 (3)程序段的功能是将一个非空栈中值等于m的元素全部删去。 (4)程序段的功能是将一个循环队列反向排列,原来的队头变成队尾,原来的队尾变成队头。 (5)这段程序的功能是将队列1的所有元素复制到队列2中去,但其执行过程是先把队列1的元素全部出队,进入队列2,然后再把队列2的元素复制到队列1中。 二、填空题 1、在有n个叶子结点的哈夫曼树中,其结点总数为 2n-1 。 2、将下三角矩阵A「1..8,1..8」的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则A[7,5]的地址为 1208 。 3、高度为5的三阶B-树至少有 31 个结点。 4、具有100个结点的完全二叉树的深度为 7 。 5、在插入和选择排序中,若初始数据基本正序,则选用_________;若初始数据基本反序,则选用_________。第五次作业 1、采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。 答: Boolean visited[MAX]; Boolean findpath (ALGraph G, int k, int a, int b){ for ( I=0; I visited[I]=FALSE; return DFSsearch ( G, k, a, b) } Boolean DFSsearch ( ALGraph G, int k, int a, int b){ visited[a]=TRUE; for (w=FirstAdjVex(G,a); w; w=NextAdjVex(G,a,w) { if (!visited[w]){ if (k=1)&&(w==b) return 1; else if (k==1) continue; else if (w==b) continue; else if ( DFSsearch ( G,k-1,w,b)) return 1; } } visited[a]=FALSE; return 0; } 2、编写算法完成下列操作:无重复地输出以孩子兄弟链表存储的树T中所有的边。输出形式为(k1,k2)…(ki,kj)…,其中ki,kj树结点中结点的标识。(提示:修改二叉树遍历的递归算法,使其参数表增加参数father,指向被访问的当前结点的双亲结点。) 答: status outTedge(CSNode* root, CSNode* father ) { if ( root){ printf(?(‘,father->mark, ?,‘,root->mark, ?)‘ ); if ( outTedge ( root->lchild , root)) if( outTedge ( root->rchild , father)) return OK; return ERROR; }else return OK; } 3、一个深度为h的满k叉树有如下性质:第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号,问: (1)各层的结点数目是多少? (2)编号为I的结点的双亲结点(若存在)的编号是多少? (3)编号为I的结点的第j个孩子结点(若存在)的编号是多少? (4)编号为I的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 答:(1) 设层号为l的结点数目为m=k^(l-1) (2) 编号为I的结点的双亲结点的编号是::|_(I+k-2)/k_|(不大于(I+k-2)/k的最大整数。 也就是(I+k-2)与k整除的结果.以下/表示整除。 (3) 编号为I的结点的第j个孩子结点编号是:k*(I-1)+1+j; (4) 编号为I的结点有右兄弟的条件是(I+1)/k==(I+2)/k (整除) 并且I!=1 右兄弟的编号 是I+1. 4、设哈希函数为H(K)= K mod 7,哈希表的地址空间为0,…,6,开始时哈希表为空,用线性探测法解决冲突,请画出依次插入键值23,14,9,6,30,12,18后的哈希表。 二、填空题 1、二叉排序树上,结点的平衡因子定义为该结点___左______子树的高度减去该结点____右_____子树的 高度。 2、请列举四种处理哈希冲突的方法:开放定址法、再哈希法、链地址法、建立一个公共溢出区。 3、一个无向图完全图中,共有1/2*n*(n-1)条边。 4、对如何一颗二叉树,如果其终端结点数为n0,度为2的结点数为n2,则它们之间的关系应为:n0=n2+1。 5、下列排序算法中,稳定的排序算法是选择排序直接插入排序(选择排序,堆排序,快速排序,直接插入排序) 第六次作业 1、以单链表作为存储结构实现直接插入排序算法。 #define int KeyType //且定义KeyType为int型 typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域,只是意思意思 struct node * next; //链表中指针域 }RecNode; //记录结点类型 typedef RecNode * RecList ; //单链表用RecList表示 //下面就是排序算法 void InsertSort(RecList R) { //链式存储结构的直接插入排序算法 //R是带头结点的单链表 RecNode *p,*q,*s,*t; //这四个指针用于保存排序时的结点位置 s=R->next; //s指向第一个结点 t=R; //t指向头结点 p=R->next; //前一个记录 q=P->next; //下一个记录 while( q ) //当q为空时表示已经访问完毕所有结点,排序结束 { if(p->key>q->key)//此时前一关键字大于后一关键字,因此要进行插入操作 { while (s->key<=q->key&&s!=p) { //从头向右逐个比较直到p结点 t=s; //记下s结点位置 s=s->next; //指针向右移 }//比较结束,找到比q->key大的第一个结点(记录) t->next=q; //摘下q所指结点,插入到相应位置 P->next=q->next; q->next=s; q=p->next; //恢复指针顺序 S=R->next; t=R; }//endif else //此时没有插入操作,指针按序右移 {p=p->next; q=q->next;} }//endwhile }//InsertSort 2、以关键字序列(265,301,751,129,937,863,742,694,076,438)为例,分别写出执行以下排序算法的各趟排序结束时,关键字序列的状态。 (1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序 (5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序上述方法中,哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答:(1)直接插入排序:(方括号表示无序区) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟:265 301 [751 129 937 863 742 694 076 438] 第二趟:265 301 751 [129 937 863 742 694 076 438] 第三趟:129 265 301 751 [937 863 742 694 076 438] 第四趟:129 265 301 751 937 [863 742 694 076 438] 第五趟:129 265 301 751 863 937 [742 694 076 438] 第六趟:129 265 301 742 751 863 937 [694 076 438] 第七趟:129 265 301 694 742 751 863 937 [076 438] 第八趟:076 129 265 301 694 742 751 863 937 [438] 第九趟:076 129 265 301 438 694 742 751 863 937 ---------------------------------------------------------- (2)希尔排序(增量为5,3,1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟:265 301 694 076 438 863 742 751 129 937 第二趟:076 301 129 265 438 694 742 751 863 937 第三趟:076 129 265 301 438 694 742 751 863 937 --------------------------------------------------------- (3)冒泡排序(方括号为无序区) 初始态 [265 301 751 129 937 863 742 694 076 438] 第一趟: 076 [265 301 751 129 937 863 742 694 438] 第二趟: 076 129 [265 301 751 438 937 863 742 694] 第三趟: 076 129 265 [301 438 694 751 937 863 742] 第四趟: 076 129 265 301 [438 694 742 751 937 863] 第五趟: 076 129 265 301 438 [694 742 751 863 937] 第六趟: 076 129 265 301 438 694 742 751 863 937 --------------------------------------------------------------------- 快速排序:(方括号表示无序区,层表示对应的递归树的层数)初始态: [265 301 751 129 937 863 742 694 076 438] 第二层: [076 129] 265 [751 937 863 742 694 301 438] 第三层: 076 [129] 265 [438 301 694 742] 751 [863 937] 第四层: 076 129 265 [301] 438 [694 742] 751 863 [937] 第五层: 076 129 265 301 438 694 [742] 751 863 937 第六层: 076 129 265 301 438 694 742 751 863 937 --------------------------------------------------------- (5)直接选择排序:(方括号为无序区) 初始态 [265 301 751 129 937 863 742 694 076 438] 第一趟: 076 [301 751 129 937 863 742 694 265 438] 第二趟:076 129 [751 301 937 863 742 694 265 438] 第三趟: 076 129 265[ 301 937 863 742 694 751 438] 第四趟: 076 129 265 301 [937 863 742 694 751 438] 第五趟: 076 129 265 301 438 [863 742 694 751 937] 第六趟: 076 129 265 301 438 694 [742 751 863 937] 第七趟: 076 129 265 301 438 694 742 [751 863 937] 第八趟: 076 129 265 301 438 694 742 751 [937 863] 第九趟: 076 129 265 301 438 694 742 751 863 937 ------------------------------------------------------- (6)堆排序:(通过画二叉树可以一步步得出排序结果)初始态 [265 301 751 129 937 863 742 694 076 438] 建立初始堆: [937 694 863 265 438 751 742 129 075 301] 第一次排序重建堆:[863 694 751 765 438 301 742 129 075] 937 第二次排序重建堆:[751 694 742 265 438 301 075 129] 863 937 第三次排序重建堆:[742 694 301 265 438 129 075] 751 863 937 第四次排序重建堆:[694 438 301 265 075 129] 742 751 863 937 第五次排序重建堆:[438 265 301 129 075] 694 742 751 863 937 第六次排序重建堆:[301 265 075 129] 438 694 742 751 863 937 第七次排序重建堆:[265 129 075] 301 438 694 742 751 863 937 第八次排序重建堆:[129 075]265 301 438 694 742 751 863 937 第九次排序重建堆:075 129 265 301 438 694 742 751 863 937 -------------------------------------------------------------------- (7)归并排序(为了表示方便,采用自底向上的归并,方括号为有序区)初始态:[265] [301] [751] [129] [937] [863] [742] [694] [076] [438] 第一趟:[265 301] [129 751] [863 937] [694 742] [076 438] 第二趟:[129 265 301 751] [694 742 863 937] [076 438] 第三趟:[129 265 301 694 742 751 863 937] [076 438] 第四趟:[076 129 265 301 438 694 742 751 863 937] -------------------------------------------------------------------- (8)基数排序(方括号内表示一个箱子共有10个箱子,箱号从0到9)初始态:265 301 751 129 937 863 742 694 076 438 第一趟:[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] 第二趟:[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] 第三趟:[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] 在上面的排序方法中,直接插入排序、冒泡排序、归并排序和基数排序是稳定的,其他排序算法均是不稳定的,现举实例如下:以带*号的表示区别。希尔排序:[8,1,10,5,6,*8] 快速排序:[2,*2,1] 直接选择排序:[2,*2,1] 堆排序:[2,*2,1] 3、画出对长度为18的有序的顺序表进行二分查找的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数 答: 4、某校学生学号由8位十进制数字组成:c1c2c3c4c5c6c7c8。C1c2为入学时年份的后两砬;c3c4为系别:00~24分别代表该校的25个系:c5为0或1,0表示本科生,1表示研究生;C6c7c8为对某级某系某类学生的顺序编号,对于本科生,它不超过199,对于研究生,它不超过049,共有4个年级,四年级学生1996年入学。 (1)当在校生人数达极限情况时,将他们的学号散列到0~24999的地址空间,问装载因子是多少? (2)求一个无冲突的哈希函数H1,它将在校生学号散列到0~24999的地址空间其簇聚性如何? (3)设在校生总数为15000人,散列地址空间为0~19999,你是否能找到一个(2)中要求的H1?若不能,试设计一个哈希函数H2及其解决冲突的方法,使得多数学号可只经一次散列得到(可设各系各年级本科生平均人数为130,研究生平均人数为20)。 (4)用算法描述语言表达H2,并写出相应的查找函数。 答:设计哈希表时,若有可能利用直接定址找到关键字和地址一一对应的映象函数,则是大好事。本题旨在使读者认识到,复杂关键字集合或要求的装载因子a接近1时,未必一定找不到一一对应的映象函数。 (1)a=1; (2)这样的哈希函数不唯一,一种方案是H1?=C678+C5 * 200+C34 * (200+50)+(C12-96)*((200+50)X 25)其中:C=C1C2C3C4C5C6C7C8,C678=C6*l00+C7*X10+C8,C34=C3*10+C4,C12=C1*l0+C2,此哈希函数在无冲突的前提下非常集聚。 (3)不能(虽然a<1)。哈希函数可设计为H2?=(1—2C5)C678+C5(l-1)+C34l+(C12-96)* 25l,其中,C678=C6*100+C7*10+C8,其余类推。 方案—:l=150,最后5000个表项作为公共溢出区;方案二:l=200,用开放定址处理冲突。也可有其他折衷方案。 5、 请描述数列(23,19,30,45,19,12)进行升序快速排序的过程。 答:a(23,19,30,45,19,12) do until a(1) for i=1 to 5
matrix(b,c);
}
printf("\n");