[理学]数据结构java版习题解答

《[理学]数据结构java版习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、练习题解答AINDEX练习题答案A-57练习题解答第一章练习题答案}}}【1.1节练习题答案】A-57练习题解答(a)n+(n–1)+(n–2)+…+2+1=(b)n+(n–1)+(n–2)+…+2+1=A-57练习题解答}}}【1.2节练习题答案】A-57练习题解答f(n)≦c.g(n)→f(n)=O(g(n))(a)f(n)=100n+9c=101,g(n)=n,n0=10得知f(n)=O(n)(b)f(n)=1000n2+100n–8c=2000,g(n)=n2,n0=1得知f(n)=O(n2)(

2、c)f(n)=5*2n+9n2+2c=10,n0=5得知f(n)=O(2n)f(n)≧cg(n)→f(n)=Ω(g(n))(a)f(n)=3n+1c=2,n0=1,g(n)=n得知f(n)=Ω(n)(b)f(n)=100n2+4n+5c=10,n0=1,g(n)=n2得知f(n)=Ω(n2)(c)f(n)=8*2n+8n+16c=8,n0=1,g(n)=2n得知f(n)=Ω(n2)c1.g(n)≦f(n)≦c2.g(n)→f(n)=Q(g(n))(a)f(n)=3n+2c1=3,c2=6,n0=1得知f

3、(n)=Q(n)(b)f(n)=9n2+4n+2c1=9,c2=16,n0=1得知f(n)=Q(n2)(c)f(n)=8n4+5n3+5c1=8,c2=20,n0=1得知f(n)=Q(n4)A-57练习题解答A-57练习题解答第二章练习题答案}}}【2.1节练习题答案】1.分别以行为主和以列为主说明之。(a)以行为主A(i,j)=l0+(i–1)*u2*d+(j–1)*d(b)以列为主A(i,j)=l0+(j–1)*u1*d+(i–1)*d2.以列为主A(i,j)=l0+(j–12)*md+(i–l1)

4、dm=u1–l1+1=5–(–3)+1=9m=u2–l2+1=2–(–4)+1=7A(1,1)=100+(1–(–4))*9+(1–(–3))=100+45+4=1493.分别以行为主和以列为主的说明。由于数组为A(1：u1,1：u2,1：u3)，因此p=u1-l1+1,q=u2-l2+1,r=u3-l3+1所以p=u1-1+1=u1,q=u2-1+1=u2,r=u3-1+1=u3(a)以行为主A(i,j,k)=l0+(i–1)*u2*u3*d+(j–1)*u3*d+(k-1)(b)以列为主A(i,j,

5、k)=l0+(k–1)*u1*u2*d+(j–1)*u1*d+(i-1)*d4.以列为主：A(i,j,k)=l0+(k–l3)*pqd+(j–l2)*pd+(i-l1)*dp=5-(-3)+1=9,q=2-(-4)+1=7,r=5-1+1=5A(2,1,2)=100+(2-1)*9*7*1+(1-(-4))*9*1+(2-(-3))*1=100+63+45+5=2535.以行为主：A(i1,i2,i3,…,in)=l0+(i1–1)u2u3…un+(i2–1)u3u4…unA-57练习题解答…+(i3–

6、1)u4u5…un+(in–1)以列为主：A(i1,i2,i3,…,in)=l0+(in–1)u1u2…un-1+(in-1–1)u1u2…un-2+(i3–1)u4u5…un…+(i2–1)*n1+(i1–1)}}}【2.2节练习题答案】1.ptr012345(a)由上图知ptr+2为a[2]元素的地址，所以*(ptr+2)和a[2]表示的结果是一样的，其值为2。(a)a为指针常数，但ptr为指针变量，所以ptr可以用于递增或递减的运算符，如ptr++，或ptr––，但a就不能使用此运算符，因为常数不

7、可以当做LVALUE。2.//filename:binary_search.javaimportjava.io.*;publicclassbinary_search{staticint[]A={-9999,2,4,6,8,10,12,14,16,18,20};staticintcount=0;publicstaticintbinary_search(intkey){A-57练习题解答inti=1;intj=10;intk;count=0;do{count++;k=(i+j)/2;if(A[k]==key

8、)break;elseif(A[k]