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

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

3、(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-

4、 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

5、-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为

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 co

7、unt+; 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.

8、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 " +

9、(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 fin

10、al 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.&qu

11、ot;);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 eleme

12、nts = " + 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("

13、; + 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,

14、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;j<=n;j+) k=n(i1)-i(i-1)/2+j Bk=Ai, j; (b) 提取if(i>j) p=0;else k=n(i-1)-i(i-1)/2+j; p=Bk;【2.6节练习题答案】453423121806958474644332211979685756544332211087867665553423120187777665635241301917657564625

15、140292716154747261203928262514373716049383635241328170594837第三章 练习题答案【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 !”

16、); 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 < 0) / 当堆栈没有数据存在，则显示错误System.out.print("nNo item, stack is empty !n&quo

17、t;);else System.out.print("nItem " + itemtop + " deleted !n");top-; System.out.println(""); 【3.4节练习题答案】中序后序(1) a > b && c > d && e < f(a > b) && (c > d) && (e < f)(a > b) && (c > d) && (e < f)a b

18、 > c d > && e f < &&(2) (a + b) * c / d + e 8(a + b) * c ) / d + e 8(a + b) * c) / d) + e) 8a b + c * d / e + 8 第四章 练习题答案【4.1节练习题答案】1. 有一链表如下：head删除此链表最后节点如下：this=head;while(this.next != null)/ 寻找链表最后节点 prev=this; / prev紧跟随在this之后 this=this.next;prev.next=null;this = null;2.

19、(a) current(b) current将指到链表节点的尾端【4.2节练习题答案】(a) 先追踪A，B两个循环链表的尾端atail = A;while(atail.next != A) atail = atail.next;Aatailbtail = B;while(btail.next != B) btail = btail.next;btailB (b) 将B指针指到的节点指定给atail.next ，并将A指针指到的节点指定给btail.next，如下所示：atail.next = B;btail.next = A;【4.3节练习题答案】1. new.rlink = x.rlink;

20、x.rlinkllink = new;new.llink = x;.x.rlink = new;2. head.rlink = x.rlink;x.rlink.llink = head;x = null;【4. 4节练习题答案】tailhead1. 有一环状链表如下所示：由于堆栈的特点为先进先出，又由于循环链表以哪一节点为前端都可以，因此假设上图的head所指向的为前端节点，即每次加入的节点为前端，删除则从前端删除。增加的操作为new.next = head;tail.next = new;head = new;删除的操作：this = head;head = head.next;tail.n

21、ext = head;this = null;若此循环链表没有tail指针时，则需遍历。 第五章 练习题答案【5.1节练习题答案】(1) 递归方法求gcdpublic static int gcd(int in, int n) int temp; temp + m%n; if(temp = 0) return m; else m = n; n = temp; gcd(m, n); (2) 非递归的方式求gcdpublic static int gcd (int m, int n) int temp, temp = m%n; while (temp != 0) m = n; n = temp;

22、temp = m%n; return m;【5.4节练习题答案】1ABC3421move 1 from A to Bmove 2 from A to Cmove 1 from B to Cmove 3 from A to Bmove 1 from C to Amove 2 from C to Bmove 1 from A to Bmove 4 from A to Cmove 1 from B to Cmove 2 from B to Amove 1 from C to Amove 3 from B to Cmove 1 from A to Bmove 2 from A to Cmove 1 f

23、rom B to C 第六章 练习题答案【6.1节练习题答案】共需8*25=200个links但实际用了24个links故浪费了(20024)=176个links【6.2节练习题答案】1. (1) Yes, (2) No, 3) No.2. (1) 281=2561=255(2) 26-1=25=323. 1281=127(根据n0=n2+1)【6.3节练习题答案】以下是用一维数组来存储三叉树的节点表示法1stlevel2ndlevel3rdlevel4thlevel 共1个节点 共3个节点 共9个节点 共34-1=27个节点【6.4节练习题答案】先序遍历：a，b，d，h，e，c，f，i，g中

24、序遍历：d，h，b，e，a，f，i，c，g后序遍历：h，d，e，b，i，f，g，c，a【6.5节练习题答案】30201015525504060451.2. 加入3和13之后的二叉查找树如下：3020101552550406045133删除50之后的二叉查找树如下：（此答案乃以右边最小的节点取代之）30201015525604045133【6.6节练习题答案】ABFCDHGEIJNMLK1.2. 中序为ECBDA，先序为ABCED，其所对应的二叉树如下：ABDCE3. 中序为DFBAEGC，后序为FDBGECA，其所对应的二叉树如下：BCEDFGA第七章 练习题答案【7.1节练习题答案】1re1

25、15231040301540102330302310154011.1re21re3 a a1re51re4 4030102315a 1re12.2020201re71re61re31re41re51re2 a a4560453010301re85040103050401060504045605553. 删除节点30，则由节点5代替，由于删除后仍然符合Heap的定义，因此不需要调整。 删除306050452051040605045203010405a602045503010406050452030104055 aa删除节点60，以节点10取代，由于删除后不符合Heap的定义，因此需要调整。105

26、045205406050452051040 删除60 a 50与10交换 10与20交换调整调整5020451054050104520540 a a OK!81203010604540203010560454020510306045405032456755050aa520306045405010a4.a此为这是一棵min-heap【7.2节练习题答案】minmaxminmax(a) 加入172030101612181514176 加入82030108121815141761620301016121815141768 16和18交换 ok!加入22030108121815141716622030

27、10821815141716612203010861815141716212 12和2交换 6和2交换(b) 删除2017301086181514121621230108618151417162 12和17交换 再删除101730148151612261817301686181514122 a OK!【7.3节练习题答案】(a) 加入2530102262216201814230105262216201814530101426221620182 a a再加入50250530221620181410262305502216201814102623052622162018141050 a a(b)

28、删除50230526221620181410226530221620181410a 第八章 练习题答案【8.1节练习题答案】1. (1) 加入JanJan(2) 加入FebFebJan(3) 加入MarFebJanMar(4) 加入AprFebJanMarApr(5) 加入MayFebJanMarAprMay(6) 加入JunFebJanMarAprMayJun(7) 加入JulyFebJanMarAprMayJunJuly(8) 加入AugFebJanMarAprMayJunJulyAug属于LR型，并调整。AugJanMarAprMayJunJulyFebAugJanMarAprMayJu

29、nJulyFebSep(9) 加入SepAugJanMarAprMayJunJulyAugSepOct(10) 加入Oct属于RL型，并调整。AugJanMarAprOctJunJulyFebSepMay(11) AugJanMarAprOctJunJulyFebSepMayNov-20-111000-1加入Nov属于RR型，并调整JanMarOctAugSepMayJulyJunNovAprFeb(12) 加入DecJanMarOctAugSepMayJulyJunNovAprFebDec2.(a) 删除30后，根据课文8.1节的解释，知其为RL型55506070(b) 删除45后的AVL-

30、tree为50486080305535由课文8.1节得知其为LR型，调整后的AVL-tree50356080305548 第九章 练习题答案【9.1节练习题答案】1. 依次加入50、10、22及12(1) 加入5040,652580505, 153545557585(2) 加入1040,6510,2580505354555758515(3) 加入2215,2240,6510,25805053545557585 (4) 加入12401080505223545557512651525852.5025708565405(1) 删除60(2) 删除70502565, 8540565, 8540525,

31、 50不符合2-3-tree，再调整如下：3. 删除70，由于删除后不符合2-3 Tree之定义，故需调整。60359515 50 75, 80 96 删除80，由于删除后符合2-3 Tree之定义，故不需调整。60359515 50 75 96 删除96，由于删除后不符合2-3 Tree之定义，故需要调整。75, 9575, 9535, 606035=> 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

32、) 删除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

33、, 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,100833

34、36,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.节点入度出度130222

35、3124135216232.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)