1、数据结构习题参考答案习题1 参考答案1至8题答案略。9.（1）【解】该逻辑结构为线性结构，其图形表示如下： SunMonTueWedThuFriSat（2）【解】该逻辑结构为树型结构，其图形表示如下：bcdefghjika（3）【解】该逻辑结构为图型结构，其图形表示如下：bcdea（4）【解】该逻辑结构为线性结构，其图形表示如下：c1c2c3cn10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType类型。每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。可用一个表格（如下表）的形式表示图书间的逻辑关系，即该
2、问题数学模型可采用简单的线性结构来表示。图书信息表编号书名作者出版社出版日期1数据结构顾泽元北京航空航天大学出版社2011年6月2高等数学李 四北京航空航天大学出版社2009年1月3计算方法张 五清华大学出版社2008年12月根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。所以，现用抽象数据类型bookList表示问题模型，其逻辑结构与基本操作的定义如下：（1）逻辑结构bookList=( D, r )D=bi| bi为bookType类型的元素，i=1,2,3, ., n，n0r= | i=1,2, n-1, n0 （2）基本操作初始化操作函数：InitB
3、ookList(&BL)。初始条件：图书表BL不存在。操作结果：构造一个空的图书表BL。求图书表长度操作函数：bookListLength(BL)。初始条件：图书表BL已存在。操作结果：返回图书表BL中所包含的数据元素（图书）的个数。取图书表中元素操作函数：getBook(BL, i, &b)。初始条件：图书表BL已存在，且1ibookListLength(BL)。操作结果：用b返回图书表BL中的第i个数据元素的值。按编号查找操作函数：locateById(BL, id)。初始条件：图书表BL已存在，id是给定的一个图书编号。操作结果：返回图书表BL中图书编号为id的数据元素的位序，若这样的数
4、据元素不存在，则返回0。按编号查找操作函数：locateByName(BL, i, name)。初始条件：图书表BL已存在，且1ibookListLength(BL)，name是给定的一个图书名。操作结果：从图书表BL中第i个元素开始，查找图书名与给定name相等的第一个元素，若找到则返回其位序，否则返回0。插入图书操作函数：insertBook(&BL, i, b)。初始条件：图书表BL已存在，且1ibookListLength(BL)+1。操作结果：在图书表BL的第i个位置上插入一个值为b的新元素，使线性表的长度增1。删除操作操作函数：deleteBook(&BL, i, &b)。初始条件
5、：线性表L已存在，1ilistLength(L)。操作结果：删除图书表BL的第i个数据元素，并用b返回其值，使线性表的长度减1。11. （1）【解】函数体内为简单语句，时间复杂度为T(n)=O(1)（2）【解】选取的基本语句为“if(aiak) k=i;”其执行频度为n-1，时间复杂度为T(n)=O(n)。（3）【解】选取的基本语句为最内层的循环体语句“total+=aij;”，其执行频度为n(n+1)/2，时间复杂度为T(n)=O(n2)。（4）【解】选取的基本语句为最内层的循环体语句“cij+=aik*bkj;”，其执行频度为n3，时间复杂度为T(n)=O(n3)。（5）【解】函数有两个并
6、列的循环，其问题规模分别为n和m，对于第一个for循环选取的基本语句为“if(aiamax) max=i;”，其执行频度为n-1；对于第二个for循环选取的基本语句为“if(bibmin) min=i;”，其执行频度为m-1。所以该函数的时间复杂度为T(n,m)=O(n+m)。（6）【解】选取的基本语句为while的循环体，其执行频度为max，时间复杂度为T(n)=O()。12. 【解】算法（1）中有两个并列的循环，每个循环的循环体语句执行次数均为n，故该函数的语句频度为2n。算法（2）只用了一个循环，其循环体语句执行次数为n，即该函数的语句频度为n。所以算法（1）与算法（2）相比较，算法（1
7、）的时间效率更好。但它们的时间复杂度都为O（n），这说明：随着n值的增大，这两个函数执行时间的增长率相同，都是线性增长的。13. 【解】由题意，设计程序如下：#include #include struct stuInfo int num; char name18; int score;void inputInfo(struct stuInfo stus, int n) /输入n个同学信息存于数组stus中 int i; for(i=0;in;i+) printf(输入%d个学生信息：n, i+1); printf(学号：); scanf(%d, &stusi.num); printf(姓名：
8、); scanf(%s, stusi.name); printf(成绩：); scanf(%d, &stusi.score); void sortByScore(struct stuInfo stus, int n) /将数组stus中n个同学信息按成绩进行递减排序 int i,j,k; struct stuInfo temp; for(i=0;in-1;i+) k=i; for(j=i+1;jstusk.score) k=j; if(k!=i) temp=stusi; stusi=stusk;stusk=temp; void outputInfo(struct stuInfo stus, i
9、nt n) /输出数组stus中n个同学信息报表 int i; printf(%6s %17s %6sn, 学号, 姓名, 成绩)； for(i=0;in;i+) printf(%6d %17s %6dn, stusi.num, stusi.name, stusi.score);int main() int n; struct stuInfo *stus; printf(输入学生数:); scanf(%d, &n); stus=(struct stuInfo*)malloc(n*sizeof(struct stuInfo); if(!stus) printf(内存空间溢出！n); return
10、 -2; inputInfo(stus, n); sortByScore(stus, n); outputInfo(stus, n); system(pause);14.【解】由题意，函数设计如下：Status TriArea(double a, double b, double c, double &area) double s; if(a=0|b=0|c=0) return ERROR; if(a+b=c|a+c=b|b+cnext=p-next; p-next=s; （2）q=p-next; p-next=q-next; free(p); （3）q-next=L-next; L-next
11、=q; L-next=NULL（4）q-next=L; L=q; L=NULL 9. （1）s-next=p-next；s-pre=p; p-next-pre=s; p-next=s;（2）s-pre=p-pre; s-next=p; p-pre-next=s; p-pre=s;（3）q=p-next; p-next=q-next; q-next-pre=p; free(q);（4）q=ppre; p-pre=q-pre; q-pre-next=p; free(q);（5）p-pre-next =p-next; p-next-pre= p-pre; free(p);（6）s-next=L-ne
12、xt; s-pre=L; L-next-pre =s; L-next=s;10. 略11. 【解】算法如下所示： void union(List La,List Lb,List &Lc) int i=1,j=1,k=1,m; LElemType x,y,e; while(!listEmpty(La)&!listEmpty(Lb) getElem(La,i,x); getElem(Lb,j,y); if(xy) listInsert(Lc,k,x); i+; else listInsert(Lc,k,y); j+; k+;if(listEmpty(La) for(m=j;m=listLength
13、(Lb);m+) listInsert(Lc,k+,getElem(Lb,m,e);else for(m=i;m=0; i-) /查找插入位置，并进行元素后移 if(eL.basei) L.basei+1=L.basei; else break; L.basei+1=e; L.length+; return OK;13. 【解】算法如下所示。 void reverse(SqList &L) int i; LElemType t; for(i=0;inext; L-next= NULL; while(p) q=p-next; p-next=L-next; L-next=p; p=q; 15.【解
14、】算法如下所示：int count(LinkList L, LElemType x) int n=0; LNode *p; p=L-next; while(p!=NULL) if(p-data= =x) n+; p=p-next; return n;16.【解】算法如下所示：void delinsert(LinkList &L) LNode *p,*pre,*q;p=L-next; /p是链表的工作指针 pre=L; /pre指向链表中数据域最小值结点的前驱 q=p; /q指向数据域最小值结点，初始假定是首元结点 while(p-next!=NULL) if(p-next-datadata)
15、/找到新的最小值结点 pre=p; q=p-next; p=p-next; if(q!=L-next) /若最小值是第一元素结点，则不需再操作 pre-next=q-next; /将最小值结点从链表上摘下 q-next=L-next; /将q结点插到头结点之后 L-next=q; 17. 【解】该算法的时间复杂度为O(n2)，而算法2-16的时间复杂度为O(n)，显然算法2-16的效率更高。18. 【解】不带头结点的单链表的插入操作listInsert(&L, i, e)和删除操作listDelete(&L, i, &e)的算法如下：Status listInsert(LinkList &L,
16、 int i, LElemType e) /在不带头结点单链表L的第i个位置插入一个值为e的结点 LNode *p=L,*q; /p用于查找第i-1个结点，初始指向头结点；q用于指向欲插入结点 int j=1; if(i=1) q=(LNode*)malloc(sizeof(LNode); /生成新结点 if(!q) return OVERFLOW; q-data=e; q-next=L; L=q; return OK; while (jnext) p=p-next; j+; if(j=i-1) /若p所指结点第j个结点为第i-1个结点时，在其后插入新结点 q=(LNode*)malloc(s
17、izeof(LNode); /生成新结点 if(!q) return OVERFLOW; q-data=e; /将e赋给新结点的数据域 q-next=p-next; p-next=q; return OK; else return ERROR; /第i-1个结点不存在，插入位置不正确Status listDelete(LinkList &L, int i, LElemType &e) /删除不带头结点单链表L的第i个元素 LNode *p=L,*q; int j=1; if(i=1) L-data=e; L=L-next; free(p); return OK; while(jnext) p=
18、p-next; j+; if(j=i-1&p-next) /当p所指结点为第i-1个结点且第i个结点存在时，执行删除 q=p-next; p-next=q-next; e=q-data; /由e返回删除元素的值 free(q); return OK; else return ERROR;若单链表带有头结点，则在首元结点的位置上插入新结点或者是删除首先结点的情况与在链表中间位置插入新结点或者是删除中间某个结点的情况是相同的，可以统一处理，但若单链表不带头结点，则在首元结点的位置上插入新结点或者是删除首先结点的情况需要特殊处理，由此可见头结点的好处。19. 【解】算法如下：int listLeng
19、th(LinkList L) /求循环单链表L的长度 LNode *p=L; /p指向头结点 int j=0; /j用于计数，表示p所指结点的位序 while(p-next!=L) /p所指结点存在 p=p-next; /指针后移，指向其后继 j+; /计数器加1 return j; Status listEmpty(LinkList L) /循环单链表的判空操作 if(L-next=L) return TRUE; else return FALSE;20.【解】具体算法如下：Status swap(DLNode *p) DLNode *q； if(p-next=p-prior) return
20、 ERROR; q=p-next; p-next=q-next; q-next-prior= p; q-prior= p-prior; q-next=p; p-prior-next=q; p-prior=q; return OK; 21. 【解】算法如下。void setUnion(mySetType &A, mySetType B) /集合的并集运算，实现A=AB int i,len1,len2,e; len1=listLength(A); len2=listLength(B); for(i=1;i=len2;i+) getElem(B,i,e); if(!locateElem(A, e)
21、listInsert(A, +len1, e); void setIntersection(mySetType A, mySetType B, mySetType &C) /集合交集运算，实现C=AB int i,e,len,k=0; clearList(C); k=0; /集合C清空；用k保存当前集合C的长度 len=listLength(A); for(i=1; inext; while(pb!=NULL) pa=La-next; while(pa!=NULL&pa-data!=pb-data) pa=pa-next; if(pa=NULL) s=(LinkList) malloc (si
22、zeof(LNode); s-data=pb-data; s-next=La-next; La-next=s; pb=pb-next;23. 【解】一元多项式的创建操作、输出操作及测试主函数的参考算法如下： void CreatPoly(Poly &L, int n) /一元多项式的创建操作，其中n为一元多项式的项数 int i,coef,expn; Poly p,s; L=(Poly)malloc(sizeof(struct PNode); L-next=NULL; p=L; for(i=1;icoef=coef;s-exp=expn; s-next=NULL;p-next=s;p=s; v
23、oid OutputPoly(Poly L) /一元多项式的输出操作 int flag=1; /flag用来是否为第一项的标识 Poly p; p=L-next; while(p) if(flag) printf(%dX%d,p-coef,p-exp); flag=0; else printf(%+dX%d,p-coef,p-exp); p=p-next; printf(n); int main() Poly La,Lb; int n; printf(Creat Poly La:n); printf(t Input the number of items of La:); scanf(%d,&n); CreatPoly(La,n); printf(nLa(x)=); OutputPoly(La); printf(Creat Poly Lb:n); printf(tInput the number of items of Lb:); scanf(%d,&n); CreatPoly(Lb,n); printf(nLb(x)=); OutputPoly(Lb); PolyAdd(La,Lb); printf(Lc(a)=La(x)+Lb(x)=); OutputPoly(La); syste
