数据结构(Java版)-习题解答与实验指导 下载本文

入栈,头插入,list.insert(0,x); O(1)list.heada0?an-1∧list.heada0入栈,尾插入,list.insert(x); O(n)?an-1∧

出栈,头删除,list.remove(0); O(1)(a) 头插入和头删除出栈,尾删除,list.remove(list.size()-1); 两次遍历,O(n)(b) 尾插入和尾删除图4.2 使用单链表对象作为栈成员变量的操作效率分析

③ 使用一个循环单链表、双链表或循环分析省双链表对象作为栈的成员变量,入栈和出栈操作效率省略。

(4) 栈的应用

4-5 写出中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K对应的后缀表达式。

【答】ABCDEF+*G/-H+*+IJ+K*-

4.2 队列

1. 队列 (1) 队列定义

4-6 什么是队列?有何特点?说明在什么情况下需要使用队列。

【答】队列是一种特殊的线性表,其插入和删除操作分别在线性表的两端进行。队列的特点是“先进先出”。广度优先搜索遍历算法需要使用队列作为辅助结构。

4-7 已知入队序列为{A,B,C,D},有几种出队序列? 【答】一种{A,B,C,D}。 (2) 队列的实现方案讨论

4-8 能否使用一个线性表作为队列,或将队列声明为继承线性表?为什么?

【答】都不能。因为队列和线性表是不同的抽象数据类型,队列不支持中间插入和删除操作。

① 如果使用一个线性表对象作为队列,有逻辑错。例如:

SeqList queue = new SeqList(); //声明一个线性表对象作为队列

queue.insert(i,x); //语法正确,逻辑错,因线性表支持中间插入操作,但队列不支持

② 如果声明队列为继承线性表如下,则队列类继承了顺序表类的

- 38 -

isEmpty()、insert(i,x)、remove(i)等成员方法,而队列不支持中间插入和删除操作。

public class SeqQueue extends SeqList //顺序队列类,继承顺序表类

public class LinkedQueue extends SinglyList //链式队列类,继承单链表类

4-9 使用一个顺序表对象作为顺序队列的成员变量,分析入队、出队操作的时间效率。

【答】见教材第98页图4.11。

4-10 什么是队列的假溢出?为什么顺序队列会出现假溢出?怎样解决队列的假溢出问题?顺序栈会出现假溢出吗?链式队列会出现假溢出吗?为什么?

【答】① 顺序队列,当入队的元素个数(包括已出队元素)超过数组容量时,队列尾下标越界,数据溢出。此时,由于之前已有若干元素出队,数组前部已空出许多存储单元,所以,这种溢出并不是因存储空间不够而产生的,称之为假溢出。顺序队列之所以会产生假溢出现象,是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。

② 顺序栈不会出现假溢出。因为顺序栈的存储单元可以重复使用,如果数组容量不够,则是数据溢出,而不是假溢出。

③ 链式队列不会出现假溢出。因为每次元素入队,都要申请新结点,数据不会溢出。

4-11 使用一个链式存储的线性表对象作为链式队列的成员变量,分析入队、出队操作的时间效率。

【答】见教材第100页图4.14。

2. 优先队列

习4-13 已知一个对象由“(关键字,优先级)”表示,对象序列如下,画出将这些对象依次全部进队的结果图,分别使用一个顺序表、排序顺序表、单链表、排序单链表、循环双链表、排序循环双链表作为优先队列的成员变量,讨论优先队列的入队和出队操作的效率。

{(E,4),(D,3),(A,1),(F,3),(B,2),(C,1)}

【答】如图4.1所示,设优先队列长度为n。

(a) 使用顺序表作为成员变量,入队操作执行顺序表尾插入,时间

- 39 -

复杂度是O(1);出队操作执行中间删除,顺序查找首个优先级最高元素并将其删除,求最大值算法需要遍历顺序表,时间复杂度是O(n),平均移动n/2个元素。

(b) 使用排序顺序表作为成员变量,元素按优先级升序排序,队头元素优先级最高,入队操作执行顺序表中间插入,顺序查找根据优先级确定元素的插入位置,移动若干元素,时间复杂度是O(n);出队操作执行顺序表头删除,时间复杂度是O(n)。

(c) 使用单链表作为成员变量,入队操作执行单链表尾插入,时间复杂度是O(n);出队操作执行中间删除,顺序查找优先级最高的元素并将其删除,时间复杂度是O(n)。

(d) 使用排序单链表作为成员变量,元素按优先级升序排序,队头元素优先级最高,入队操作执行单链表中间插入,顺序查找根据优先级确定元素的插入位置,时间复杂度是O(n);出队操作执行单链表头删除,时间复杂度是O(1)。

(e) 使用循环双链表作为成员变量,入队操作执行循环双链表尾插

入,时间复杂度为O(1);出队操作执行中间删除,时间复杂度是O(n)。

(f) 使用排序循环双链表作为成员变量,入队操作执行中间插入,时间复杂度是O(n);出队操作执行循环双链表头删除,时间复杂度是O(1)。

- 40 -

序号01?n-1?length-1顺序表list(E,4)(D,3)(A,1)(F,3)(B,2)(C,1)入队,尾插入,O(1)出队,查找到尾再中间删除,O(n)(a)使用顺序表作为成员变量序号01?n-1?length-1排序顺序表list(A,1)(C,1)(B,2)(D,3)(F,3)(E,4)出队,头删除,O(n)(b)使用排序顺序表作为成员变量head(E,4)(D,3)(A,1)(F,3)(B,2)(C,1)∧入队,尾插入,O(n)入队,中间插入,O(n)出队,查找到尾再中间删除,O(n)(c)使用单链表作为成员变量head(A,1)出队,头删除,O(1)(d)使用排序单链表作为成员变量head入队,尾插入,O(1)(E,4)(D,3)(A,1)(C,1)(B,2)(D,3)(F,3)

(E,4)∧入队,中间插入,O(n)(F,3)(B,2)(C,1)出队,查找到尾再中间删除,O(n)(e)使用循环双链表作为成员变量head(A,1)出队,头删除,O(1)(C,1)(B,2)(D,3)入队,中间插入,O(n)(F,3)(E,4)(f)使用排序循环双链表作为成员变量图4.3 使用各种线性表对象作为优先队列成员变量的操作效率比较

综上所述,出队时间是O(1)的优先队列有两种,分别使用排序单链表和排序循环双链表,前者仅支持按优先级升序排序,后者支持升序和降序。

4.3 递归

【习4.1】 打印数字塔。

打印如下形式的数字塔:

1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1

- 41 -

1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 题目本身虽不是递归定义的,但可以用递归算法求解。程序如下:

public class DigitTower {

public static void i,int n) line(int //输出一行,递归方法

{ System.out.print(String.format(\ if (i

{ line(i+1,n);

System.out.print(String.format(\ } }

public static void main(String args[]) {

int n=9;

for(int i=1; i<=n; i++)

{ System.out.print(String.format(\')); //前导空格

line(1,i);

System.out.println(); } } }

- 42 -