清华数据结构习题集答案C语言版严蔚敏

1、清华数据结构习题集答案（C语言版严蔚敏）第1章绪论简述下列术语：数据，数据元素.数据对象.数据结构、存储结构.数据类型和抽象數据类型。解：数据是对客观爭物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符 号的总称。数据元素定数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象定性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之问存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。I败据类型是一个值的集合和定义在这个值集上的一组樂作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。長对一般数据类型的扩展。

2、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的低念，但含义比一般数据类型更广.更抽象。一般数据类型由 具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型 通常由编程者定义，包括定义它所使用的数据利在这些数据上所进行的探作。在定义抽象数据类型中的数 据部分和擾作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实 现，这样抽象层次更高，更能为其他用户提供良好的使用接口。设有数据结构（D.R）,其中D = 1,2,3,4, /? = /,广=（1,2）,（2,3）,（3,

3、4）试按图论中图的画法惯例画出其逻辑结构图。试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子.分母均为自 然数且分母不为零的分数）.解：ADT Complex数据对象：Okii为实数）数据关系：R=rJ基本操作：InitComplex（&C.rc im）操作结果：构造一个复数C,其实部和虛部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k.&e)操作结果：用c返回复数C的第k元的值Put(&C,k.e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1,否则返回

4、0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回0Max(C.&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个)ADT ComplexADT RationalNumber(数据对象：DMs.nis. m为自然数，且m不为0数据关系：R=m基本操作：InitRations1Number(&R s.m)操作结果：构造一个有理数R,其分子和分母分别为s和mDestroyRationa1Number(&R)操作结果：销毁有理数RGet(R.k.&c)操作结果：用c返回有理数R的第k元的值

5、Put(&R.ke)操作结果：改变有理数R的笫k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1,否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1,否则返回0Max(R.&e)操作结果：用e返回有理数R的两个元素中值校大的一个Min(R.&e)操作结果：用e返回有理数R的两个元素中值较小的一个)?DT Rat ionalNumber试画出与下列程序段等价的框图。(1) product=l； i=l；)wh订 e(i=n) product = i；i+;(2) i=0；do while(i!=n) & (ai!=x

6、);(3) switch case xy： z=y-x； break；case x=y： z=abs (x*y)； break； default: z=(x-y)/abs(x)*abs(y)；在程序设计中.常用下列三种不同的出错处理方式：(1) 用exit语句终止执行并报告错惧；(2) 以函数的返回值区别正确返回或错误返回；)(3) 设置一个養型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。解：(l)exit #用于异常错误处理，它可以强行中断程序的执行，返回操作系统。(2) 以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3) 用整型函数进

7、行错误处理的优点是可以给出错误类型，便于迅速确定错误。在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf和printf语句；(2) 通过函数的參数显式传递；(3) 通过全局变量隐式传递。试讨论这三种方法的优缺点。解：(1)用scanf printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制， 较为烦琐，如果出现错误，则会引起整个系统的崩溃。(2) 通过函数的参数传递进行输入输出，便于实現信息的隐蔽，减少出错的可能。(3) 通过全局变量的隐式传递进行输入输出最为方便，只需侈改变量的值即可，但过多的全局变量使程 序的维护较为困难。设n为正整数。试确定下列各

8、程序段中前置以记号的语句的頻度：(1) i=l; 口；while(i=n-l) k +二 10*i；i卄；(2) i=l; k=0；do 0 k += 10*i； i+; vrh订e(i=n-l)； i=l; k=0;while (i=n-l) i+; k += 10*i；k=0；for(i=l； i=n； i+)( for(j=i； j=n； j+) k+；for(i=l； i=n； i+) for(j=l； j=i; j+) for(k=l； k=j: k+) x += delta； i=l; j=0;wh订e(i+jj) j+;else i+；(7) x=n； y=0； 十巴凹21 +

9、(1+2) + (l+2+3)+. + (H2+3,.+n)-X j-i 21 n1 1 n1 n冷Q + 1)冷工雀+眾厂+*2 /-/ /-I乙 r-1 乙 r-1=n(n +1)(2“ +1) + n(n +1) = n(n +1)(2 + 3) 12 12向下取整(8) 1100假设n为2的乘碁，并且n2,试求下列算法的时间复杂度及变* count的值(以n的函数形式表示)。 int Time(int n) count = 0；x=2；while(x438 时，n2 50/2 log 2 n判断下列各对函数/S)和g()，当“TCC时，哪个函数增长更快(1) /()= 10/72 +

10、ln(!+10 ), g(n) = 2n4 +n + l(2) /(n) = (In(n!)+5)2, g(n)=13沪(3) f(n)=n2A + yin4 +1 , g() = (ln(n!)2 +n /S)=2()+(2)2, gS) =)+/(解:(l)g(n)快(2)g(n)快(3)f(n)快(4) f(n)快试用数学归纳法证明：(1)工厂=( + 1X2“ +1)/6 (n 0) 亡=(兀心 一 l)/(x-l)(X 1,/7 0)/- 1)J-l f -l) = n2(n 1)/l试写一算法，自大至小依次输出顺序读入的三个整数X, Y和Z的值解：int max3(int x.in

11、t z)(if(xy)if(xz) return x；else return z；elseif(yz) return y；else return z；巳知k阶斐波那契序列的定:义为办=0，/ = 0，fk-2 = 0 fk- = i ；fn = fn- + fn-2 + + fn-k +试编写求k阶斐波那契序列的笫m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。解：k0为阶数，n为数列的第n项int Fibonacci(int k,int n)if(kl) exit(OVERFLOW)；int *p.x；p=new intk+l；if(!p) exit(OVERFLOW

12、)；int i,j;for(i=0；ik+l；i+)if(ik-l) pi=O；else pi=l;for (i=k+l；in+l；i+)x=p0:for(j=0；jarrsize或对某个k(l k maxint时，应按 出错处理。注意选择你认为较好的出错处理方法。解：ttincludcOttincludeOttdefine MAXINT 65535#define ArrSize 100int fun(int i)；int main()(int ik;int aArrSize；coutnEnter k：cink；if(kArrSize-l) exit(0)；for(i=0；iMAXINT) e

13、xit(0)；else ai=2*i*ai-l；for(i=0；iMAXINT) exit(0)；else coutaiN-l) exit(O)； cout输入多项式的系数aLOan：for (iO； iOn； ii) cinai :coutwThe polynomai 1 value is M0) return ani+polynomai1(ai-lx.n)*x；else return an；本算法的时问复杂度为o(n)第2章践性表描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结 点是

14、在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为 了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。填空題。解：(1)在顺序表中插入或册除一个元素，需要平均移益表中一半元素，具体移动的元素个曝邑元素 在表中的位置勺关。(2) 顺序表中逻辑上相邻的元素的物理位置住紧邻。单链表中逻辑上相邻的元素的物理位矍不一定 紧邻。 5 7 3 8 r “PQKS解:1SQSL10Tp14T16TsJ画出执行下列各行语句后各指针及链表的示意图。L= QinkList)malloc(sizeof(LNode) ； P=L；for(i=l；inext=(

15、LinkList)malloc(sizeof(LNode)； P=P-next； P-data=i*2-l；P-next=NULL；for(i=4；i=l；i) Ins丄inkList(L,i+l,i*2)； for(i=l；inext=S；(2) P-next=P-next-next ；(3) P-next=S-next；(4) S-next=P-next；(5) S-next=L；(6) S-next=NULL；(7) Q=P;(8) while(P-next!=Q) P=P-next；(9) wh订e(P-next!=NULL) P=P-next；(10) P=Q；(11) P=L；(1

16、2) L=S;(13) L=P；解：a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d(9) (1) (6)巳知L是帝表头结点的非空单後表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中 选择合适的语句序列。a. 删除P结点的直接后继结点的语句序列是.b. 删除P结点的克接前驱结点的语句序列長oC删除P结点的语句序列是d删除首元结点的语句序列是Oe. 蒯除尾元结点的语句序列是.(1) P=P-next；(2) P-next=P；(3) P-next=P-next-next ；(4) P=P-next-next；(5) while(P!=NU

17、LL) P=P-next；(6) e(Q-next!=NULL) P=Q； Q=Q-next； (7) while(P-next!=Q) P-P-next；(8) wh订e (P-next-next!=Q) P=P-next；(9) while(P-next-next!=NULL) P=P-next；(10) Q=P;(11) Q=P-next；(12) P=L;(13) L=L-next；(14) free (Q)；解：a. (11) (3) (14)b.(10)(12)(14)C(10)(12)(7)(3)(14)d.(12)(ID(14)C(9)(ID(14)巳知P结点是某双向链表的中间

18、结点.试从下列提供的答案中选择合适的语句序列. a.在P结点后插入S结点的语句序列是b在P结点前插入S结点的语句序列是。c. 蒯除P结点的直接后继结点的语句序列是。d蒯除P结点的直接前驱结点的语句序列是O(e删除P结点的语句序列是o(1) P-next=P-next-next；(2) P-pr i ou=P-pr i ou-pr i ou；(3) P-next=S；(4) P-priou=S；(5) S-next=P；(6) S-priou=P；(7) S-next=P-next；?(8) S-pr i ou=P-pr i ou；(9) P-priou-next=P-next；(10) P-p

19、riou-next=P；(11) P-next-pr i ou=P；(12) P-next-priou=S；(13) P-pri ou-next=S；(14) P-next-priou=P-priou；(15) Q=P-next；(16) Q=P-priou；(17) free(P)；(18) free(Q)；解：a. (7) (3) (6) (12)b.(8)(13)C(15)(11)(18)d.(16)(10)(18)e.(14)(17)筒述以下算法的功能。(1)StatusA(LinkedListL) q = (q,”)B = (妬,J/T B AB A, = B, = A = BA,

20、BH A B ABA B S，,a”) (yj A = (%“2,，” J B =也)C = (%片，網妇,休+|,心)m n厶=(4,“2,“)L =.an)改造为(al.a3ana2)Status ListChange_DuL(DuLinkList &L)DuLinkList p.q.r； p=L-next； r=L-pre； i = l;while(p!=r) if(i%2=0)q 二P；p-p-next；Pn(x) =+ c2xe2 + + cmxm n = em e心 -el 0 q H 0(z = 12 )mlPnMx0 P(Q=Ei(x)-%(x) PB Pn Pj pk Pi

21、Pj pk Pi Pj Pk Pi Pi Pj PkPj Pi2n 1 olor；Push(s,g )；while(!StackEmpty(s)Pop(s.e)；CurPos=；g Color二Fi11Color； g . Visited；if0 &!g. Visited &gj . Color=01lColor)Push(s.g);if0 &!g. Visited &g . Color=01dColor)Push(s.g)；void CreateGDS（ElemType gMN）int i.j;for（i=0；iM；i+）for（j=0；jN；j+）gi jl. =i;gi jl.=j;gi

22、 j. Visited=0;gi jl. Color=0；for（i=2；i5；i+）for（j=2；j4；j+）gij Color二3；for（i=5；iM-l；i+）for（j=3；j6；jMgijl. Color=3；void ShowGraphArray（ElemType gMN）int i.j;for（i=0；iM；i+）（for（j=0；jN；j+）coutgi： j Color；0n + 1 n = 0F(%) h0P/4 1sqrtA込P + - 2l P)sqrt(A、p) =p1 - A ein = 0aknin,n)= maxaknm 一 ,aknin,n -1)a(a

23、+1)2i(i-1)-1il jlij f1(i) = (n+l)i-li2c = -(n + 1)|i-j| 10 k 3n -1ab = 0s(n) = s(n-l) + an =s(n-l) + a1 +(n-l)d add(a,b) = 0总共需进行k次交换。注意最后一组可能出现不足k个元素的情况，此时最后一组为剩余元素加第一组 的前几个元素共k个构成最后一组。void RRMove(ElemType At int n)ElemType e；int i=Otj.p；while(in-k) p 二 i/kH；for(j=0；jk;j+)e=Aj；Aj=A(p*k+j)%n；A

24、(p*k+j)%n=e；i+;解：#include #define RS 4#define CS 4typedef int ElemType；typedef structElemType e；int i,j;int Flags；NodeType；void Initialize(NodeType aRSCS,ElemType ARSCS)； void SaddlePoint(NodeType aRSCS)；ElemType RowMin(NodeType aRSCS,int k):ElemType ColMax(NodeType aRSCS.int k)；void Show(NodeType a

25、RSCS)；int main()ElemType ARSCS=(),() ,() ,();NodeType aRSCS;Initialize(a.A)；SaddlePoint(a)；Show (a)；return 0；void Initialize(NodeType aRSCS.ElemType ARSCS) int i,j;for(i=0；iRS；i+)for(j=0；jCS；j+)aij.e=Aij:aijl. i=i;aijl. j=j;ai j Flags二0；) void SaddlePoint(NodeType aRSCS)

26、int i.j;ElemType x.y； for(i=0；iRS；i+)x-RowMin(a,i): for(j=0；jCS；j+)( y-ColMax(a.j)；if (ai j. ex&ai j. e=y) ai jl. Flagsl；ElemType RowMin(NodeType aRSCS.int k)ElemType x；x=ak0. e；int i；for(i=l；iaki. e)(x二akCi, e；return x；ElemType ColMax(NodeType aRSCSt int k)ElemType x；x=a0kJ. e；int i；for(i=l；iRS；i+)

27、if (xai kJ. e) *!x=aiEk e；return x；void Show(NodeType aRSCS)for(int i=0；iRS；i+)for(int j=0；jCS;j+4)if (ai j. Flags)coutiwis a sadd 1 e pointwendl；解：typedef int ElemType；class Triplepublic：int row；int col；ElemType e；TripleO virtual TripleO BOOL operator仃riple b)；BOOL operator (Triple b):;BOOL Triple：

28、operatorCTriple b)i f(row return TRIE；if(row-&col return TRUE； return FALSE；BOOL Triple：operator=(Triple b) i f (row= & col=return TRUE；elsereturn FALSE； class CSparseMatpublic：CSparseMat () virtual CSparseMat()(CSparseMat(ini r,int n)；CSparseMat operator+(CSparseMat B)；void ShowSparse(CDC* pD

29、C)；Tripleow=；m_pti col=；m_pti. e=；) void CSparseMat:ShowSparse(CDC pDC)char str10:int k=0；for(int i=0；im_nRow；i+)(for(int j-0；jText()ut (0+j*20.0+i*20t str, strlen(str)； ow-m_pti. row；k col=m_pti col ；k e二m_pt i e；i+;elseif (m_ptij) k row-m_pti row；k col=m_pti col；kJ. e=m_pt i, e+j. e；i+; j+;elsek r

30、ow=j. row；Lk.col二j col；kJ. e=j. e；jf)k+；while(im_nTrs) k. row=m_pti row；k col-m_pti col；k e=m_pt i e；i+;k+；while(jttincludeOftincludeOttdefine Max 128typedef int ElemType； typedef struct int col； ElemType e；Twin； class CSparseMatpublic：CSparseMat () (CSparseMat(int n)； virtual CSparseMat

31、()void ShowSparse(int j)；Twin* m_pt； olm_pti.e；for(i=0；im_nRow；i+)cout-请输入每行第一个非零元在二元组中的序号(没有输入-1)：； cinrposi: olj)x-m_ptk. e；k+；coutxendl ；int mainOCSparseMat A(3.3,5)；(2.1)；return 0； 解：typedef int ElemType； typedef struct OLNode int row；int col；ElemType e；struct OLNode right.down；OLNode.*0Link；class CCrossListMatOLinkRHead,*CHead；kH -1k_l1 + 2n2 + 33 +. + knkn() = 1 + 2n2 + 3n3 +. + knk 一(q + n2 + z?3 +. + 人)=1 + 工(i 一 1)坷r-ln = l + nkk nQ=n-nk =n- ogk(n(k 一 1) +1)1 n0 nQ =(k 一l)nl +1 nQ = k1 k01kh-n =k_lk-1ku 1kH 1 1 k”R刖伙-叽+1下h-S育3 一 1 2/? 3W -12n + l 3 3(2