《数据结构Java版》习题解答.doc

1、- I -第 0 章 Java 程序设计基础.1【习 0.1】 实验 0.1 哥德巴赫猜想。 .1【习 0.2】 实验 0.2 杨辉三角形。 .1【习 0.3】 实验 0.3 金额的中文大写形式。 .1【习 0.4】 实验 0.4 下标和相等的数字方阵。 .1【习 0.5】 实验 0.5 找出一个二维数组的鞍点 .2【习 0.6】 实验 0.6 复数类。 .2【习 0.7】 实验 0.8 图形接口与实现图形接口的类 .2第 1 章 绪论.3【习 1.1】 实验 1.1 判断数组元素是否已按升序排序。 .3【习 1.2】 实验 1.3 用递归算法求两个整数的最大公因数。 .3第 2 章 线性表.

2、5【习 2.1】 习 2-5 图 2.19 的数据结构声明。 .5【习 2.2】 习 2-6 如果在遍历单链表时，将 p=p.next 语句写成 p.next=p，结果会怎样？ .5【习 2.3】 实验 2.2 由指定数组中的多个对象构造单链表。 .5【习 2.4】 实验 2.2 单链表的查找、包含、删除操作详见 8.2.1。 .5【习 2.5】 实验 2.2 单链表的替换操作。 .6【习 2.6】 实验 2.2 首尾相接地连接两条单链表。 .6【习 2.7】 实验 2.2 复制单链表。 .6【习 2.8】 实验 2.2 单链表构造、复制、比较等操作的递归方法。 .7【习 2.9】 建立按升序

3、排序的单链表（不带头结点）。 .8【习 2.10】 实验 2.6 带头结点的循环双链表类，实现线性表接口。 .10【习 2.11】 实验 2.5 建立按升序排序的循环双链表。 .14第 3 章 栈和队列.17【习 3.1】 习 3-5 栈和队列有何异同？ .17【习 3.2】 能否将栈声明为继承线性表，入栈方法是 add(0,e)，出栈方法是 remove(0)？为什么？ .17【习 3.3】 能否用一个线性表作为栈的成员变量，入栈方法是 add(0,e)，出栈方法是 remove(0)？为什么？ .17【习 3.4】 能否将队列声明为继承线性表，入队方法是 add(e)，出队方法是 remo

4、ve(0)？为什么？ .17第 4 章 串.18【习 4.1】 实验 4.6 找出两个字符串中所有共同的字符。 .18【习 4.2】 习 4-9(1) 已知目标串为“abbaba“、模式串为“aba“，画出其 KMP 算法的匹配过程，并给出比较次数。 .18- II -【习 4.3】 习 4-9(2) 已知 target=“ababaab“、pattern=“aab“，求模式串的 next 数组，画出其KMP 算法的匹配过程，并给出比较次数。 .18第 5 章 数组和广义表.20【习 5.1】 求一个矩阵的转置矩阵。 .20第 6 章 树和二叉树.21【习 6.1】 画出 3 个结点的各种形态

5、的树和二叉树。 .21【习 6.2】 找出分别满足下面条件的所有二叉树。 .21【习 6.3】 输出叶子结点。 .21【习 6.4】 求一棵二叉树的叶子结点个数。 .22【习 6.5】 判断两棵二叉树是否相等。 .22【习 6.6】 复制一棵二叉树。 .23【习 6.7】 二叉树的替换操作。 .23【习 6.8】 后根次序遍历中序线索二叉树。 .24第 7 章 图.25第 8 章 查找.26【习 8.1】 实验 8.1 顺序表的查找、删除、替换、比较操作。 .26【习 8.2】 实验 8.2 单链表的全部替换操作。 .28【习 8.3】 实验 8.2 单链表的全部删除操作。 .28【习 8.4

6、】 折半查找的递归算法。 .29【习 8.5】 二叉排序树查找的递归算法。 .29【习 8.6】 二叉排序树插入结点的非递归算法。 .30【习 8.7】 判断一棵二叉树是否为二叉排序树。 .31第 9 章 排序.32【习 9.1】 判断一个数据序列是否为最小堆序列。 .32【习 9.2】 归并两条排序的单链表。 .32【习 9.3】 说明二叉排序树与堆的差别。 .34图 0.1 下标和相等的数字方阵算法描述 .1图 2.1 p.next=p 将改变结点间的链接关系 .5图 4.1 目标串“abbaba“和模式串“aba“的 KMP 算法模式匹配过程 .18图 4.2 目标串“ababaab“

7、和模式串“aab“的 KMP 算法模式匹配过程 .19图 6.1 3 个结点树和二叉树的形态 .21图 6.2 单支二叉树 .21图 9.2 归并两条排序的单链表 .33- III -表 4.1 模式串“aab“的 next 数组 .19- 1 -第 0 章 Java 程序设计基础【习 0.1】 实验 0.1 哥德巴赫猜想。【习 0.2】 实验 0.2 杨辉三角形。【习 0.3】 实验 0.3 金额的中文大写形式。【习 0.4】 实验 0.4 下标和相等的数字方阵。输出下列方阵（当 n=4 时） 。1 2 6 7 或 1 3 4 103 5 8 13 2 5 9 114 9 12 14 6 8

8、 12 1510 11 15 16 7 13 14 16采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图 0.1 所示。j 12673581349121410115160123123i = 右 下 三 角下 标 和 为 n 2*n-左 上 三 角下 标 和 为 0 n-1 下 标 和 为 4下 标 和 为 5下 标 和 为 6图 0.1 下标和相等的数字方阵算法描述程序如下。public class Upmatpublic static void main(String args) int n=4; /阶数int mat = new intnn;int k=1; /k 是自然数

9、，递增变化boolean up = true; /方向向上for (int sum=0; sum=0; i-)matisum-i = k+; /k 先赋值后自加elsefor (int i=0; isum-n; j-)matsum-jj = k+;up=!up;for (int i=0; itablei+1)return false;return true;public static boolean isSorted(Comparable table) /判断对象数组是否已按升序排序 /若已排序返回 true，否则返回 falseif (table=null)return false;for

10、(int i=0; i0)return false;return true;【习 1.2】 实验 1.3 用递归算法求两个整数的最大公因数。public class Gcdpublic static int gcd(int a, int b) /返回 a,b 的最大公因数，递归方法if(b=0)return a;if(a table【习 2.2】 习 2-6 如果在遍历单链表时，将 p=p.next 语句写成 p.next=p，结果会怎样？使 p.next 指向 p 结点自己，改变了结点间的链接关系，丢失后继结点，如图 2.1 所示。Ahead BCD图 2.1 p.next=p 将改变结点间

11、的链接关系【习 2.3】 实验 2.2 由指定数组中的多个对象构造单链表。在 SinglyLinkedList 单链表类中，增加构造方法如下。public SinglyLinkedList(E element) /由指定数组中的多个对象构造单链表this.head = null;if (element!=null Node rear=this.head;int i=1;while (i search(E element, Node start) /从单链表结点 start 开始顺序查找指定对象public Node search(E element) /若查找到指定对象，则返回结点，否则返回-

12、 6 -nullpublic boolean contain(E element) /以查找结果判断单链表是否包含指定对象public boolean remove(E element) /移去首次出现的指定对象【习 2.5】 实验 2.2 单链表的替换操作。在 SinglyLinkedList 单链表类中，增加替换操作方法如下。public boolean replace(Object obj, E element) /将元素值为 obj 的结点值替换为 element /若替换成功返回 true，否则返回false，O(n)if (obj=null | element=null)retur

13、n false;Node p=this.head;while (p!=null)if (obj.equals(p.data)p.data = element;return true;p = p.next;return false;【习 2.6】 实验 2.2 首尾相接地连接两条单链表。在 SinglyLinkedList 单链表类中，增加替换操作方法如下。public void concat(SinglyLinkedList list) /将指定单链表 list 链接在当前单链表之后if (this.head=null)this.head = list.head;elseNode p=this

14、.head;while (p.next!=null)p = p.next;p.next = list.head;【习 2.7】 实验 2.2 复制单链表。- 7 -在 SinglyLinkedList 单链表类中，增加构造方法如下。public SinglyLinkedList(SinglyLinkedList list) /以单链表 list 构造新的单链表 /复制单链表this.head = null;if (list!=null Node p = list.head.next;Node rear = this.head;while (p!=null)rear.next = new Nod

15、e(p.data);rear = rear.next; p = p.next;【习 2.8】 实验 2.2 单链表构造、复制、比较等操作的递归方法。由指定数组中的多个对象构造单链表的操作也可设计为以下的递归方法：public SinglyLinkedList(E element) /由指定数组中的多个对象构造单链表this.head = null;if (element!=null)this.head = create(element,0);private Node create(E element, int i) /由指定数组构造单链表，递归方法 Node p=null;if (i list) /以单链表 list 构造新的单链表