数据结构习题集答案-C语言版(严蔚敏-吴伟民)

第1章绪论解：数据数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。解：Dddd4，Rrddd（解： 和 不为 和 ()解：试讨论这三种方法的优缺点。用和++++++++++0-解：n(n1).=2

i(i1)nni1 21n=2i1

i(i1n2i

(i2i)1n2i

i21ni2i11=12

n(n1n(n4

1n(n1)(2n3)12n（ 解：o(log2n)og2n21O2n和On0，假设现实计算机可连续107（0多天105次。（解：2n1012 n101012 fn21n4n21000gn15n4500n3hn500n3.5nlogn是是是是解：对错错对2n2和50nlognn2的值大于50nlog2n22解：n2的增长趋势快。但在n较小的时候，50nlogn的值较大。22 n250nlogn2fngnnfn10n2n10n3，gn2n4n7fnn52，gn1n25n4fnn21 ，gnn2n4fn2n32n2，gnnn2n5解：快快nni2nn1/6 0i1nni0

xixn1/x x,n0nn2i12n1 nni1n2in2 1i1和 f00，f10，…，fk20，fk11；fn

fn1fn2…fnk，nk,k1,…解：c + + 项目名称性别校名成绩得分 o / / / + = 2i.k1kn，使2k

maxint时，r r + + < nPxaxiPn

，并确定算法中每一语句的执行次数n i n 0i0inx0和nnx0 - +> 第2章线性表解：解：表中一半元素必定不一定解：。解： ) l 已知是无表头结点的单链表，且在点后入结的句列是 。在点前入结的句列是 。表插入结的句列是 表插入结的句列是 L1解： 已知删除点直后结的句列是 删除点直前结的句列是 删除点语序是 除首结的句列是 除元结的句列LL1e解： 1 已知结是双链表中结，从列供案中择适语序在点后入结的句列是 在点前入结的句列是 删除结点直后结的句列是 删除结点直前结的句列是 删除结点语序是 1ee解：1 /和 B B 解：，将 / |/ +/删除第一个元素 / / || + 1 / + 设A1am和B1bn均为顺序表，和B分别为A和B中除去最大共同前ABABABABABABAB + + /返回单链表的长度 + 解： & 个 | + + + L | / + / + / / + （和解： R e 同解： = e 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表1an逆置为an1。解：/ + 2/ L A1a2am，B12nC11ammm1n当mnC11anbnan1am当mn线性表和表利用解：/ e 和B（）（）解：/p / / L / / e 和同和排解：/、s & + + ++ /、s / / e e e e e （或）/、s & + + + + + /、s & + + + + + （或）（表或表 /、s / / e e e e e e /、s / / e e e e e e 已知，和（解：/中 / / / / e e e e 。解：/ R e ，和，其中t解：/ L / / （，解：/ (&| &) e 在至 / //和⊕ ⊕⊕⊕⊕ ⊕⊕⊕⊕域和r（）解： | | R L1a2n改造为L13ana4a2解：/. = / / + （解： L / / / / n12m已知稀疏多项式Pxcx1cxe2…cn12m

mmxem，其中nemm

1…1

0，i0i,mm1n0的算法（0 / l + + + Pxxx解：/ ++ + + + + + + + + + + + + + + + + + + + + 解：f = e 解：/ 第3章栈和队列（解：解：（ 解：（ 5 + 解：假设以和和（。（（）（）解：SXSSXX假定前第的第的第b后将后ab12n使pjpkpi解：pjpkpi解为通过输入序列pjpk

pi可以得到输出序列pipj

pk使pjpkpi。↑ ×↑输入字符主要操作输入字符主要操作12n1 - voidtest(int&sum){intx;cin>>x;if(x==0)sum=0;else{test(sum);sum+=x;}cout<<sum;}解： < 解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。（QElemTypechar。voidmn(){QueueQ;InitQueue(Q);charx=‘e’,y=‘c’;EnQueue(Q,‘h’);EnQueue(Q,‘r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,‘a’);While(!QueueEmpty(Q)){DeQueue(Q,y);cout<<y;}cout<<x;}解：charintvoidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}解：队列逆置)和出栈为或正误解： = - < + < = + < < / - - = + - / 表示（） f f + f + + 解：O + + + 。Or + 到 l r l r l l & = = = = + + + + + + + 解：/ f + f/ f + + / ff+ f + f + = + -/ -/ - - 2如题 f + 解：RR << < & + + - = = + gm,n

m0,n0解：

gm1,2n

m0,n0 和 > << < 、、Fn

n

n0 解：

nFn

n0 < AA

的迭代函数定义如下：sqrtA,p,e

p 1

A

p2Aesqrtp ,e

p2Ae 2 p >> < ( akmm,n

n1akmm

m0m0,n0akmmakmm,n

m0,n0 非递归算法： - - - （解： L + = = L - 解： =& = =& 设标志节省存储空间，但运行时间较长。不设标志则正好相反。（解： (= (= 假设称正读和反读都相同的字符序列为“回文”，例如，b和是回文，和’解：m + fn1，其中项解：c / + 解：/ =& =&/ = / / = / = =& / /3 、、、 （’和 仅限： + 第4章串I码为解：串赋值s、串比较、求串长、串连接、求子串/ s : : : : s : : : & s15)××8)0××)0××)0××))0×××××7)0×××××)0×××××4解：ka(ab2，解：ki(n)i(i)1i1，j1，ij21 12f1(i)(n2)i2

f(j

c(n1)解： 解： ij1 0kn1 解： 解：行个，n2稀疏矩阵需要n2n2个n2 】 】 (】 (】( 【)()】 【)】 【【)】】 【【)】】1 【【】 【【】 【【【 【【【 【【【】】 【【】 【【【 (()() ()))s(ns(nans(na1n a b0add(abadd(a,b)

b0 R + + d + + + + = + + + + d< O O=O =& O= =& / / / /: / + = + + =& + ) /: + = ++ + + + + + + / / / /: / + + / + = + Cs / / / / C C Cs C: + + + L Cs: Cs //// C Cs C dCs C: + + + L Cs:d / / + L &= / / + / / Cs: + + &=& < C 以下是关于广义表算法涉及的描述及方法/// / / )- + / / )L / / / / )/ / L / L / / / = < / / / =/ +/ / = / / (& / =/ =/ / / / 36章树和二叉树解：二叉树是颗有序树，但度为2的树则未必有序。棵kH1

k1如果左孩子，则ipk2k 结点p的右孩子的编号为，左孩子的编号为，第i个孩子的编号为 解：1n12n23n3...knkk而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即kn01n12n23n3...knk(n1n2n3...nk)1(i1)nii1节点数目。解：nkn1nkkn0nnk

nn1k解： ogk(n(k)0k11n0

h1

kh1，k1，kh1 kn1

k

0 nk1

，从而得n0(k1)n11解：kH11n

kH1

3H1

12n3H

1k12n13H

k13(2n

log3(2n1)H1log3(2n1)Hlog3(2n1) 11n 由n0n3 1n2n02Hlog3(3n0)1log3n0nn2li11，其中l表示第设根ii1i1211n112n1。 （ 112(1)1设有2(1)2(l2)...2(lp)...2(ln)1一个叶子结点，这意味着在某叶子结点上新生两个叶子结点，而结点lp12(1)2(l2)...2(lp1)2(lp1)...2(ln)2(lp)2(lp)2(1)2(l2)...2(lp)...2(ln)1k12nmn

时，采用顺序存储比采用三叉链表更节省空间。假设和、或）前序遍历时n在m前？中序遍历时n在m前？后序遍历时n在m前？n在m左方n在m右左方n是m祖先n是m子孙a（解： 解：111解：e / / /， 解：JGG，L对于LLLL)LL)LLLL由此画出二叉树，进而画出树。 解：树 先根先 先序后根中 中序 解；解：、、、、、、、、、、111113 / / / / / =/结点 / / / / / / / &+ /////e/求的 e / 结点 / = + + + / &+ e / / & /e ) / / ) / / //e + / &+ /e 4/ee R/e = R R/e /e = e e e R R/e e e R/e e /和 L R R e / e e / e &= /e |R = e e / e/ e e/ e R/ e R e ) s )