数据结构习题答案.doc 25页

'计算机科学与工程学院二OO五年三月 目录第一章绪论3第二章线性表5第三章栈和队列9第三章串10第五章数组与广义表12第六章树和二叉树14第七章图18第八章查找22第九章内部排序24 第一章绪论1.2.3综合题14、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;While(i<=n-1){@k+=10*I;i++;}答：n-1(2)i=1;k=0;do{@k+=10*I;i++;}while(I<=n-1);答：n-1(3)i=1;k=0;While(i<=n-1){i++;@k+=10*i;}答：n-1(4)k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}答：(n+1)*n/2(5)for(i=1;i<=n;i++){for(j=i;j<=n;j++){for(k=1;k<=j;k++)@x+=delta;}答：1/6*n*(n+1)*(n+2)(6)i=1;j=0;While(i+j<=n){@if(i>j)j++;elsei++;}答：n(7)x=n;y=o; while(x>=(y+1)*(y+1)){@y++;}答：ëÖnû(1)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}答：11001.2.3综合题20、voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(xy;//<->为表示交换的双目运算符,以下同if(yz;if(xy;//冒泡排序printf("%d%d%d",x,y,z);}//print_descending1.2.3综合题22试编写算法，计算i!.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中（I=1,2,….,n）。假设计算机中允许的整数最大值为maxint,则当n>arrsize或对某个k(1≤k≤n)使k!.2k>maxint时，应按出错处理，注意选择你认为较好的出错处理方法。解：Statusalgo119(inta[ARRSIZE])//求i!*2^i序列的值且不超过maxint{  last=1;  for(i=1;i<=ARRSIZE;i++)  {a[i-1]=last*2*i;  if((a[i-1]/last)!=(2*i))reurnOVERFLOW;  last=a[i-1];  returnOK;  }}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 第二章线性表作业：2.2.2综合题3、编写一个函数将一个向量A（有n个元素且任何元素均不为0）分拆成两个向量，使A中大于0的元素存放在B中，小于0的元素存放在C中。解：本题的算法思想是：依次遍历A的元素，比较当前的元素值，大于0者赋给B（假设有p个元素），小于0者赋给C（假设有q个元素）。实现本题功能的函数如下：voidret(vectorA，intn，vectorB，int*p，vectorC，int*q){inti；*p=0；*q=0；for(i=0；i<=n-1；i++){if(A[i]>0){(*p)++；B[*p]=A[i]；}if(A[i]<0){(*q)++；C[*q]=A[i]；}}}2.2.2综合题5、编写一个函数从一给定的向量A中删除元素值在x到y(x≤y)之间的所有元素，要求以较高的效率来实现。解：本题的算法思想是：从0开始扫描向量A，以k记录下元素值在x到y之间的元素个数，对于不满足该条件的元素，前移k个位置。最后返回向量的新长度，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下：intdel(A，n，x，y)vectorA；intn;ElemTypex,y;{inti=0，k=0；while(i=x&&A[i]<=y)k++；elseA[i-k]=A[i];/*前移k个位置*/i++;}return(n-k);} 2.2.2综合题8、有两个向量A（有m个元素）和B（有n个元素），其元素均以从小到大的升序排列，编写一个函数将它们合并成一个向量C，要求C的元素也是以从小到大的升序排列。解：本题的算法思想是：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个向量扫描完毕，然后将未完的一个向量的余下所有元素赋给C即可。实现本题功能的函数如下：intlink(vectora,intm,vectorb,intn,vectorc){inti=0,j=0,l,k=0;while(ib[j])c[k++]=b[j++];else{/*相等者只保存一个*/c[k++]=b[j++];i++;}}if(i==m)/*b未完时，当余下的元素赋给c*/for(l=j;ldata==x)n++;p=p->next; }return(n);}2.2.2综合题11、有一个单链表L（至少有1个结点），其头结点指针为head，编写一个函数将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。解：本题采用的算法是：从头到尾扫描单链表L，将第一个结点的next域置为NULL，将第二个结点的next域指向第一个结点，将第三个结点的next域指向第二个结点，如此等等，直到最后一个结点，便用head指向它，这样达到了本题的要求。实现本题功能的函数如下：voidinvert(head)node*head;{node*p，*q，*r;p=head;q=p->next;while(q!=NULL)/*当L没有后续结点时终止*/{r=q->next;q->next=p;p=q;q=r;}head->next=NULL;head=p;/*p指向L的最后一个结点，现改为头结点*/}2.2.2综合题16、有一个有序单链表（从小到大排列），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下：node*insertorder(head，x)node*head;ElemTypex;{node*s，*p，*q;s=(node*)malloc(sizeof(node));/*建立一个待插入的结点*/s->data=x;s->next=NULL;if(head==NULL||xdata)/*若单链表为空或x小于第一个结点的date域*/{s->next=head;/*则把s结点插入到表头后面*/ head=s;}else{q=head;/*为s结点寻找插入位置，p指向待比较的结点，q指向p的前驱结点*/p=q->next;while(p!=NULL&&x>p->data)/*若x小于p所指结点的data域值*/if(x>p->data)/*则退出while循环*/{q=p;p=p->next;}s->next=p;/*将s结点插入到q和p之间*/q->next=s;}return(head);}2.2.2综合题23、假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写一个函数删除该结点的前驱结点。解：本题利用循环单链表的特点，通过p指针可循环找到其前驱结点q及q的前驱结点r，然后将其删除。实现本题功能的函数如下：node*del(p)node*p;{node*q，*r;q=p;/*查找p结点的前驱结点，用q指针指向*/while(q->next!=p)q=q->next;r=q;/*查找q结点的前驱结点，用r指针指向*/while(r->next!=q)r=r->next;r->next=p;/*删除q所指的结点*/free(q);return(p);}2.2.2综合题41试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE（L，X）。LNode*Locate(LinkListL,intx)//链表上的元素查找,返回指针{  for(p=l->next;p&&p->data!=x;p=p->next);  returnp;}//Locate 第三章栈和队列3.2.2综合习题13、如果用一个循环数组qu[0，m0-1]表示队列时，该队列只有一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。（1）编写实现队列的五个基本运算；（2）队列中能容纳元素的最多个数还是m0-1吗?解：（1）依题意，有如下条件：队列为空:count==0，front==1队列为满:count==m0队列尾的第一个元素位置==(front+count)%m0队列首的第一个元素位置==(front+1)%m0队列类型定义如下：typedefintqu[m0]；由此得到如下对应上述基本运算的5个函数如下：/*m0定义为全局变量*/voidmakenull(front，count)/*使队列q为空*/intfront，count；{front=1；count=0；}intempty(count)/*判定队列q是否为空*/intcount；{if(count==0)return(1)；elsereturn(0)；}voidpop(q，front，count，x)/*取队列头元素给x*/quq；intfront，count；ElemType*x;{if(count==0)printf("队列下溢出n")；else{front=(front+1)%m0；*x=q[front]；}}voidenqueue(q，x，front，count)/*将元素x入队列*/quq；intfront，count；ElemTypex;{intplace；if(count==m0)printf("队列上溢出n")；else{count++；e=(front+count)%m0；q[place]=x；}}voiddequeue(q，front，count)/*删除队列头元素*/quq；intfront，count； {if(count==0)printf("队列下溢出n")；else{front=(front+1)%m0；count--；}}（2）队列中可容纳的最多元素个数为m0个。3.2.2综合习题31假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘bcde’和‘ababa’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0{  InitStack(S);InitQueue(Q);  while((c=getchar()!="@")  {    Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构  }  while(!StackEmpty(S))  {    Pop(S,a);DeQueue(Q,b));    if(a!=b)returnERROR;  }  returnOK;}//Palindrome_Test第二章串4.2.3综合习题2、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。解：两个串相等表示对应的字符必须都相同，所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等，由此得到如下函数：intsame(x，y)orderstring*x，*y;{inti=0，tag=1;if(x->len!=y->len)return(0);else{ while(ilen&&tag){if(x->vec[i]!=y->vec[i])tag=0;i++;}return(tag);}}4.2.3综合习题4、采用顺序结构存储串s，编写一个函数删除s中第i个字符开始的j个字符。解：本题的算法思想是：先判定s串中要删除的内容是否存在，若存在则将第i+j-1之后的字符前移j个位置。其函数如下：orderstring*delij(s，i，j)orderstring*s;inti，j;{inth;if(i+jlen){for(h=i;hvec[h]=s->vec[h+j];s->len-=j;return(s);}elseprintf("无法进行删除操作n");}4.2.3综合习题24、编写算法，求串s所含不同字符的总数和每种字符的个数。typedefstruct{                charch;                intnum;              }mytype;voidStrAnalyze(StringtypeS)//统计串S中字符的种类和个数{  mytypeT[MAXSIZE];//用结构数组T存储统计结果  for(i=1;i<=S[0];i++)  {    c=S[i];j=0;    while(T[j].ch&&T[j].ch!=c)j++;//查找当前字符c是否已记录过    if(T[j].ch)T[j].num++;     elseT[j]={c,1};  }//for  for(j=0;T[j].ch;j++)    printf("%c:  %dn",T[j].ch,T[j].num);}//StrAnalyze4.2.3综合习题30试写一算法，在串的堆存储结构上实现基本操作Concat(&T,s1.s2).voidHString_Concat(HStrings1,HStrings2,HString&t)//将堆结构表示的串s1和s2连接为新串t{  if(t.ch)free(t.ch);  t.ch=malloc((s1.length+s2.length)*sizeof(char));  for(i=1;i<=s1.length;i++)t.ch[i-1]=s1.ch[i-1];  for(j=1;j<=s2.length;j++,i++)t.ch[i-1]=s2.ch[j-1];  t.length=s1.length+s2.length;}//HString_Concat第五章数组与广义表5.2.3综合习题9、假设稀疏矩阵A和B（具有相同的大小m×n）都采用三元组表示，编写一个函数计算C=A+B，要求C也采用三元组表示。解：本题采用的算法思想是：依次扫描A和B的行号和列号，若A的当前项的行号等于B的当前项的行号，则比较其列号，将较小列的项存入C中，如果列号也相等，则将对应的元素值相加后存入C中；若A的当前项的行号小于B的当前项的行号，则将A的项存入C中；若A的当前项的行号大于B的当前项的行号，则将B的项存入C中。这样产生了C，因此，实现本题功能的函数如下：voidmatadd(A，B，C)smatrikA，B，C;{inti=1，j=1，k=1;while(i<=A[0][2]&&j<=B[0][2])/*若A的当前项的行号等于B的当前项的行号，则比较其列号，将较小列的项*//*存入C中，如果列号也相等，则将对应的元素值相加后存入C中*/if(A[i][0]==B[j][0])if(A[i][1]B[j][1]){C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2];k++;j++;}else{C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=A[i][2]+B[j][2];if(C[k][2]!=0)k++;i++;j++;}elseif(A[i][0]A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.第六章树和二叉树6.2.3.综合习题：6、一棵有11个结点的二叉树的存储情况如图8.34所示，left[i]和right[i]分别为i结点左、右孩子，根结点为序号3的结点。画出该二叉树并给出前序、中序和后序遍历该树的结点序列。 解：该二叉树的表示如图8.35所示。其各种遍历结果如下：前序遍历：acbrsedfmlk中序遍历：rbsceafdlkm后序遍历：rsbecfklmda6.2.3.综合习题8、输入一个正整数序列{40，28，6，72，100，3，54，1，80，91，38}，建立一棵二叉排序树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。解：本题的二叉排序树如图8.38所示。删除72之后的二叉排序树如图8.39所示。 6.2.3.综合习题12、设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。解：本题的哈夫曼树如图8.43所示。 其加权路径长度WPL=7×2+8×2+4×3+2×4+3×4+9×2=806.2.3.综合习题37设树b是一棵采用链接结构存储的二叉树，编写一个把树b的左、右子树进行交换的函数。解：依题意：交换二叉树的左、右子树的递归模型如下：因此，实现本题功能的函数如下：btree*swap(btree*b){btree*t，*t1，*t2;if(b==NULL)t=NULL;else{t=(btree*)malloc(sizeof(btree));/*复制一个根结点*/t->data=b->data;t1=swap(b->left);t2=swap(b->right);t->left=t2;t->right=t1;}return(t); }第七章图7.2.3综合习题：1、给出如图9.8所示的无向图G的邻接矩阵和邻接表两种存储结构。解：图G对应的邻接矩阵和邻接表两种存储结构分别如图9.9和9.10所示。 7.2.3综合习题2、用宽度优先搜索和深度优先搜索对如图9.11所示的图G进行遍历（从顶点1出发），给出遍历序列。解：搜索本题图的宽度优先搜索的序列为：1，2，3，6，4，5，8，7，深度优先搜索的序列为：1，2，6，4，5，7，8，3。7.2.3综合习题3、使用普里姆算法构造出如图9.12所示的图G的一棵最小生成树。解：使用普里姆算法构造棵最小生成树的过程如图9.13所示。 7.2.3综合习题4、使用克鲁斯卡尔算法构造出如图9.14所示的图G的一棵最小生成树。解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图9.15所示。 7.2.3综合习题6、编写一个函数根据用户输入的偶对（以输入0表示结束）建立其有向图的邻接表。解：本题的算法思想是：先产生邻接表的n个头结点（其结点数值域从1到n），然后接受用户输入的（以其中之一为0标志结束），对于每条这样的边，申请一个邻接结点，并插入到vi的单链表中，如此反复，直到将图中所有边处理完毕，则建立了该有向图的邻接表。因此，实现本题功能的函数如下：voidcreatadjlist(adjlistg){inti，j，k;structvexnode*s;for(k=1;k<=n;k++)/*给头结点赋初值*/{g[k].data=k;g[k].link=NULL;}printf("输入一个偶对:");scanf("%d，%d"，&i，&j);while(i!=0&&j!=0){s=(structvexnode*)malloc(sizeof(vexnode));/*产生一个单链表结点s*/s->adjvex=j;/*将s插到i为表头的单链表的最前面*/s->next=g[i].link;/*将s插入*/g[i].link=s;printf("输入一个偶对:");scanf("%d，%d"，&i，&j);}}第八章查找8.2.3综合习题：5、5.设线性表的关键字集合key={32，13，49，55，22，39，20}，选取哈希函数的方法为“除留余数法”，解决冲突方法“线性探测再散列”，请按上述条件求出key 中各值的地址，并求对该表的平均查找长度ASL。解：依题意，采用的哈希函数为：H(key)=key%7所以有：H(32)=32%7=4H(13)=13%7=6H(49)=49%7=0H(55)=55%7=6(冲突)H(55)=(6+1)%8=7H(22)=22%7=1H(39)=39%7=4(冲突)H(39)=(4+1)%8=5H(20)=20%7=6(冲突)H(20)=(6+1)%8=7(仍冲突)H(20)=(6-1)%8=5(仍冲突)H(20)=(6+4)%8=2平均查找长度ASL=（1*4+2*2+4）/7=8.2.3综合习题7、画出对长度为10的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的平均查找长度。解：依题意，假设长度为10的有序表为a，进行二分查找的判定树如图10.3所示。查找成功的平均查找长度：ASL=(1×1+2×2+3×4+4×3)/10=2.98.2.3综合习题14、试将折半查找的算法改写成递归算法。intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法{  if(low>high)return0;//查找不到时返回0  mid=(low+high)/2;  if(ST.elem[mid].key==key)returnmid;   elseif(ST.elem[mid].key>key)    returnSearch_Bin_Recursive(ST,key,low,mid-1);  elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);  }}//Search_Bin_Recursive8.2.3综合习题19．试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表做存储机构，且树中结点的关键字均不同。intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{  if(T->lchild&&flag)Is_BSTree(T->lchild);  if(T->datadata;  if(T->rchild&&flag)Is_BSTree(T->rchild);  returnflag;}//Is_BSTree第九章内部排序9.2.3综合习题：16、采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。解：依题意，单链表定义如下：structnode{intkey;structnode*next;};因此，实现本题功能的函数如下：structnode*selectsort(structnode*h){structnode*p，*q，*r，*s，*t,*k;t=(structnode*)malloc(sizeof(structnode));t->next=NULL;r=t;while(h!=NULL){p=h;s=h;k=h;while(p!=NULL) {if(p->keykey){s=p;k=q;}q=p;p=p->next;}if(s==h)h=h->next;elsek->next=s->next;r->next=s;r=r->next;}r=NULL;p=t;t=t->next;free(p);returnt;}9.2.3综合习题26如下述改写教科书10.3节中所述起泡算法；将1.4.3节中算法中用以起控制作用的布尔变量change改为一个整型变量，指示每一趟排序中进行交换的最后一个记录的位置，并以它作为下一趟起泡排序循环终止的控制值。voidBubble_Sort1(inta[],intn)//对包含n个元素的数组a进行改进的冒泡排序{  change=n-1;//change指示上一趟冒泡中最后发生交换的元素  while(change)  {    for(c=0,i=0;ia[i+1])      {        a[i]<->a[i+1];        c=i+1;//c指示这一趟冒泡中发生交换的元素      }    change=c;  }//while}//Bubble_Sort1'