数据结构习题答案

1、计算机科学与工程学院二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<=

2、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+; else i+;答：n(7) x= n; y= o;while (x

3、>=(y+1) * (y + 1) y +;答：ëÖ n û(8) x= 91; y= 100;while (y>0) if (x>100)x-=10; y - -; else x + ;答：11001.2.3 综合题20、void print_descending(int x,int y,int z)/按从大到小顺序输出三个数scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; /<->为表示交换的双目运算符,以下同if(y<z) y&

4、lt;->z;if(x<y) x<->y; /冒泡排序printf("%d %d %d",x,y,z);/print_descending1.2.3 综合题22试编写算法，计算 i !. 2i的值并存入数组a0arrsize - 1 的第i- 1个分量中（I= 1,2,.,n）。假设计算机中允许的整数最大值为maxint, 则当n>arrsize 或对某个k(1kn)使 k!. 2k>maxint 时，应按出错处理，注意选择你认为较好的出错处理方法。解：Status algo119(int aARRSIZE)/求i!*2i序列的值且不超过

5、maxint  last=1;  for(i=1;i<=ARRSIZE;i+)   ai-1=last*2*i;   if(ai-1/last)!=(2*i) reurn OVERFLOW;   last=ai-1;   return OK;  /algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.第二章 线性表作业：2.2.2 综合题3、编写一个函数将一个向量 A（有 n 个元素且任何元素均不为 0）分拆成两个向量

6、，使 A 中大于 0 的元素存放在 B 中，小于 0 的元素存放在 C 中。解：本题的算法思想是：依次遍历 A 的元素，比较当前的元素值，大于 0 者赋给 B（假设有 p 个元素），小于 0 者赋给 C（假设有 q 个元素）。实现本题功能的函数如下： void ret(vector A，int n，vector B，int *p，vector C，int *q) int i； *p=0；*q=0； for (i=0；i<=n-1；i+) if (Ai>0) (*p)+； B*p=Ai； if (Ai<0) (*q)+； C*q=Ai； 2.2.2 综合题5、编写一个函数从一给

7、定的向量 A 中删除元素值在 x 到 y(xy)之间的所有元素，要求以较高的效率来实现。解：本题的算法思想是：从 0 开始扫描向量 A，以 k 记录下元素值在 x 到 y 之间的元素个数，对于不满足该条件的元素，前移 k 个位置。 最后返回向量的新长度，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下： int del(A，n，x，y) vector A；int n;ElemType x,y; int i=0，k=0； while (i<n) if (Ai>=x && Ai<=y) k+； else Ai-k = Ai; /* 前

8、移 k 个位置 */ i+; return(n-k); 2.2.2 综合题8、有两个向量 A（有 m 个元素）和 B（有 n 个元素），其元素均以从小到大的升序排列，编写一个函数将它们合并成一个向量 C，要求 C 的元素也是以从小到大的升序排列。解：本题的算法思想是：依次扫描通过 A 和 B 的元素，比较当前的元素的值，将较小值的元素赋给 C，如此直到一个向量扫描完毕，然后将未完的一个向量的余下所有元素赋给 C 即可。实现本题功能的函数如下： int link(vector a,int m,vector b,int n,vector c) int i=0,j=0,l,k=0; while(i&

9、lt;m && j<n) /* 扫描通过 a 和 b，将当前较小者赋给 c */ if(ai<bj) ck+=ai+; else if(ai>bj) ck+=bj+; else /* 相等者只保存一个 */ ck+=bj+; i+; if(i=m) /* b 未完时，当余下的元素赋给 c*/ for(l=j;l<n;l+) ck+=bl; if(j=n) /* a 未完时，当余下的元素赋给 c */ for(l=i;i<m;l+) ck+=al; return k; /* 返回 c 的长度 */ 2.2.2 综合题9、有一个单链表（不同结点的数据域

10、值可能相同），其头指针为 head，编写一个函数计算数据域为 x 的结点个数。 解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加 1，结点个数存储在变量 n 中。实现本题功能的函数如下：int count(head,x) node *head; ElemType x; node *p; int n=0; p=head; while (p!=NULL) if (p->data=x) n+; p=p->next; return(n); 2.2.2 综合题11、有一个单链表 L（至少有 1 个结点），其头结点指针为 head，编写一个函数将 L逆置，即最后一个结点变成第一个

11、结点，原来倒数第二个结点变成第二个结点，如此等等。 解：本题采用的算法是：从头到尾扫描单链表 L，将第一个结点的 next 域置为 NULL，将第二个结点的 next 域指向第一个结点，将第三个结点的 next 域指向第二个结点，如此等等，直到最后一个结点，便用 head 指向它，这样达到了本题的要求。实现本题功能的函数如下： void invert(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

12、=r; head->next=NULL; head=p; /*p 指向 L 的最后一个结点，现改为头结点*/ 2.2.2 综合题16、有一个有序单链表（从小到大排列），表头指针为 head，编写一个函数向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然有序。 解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下： node *insertorder(head，x) node *head; ElemType x; node *s，*p，*q; s=(node *)malloc(sizeof

13、(node); /*建立一个待插入的结点*/ s->data=x; s->next=NULL; if (head=NULL | x<head->data) /*若单链表为空或 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 域值*

14、/ 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;

15、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(LinkList L,int x)/链表上的元素查找,返回指针  for(p=l-&

16、gt;next;p&&p->data!=x;p=p->next);  return p;/Locate第三章 栈和队列3.2.2 综合习题13、如果用一个循环数组 qu0，m0-1表示队列时，该队列只有一个头指针 front，不设队尾指针 rear，而改置计数器 count 用以记录队列中结点的个数。 （1）编写实现队列的五个基本运算； （2）队列中能容纳元素的最多个数还是 m0-1 吗? 解： （1）依题意，有如下条件： 队列为空:count=0，front=1 队列为满:count=m0 队列尾的第一个元素位置=(front+count) %

17、 m0 队列首的第一个元素位置=(front+1) % m0 队列类型定义如下： typedef int qum0； 由此得到如下对应上述基本运算的 5 个函数如下： /* m0 定义为全局变量 */ void makenull(front，count) /*使队列 q 为空*/ int front，count； front=1； count=0； int empty(count) /*判定队列 q 是否为空*/ int count； if (count=0) return(1)； else return(0)； void pop(q，front，count，x) /*取队列头元素给 x*/

18、qu q；int front，count； ElemType *x; if (count=0) printf("队列下溢出n")； else front=(front+1) % m0； *x=qfront； void enqueue(q，x，front，count) /*将元素 x 入队列*/ qu q； int front，count； ElemType x; int place； if (count=m0) printf("队列上溢出n")； else count+； e=(front+count) % m0； qplace=x； void dequ

19、eue(q，front，count) /*删除队列头元素*/ qu q； int front，count； if (count=0) printf("队列下溢出n")； else front=(front+1) % m0； count-； （2）队列中可容纳的最多元素个数为 m0 个。3.2.2 综合习题31假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，bcde和ababa则不是回文，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0&

20、#160; 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) return ERROR;

21、    return OK;/Palindrome_Test第三章 串4.2.3 综合习题 2、若 x 和 y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。 解：两个串相等表示对应的字符必须都相同，所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等，由此得到如下函数： int same(x，y) orderstring *x，*y; int i=0，tag=1; if (x->len!=y->len) return(0); else while (i<x-

22、>len && tag) if (x->veci!=y->veci) 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;int i，j; int h; if (i+j<s->len) for (h=i;h<i+j-1;h+) /*第

23、 i+j-1 之后的字符都前移 j 个位置*/ s->vech=s->vech+j; s->len-=j; return(s); else printf("无法进行删除操作n"); 4.2.3 综合习题24、编写算法，求串s所含不同字符的总数和每种字符的个数。typedef struct                 char ch;     &#

24、160;          int num;               mytype;void StrAnalyze(Stringtype S)/统计串S中字符的种类和个数  mytype TMAXSIZE; /用结构数组T存储统计结果  for(i=1;i<=S0;i+)   &

25、#160;  c=Si;j=0;    while(Tj.ch&&Tj.ch!=c) j+; /查找当前字符c是否已记录过    if(Tj.ch) Tj.num+;    else Tj=c,1;  /for  for(j=0;Tj.ch;j+)    printf("%c:  %dn",Tj.ch,Tj.num);/S

26、trAnalyze4.2.3 综合习题30试写一算法，在串的堆存储结构上实现基本操作Concat(&T,s1.s2).void HString_Concat(HString s1,HString s2,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.chi-1=s1.chi-1;  f

27、or(j=1;j<=s2.length;j+,i+) t.chi-1=s2.chj-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 的

28、当前项的行号小于 B 的当前项的行号，则将 A 的项存入 C 中；若 A 的当前项的行号大于 B 的当前项的行号，则将 B 的项存入 C 中。这样产生了 C，因此，实现本题功能的函数如下： void matadd(A，B，C) smatrik A，B，C; int i=1，j=1，k=1; while (i<=A02 && j<=B02) /*若 A 的当前项的行号等于 B 的当前项的行号，则比较其列号，将较小列的项*/ /*存入 C 中，如果列号也相等，则将对应的元素值相加后存入 C 中*/if (Ai0=Bj0) if (Ai1<Bj1) Ck0=Ai0;

29、 Ck1=Ai1; Ck2=Ai2; k+; i+; else if (Ai1>Bj1) Ck0=Bj0; Ck1=Bj1; Ck2=Bj2; k+; j+; else Ck0=Bj0; Ck1=Bj1; Ck2=Ai2+Bj2; if (Ck2!=0) k+; i+; j+; else if (Ai0<Bj0) /*若 A 的当前项的行号小于 B 的当前项的行号，则将 A 的项存入 C 中*/ Ck0=Ai0; Ck1=Ai1; Ck2=Ai2; k+; i+; else /*若 A 的当前项的行号大于 B 的当前项的行号，则将 B 的项存入 C 中*/ Ck0=Bj0;Ck1=

30、Bj1; Ck2=Bj2; k+; j+; C00=A00; /*产生第 0 行的结果*/ C01=A01; C02=k-1; 5.2.3 综合习题26试设计一个算法，将数组An中的元素A0至An-1循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O（n）。void RSh(int An,int k)/把数组A的元素循环右移k位,只用一个辅助存储空间  for(i=1;i<=k;i+)    if(n%i=0&&k%i=0) p=i;/求n和k的最大公约数p  for(i=

31、0;i<p;i+)       j=i;l=(i+k)%n;temp=Ai;    while(l!=i)          Aj=temp;      temp=Al;      Al=Aj;      j=l;

32、l=(j+k)%n;    / 循环右移一步    Ai=temp;  /for/RSh分析:要把A的元素循环右移k位,则A0移至Ak,Ak移至A2k.直到最终回到A0.然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A0,A1,.Ap-1为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=

33、6,则p=3.第一条链:A0->A6,A6->A12,A12->A3,A3->A9,A9->A0.第二条链:A1->A7,A7->A13,A13->A4,A4->A10,A10->A1.第三条链:A2->A8,A8->A14,A14->A5,A5->A11,A11->A2.恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的. 第六章 树和二叉树6.2.3. 综合习题： 6、一棵有 11 个结点的二叉树的存储情况如图 8.34 所示，lefti和 righti分别为 i 结点左、右孩

34、子，根结点为序号 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

35、，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 *)mal

36、loc(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 出发），给出遍历序列。解：搜索本题

37、图的宽度优先搜索的序列为：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

38、到 n），然后接受用户输入的<vi，vj>（以其中之一为 0 标志结束），对于每条这样的边，申请一个邻接结点，并插入到 vi的单链表中，如此反复，直到将图中所有边处理完毕，则建立了该有向图的邻接表。 因此，实现本题功能的函数如下： void creatadjlist(adjlist g) int i，j，k; struct vexnode *s; for (k=1;k<=n;k+) /*给头结点赋初值*/ gk.data=k; gk.link=NULL; printf("输入一个偶对:"); scanf("%d，%d"，&i，&

39、amp;j); while (i!=0 && j!=0) s=(struct vexnode *)malloc(sizeof(vexnode); /*产生一个单链表结点 s*/ s->adjvex=j; /*将 s 插到 i 为表头的单链表的最前面*/ s->next=gi.link; /*将 s 插入*/ gi.link=s; printf("输入一个偶对:"); scanf("%d，%d"，&i，&j); 第八章 查找8.2.3 综合习题：5、5. 设线性表的关键字集合 key=32，13，49，55，22

40、，39，20，选取哈希函数的方法为“除留余数法”，解决冲突方法“线性探测再散列”，请按上述条件求出 key 中各值的地址，并求对该表的平均查找长度 ASL。 解：依题意，采用的哈希函数为： H(key)=key % 7所以有： H(32)=32 % 7=4 H(13)=13 % 7=6 H(49)=49 % 7=0 H(55)=55 % 7=6 (冲突) H(55)=(6+1) % 8=7 H(22)=22 % 7=1 H(39)=39 % 7=4 (冲突) H(39)=(4+1) % 8=5 H(20)=20 % 7=6 (冲突) H(20)=(6+1) % 8=7 (仍冲突) H(20)=

41、(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、试将折半查找的算法改写成递归算法。int Search_Bin_Recursive(SSTable ST,int key,

42、int low,int high)/折半查找的递归算法  if(low>high) return 0; /查找不到时返回0  mid=(low+high)/2;  if(ST.elemmid.key=key) return mid;  else if(ST.elemmid.key>key)    return Search_Bin_Recursive(ST,key,low,mid-1);  else return Search_Bin_Recursive(ST,key,mid+1,high);  /Search_Bin_Recursive8.2.3 综合习题19试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表做存储机构，且树中结点的关键字均不同。int last=0,flag=1; in