数据结构习题答案.doc

《数据结构习题答案.doc》由会员分享，可在线阅读，更多相关《数据结构习题答案.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、(y+1) * (y + 1) y +;答： n (8) x= 91; y= 100;while (y0) if (x100)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(xy) xy; /为表示交换的双目运算符,以下同 if(yz) yz; if(xy) xy; /冒泡排序 printf(%d %d %d,x,y,z);/print_descending1.2.3 综合题22试编写算法，计算

4、 i !. 2i 的值并存入数组a0arrsize - 1 的第i- 1个分量中（I= 1,2,.,n）。假设计算机中允许的整数最大值为maxint, 则当narrsize 或对某个k(1kn)使 k!. 2k maxint 时，应按出错处理，注意选择你认为较好的出错处理方法。解：Status algo119(int aARRSIZE)/求i!*2i序列的值且不超过maxintlast=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

5、分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.第二章 线性表作业：2.2.2 综合题3、编写一个函数将一个向量 A（有 n 个元素且任何元素均不为 0）分拆成两个向量，使 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

6、 (i=0；i0) (*p)+； B*p=Ai； if (Ai0) (*q)+； C*q=Ai；2.2.2 综合题5、编写一个函数从一给定的向量 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

7、 (i=x & Ai=y) k+； else Ai-k = Ai; /* 前移 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

8、,vector c) int i=0,j=0,l,k=0; while(im & jn) /* 扫描通过 a 和 b，将当前较小者赋给 c */ if(aibj) ck+=bj+; else /* 相等者只保存一个 */ ck+=bj+; i+; if(i=m) /* b 未完时，当余下的元素赋给 c*/ for(l=j;ln;l+) ck+=bl; if(j=n) /* a 未完时，当余下的元素赋给 c */ for(l=i;idata=x) n+; p=p-next; return(n); 2.2.2 综合题11、有一个单链表 L（至少有 1 个结点），其头结点指针为 head，编写一个函

9、数将 L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 解：本题采用的算法是：从头到尾扫描单链表 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;

10、p=q; q=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(size

11、of(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 & xp-data) /*若 x 小于 p 所指结点的 data 域值*/ if (xp-data) /*则退出 while 循环*/ q=p; p=p-nex

12、t; 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;

13、/*查找 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-next;p&p-data!=x;p=p-next);return p;/Locate第三章 栈和队列3.2.2 综合习题13、如果用一个循环数组 qu0，m0-1表示队列时，该队列只有一个头指针

14、 front，不设队尾指针 rear，而改置计数器 count 用以记录队列中结点的个数。 （1）编写实现队列的五个基本运算； （2）队列中能容纳元素的最多个数还是 m0-1 吗? 解： （1）依题意，有如下条件： 队列为空:count=0，front=1 队列为满:count=m0 队列尾的第一个元素位置=(front+count) % m0 队列首的第一个元素位置=(front+1) % m0 队列类型定义如下： typedef int qum0； 由此得到如下对应上述基本运算的 5 个函数如下： /* m0 定义为全局变量 */ void makenull(front，count) /*

15、使队列 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*/ 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

16、) /*将元素 x 入队列*/ qu q； int front，count； ElemType x; int place； if (count=m0) printf(队列上溢出n)； else count+； e=(front+count) % m0； qplace=x； void dequeue(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假

17、设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，bcde和ababa则不是回文，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0InitStack(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;return OK;/Palindrom

18、e_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 (ilen & tag) if (x-veci!=y-veci) tag=0; i+;return(tag); 4.2.

19、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+jlen) for (h=i;hvech=s-vech+j; s-len-=j; return(s); else printf(无法进行删除操作n); 4.2.3 综合习题24、编写算法，求串s所含不同字符的总数和每种字符的个数。typedef

20、struct char ch; int num; mytype;void StrAnalyze(Stringtype S)/统计串S中字符的种类和个数mytype TMAXSIZE; /用结构数组T存储统计结果for(i=1;i=S0;i+)c=Si;j=0;while(Tj.ch&Tj.ch!=c) j+; /查找当前字符c是否已记录过if(Tj.ch) Tj.num+;else Tj=c,1;/forfor(j=0;Tj.ch;j+)printf(%c:%dn,Tj.ch,Tj.num);/StrAnalyze4.2.3 综合习题30试写一算法，在串的堆存储结构上实现基本操作Concat(

21、&T,s1.s2).void HString_Concat(HString s1,HString s2,HString &t)/将堆结构表示的串s1和s2连接为新串tif(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;for(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、

22、假设稀疏矩阵 A 和 B（具有相同的大小 mn）都采用三元组表示，编写一个函数计算 C=A+B，要求 C 也采用三元组表示。 解：本题采用的算法思想是：依次扫描 A 和 B 的行号和列号，若 A 的当前项的行号等于 B 的当前项的行号，则比较其列号，将较小列的项存入 C 中，如果列号也相等，则将对应的元素值相加后存入 C 中；若 A 的当前项的行号小于 B 的当前项的行号，则将 A 的项存入 C 中；若 A 的当前项的行号大于 B 的当前项的行号，则将 B 的项存入 C 中。这样产生了 C，因此，实现本题功能的函数如下： void matadd(A，B，C) smatrik A，B，C; in

23、t i=1，j=1，k=1; while (i=A02 & j=B02) /*若 A 的当前项的行号等于 B 的当前项的行号，则比较其列号，将较小列的项*/ /*存入 C 中，如果列号也相等，则将对应的元素值相加后存入 C 中*/if (Ai0=Bj0) if (Ai1Bj1) Ck0=Bj0; Ck1=Bj1; Ck2=Bj2; k+; j+; else Ck0=Bj0; Ck1=Bj1; Ck2=Ai2+Bj2; if (Ck2!=0) k+; i+; j+; else if (Ai0Bj0) /*若 A 的当前项的行号小于 B 的当前项的行号，则将 A 的项存入 C 中*/Ck0=Ai0

24、; Ck1=Ai1; Ck2=Ai2; k+; i+; else /*若 A 的当前项的行号大于 B 的当前项的行号，则将 B 的项存入 C 中*/ Ck0=Bj0;Ck1=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

25、=0) p=i;/求n和k的最大公约数pfor(i=0;iA6,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 结点左、右孩子，根结点为序号 3 的结点。画出该二叉树并给出前序、中序和后序遍历该树的结点序列。解：该二

26、叉树的表示如图 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。 解：本题的哈夫曼树如图

27、8.43 所示。其加权路径长度 WPL=72+82+43+24+34+92=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-

28、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 的一棵最小生成树。 解：使用

29、普里姆算法构造棵最小生成树的过程如图 9.13 所示。7.2.3综合习题4、使用克鲁斯卡尔算法构造出如图 9.14 所示的图 G 的一棵最小生成树。 解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 9.15 所示。7.2.3综合习题6、编写一个函数根据用户输入的偶对（以输入 0 表示结束）建立其有向图的邻接表。 解：本题的算法思想是：先产生邻接表的 n 个头结点（其结点数值域从 1 到 n），然后接受用户输入的（以其中之一为 0 标志结束），对于每条这样的边，申请一个邻接结点，并插入到 vi的单链表中，如此反复，直到将图中所有边处理完毕，则建立了该有向图的邻接表。 因此，实现本题功能的函数如

30、下： void creatadjlist(adjlist g) int i，j，k; struct vexnode *s; for (k=1;kadjvex=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，39，20，选取哈希函数的方法为“除留余数法”，解决冲突方法“线性探测再散列”，请按上述条件求出 key 中各值的地址，并求对该表的

31、平均查找长度 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)=(6-1) % 8=5 (仍冲突) H(20)=(6+4) % 8=2 平均查找长度 ASL=（1*4+2*2+4）/7=8.2.3

32、综合习题7、画出对长度为 10 的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的平均查找长度。 解：依题意，假设长度为 10 的有序表为 a，进行二分查找的判定树如图 10.3 所示。 查找成功的平均查找长度： ASL=(11+22+34+43)/10=2.98.2.3 综合习题14、试将折半查找的算法改写成递归算法。int Search_Bin_Recursive(SSTable ST,int key,int low,int high)/折半查找的递归算法if(lowhigh) return 0; /查找不到时返回0mid=(low+high)/2;if(ST.elemmid.ke

33、y=key) return mid;else if(ST.elemmid.keykey)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; int Is_BSTree(Bitree T)/判断二叉树T是否二叉排序树,是则返回1,否则返回0if(T-

34、lchild&flag) Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag) Is_BSTree(T-rchild);return flag;/Is_BSTree第九章 内部排序9.2.3 综合习题：16、采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。解：依题意，单链表定义如下： struct node int key; struct node *next;因此，实现本题功能的函数如下：struct node *selectsort(struct node *h) struct node *p，*q，*r，*s，*t,*k; t=(struct node *) malloc (sizeof (struct node); t-next=NULL; r=t; while (h!=NULL) p=h; s=h; k=h; while (p!=NULL) if (p-keykey)