AI N D E X练习题答案第一章练习题答案(a) n+(n–1)+(n–2)+…+2+1=2)1(+ n n (b) n+(n–1)+(n–2)+…+2+1=2)1(+nnf(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)(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+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)= Θ(g(n))(a) f(n)=3n+2c1=3, c2=6, n0=1得知f(n) = Θ (n)(b) f(n)=9n2+4n+2c1=9, c2=16, n0=1得知f(n) = Θ (n2)(c) f(n)=8n4+5n3+5c1=8, c2=20, n0=1得知f(n) = Θ (n4)A-2练习题解答第二章练习题答案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)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, 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 = 253A-35. 以行为主：A(i1, i2, i3, …, i n) = l0 +(i1–1)u2u3…u n+(i2–1)u3u4…u n+(i3–1)u4u5…u n…+(i n–1)以列为主：A(i1, i2, i3, …, i n)=l0+(i n–1)u1u2…u n-1+(i n-1–1)u1u2…u n-2+(i3–1)u4u5…u n…+(i2–1)*n1+(i1–1)2.2节练习题答案1.(a) 由上图知ptr+2为a[2]元素的地址，所以*(ptr+2)和a[2]表示的结果是一样的，其值为2。

A-4练习题解答(b) a为指针常数，但ptr为指针变量，所以ptr可以用于递增或递减的运算符，如ptr++，或ptr––，但a就不能使用此运算符，因为常数不可以当做LVALUE。

2. // file name: binary_search.javaimport 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(A[k] == key)break;else if(A[k] < key)i = k+1;elsej = 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");A-5System.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");}}// file name: sparse_matrix.java */import java.io.*;public class sparse_matrix{//存储稀疏矩阵的数据结构预设10 - 1 = 9 个元素static int[][] sm = new int[10][3];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(source[row][col] !=0){non_zero++; //计算非零元素个数A-6练习题解答sm[sm_row][0] = row+1;sm[sm_row][1] = col+1;sm[sm_row][2] = source[row][col];sm_row++;}if(col == width-1){ //先扫单一列上所有元素row++;if(row <= height-1) //当扫到最后一列就不归零col=0;}elsecol++;}System.out.println("Total nonzero elements = " + non_zero);//稀疏矩阵数据结构信息sm[0][0] = row;//最后col停在数组编号最后一个元素,换成个//数要加1sm[0][1] = col+1;sm[0][2] = 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(" "+ sm[i][j]);System.out.println("");}}public static void main(String args[])A-7A-8{ sparse_matrix myApp = new sparse_matrix(); myApp.scan_matrix();myApp.output_sm(non_zero);} }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.⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-0006300002000080000900035432103210x x x x x x y y y y 以下的算法以行为主 (a) 存储for(i=1;i<=n;i++) for(j=1;j<=n;j++){ k=n(i –1)-i(i-1)/2+j B[k]=A[i, j]; } (b) 提取练习题解答if(i>j)p=0;else {k=n(i-1)-i(i-1)/2+j;p=B[k];}第三章练习题答案由于堆栈和队列都属于顺序列表，因此可利用数组(array)的数据结构表示，而注标值表示最大的容量。

3.2节练习题答案若top的初值为0，则push和pop函数分别如下A-9pulbic 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 {item[top] = 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");else {System.out.print("\nItem " + item[top] + " deleted !\n");top--;}System.out.println("");}中序→后序(1) a > b && c > d && e < f(a > b) && (c > d) && (e < f)(((a > b) && (c > d)) && (e < f))a b > c d > && e f < &&(2) (a + b) * c / d + e – 8((a + b) * c ) / d + e – 8((((a + b) * c) / d) + e) – 8A-10a b + c * d / e + 8 –第四章 练习题答案1. 有一链表如下：this=head;while(this.next != null){// 寻找链表最后节点 p rev=this; // prev 紧跟随在this 之后 this=this.next;｝prev.next=null; this = null; 2.(a) current (b) current 将指到链表节点的尾端(a) 先追踪A ，B 两个循环链表的尾端atail = A;while(atail.next != A) atail = atail.next;Aatailheadbtail = B;while(btail.next != B)btail = btail.next;(b) 将B 指针指到的节点指定给atail.next ，并将A 指针指到的节点指定给btail.next ，如下所示： atail.next = B;btail .next = A; 1.new.rlink = x.rlink; x.rlinkllink = new; new.llink = x;. x.rlink = new;2.head.rlink = x.rlink; x.rlink.llink = head; x = null;1.有一环状链表如下所示：由于堆栈的特点为先进先出，又由于循环链表以哪一节点为前端都可以，因此假设上图的head 所指向的为前端节点，即每次加入的节点为前端，删除则从前端删除。