[理学]数据结构Java版习题解答.doc

练习题解答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, 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 (n4) 第二章 练习题答案【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- l3+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)*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为指针常数，但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 count+; 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_search(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节练习题答案】/ file 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, 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(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); 【2.4节练习题答案】1.(a) 使用n+2长度存储p=(7, 6, 0, 8, 5, 0, 3, 0, 7)(b) 只考虑非零项p=(5, 7, 6, 5, 8, 4, 5, 2, 3, 0, 7)2.【2.5节练习题答案】以下的算法以行为主(a) 存储for(i=1;i=n;i+) for(j=1;jj) p=0;else k=n(i-1)-i(i-1)/2+j; p=Bk;【2.6节练习题答案】453423121806958474644332211979685756544332211087867665553423120187777665635241301917657564625140292716154747261203928262514373716049383635241328170594837第三章 练习题答案【3.1节练习题答案】由于堆栈和队列都属于顺序列表，因此可利用数组(array)的数据结构表示，而注标值表示最大的容量。【3.2节练习题答案】若top的初值为0，则push和pop函数分别如下pulbic static void push_f() DataInputStream in = new DataInputStream(System.in); if(top MAX) System.out.println(” Stack is full !”); else top+; System.out.print(n Please enter item to insert: ); System.out.flush(); try itemtop = in.readLine(); catch (IOException e) System.out.println();public static void pop_f() / 删除函数if(top b & c d & e b) & (c d) & (e b) & (c d) & (e c d & e f 15 5015 50 【9.2节练习题答案】1. 依序加入8，30及655152, 5, 810, 40(1) 加入8(2) 加入3015,30552,5,810, 40(3)加入615, 305525, 10, 406, 82.(1) 删除80309010, 605, 8(2) 删除3010908, 605(3) 删除890605,1060105(4) 删除90 第十章 练习题答案【10.1节练习题答案】(1) 加入30 (2) 加入5030, 5030, x(3) 加入25 (4) 加入3230, 5025, x32, x30, 5025, x(5) 加入35 (6) 加入3330, 5025, x32, 2533, x30, 5025, x32, 3530, 5025, 2832, 3533, x30, 5025, 2832, 3533, x29, x(7) 加入28 (8) 加入29(9) 加入6030, 5025, 2832, 3533, x29, x60, x2. 接上题(1) 删除28 (2) 删除3530, 5025, 2932, 3360, x30, 5025, 2932, 3533, x60, x30, 3325, 2932, x60, x(3) 删除50（此处是将50的左子树中最大的提上去）【10.2节练习题答案】5010,30,4060,80,10082033,35,375565105,11045851. (a) 加入33，加入后符合2-3-4 Tree的定义，故不需调整 加入36，由于加入后不符合2-3-4 Tree的定义，故需要调整。5010,30,35,4060,80,10083336,375565105,110458520加入38，由于加入后符合2-3-4 Tree的定义，故不需调整。5010,30,35,4060,80,10083336,37,385565105,1104585205010,30,35,4060,80,10083336,37,385565458520110(b) 删除105，删除后符合2-3-4 Tree的定义，故不需调整。删除110，由于删除后不符合2-3-4 Tree的定义，故需要调整。5010,30,35,4060,8083336,37,385565452085, 100 第十一章 练习题答案【11.1节练习题答案】1.节点入度出度1302223124135216232.123211231(a) 若V(G) V(G)及E(G) E(G)，则G为G的子图，如(b)强连通单元为1342【11.2节练习题答案】邻接矩阵ABCDEFGHA01111000B10000000C10000000D10000011E10000110F00001010G00011100H00010000邻接表ABCDEBACADAGHEAFGFEGGDEFHD【11.3节练习题答案】深度优先：AEFGDBC广度优先：AEBCDFG注意!上述答案不是惟一。【11.4节练习题答案】(a) Primes algorithm1011016125522410612552243101066 52561255224310716142106125522431016210 (b) Kruskals algorithm 6125522410310721614261824615410372615410310726154103107214615410310721416166154103107214226154103107214162225 (c) Sollins algorithm以每一个节点为起点，找一边为其最短(1,6)，(2,7)，(3,4)，(4,3)，(5,4)，(6,1)，(7,2)其中(1,6)，(6,1)，(3,4)和(4,3)及(2,7)和(7,2)都重复因此，保留(1,6)，(2,7)，(3,4)，(5,4)615410310721422之后(1,6)，(2,7)，(3,4,5)所组成的tree取之间最短的边分别为(2,3)及(5,6)6154103107214162225【11.5节练习题答案】Jk123456710655203*3*55*4*301*352*46*401350*44*50135042*60135042由上表得知节点1到节点7最短距离为2，并且经由5个路径，分别如下, ,。其余节点的最短距离依此类推。【11.6节练习题答案】(a) 拓扑排序：j，k，l，m，n，o注意!此答案不是惟一。也可以是j，k，l，m，n，o(b)countLinkvertexLinkV10234V2156V3156V416V520V630其中link字段为0或以斜线表示的话，代表以