《数据结构(Java版)(第2版)》习习题解答

1、数据结构（Java版）（第2版）习题解答叶核亚 编著目录第0章 Java程序设计基础1【习】 实验 哥德巴赫猜想。1【习】 实验 杨辉三角形。1【习】 实验 金额的中文大写形式。1【习】 实验 下标和相等的数字方阵。1【习】 实验 找出一个二维数组的鞍点2【习】 实验 复数类。2【习】 实验 图形接口与实现图形接口的类2第1章 绪论3【习】 实验 判断数组元素是否已按升序排序。3【习】 实验 用递归算法求两个整数的最大公因数。3第2章 线性表5【习】 习2-5 图的数据结构声明。5【习】 习2-6 如果在遍历单链表时，将p=语句写成=p，结果会怎样5【习】 实验 由指定数组中的多个对象构造单链

2、表。5【习】 实验 单链表的查找、包含、删除操作详见。5【习】 实验 单链表的替换操作。6【习】 实验 首尾相接地连接两条单链表。6【习】 实验 复制单链表。6【习】 实验 单链表构造、复制、比较等操作的递归方法。7【习】 建立按升序排序的单链表（不带头结点）。8【习】 实验 带头结点的循环双链表类，实现线性表接口。10【习】 实验 建立按升序排序的循环双链表。14第3章 栈和队列17【习】 习3-5 栈和队列有何异同17【习】 能否将栈声明为继承线性表，入栈方法是add(0,e)，出栈方法是remove(0)为什么17【习】 能否用一个线性表作为栈的成员变量，入栈方法是add(0,e)，出栈

3、方法是remove(0)为什么17【习】 能否将队列声明为继承线性表，入队方法是add(e)，出队方法是remove(0)为什么17第4章 串18【习】 实验 找出两个字符串中所有共同的字符。18【习】 习4-9(1) 已知目标串为"abbaba"、模式串为"aba"，画出其KMP算法的匹配过程，并给出比较次数。18【习】 习4-9(2) 已知target="ababaab"、pattern="aab"，求模式串的next数组，画出其KMP算法的匹配过程，并给出比较次数。18第5章 数组和广义表20【习】 求一个矩

4、阵的转置矩阵。20第6章 树和二叉树21【习】 画出3个结点的各种形态的树和二叉树。21【习】 找出分别满足下面条件的所有二叉树。21【习】 输出叶子结点。21【习】 求一棵二叉树的叶子结点个数。22【习】 判断两棵二叉树是否相等。22【习】 复制一棵二叉树。23【习】 二叉树的替换操作。23【习】 后根次序遍历中序线索二叉树。24第7章 图25第8章 查找26【习】 实验 顺序表的查找、删除、替换、比较操作。26【习】 实验 单链表的全部替换操作。28【习】 实验 单链表的全部删除操作。28【习】 折半查找的递归算法。29【习】 二叉排序树查找的递归算法。29【习】 二叉排序树插入结点的非递

5、归算法。30【习】 判断一棵二叉树是否为二叉排序树。31第9章 排序32【习】 判断一个数据序列是否为最小堆序列。32【习】 归并两条排序的单链表。32【习】 说明二叉排序树与堆的差别。34图 下标和相等的数字方阵算法描述1图 =p将改变结点间的链接关系5图 目标串"abbaba"和模式串"aba"的KMP算法模式匹配过程18图 目标串"ababaab"和模式串"aab"的KMP算法模式匹配过程19图 3个结点树和二叉树的形态21图 单支二叉树21图 归并两条排序的单链表33表 模式串"aab"

6、的next数组1910第0章 Java程序设计基础【习0.1】 实验 哥德巴赫猜想。【习0.2】 实验 杨辉三角形。【习0.3】 实验 金额的中文大写形式。【习0.4】 实验 下标和相等的数字方阵。输出下列方阵（当n=4时）。1267 或 1341035813 25911491214 68121510111516 7131416采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图所示。图0.1 下标和相等的数字方阵算法描述程序如下。public class Upmat public static void main(String args) 表0.1 int n=4; ength;

7、 j+) .1ength, ; for (int i=0; i< i+) for (int j=0; j<i.length; j+) ji=ij; return trans;第6章 树和二叉树【习6.1】 画出3个结点的各种形态的树和二叉树。3个结点的树有2种形态，3个结点的二叉树有5种形态，如图所示。图6.1 3个结点树和二叉树的形态【习6.2】 找出分别满足下面条件的所有二叉树。 先根遍历序列和中根遍历序列相同：右单支二叉树，如图（a）所示。 中根遍历序列和后根遍历序列相同：左单支二叉树，如图（b）所示。 先根遍历序列和后根遍历序列相同：空树，只有一个根结点的二叉树。图6.2

8、单支二叉树【习6.3】 输出叶子结点。在BinaryTree类中增加以下方法。public void leaf() quals(i) return false; return true; return false;【习6.4】 实验 单链表的全部替换操作。在SinglyLinkedList单链表类中，增加替换操作方法如下。public boolean replace(Object obj, E element) /详见实验public boolean replaceAll(Object obj, E element) /将所有元素值为obj的结点值替换为element /若替换成功返回true

9、，否则返回false boolean done=false; if (obj!=null && element!=null) Node<E> p=; while (p!=null) if ) = element; done = true; p = ; return done;【习6.5】 实验 单链表的全部删除操作。在SinglyLinkedList单链表类中，增加删除操作方法如下。public boolean removeAll(Object obj) /将所有元素值为obj的结点删除 if =null | obj=null) return false; bool

10、ean done=false; while !=null && = /头删除 done = true; Node<E> front=, p=; while (p!=null) if ) = ; /删除p结点 p = ; done = true; else front = p; p=; return done;【习6.6】 折半查找的递归算法。public static int binarySearch(int table, int value) /折半查找算法，数组元素已按升序排列 /若查找成功返回元素下标，否则返回-1 if (table!=null) retur

11、n binarySearch(table, value, 0, ; return -1; private static int binarySearch(int table, int value, int low, int high) /折半查找，递归算法 /low、high指定查找范围的下界和上界 if (low<=high) /边界有效 int mid = (low+high)/2; /中间位置，当前比较元素位置 " "); if (tablemid=value) return mid; /查找成功 else if (tablemid>value) /给定值

12、小 return binarySearch(table, value, low, mid-1); /查找范围缩小到前半段 else return binarySearch(table, value, mid+1, high); /查找范围缩小到后半段 return -1;【习6.7】 二叉排序树查找的递归算法。将二叉排序树类BinarySortTree中的search(value)方法替换为以下方法。public BinaryNode<E> searchNode(E value) /查找值为value的结点 /若查找成功返回结点，否则返回null if (value=null |

13、!(value instanceof Comparable) return null; return searchNode(value, root);private BinaryNode<E> searchNode(E value, BinaryNode<E> p) /查找值为value的结点，递归算法 if (p!=null) Comparable cmpobj = (Comparable)value; if =0) /若两个对象相等，查找成功 return p; " "); if <0) return searchNode(value, ;

14、 /在左子树中查找 else return searchNode(value, ; /在右子树中查找 return null;【习6.8】 二叉排序树插入结点的非递归算法。将二叉排序树类BinarySortTree中的insert(value)方法替换为以下方法。public boolean insertNode(E value) /插入结点，非递归算法 if (value=null | !(value instanceof Comparable) return false; if (root=null) root=new BinaryNode<E>(value); /建立根结点

15、else BinaryNode<E> p=, parent=null; Comparable cmpobj = (Comparable)value; while (p!=null) parent = p; if =0) return false; /不插入重复关键字 if <0) p=; else p=; p=new BinaryNode<E>(value); /建立叶子结点p if<0) = p; /p作为parent的左孩子 else = p; /p作为parent的右孩子 return true; 【习6.9】 判断一棵二叉树是否为二叉排序树。将二叉树

16、类BinaryTree中增加以下方法。public boolean isSorted() /判断一棵二叉树是否为二叉排序树 return isSorted;public boolean isSorted(BinaryNode<E> p) boolean yes = true; if (p!=null) if (! instanceof Comparable) return false; Comparable cmpobj = (Comparable); if (=null | !=null && && =null | !=null &&

17、; yes = isSorted; if (yes) yes = isSorted; else yes = false; return yes;第7章 排序【习7.1】 判断一个数据序列是否为最小堆序列。public static boolean isMinHeap(int table) /判断一个数据序列是否为最小堆 if (table=null) return false; int i = 2 -1; /最深一棵子树的根结点 while (i>=0) int j=2*i+1; /左孩子 if (j< if (tablei>tablej) return false; els

18、e if (j+1< && tablei>tablej+1) /右孩子 return false; i-; return true;【习7.2】 归并两条排序的单链表。使用一趟归并排序算法，将两条排序的单链表合并成一条排序的单链表。算法描述如图所示。图7.2 归并两条排序的单链表在带头结点的单链表类SortedHSLinkedList中，增加merge()方法如下：public void merge(SortedHSLinkedList<E> list) /归并两条排序的单链表 if (list=null | =null) return; if =null) = ; return; Node<E> front=, p=; /front是p的前驱，p指向this单链表的第一个结点 Node<E> q= /q指向list单链表的第一个结点 while (p!=null && q!=null) if (Comparable)pareTo(Comparable)<0) /比较两个链表当前结点