《数据结构习题和答案》由会员分享，可在线阅读，更多相关《数据结构习题和答案（35页珍藏版）》请在金锄头文库上搜索。
1、 .wd.习题1参考答案1至8题答案略。9.1【解】该逻辑构造为线性构造，其图形表示如下：SunMonTueWedThuFriSat2【解】该逻辑构造为树型构造，其图形表示如下：bcdefghjika3【解】该逻辑构造为图型构造，其图形表示如下：bcdea4【解】该逻辑构造为线性构造，其图形表示如下：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 基本操作初始化操作函数：InitBookList(&BL)。初始条件：图
3、书表BL不存在。操作结果：构造一个空的图书表BL。求图书表长度操作函数：bookListLength(BL)。初始条件：图书表BL已存在。操作结果：返回图书表BL中所包含的数据元素图书的个数。取图书表中元素操作函数：getBook(BL,i, &b)。初始条件：图书表BL已存在，且1ibookListLength(BL)。操作结果：用b返回图书表BL中的第i个数据元素的值。按编号查找操作函数：locateById(BL,id)。初始条件：图书表BL已存在，id是给定的一个图书编号。操作结果：返回图书表BL中图书编号为id的数据元素的位序，假设这样的数据元素不存在，那么返回0。按编号查找操作函数
4、：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)。初始条件：线性表L已存在，1ilistLength(L
5、)。操作结果：删除图书表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【解】函数有两个并列的循环，其问题规模分别为n和m，对于第一个for循环选取的 基本语
6、句为“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的时间效率更好。但它们的时间复杂度都为On，这说明：随着n值的增大，这两个函数执行时间的增
7、长率一样，都是线性增长的。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(姓名：); scanf(%s, stusi.name); printf(成绩：); scanf(%d, &s
8、tusi.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, int n) /输出数组stus中n个同学信息报表 int i; printf(%6s %17s %6s
9、n, 学号, 姓名, 成绩)； 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 -2; inputInfo(stus, n); sortByScore(stus, n); outp
10、utInfo(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; 2q=p-next; p-next=q-next; free(p);3q-next=L-next;L-next=q;L-next=NULL4q-next=L; L=q; L=NULL 9.1s-next=p-next；s-p
11、re=p; p-next-pre=s; p-next=s;2s-pre=p-pre;s-next=p; p-pre-next=s; p-pre=s;3q=p-next; p-next=q-next; q-next-pre=p; free(q);4q=ppre; p-pre=q-pre; q-pre-next=p; free(q);5p-pre-next =p-next; p-next-pre= p-pre;free(p);6s-next=L-next; s-pre=L; L-next-pre =s; L-next=s;10. 略11.【解】算法如下所示：void union(List La,L
12、ist Lb,List &Lc) inti=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(Lb);m+) listInsert(Lc,k+,getElem(Lb,m,e);elsefor(m=i;m=listLength(La);m+) listInsert(Lc,k+,getElem(La,m,e); 12.【解】要让插入新元素后的顺序表仍然按值递增有序，必须把x插入到表中第一个大于x的元素之前。应先在表中找到该位置，然后将该位置以后的所有元素后移一位，空出一个位置，再将x插入。算法如下所示：Status ins
