《[理学]数据结构java版习题解答》由会员分享，可在线阅读，更多相关《[理学]数据结构java版习题解答（57页珍藏版）》请在金锄头文库上搜索。
1、 练习题解答AINDEX练习题答案 第一章 练习题答案【1.1节练习题答案】A-57(a) n+(n1)+(n2)+2+1= (b) n+(n1)+(n2)+2+1= 【1.2节练习题答案】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+100n8c=2000, g(n)= n2, n0=1得知f(n)=O(n2)(c) f(n)=5*2n+9 n2+2c=10, n0=5得知f(n)=O(2n)f(n)c g(n) f(n)=(g(n)(a) f(n)=3n+1 c=2,
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+2 c1=3, c2=6, n0=1 得知f(n) = Q (n)(b) f(n)=9n2+4n+2 c1=9, c2=16, n0=1 得知f(n) = Q (n2)(c) f(n)=8n4+5n3+5 c1=8, c2=20, n0=1 得知f(n) = Q (n
3、4) 第二章 练习题答案【2.1节练习题答案】1. 分别以行为主和以列为主说明之。(a) 以行为主A(i, j)=l0+(i1)*u2*d+(j1)*d(b) 以列为主A(i, j)=l0+(j1)*u1*d+(i1)*d2. 以列为主A(i, j)=l0+(j12)*md+(il1)dm=u1l1+1=5(3)+1=9m=u2l2+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- l
4、3+1 所以p = u1-1+1 = u1, q = u2-1+1 = u2, r = u3-1+1 = u3 (a) 以行为主A(i, j, k)=l0 + (i1)*u2*u3*d + (j1)*u3*d +(k-1)(b) 以列为主A(i, j, k)=l0 + (k1)*u1*u2*d + (j1)*u1*d + (i-1)*d4. 以列为主：A(i, j, k)=l0 + (kl3)*pqd + (jl2)*pd + (i-l1)*d p = 5-(-3) + 1 = 9, q = 2-(-4)+1 = 7, r = 5-1+1 = 5 A(2, 1, 2) = 100 + (2-1
5、)*9*7*1 + (1-(-4)*9*1 + (2-(-3)*1 = 100 + 63 + 45 + 5 = 2535. 以行为主：A(i1, i2, i3, , in) = l0 +(i11)u2u3un+(i21)u3u4un+(i31)u4u5un +(in1)以列为主：A(i1, i2, i3, , in)=l0+(in1)u1u2un-1+(in-11)u1u2un-2+(i31)u4u5un +(i21)*n1+(i11)【2.2节练习题答案】1.ptr012345(a) 由上图知ptr+2为a2元素的地址，所以*(ptr+2)和a2表示的结果是一样的，其值为2。(b) a为指针
6、常数，但ptr为指针变量，所以ptr可以用于递增或递减的运算符，如ptr+，或ptr，但a就不能使用此运算符，因为常数不可以当做LVALUE。2. / file name: binary_search.java import java.io.*;public class binary_search static int A= -9999,2,4,6,8,10,12,14,16,18,20; static int count=0; public static int binary_search(int key) int i=1; int j=10; int k; count=0; do coun
7、t+; k = (i+j)/2; if(Ak = key) break; else if(Ak key) i = k+1; else j = k-1; while(i=j); return count; public static void main (String args) / 主函数 binary_search myApp = new binary_search(); System.out.println(Search 1, + myApp.binary_search(1) + times); System.out.println(Search 3, + myApp.binary_sea
8、rch(3) + times); System.out.println(Search 13, + myApp.binary_search(13) + times); System.out.println(Search 21, + myApp.binary_search(21) + times); System.out.println(Total + (myApp.binary_search(1) + myApp.binary_search(3)+ myApp.binary_search(13) + myApp.binary_search(21) + times); 【2.3节练习题答案】/ f
9、ile name: sparse_matrix.java */import java.io.*;public class sparse_matrix /存储稀疏矩阵的数据结构预设 10 - 1 = 9 个元素static int sm = new int103; static int sm_row=1; static final int width = 6; static final int height = 6; static int source= 0,15, 0, 0,-8, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0,-6, 0, 0, 0, 0,18, 0, 0, 0,
10、 0, 0, 0, 0, 0,16, 72, 0, 0, 0,20, 0 ; static int row=0,col=0; static int non_zero=0; public static void scan_matrix() System.out.println(Scan the matrix.);while (row height & col width) if(sourcerowcol !=0) non_zero+; /计算非零元素个数smsm_row0 = row+1;smsm_row1 = col+1;smsm_row2 = sourcerowcol;sm_row+; if
11、(col = width-1) /先扫单一列上所有元素 row+; if(row = height-1) /当扫到最后一列就不归零 col=0; else col+; System.out.println(Total nonzero elements = + non_zero); /稀疏矩阵数据结构信息 sm00 = row; /最后col停在数组编号最后一个元素,换成个/数要加1 sm01 = col+1; sm02 = non_zero; public static void output_sm(int non_zero_) int i,j;System.out.println( 1) 2) 3);System.out.println(-);for(i=0 ; i = non_zero_ ;i+) System.out.print(A( + i + ,); for(j=0 ; j 3; j+) System.out.print( + smij); System.out.println(); public static void main(String args) sparse_matrix myApp = new sparse_matrix();myApp.scan_matrix();myApp.output_sm(non_zero)
