数据结构习题参考答案

习题1参考答案1至8题答案略。9.（1）【解】该逻辑结构为线性结构，其图形表示如下：（2）【解】该逻辑结构为树型结构，其图形表示如下：（3）【解】该逻辑结构为图型结构，其图形表示如下：（4）【解】该逻辑结构为线性结构，其图形表示如下：10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType类型。每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。图书信息表编号书名作者出版社出版日期1数据结构顾泽元北京航空航天大学出版社2011年6月2高等数学李四北京航空航天大学出版社2009年1月3计算方法张五清华大学出版社2008年12月根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。所以，现用抽象数据类型bookList表示问题模型，其逻辑结构与基本操作的定义如下：（1）逻辑结构bookList=(D,{r})D={bi|bi为bookType类型的元素，i=1,2,3,.....,n，n≥0}r={bki,bi+1|i=1,2,…,n-1,n≥0}（2）基本操作①初始化操作函数：InitBookList(&BL)。c1c2c3cn……bcdeaSunMonTueWedThuFriSatbcdefghjika初始条件：图书表BL不存在。操作结果：构造一个空的图书表BL。②求图书表长度操作函数：bookListLength(BL)。初始条件：图书表BL已存在。操作结果：返回图书表BL中所包含的数据元素（图书）的个数。③取图书表中元素操作函数：getBook(BL,i,&b)。初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)。操作结果：用b返回图书表BL中的第i个数据元素的值。④按编号查找操作函数：locateById(BL,id)。初始条件：图书表BL已存在，id是给定的一个图书编号。操作结果：返回图书表BL中图书编号为id的数据元素的位序，若这样的数据元素不存在，则返回0。⑤按编号查找操作函数：locateByName(BL,i,name)。初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)，name是给定的一个图书名。操作结果：从图书表BL中第i个元素开始，查找图书名与给定name相等的第一个元素，若找到则返回其位序，否则返回0。⑥插入图书操作函数：insertBook(&BL,i,b)。初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)+1。操作结果：在图书表BL的第i个位置上插入一个值为b的新元素，使线性表的长度增1。⑦删除操作操作函数：deleteBook(&BL,i,&b)。初始条件：线性表L已存在，1≤i≤listLength(L)。操作结果：删除图书表BL的第i个数据元素，并用b返回其值，使线性表的长度减1。11.（1）【解】函数体内为简单语句，时间复杂度为T(n)=O(1)（2）【解】选取的基本语句为“if(a[i]a[k])k=i;”其执行频度为n-1，时间复杂度为T(n)=O(n)。（3）【解】选取的基本语句为最内层的循环体语句“total+=a[i][j];”，其执行频度为n(n+1)/2，时间复杂度为T(n)=O(n2)。（4）【解】选取的基本语句为最内层的循环体语句“c[i][j]+=a[i][k]*b[k][j];”，其执行频度为n3，时间复杂度为T(n)=O(n3)。（5）【解】函数有两个并列的循环，其问题规模分别为n和m，对于第一个for循环选取的基本语句为“if(a[i]a[max])max=i;”，其执行频度为n-1；对于第二个for循环选取的基本语句为“if(b[i]b[min])min=i;”，其执行频度为m-1。所以该函数的时间复杂度为T(n,m)=O(n+m)。（6）【解】选取的基本语句为while的循环体，其执行频度为max{1|kikin}，时间复杂度为T(n)=O(n)。12.【解】算法（1）中有两个并列的循环，每个循环的循环体语句执行次数均为n，故该函数的语句频度为2n。算法（2）只用了一个循环，其循环体语句执行次数为n，即该函数的语句频度为n。所以算法（1）与算法（2）相比较，算法（1）的时间效率更好。但它们的时间复杂度都为O（n），这说明：随着n值的增大，这两个函数执行时间的增长率相同，都是线性增长的。13.【解】由题意，设计程序如下：#includestdio.h#includestdlib.hstructstuInfo{intnum;charname[18];intscore;};voidinputInfo(structstuInfostus[],intn){//输入n个同学信息存于数组stus中inti;for(i=0;in;i++){printf(输入%d个学生信息：\n,i+1);printf(学号：);scanf(%d,&stus[i].num);printf(姓名：);scanf(%s,stus[i].name);printf(成绩：);scanf(%d,&stus[i].score);}}voidsortByScore(structstuInfostus[],intn){//将数组stus中n个同学信息按成绩进行递减排序inti,j,k;structstuInfotemp;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)if(stus[j].scorestus[k].score)k=j;if(k!=i){temp=stus[i];stus[i]=stus[k];stus[k]=temp;}}}voidoutputInfo(structstuInfostus[],intn){//输出数组stus中n个同学信息报表inti;printf(%6s%17s%6s\n,学号,姓名,成绩)；for(i=0;in;i++)printf(%6d%17s%6d\n,stus[i].num,stus[i].name,stus[i].score);}intmain(){intn;structstuInfo*stus;printf(输入学生数:);scanf(%d,&n);stus=(structstuInfo*)malloc(n*sizeof(structstuInfo));if(!stus){printf(内存空间溢出！\n);return-2;}inputInfo(stus,n);sortByScore(stus,n);outputInfo(stus,n);system(pause);}14.【解】由题意，函数设计如下：StatusTriArea(doublea,doubleb,doublec,double&area){doubles;if(a=0||b=0||c=0)returnERROR;if(a+b=c||a+c=b||b+c=a)returnERROR;s=(a+b+c)/2;area=sqrt(s*(s-a)*(s-b)*(s-c));returnOK;}15.【解】由题意，设欲交换的变量为int类型，则swap函数设计如下：voidswap(int&a,int&b){inttemp;temp=a;a=b;b=t;}习题2参考答案1.属于同一数据对象2.A3.20084.C5.n-i+1、n-i6.A7.D8.（1）s-next=p-next;p-next=s;（2）q=p-next;p-next=q-next;free(p);（3）q-next=L-next;L-next=q;L-next==NULL（4）q-next=L;L=q;L==NULL9.（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-next;s-pre=L;L-next-pre=s;L-next=s;10.略11.【解】算法如下所示：voidunion(ListLa,ListLb,List&Lc){inti=1,j=1,k=1,m;LElemTypex,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插入。算法如下所示：StatusinsertOrderList(SqList&L,LelemTypee){inti;if(L.length==L.listSize){//若存储空间已满，则追加存储空间newBase=(LElemType*)realloc(L.base,(L.listSize+ListSpaceIncr)*sizeof(LElemType));if(!newBase)returnOVERFLOW;//存储空间扩充失败L.base=newBase;L.listSize+=ListSpaceIncr;//存储空间扩充成功}for(i=L.length-1;i=0;i--)//查找插入位置，并进行元素后移if(eL.base[i])L.base[i+1]=L.base[i];elsebreak;L.base[i+1]=e;L.length++;returnOK;}13.【解】算法如下所示。voidreverse(SqList&L){inti;LElemTypet;for(i=0;i=L.length/2-1;i++){t=L.base[i];L.base[i]=L.base[L.length-i-1];L.base[L.length-i-1]=t;}}14.【解】算法如下所示：voidInverseList(LinkList&L){LinkListp,q;p=L-next;L-next=NULL;while(p){q=p-next;p-next=L-next;L-next=p;p=q;}}15.【解】算法如下所示：intcount(LinkListL,LElemTypex){intn=0;LNode*p;p=L-next;while(p!=NULL){if(p-data==x)n++;p=p-next;}returnn;}16.【解】算法如下所示：voiddelinsert(LinkList&L){LNode*p,*pre,*q;p=L-next;//p是链表的工作指针pre=L;//pre指向链表中数据域最小值结点的前驱q=p;//q指向数据域最小值结点，初始假定是首元结点while(p-n