数据结构习题参考答案.doc

习题1 参考答案1至8题答案略。9.（1）【解】该逻辑结构为线性结构，其图形表示如下： SunMonTueWedThuFriSat（2）【解】该逻辑结构为树型结构，其图形表示如下：bcdefghjika（3）【解】该逻辑结构为图型结构，其图形表示如下：bcdea（4）【解】该逻辑结构为线性结构，其图形表示如下：c1c2c3cn10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType类型。每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。图书信息表编号书名作者出版社出版日期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)。初始条件：图书表BL不存在。操作结果：构造一个空的图书表BL。求图书表长度操作函数：bookListLength(BL)。初始条件：图书表BL已存在。操作结果：返回图书表BL中所包含的数据元素（图书）的个数。取图书表中元素操作函数：getBook(BL, i, &b)。初始条件：图书表BL已存在，且1ibookListLength(BL)。操作结果：用b返回图书表BL中的第i个数据元素的值。按编号查找操作函数：locateById(BL, id)。初始条件：图书表BL已存在，id是给定的一个图书编号。操作结果：返回图书表BL中图书编号为id的数据元素的位序，若这样的数据元素不存在，则返回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)。初始条件：线性表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）【解】函数有两个并列的循环，其问题规模分别为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）的时间效率更好。但它们的时间复杂度都为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(姓名：); scanf(%s, ); 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, int n) /输出数组stus中n个同学信息报表 int i; printf(%6s %17s %6sn, 学号, 姓名, 成绩)； for(i=0;in;i+) printf(%6d %17s %6dn, stusi.num, , 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); 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=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-next; 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(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.【解】算法如下所示：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)/找到新的最小值结点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, 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(sizeof(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=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 listLength(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 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) 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 (sizeof(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; void 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); system(pause); return 0; 习题3 参考答案1. 答案略2. 【解】可能得到的出栈序列及其操作序为： A（IOIOIOIO）、B（IIIIOOOO）、D（IOIIOOIO）不可能得到的出栈序列有：C、E（原因：其第一个出栈元素为c，则说明元素a与b已入栈但未出栈，则根据栈的后进先出特性，元素a不可能在元素b前面出栈）F（原因：其第一个出栈元素为b，则说明元素a、b、c已入栈但未出栈，则根据栈的后进先出特性，元素元素a、b、c的出栈顺序一定为c,b,a）3. （1）【解】栈空的判定条件为：S.top=0 元素e入栈操作语句为：S.baseS.top+=e; 栈顶元素出栈并将其值赋给e的操作语句为：e=S.base-S.top;（2）【解】栈空的判定条件为：S.top=-1 元素e入栈操作语句为：S.base+S.top=e; 栈顶元素出栈并将其值赋给e的操作语句为：e=S.baseS.top-;4. 【解】此双向栈的类型定义及初始化、入栈、出栈算法定义如下：typedef struct SElemType *base; int top0, top1; int stackSize; DSqStack; /SqStack为顺序栈类型Status InitDStack( DSqStack &S, int size) /初始化操作 S.base=(SElemType *)malloc(size*sizeof(SElemType); if(!S.base) return OVERFLOW; S.stackSize=size; S.top0=-1; S.top1=size; return OK;Status PushD(DSqStack &S, int i, SElemType e) /入栈操作 if(S.top0+1=S.top1) return OVERFLOW; /栈满 if(i=0)S.base+S.top0=e; /元素e入低端栈 else S.base-S.top1=e; /元素e入高端栈 return OK;Status PopD(DSqStack &S, int i, SElemType &e) /出栈操作 if(i=0) /低端栈进行出栈操作 if(S.top0=-1) return ERROR; /栈空 else e=S.baseS.top0-; return OK; else /高端栈进行出栈操作 if(S.top1=S.stackSize) return ERROR; /栈空 else e=S.baseS.top1+; return OK; 5. 【解】本题算法如下：void DtoX( int n) /n为大于等于0的十进制整数，将其转换成十六进制输出 int m; char s; SqStack S; /定义顺序栈S，栈内元素类型为int类型 printf(%d(D)=0X, n); if(x=0) printf(0n); return; InitSqStack(S, 30); while(n) push(S, n%16); n/=16; while(!stackIsEmpty(S) pos(S, m) if(m=9) printf(%d, m); else printf(%c,A+m-10); printf(n);6. 【解】本题算法如下：Status HW_String(char *str) /判断一个字符串str是否为回文，设字符串最大长度200 char ch, *s=str; int flag=1; SqStack S; /定义顺序栈S，栈内元素类型为char类型 InitSqStack(S, 200); while(*s) push(S, *s); s+; s=str; while(!stackIsEmpty(S) push(S, ch); if(ch!=*s) return FALSE; else s+; return TRUE;7. 【解】本题算法如下：int bracketsCheck3( ) /输入表达式串，检查括号匹配情况 /返回0表示匹配正确，返回1表示花括号匹配错误， /返回值2表示方括号匹配错误，返回3圆括号匹配错误， /返回4则表示有缺失右括号（花括号、方括号及圆括号）错误。 char ch, c; SqStack S; InitSqStack(S, 30); ch=getchar(); while(ch!=n) if(ch=|ch=|ch=( ) Push(S, ch); /为左括号则入栈 else switch(ch) case : if(getTop(S, c)&c=) Pop(S, c); else return 1; break; case : if(getTop(S, c)&c=) Pop(S, c); else return 2; break; case ): if(getTop(S, c)&c=() Pop(S, c); else return 3; break; ch=getchar(); if(stackIsEmpty(S) return 0; else return 4;8. 【解】修改教材算法3-8，即可得到求解迷宫问题的所有可行解算法函数Maze。为了更好地理解本算法，在此给出完整程序。#include #include #include dataStru.htypedef struct int x; int y;posType;#define Row 12#define Col 12posType nextPos(posType curPos, int d) /返回curPos沿方向d行进的下一位置 posType pos; switch(d) case 1: pos.x=curPos.x; pos.y=curPos.y+1; break; case 2: pos.x=curPos.x+1; pos.y=curPos.y; break; case 3: pos.x=curPos.x; pos.y=curPos.y-1; break; case 4: pos.x=curPos.x-1; pos.y=curPos.y; break; return pos;Status canGo(posType pos, int MRowCol) /判断pos位置是否可通 if(Mpos.xpos.y=0) return TRUE; else return FALSE;void printMaze(int MRowCol) /输出迷宫数组 int i,j; printf(t%3c, ); for(i=0; iCol; i+) printf(%2d ,i); printf(n); for(i=0;iRow;i+) printf(t%2d , i); for(j=0;jCol; j+) if(Mij=1) printf(|); else if(Mij=0)printf( ); else if(Mij=2)printf( = ); else printf(%2d ,-Mij); printf(n); printf(n);void Maze(int MRowCol, posType start, posType end, int step) /迷宫问题求解的递归算法；求从start到出口end的路径所有可行解 posType pos; int d,i,j; if (!canGo(start, M, step) return ; /start不可通，则不存在可行路径 else Mstart.xstart.y=-step; /用到该路径块步数的负值标识此路径块 if (start.x=end.x&start.y=end.y) / /到达出口 printMaze(M); system(pause); return; int flag=0; for(d=1;d=4;d+) pos=nextPos(start, d); Maze(M, pos, end, step+1); for(i=1;iRow-1; i+) /清除前一递归调用过程中所走的M中的步数值 for(j=1;jstep) Mij=0; int main() int MRowCol= /定义表示迷宫的二维数组 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1 , 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1 , 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1 , 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 , 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1 , 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1 , 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1 , 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1 , 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1 , 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 , 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ; posType start,end; start.x=1;start.y=1; end.x=10;end.y=10; printMaze(M); Maze(M,start,end,1); return 0; 9. 答案略10. Fib(n)的递归算法如下：int Fib( int n) if(n=0|n=1) return n; else return Fib(n-1)+Fib(n-2);11. （1）【解】int max_Array( int a, int n) /求数组a前n个数中的最大值，设n为大于0的数 int m; if(n=1) return a0; else m=max_array(a, n-1); return man-1? m: an-1; （2）【解】void reverseArray(int a, int n) /将数组a前n个数逆置 int temp; if(n=0|n=1) return; else temp=a0; a0=an-1; an-1=temp; /交换首尾元素 reverseArray(a+1, n-2); /递归逆置剩余元素 12. （1）【解】void traverseList(LinkList L) /利用递归算法，遍历不带头结点的单链表L if(L) visit(L-data); traverseList(L-next); （2）【解】求单链表L的长度。int listLength(LinkList L) /利用递归算法，求不带头结点的单链表L的长度 if(!L-next) return 0; else return listLength(L-next)+1;13. 【解】（1）背包问题求解的数学递归定义如下：Knap(T,n) =TRUE， 当T=0时FALSE， 当T0且n0且n=1时（2）由所给出的数学定义，设计出背包问题求解的递归算法如下：Status Knap( int T, int n) /设n件物品的重量存于全局数组W（下标1n）中 if(T=0) return TRUE; else if(T0&n1) return FALSE; else if( Knap(T-Wn,n-1) return TRUE; else if(Knap(T,n-1) return TRUE; else return FALSE; （3）欲给出一组具体解，只需当解中包括Wn时，将其输出即可。因此，算法如下：Status Knap( int T, int n) /设n件物品的重量存于全局数组W（下标1n）中 if(T=0) return TRUE; else if(T0&n1) return FALSE; else if( Knap(T-Wn,n-1) printf(%d , Wn