《数据结构实用教程第二版答案_徐孝凯》由会员分享，可在线阅读，更多相关《数据结构实用教程第二版答案_徐孝凯（67页珍藏版）》请在金锄头文库上搜索。
1、 第一章绪习第一章绪习 题题 一一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当 出现多个关系时， 对每个关系画出相应的结构图） ，并指出它们分别属于何种结构。 A=(K,R)其中 K=a1,a2,a3.,an R= B=(K,R)其中 K=a,b,c,d,e,f,g,h R=r r=, C=(K,R)其中 K=a,b,c,d,f,g,h R=r r=, D=(K,R)其中 K=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) E=(K,R)其中 K=48,25,64,57,82,36,7
2、5,43 R=r1,r2,r3 r1=, r2=, r3=, 解：是集合结构；是线性结构；是树型结构；散列结构。只作为参 考。 2.设计二次多项式 ax2+bx+c 的一种抽象数据类型，假定起名为 QIAdratic, 该类型的数据部分分为三个系数项 a、b 和 c，操作部分为：(请写出下面每一 个 操作的具体实现)。 初始化数据成员 ab 和 c(假定用记录类型 Quadratie 定义成员)，每个数据 成 员的默认值为 0。 Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0); 解： Quadratic InitQuadrat
3、ic(float aa,float bb,float cc) Quadratic q; q.a=aa; q.b=bb;q.c=cc; return q; 做两个多项式加法,即使对应的系数相加,并返回相加的结果。 Quadratic Add(Quadratic q1,Quadratic q2); 解： Quadratic Add(Quadratic q1,Quadratic q2); Quadratic q; q.a=q1.a+q2.a; q.b=q1.b+q2.b; q.c=q1.c+q2.c; return q; 根据给定 x 的值计算多项式的值。 float Eval(Quadratic
4、q,float x); 解： float Eval(Quadratic q,float x) return(q.a*x*x+q.b*x+q.c); 计算方程 ax2+bx+c=0 的两个实数根，对于有实根、无实根和不是实根方程 (即 a=0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。int Root(Quadratic q,float 解： int Root(Quadratic q,float float x=q.b*q.b-4*q.a*q.c; if(x=0) r1=(float)(-q.b+sqrt(x)/(2*q.a); r2=(float)(-q.b-sqrt(x)
5、/(2*q.a); return 1; else return 0; 按照 ax*2+bx+c 的格式(x2 用 x*2 表示)输出二次多项式，在输出时要注 意 去掉系数为 0 的项，并且当 b 和 c 的值为负时，其前不能出现加号。 void Print(Quadratic q) 解： void Print(Quadratic q) if(q.a) cout0) cout0) coutx2,x1=x2 和 x1=和x2) return; else if(x1=x2) return =; else return200) return 0;/返回数值 0 表示数组中数据有错，统计失败 for(j
6、=0;j=n 和 N=n 的条件，Lin 和 Col 为引用 /形参，它是对应实参的别名，其值由实参带回 Lin=0;Col=0; for(int i=0;iaLinCol)Lin=i;Col=j; 其时间复杂度为 O(m*n) 4.指出下列各算法的功能并求出其时间复杂度。 int prime(int n) int i=2; int x=(int)sqrt(n); while(ix) return 1; else return 0; 解： 判断 n 是否是一个素数，若是则返回数值 1，否则返回 0。该算法的时间复杂度 为 O(n1/2)。 int sum1(int n) int p=1,s=0
7、; for(int i=1;ix) i=x%10; ci+; 解： 利用数组 c10中的每个元素 ci对应统计出 inp 所联系的整数文件中个位值 同为 i 的整数个 数，时间复杂度为 O(n) void mtable(int n) for(int i=1;iL.size) cerrL.size+1) cerri-1;j-) L.listj+1=L.listj; L.listi-1=x; L.size+; 从线性表中删除具有给定值 x 的所有元素。 解：void Delete2(List while(i=s) /p 指向下一个待逆序的结点 /将 q 结点插入到已陈序单链表的表头 q-next=
8、HL; HL=q; 删除单链表中的第 i 个结点。 解：void Delete1(LNode* j+; if(cp=NULL) cerrnext; else ap-next=cp-next; delete cp; 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则 显示出错信息 并停止运行。 解：ElemType MaxValue(LNode*HL) /从单链表中查找出所有元素的最大值，该值由函数返回 if(HL=NULL) cerrdata; LNode*p=HL-next; while(p!=NULL) if(maxdata) max=p-data; p=p-next; r
9、eturn max; 统计出单链表中结点的值等于给定值 x 的结点数。 解：int Count(LNode*HL,ElemType x) /统计出单链表中结点的值等于给定值 x 的结点数 int n=0; while(HL!=NULL) if(HL-data=x) n+; HL=HL-next; return n; 根据一维数组 an建立一个单链表，使单链表中元素的次序与 an中元素 的次序相同， 并使该算法的时间复杂度为 O(n)。 解：void Create(LNode* for(int i=n-1;i=0;i-) InsertFront(HL,ai; 将一个单链表重新链接成有序单链表。
10、解：void OrderList(LNode*/p 指向待处理的第一个结点，初始指向原表头结点 HL=NULL; /HL 仍为待建立的有序表的表头指针，禄始值为空 while(p!=NULL) /把原单链表中的结点依次进行有序链接 LNode* q=p; /q 指向待处理的结点 p=p-next; /p 指向下一个待处理的结点LNode* ap=NULL,*cp=HL; /cp 指向有序表中待比较的结点，ap 指向其前驱结点 while(cp!=NULL) /为插入 q 结点寻找插入位置 if(q-datadata) break; else ap=cp; cp=cp-next; /将 q 结点
11、插入到 ap 和 cpxf hko pp uj q-next=cp; if(ap=NULL) HL=q; else ap-next=q; 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。 解：LNode*Mergel(LNode* /a 结点作为结果的有序单链表的表头附加结点，这样便于处理，处 理 /结束后返回 a 结点的镄针域的值 LNode*p= /p 指向结果的有序单链表的表尾结点 p-next=NULL;/初始指向表头附加结点 while(p1!=NULL)p1=p1-next; else p-next=p2;p2=p2-; p=p-next; if(p1!=NULL)p
12、-next=p1; if(p2!=NULL)p-next=p2; p1=p2=NULL; return a.next; 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假 定两个有序单链表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为 (2,3,8,8,9,10,15, 16,20)。 解：LNode*Merge2(LNode*p1,LNode*p2) /根据两个有序单链表生成一个新的有序单链表 LNode a; /用 a 作为新的有序单链表的表头附加结点 LNode*p= /p 指向结果有序单链表的表尾结点 p-next=NULL;
13、/初始指向表头附加结点 while(p1!=NULL if(p1-datadata) /由 p1-data 建立新结点，然后 p1 指针后移 newptr-data=p1-data; p1=p1-next; else /由 p2-data 建立新结点，然后 p2 指针后移 newptr-data=p2-data; p2=p2-next; /将 newptr 结点插入到结果的有序表的表尾 p-next=newptr; p=newptr; while(p1!=NULL) /继续处理 p1 单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p1-data;
14、p1=p1-next; p-next=newptr; p=newptr; while(p2!=NULL) /继续处理 p2 单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p2-data; p2=p2-next; p-next=newptr; p=newptr; p-next=NULL; return a.next; 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包 含原单链表中所有 元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数 的结点。原有单链表 保持不变。 解：void Separate(LNode*HL
15、,LNode* /a 和 b 结点分别作为 p1 和 p2 单链表的表头附加结点 LNode*t1= /t1 和 t2 分别作为指向 p1 和 p2 单链表的 /表尾结点，初始指向表头附加结点 Lnode*p=HL; while(p!=NULL) /每循环一次产生一个新结点，并把它加入到 p1 或 p2 单链表 /的未尾 LNode*newptr=new LNode; if(p-data%2=1) newptr-data=p-data; t1-next=newptr; t1=newptr; else newptr-data=p-data; t2-next=newptr; t2=newptr; p=p-next; t1-next=t2-next=NULL; p1=a.next;p2=b.next; /把指向两个单链表的表头结点的指针分别赋给 /p1 和 p2 返回 6.编写一个算法，使用表头附加结点的循环单链表
