《严蔚敏数据结构题集(C语言版)史上最全答案（一题可有多解）.doc》由会员分享，可在线阅读，更多相关《严蔚敏数据结构题集(C语言版)史上最全答案（一题可有多解）.doc（203页珍藏版）》请在三一文库上搜索。
1、第1章 绪论1.1解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类
2、型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3 解：1.4 解：ADT Complex数据对象：D=r,i|r,i为实数数据关系：R=基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C，其实部和虚部分别为re和imDestr
3、oyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个ADT ComplexADT RationalNumber数据对象：D=s,m|s,m为自然数，且m不为0数据关系：R=基本
4、操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两
5、个元素中值较小的一个ADT RationalNumber1.5 试画出与下列程序段等价的框图。(1) product=1; i=1; while(i=n) product *= i; i+; (2) i=0; do i+; while(i!=n) & (ai!=x);(3) switch case x438时，1.14 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快1.15 试用数学归纳法证明：(1) (2) (3) (4) 1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解：int max3(int x,int y,int z)if(xy)
6、if(xz) return x;else return z;elseif(yz) return y;else return z;解2：void print_descending(int x,int y,int z)/按从大到小顺序输出三个数 scanf(%d,%d,%d,&x,&y,&z); if(xy) xy; /为表示交换的双目运算符,以下同 if(yz) yz; if(xy) xy; /冒泡排序 printf(%d %d %d,x,y,z);/print_descending 解3:（上机已实现）要求实现下列函数：void Descend(int &x, int &y, int &z);
7、 /* 按从大到小顺序返回x，y和z的值 */void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值 */ int temp; if(xy) temp=x;x=y;y=temp; if(y=temp) y=temp; elsey=x;x=temp; 1.17 解：k0为阶数，n为数列的第n项int Fibonacci(int k,int n)if(k1) exit(OVERFLOW);int *p,x;p=new intk+1;if(!p) exit(OVERFLOW);int i,j;for(i=0;ik+1;i+)if(ik-1) p
8、i=0;else pi=1;for(i=k+1;in+1;i+)x=p0;for(j=0;jk;j+) pj=pj+1;pk=2*pk-1-x;return pk;解2：Status fib(int k,int m,int &f)/求k阶斐波那契序列的第m项的值fint tempd;if(k2|m0) return ERROR;if(mk-1) f=0;else if (m=k-1) f=1;elsefor(i=0;i=k-2;i+) tempi=0;tempk-1=1; /初始化for(i=k;i=m;i+) /求出序列第k至第m个元素的值sum=0;for(j=i-k;ji;j+) sum
9、+=tempj;tempi=sum;f=tempm;return OK;/fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(km). 解3:（上机已实现）要求实现下列函数：Status Fibonacci(int k, int m, int &f);/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/* 否则（比如，参数k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int te
10、mp200,i,j,sum; if(k2|m0) return ERROR; if(mk-1) f=0; else if(m=k-1) f=1; else for(i=0;i=k-2;i+) tempi=0; tempk-1=1; /初始化 for(i=k;i=m;i+) /求出序列第k至第m个元素的值 sum=0; for(j=i-k;j=i-1;j+) sum+=tempj; tempi=sum; f=tempm; return OK;1.18 解：typedef enumA,B,C,D,E SchoolName;typedef enumFemale,Male SexType;typede
11、f structchar event3; /项目SexType sex;SchoolName school;int score; Component;typedef structint MaleSum;/男团总分int FemaleSum;/女团总分int TotalSum;/团体总分 Sum;Sum SumScore(SchoolName sn,Component a,int n)Sum temp;temp.MaleSum=0;temp.FemaleSum=0;temp.TotalSum=0;int i;for(i=0;in;i+)if(ai.school=sn)if(ai.sex=Male
12、) temp.MaleSum+=ai.score;if(ai.sex=Female) temp.FemaleSum+=ai.score;temp.TotalSum=temp.MaleSum+temp.FemaleSum;return temp;解二：typedef struct char *sport; enummale,female gender; char schoolname; /校名为A,B,C,D或E char *result; int score; resulttype; typedef struct int malescore; int femalescore; int tota
13、lscore; scoretype; void summary(resulttype result )/求各校的男女总分和团体总分,假设结果已经储存在result 数组中scoretype score;i=0;while(resulti.sport!=NULL)switch(resulti.schoolname)case A:score 0 .totalscore+=resulti.score;if(resulti.gender=0) score 0 .malescore+=resulti.score;else score 0 .femalescore+=resulti.score;break
14、;case B:score.totalscore+=resulti.score;if(resulti.gender=0) score.malescore+=resulti.score;else score.femalescore+=resulti.score;break;i+；for(i=0;i5;i+)printf(School %d:n,i);printf(Total score of male:%dn,scorei.malescore);printf(Total score of female:%dn,scorei.femalescore);printf(Total score of a
15、ll:%dnn,scorei.totalscore);/summary 解3:（上机已实现）要求实现下列函数：void Scores(ResultType *result, ScoreType *score); /* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */相关数据类型定义如下：typedef enum female,male Sex;typedef struct char *sport; / 项目名称 Sex gender; /
16、 性别（女：female；男：male） char schoolname; / 校名为A,B,C,D或E char *result; / 成绩 int score; / 得分（7,5,4,3,2或1） ResultType;typedef struct int malescore; / 男子总分 int femalescore; / 女子总分 int totalscore; / 男女团体总分 ScoreType;void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已
17、经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ int i=0; while(resulti.sport!=NULL) switch(resulti.schoolname) case A: score0.totalscore+=resulti.score; if(resulti.gender=0) score0.femalescore+=resulti.score; else score0.malescore+=resulti.score; break; case B: score1.totalscore+=res
18、ulti.score; if(resulti.gender=0) score1.femalescore+=resulti.score; else score1.malescore+=resulti.score; break; case C: score2.totalscore+=resulti.score; if(resulti.gender=0) score2.femalescore+=resulti.score; else score2.malescore+=resulti.score; break; case D: score3.totalscore+=resulti.score; if
19、(resulti.gender=0) score3.femalescore+=resulti.score; else score3.malescore+=resulti.score; break; case E: score4.totalscore+=resulti.score; if(resulti.gender=0) score4.femalescore+=resulti.score; else score4.malescore+=resulti.score; break; i+; for(i=0;i5;i+) printf(School %d:n,i); printf(Total sco
20、re of male:%dn,scorei.malescore); printf(Total score of female:%dn,scorei.femalescore); printf(Total score of all:%dnn,scorei.totalscore); 1.19 解：#include#include#define MAXINT 65535#define ArrSize 100int fun(int i);int main()int i,k;int aArrSize;coutk;if(kArrSize-1) exit(0);for(i=0;iMAXINT) exit(0)
21、;else ai=2*i*ai-1;for(i=0;iMAXINT) exit(0);else coutai ;return 0;解二：Status algo119(int aARRSIZE)/求i!*2i序列的值且不超过maxintlast=1;for(i=1;i=ARRSIZE;i+) ai-1=last*2*i; if(ai-1/last)!=(2*i) reurn OVERFLOW; last=ai-1; return OK;/algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 1.20 void polyvalue()float ad;float
22、*p=a;printf(Input number of terms:);scanf(%d,&n);printf(Input the %d coefficients from a0 to a%d:n,n,n);for(i=0;i=n;i+) scanf(%f,p+);printf(Input value of x:);scanf(%f,&x);p=a;xp=1;sum=0; /xp用于存放x的i次方for(i=0;i=n;i+)sum+=xp*(*p+);xp*=x;printf(Value is:%f,sum);/polyvalue解3:（上机已实现）要求实现下列函数：Status Serie
23、s(int ARRSIZE, int a);/* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ int s=1,i,t; for(i=1;it) return OVERFLOW; s=ai-1; return OK;1.20 解：#include#include#define N 10
24、double polynomail(int a,int i,double x,int n);int main() double x;int n,i;int aN;coutx;coutn;if(nN-1) exit(0);cout输入多项式的系数a0-an:;for(i=0;iai;coutThe polynomail value is polynomail(a,n,x,n)0) return an-i+polynomail(a,i-1,x,n)*x;else return an;本算法的时间复杂度为o(n)。解3:（上机已实现）要求实现下列函数：float Polynomial(int n,
25、int a, float x0);/* 求一元多项式的值P(x0)。 */* 数组a的元素ai为i次项的系数，i=0,1,.,n */float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ int i; float t=1,s,p=0; /t存放x的i次方 for(i=0;i=n;i+) if(i!=0) t*=x; s=ai*t; p+=s; return p;第2章 线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。解：头指针是指向链表中第一
26、个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2 填空题。解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进
27、行特殊处理。2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4 解： 2.5 解：2.6 解：a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d. (9) (1) (6)2.7 解：a. (11) (3) (14)b. (10) (12) (8) (3) (14)c. (10) (12) (7) (3) (14)d. (12) (11) (3) (14)e. (9) (11) (3) (14)2.8 解：a. (7) (3) (6) (12)b. (8) (4)
28、(5) (13)c. (15) (1) (11) (18)d. (16) (2) (10) (18)e. (14) (9) (17)2.9 解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。 (2) 将单循环链表拆成两个单循环链表。2.10 解：Status DeleteK(SqList &a,int i,int k)/从顺序存储结构的线性表a中删除第i个元素起的k个元素/注意i的编号从0开始int j;if(ia.length-1|ka.length-i) return INFEASIBLE;for(j=0;j=k;j+)a.elemj+i=a.elemj+i+k;a.lengt
29、h=a.length-k;return OK;解二：Status DeleteK(SqList &a,int i,int k)/删除线性表a中第i个元素起的k个元素if(i1|ka.length) return INFEASIBLE;for(count=1;i+count-10,xva.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList 解3:（上机已实现）要求实现下列函数：void Inser
30、tOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;void InsertOrderList(SqList &L, ElemType x)/ 在有序的顺序表 L 中保序插入数据元素 x int i,j; i=L.length-1; while(i=0&x=i+1;j-) L.elemj+1=L.elemj; L.elemi+1=x; L.length+; 2.12 解：Status
31、 CompareOrderList(SqList &A,SqList &B)int i,k,j;k=A.lengthB.length?A.length:B.length;for(i=0;iB.elemi) j=1;if(A.elemik) j=1;if(B.lengthk) j=-1;if(A.length=B.length) j=0;return j;解二：int ListComp(SqList A,SqList B)/比较字符表A和B,并用返回值表示结果,值为正,表示AB;值为负,表示AB;值为零,表示A=Bfor(i=1;A.elemi|B.elemi;i+)if(A.elemi!=B.
32、elemi) return A.elemi-B.elemi;return 0;/ListComp 解3:（上机已实现）要求实现下列函数：char Compare(SqList A, SqList B);/* 比较顺序表A和B, */* 返回, 若A, 若AB */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;char Compare(SqList A, SqList B)/ 比较顺序表A和B, / 返回, 若A, 若AB int i; for(i=0;A.elemi|B.elemi;i+) if(A.elemi!=B.elemi) if(A.elemi-B.elemi0) return ; else return ; return =;2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);解：int LocateElem_L(LinkList &L,ElemTyp