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

第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章 线性表 5
【习21】 习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】 建立按升序排序的单链表（不带头结点）。 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)，出队方法是remove(0)？为什么？ 17
第4章 串 18
【习4.1】 实验4.6 找出两个字符串中所有共同的字符。 18
【习4.2】 习4-9(1) 已知目标串为"abbaba"、模式串为"aba"，画出其KMP算法的匹配过程，并给出比较次数。 18
【习4.3】 习4-9(2) 已知target="ababaab"、pattern="aab"，求模式串的next数组，画出其KMP算法的匹配过程，并给出比较次数。 18
第5章 数组和广义表 20
【习5.1】 求一个矩阵的转置矩阵。 20
第6章 树和二叉树 21
【习6.1】 画出3个结点的各种形态的树和二叉树。 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】 折半查找的递归算法。 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"和模式串"aab"的KMP算法模式匹配过程 19
图6.1 3个结点树和二叉树的形态 21
图6.2 单支二叉树 21
图9.2 归并两条排序的单链表 33

表4.1 模式串"aab"的next数组 19

- III -
第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 10
3 5 8 13 2 5 9 11
4 9 12 14 6 8 12 15
10 11 15 16 7 13 14 16
采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图0.1所示。

图0.1 下标和相等的数字方阵算法描述
程序如下。
public class Upmat
{
public static void main(String args[])
{
int n=4; //阶数
int[][] mat = new int[n][n];
int k=1; //k是自然数，递增变化
boolean up = true; //方向向上

for (int sum=0; sumt i=sum; i>=0; i--)
mat[i][sum-i] = k++; //k先赋值后自加
else
for (int i=0; i<=sum; i++)
mat[i][sum-i] = k++;
up=!up; //方向求反
}

for (int sum=n; sum<2*n-1; sum++) //右下三角
{
if (up)
for (int j=sum-n+1; jsum-n; j--)
mat[sum-j][j] = k++;
up=!up;
}

for (int i=0; iat.length; i++) //输出二维数组元素
{
for (int j=0; j口的类

第1章 绪论
【习1.1】 实验1.1 判断数组元素是否已按升序排序。
程序见例1.4的SortedArray.java。
public static boolean isSorted(int[] table) //判断整数数组是否已按升序排序
{ //若已排序返回true，否则返回false
if (table==null)
return false;
for (int i=0; ith-1; i++)
if (table[i]>table[i+1])
return false;
return true;
}
public static boolean isSorted(Comparable[] table) //判断对象数组是否已按升序排序
{ //若已排序返回true，否则返回false
if (table==null)
return false;
for (int i=0; i0)
return false;
return true;
}
【习1.2】 实验1.3 用递归算法求两个整数的最大公因数。
public class Gcd
{
public static int gcd(int a, int b) //返回a,b的最大公因数，递归方法
{
if(b==0)
return a;
if(a<0)
return gcd(-a, b);
if(b<0)
return gcd(a, -b);
return gcd(b, a%b);
}
public static void main(String args[])
{
int a=12, b=18, c=24;
System.out.println("gcd("+a+","+b+","+c+")="+gcd(gcd(a,b),c)); //获得3个整数最大公因数
}
}

第2章 线性表
【习2.1】 习2-5 图2.19的数据结构声明。
table数组元素为单链表，声明如下：
SinglyLinkedList table[]
【习2.2】 习2-6 如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？
使p.next指向p结点自己，改变了结点间的链接关系，丢失后继结点，如图2.1所示。

图2.1 p.next=p将改变结点间的链接关系
【习2.3】 实验2.2 由指定数组中的多个对象构造单链表。
在SinglyLinkedList单链表类中，增加构造方法如下。
public SinglyLinkedList(E[] element) //由指定数组中的多个对象构造单链表
{
this.head = null;
if (element!=null && element.length>0)
{
this.head = new Node(element[0]);
Node rear=this.head;
int i=1;
while (i rear.next = new Node(element[i++]);
rear = rear.next;
}
}
}
【习2.4】 实验2.2 单链表的查找、包含、删除操作详见8.2.1。
单链表的以下查找、包含、删除等操作方法详见8.2.1顺序查找。
public Node search(E element, Node start) //从单链表结点start开始顺序查找指定对象
public Node search(E element) //若查找到指定对象，则返回结点，否则返回null
public 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)
return 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;
else
{
Node p=this.head;
while (p.next!=null)
p = p.next;
p.next = list.head;
}
}
【习2.7】 实验2.2 复制单链表。
在SinglyLinkedList单链表类中，增加构造方法如下。
public SinglyLinkedList(SinglyLinkedList list) //以单链表list构造新的单链表
{ //复制单链表
this.head = null;
if (list!=null && list.head!=null)
{
this.head = new Node(list.head.data);
Node p = list.head.next;
Node rear = this.head;
while (p!=null)
{
rear.next = new Node(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构造新的单链表
{
this.head = copy(list.head);
}
private Node copy(Node p) //复制单链表，递归方法
{
Node q=null;
if (p!=null)
{
q = new Node(p.data);
q.next = copy(p.next);
}
return q;
}
比较两条单链表是否相等的操作也可设计为以下的递归方法：
public boolean equals(Object obj) //比较两条单链表是否相等
{
if (obj == this)
return true;
if (obj instanceof SinglyLinkedList)
{
SinglyLinkedList list = (SinglyLinkedList)obj;
return equals(this.head, list.head);
}
return false;
}

private boolean equals(Node p, Node q) //比较两条单链表是否相等，递归方法
{
if (p==null && q==null)
return true;
if (p!=null && q!=null)
return p.data.equals(q.data) && equals(p.next, q.next);
return false;
}
【习2.9】 建立按升序排序的单链表（不带头结点）。
采用直接插入排序算法将一个结点插入到已排序的单链表中。
import dataStructure.linearList.Node;
import dataStructure.linearList.SinglyLinkedList; //不带头结点的单链表类

public class SortedSinglyLinkedList extends SinglyLinkedList
{
public SortedSinglyLinkedList()
{
super();
}
public boolean add(E element) //根据指定对象的大小插入在合适位置
{
if (element==null || !(element instanceof Comparable))
return false; //不能插入null或非Comparable对象

Comparable cmp = (Comparable)element;
if (this.head==null || pareTo(this.head.data)<=0)
this.head = new Node>(element,this.head); //头插入
else
{
Node front=null, p=this.head;
while (p!=null && pareTo(p.data)>0)
{
front = p; //front是p的前驱结点
p = p.next;
}
front.next = new Node(element, p); //中间/尾插入
}
return true;
}

public static void main(String args[])
{
SortedSinglyLinkedList list = new SortedSinglyLinkedList();
int n=10;
System.out.print("insert： ");
for (int i=0; i 9 71 71 19 67 50 80
list: (9, 19, 22, 48, 50, 50, 67, 71, 71, 80)

insert： 42 33 52 89 13 11 50 29 78 34
list: (11, 13, 29, 33, 34, 42, 50, 52, 78, 89)

insert： 69 16 99 0 20 68 14 73 90 76
list1: (0, 14, 16, 20, 68, 69, 73, 76, 90, 99)
【习2.10】 实验2.6 带头结点的循环双链表类，实现线性表接口。
package dataStructure.linearList;
import dataStructure.linearList.DLinkNode; //导入双链表结点类
import dataStructure.linearList.LList; //导入线性表接口

public class CHDoublyLinkedList implements LList //带头结点的循环双链表类
{
protected DLinkNode head; //头指针

public CHDoublyLinkedList() //构造空链表
{
this.head = new DLinkNode(); //创建头结点，值为null
this.head.prev = head;
this.head.next = head;
}
public boolean isEmpty() //判断双链表是否为空
{
return head.next==head;
}

//以下算法同循环单链表，与单链表的差别在于，循环条件不同
public int length() //返回双链表长度
{
int i=0;
DLinkNode p=this.head.next; //此句与单链表不同
while (p!=head) //循环条件与单链表不同
{
i++;
p = p.next;
}
return i;
}

public E get(int index) //返回序号为index的对象
{
if (index>=0)
{
int j=0;
DLinkNode p=this.head.next;

while (p!=head && j {
if (index>=0 && element!=null)
{
int j=0;
DLinkNode p=this.head.next;
while (p!=head && j E old = (E)p.data;
p.data = element;
return old;
}
}
return null;
}

public String toString()
{
String str="(";
DLinkNode p = this.head.next;
while (p!=head)
{
str + p.data.toString();
p = p.next;
if (p!=head)
str += ", ";
}
return str+")";
}

//双链表的插入、删除算法与单链表不同
public boolean add(int index, E element) //插入element对象，插入后对象序号为index
{ //若操作成功返回true，O(n)
if (element==null)
return false; //不能添加空对象（null）

int j=0;
DLinkNode front = this.head;
while (front.next!=head && jxt;
}
DLinkNode q = new DLinkNode(element, front, front.next); //插入在front结点之后
front.next.prev = q;
front.next = q;
return true;
}

public boolean add(E element) //在单链表最后添加对象，O(1)
{
if (element==null)
return false; //不能添加空对象（null）

DLinkNode q = new DLinkNode(element, head.prev, head);
head.prev.next = q; //插入在头结点之前，相当于尾插入
head.prev = q;
return true;
}

public E remove(int index) //移除指定位置的对象，O(n)
{ //返回被移除的原对象，指定位置序号错误时返回null
E old = null;
int j=0;
DLinkNode p=this.head.next;
while (p!=head && j if (p!=head)
{
old = (E)p.data; //操作成功，返回原对象
p.prev.next = p.next; //删除p结点自己
p.next.prev = p.prev;
}
return old;
}

public void clear() //清空线性表
{
this.head.prev = head;
this.head.next = head;
}
//以上实现LList接口

public static void main(String args[])
{
int i=0;
CHDoublyLinkedList list = new CHDoublyLinkedList();
System.out.println("删除第"+i+"个结点"+list.remove(0));
System.out.println(list.toString());

for (i=5; i>=0; i--)
list.add(0, new String((char)('A'+i)+""));
for (i=0; i<6; i++)
list.add(new String((char)('A'+i)+""));
// list.add(i, new String((char)('A'+i)+""));
System.ou