第一部分

练习题及参考答案





1．1第1章绪论
1．1．1练习题

1． 什么是数据结构？有关数据结构的讨论涉及哪三方面？
2． 简述数据结构中运算描述和运算实现的异同。
3． 什么是算法？算法的5个特性是什么？试根据这些特性解释算法与程序的区别。
4． 分析以下算法的时间复杂度。

def fun(n):

x,y=n,100

while y>0:

if x>100:

x=x-10

y-=1

else: x+=1

5． 分析以下算法的时间复杂度。

def fun(n):

i,k=1,100

while i<=n:

k+=1

i+=2

6． 分析以下算法的时间复杂度。

def fun(n):

i=1

while i<=n:

i=i*2


7． 分析以下算法的时间复杂度。

def fun(n):

for i in range(1,n+1):

for j in range(1,n+1):

k=1

while k<=n:k=5*k


第一部分练习题及参考答案

数据结构教程（Python语言描述）学习与上机实验指导
1．1．2练习题参考答案
1． 答： 按某种逻辑关系组织起来的一组数据元素，按一定的存储方式存储于计算机中，并在其上定义了一个运算的集合，称为一个数据结构。
数据结构涉及以下三方面的内容： 
① 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构。
② 数据元素及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构。
③ 施加于该数据结构上的操作，即运算。
2． 答： 运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作； 不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心是处理步骤。
3． 答： 通常算法定义为解决某一特定任务而规定的一个指令序列。一个算法应当具有以下特性。
① 有穷性： 一个算法无论在什么情况下都应在执行有穷步后结束。
② 确定性： 算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。
③ 可行性： 算法中每一条运算都必须是足够基本的。也就是说，它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。
④ 输入： 一个算法必须有0个或多个输入。它们是在算法开始运算前给予算法的量。这些输入取自特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。
⑤ 输出： 一个算法应有一个或多个输出，输出的量是算法运算的结果。
算法和程序不同，程序可以不满足有穷性。例如，一个操作系统在用户未使用前一直处于“等待”的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停机。
4． 答： 本算法中的基本操作语句是while循环体内的语句，它的执行次数与问题规模n无关，所以算法的时间复杂度为O(1)。
5． 答： 设while循环语句执行的次数为T(n)，i从1开始递增，最后取值为1+2T(n)，有i=1+2T(n)≤n，即T(n)≤(n-1)/2=O(n)，所以该算法的时间复杂度为O(n)。
6． 答： 本算法中的基本操作语句是i=i*2，设其频度为T(n)，则有2T(n)≤n，即T(n)≤log2n=O(log2n)，所以该算法的时间复杂度为O(log2n)。
7． 答： 算法中的基本操作语句为k=5*k。对于while循环： 

k=1

while k<=n: k=5*k

其中基本操作语句k=5*k的频度为log5n，再加上外层两重循环，所以本算法的时间复杂度为O(n2log5n)。
1．2第2章线性表
1．2．1练习题

1． 简述顺序表和链表存储方式的主要优缺点。
2． 对单链表设置一个头结点的作用是什么？
3． 假设均带头结点h，给出单链表、双链表、循环单链表和循环双链表中p所指结点为尾结点的条件。
4． 在单链表、双链表和循环单链表中，若仅知道指针p指向某结点，不知道头结点，能否将p结点从相应的链表中删去？若可以，其时间复杂度各为多少？
5． 带头结点的双链表和循环双链表相比有什么不同？在何时使用循环双链表？
6． 有一个递增有序的整数顺序表L，设计一个算法将整数x插入适当位置，以保持该表的有序性，并给出算法的时间和空间复杂度。例如，L=(1,3,5,7)，插入x=6后L=(1,3,5,6,7)。
7． 有一个整数顺序表L，设计一个尽可能高效的算法删除其中所有值为负整数的元素(假设L中值为负整数的元素可能有多个)，删除后元素的相对次序不改变，并给出算法的时间和空间复杂度。例如，L=(1，2，-1，-2，3，-3)，删除后L=(1，2，3)。
8． 有一个整数顺序表L，设计一个尽可能高效的算法将所有负整数的元素移到其他元素的前面，并给出算法的时间和空间复杂度。例如，L=(1，2，-1，-2，3，-3，4)，移动后L=(-1，-2，-3，2，3，1，4)。
9． 有两个集合采用整数顺序表A、B存储，设计一个算法求两个集合的并集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，并集C=(1，3，2，5，4)。
说明： 这里的集合均指数学意义上的集合，同一个集合中不存在相同值的元素。
10． 有两个集合采用递增有序的整数顺序表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的并集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，7)，并集C=(1，2，3，4，5，7)。
11． 有两个集合采用整数顺序表A、B存储，设计一个算法求两个集合的差集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，并集C=(3)。
12． 有两个集合采用递增有序的整数顺序表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的差集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，9)，差集C=(3，7)。
13． 有两个集合采用整数顺序表A、B存储，设计一个算法求两个集合的交集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，交集C=(1，2)。
14． 有两个集合采用递增有序的整数顺序表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的交集C，C仍然用顺序表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，7)，交集C=(1，5，7)。
15． 有一个整数单链表L，设计一个算法删除其中所有值为x的结点，并给出算法的时间和空间复杂度。例如L=(1，2，2，3，1)，x=2，删除后L=(1，3，1)。
16． 有一个整数单链表L，设计一个尽可能高效的算法将所有负整数的元素移到其他元素的前面。例如，L=(1，2，-1，-2，3，-3，4)，移动后L=(-1，-2，-3，1，2，3，4)。
17． 有两个集合采用整数单链表A、B存储，设计一个算法求两个集合的并集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，并集C=(1，3，2，5，4)。
18． 有两个集合采用递增有序的整数单链表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的并集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，7)，并集C=(1，2，3，4，5，7)。
19． 有两个集合采用整数单链表A、B存储，设计一个算法求两个集合的差集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，差集C=(3)。
20． 有两个集合采用递增有序的整数单链表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的差集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，9)，差集C=(3，7)。
21． 有两个集合采用整数单链表A、B存储，设计一个算法求两个集合的交集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，2)，B=(5，1，4，2)，交集C=(1，2)。
22． 有两个集合采用递增有序的整数单链表A、B存储，设计一个在时间上尽可能高效的算法求两个集合的交集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如A=(1，3，5，7)，B=(1，2，4，5，7)，交集C=(1，5，7)。
23． 有一个递增有序的整数双链表L，其中至少有两个结点，设计一个算法就地删除L中所有值重复的结点，即多个相同值的结点仅保留一个。例如，L=(1，2，2，2，3，5，5)，删除后L=(1，2，3，5)。
24． 有两个递增有序的整数双链表A和B，分别含有m和n个整数元素，假设这m+n个元素均不相同，设计一个算法求这m+n个元素中第k(1≤k≤m+n)小的元素值。例如，A=(1，3)，B=(2，4，6，8，10)，k=2时返回2，k=6时返回8。
1．2．2练习题参考答案
1． 答： 顺序表的优点是可以随机存取元素，存储密度高，结构简单； 缺点是需要一片地址连续的存储空间，不便于插入和删除元素(需要移动大量的元素)，表的初始容量难以确定。链表的优点是便于结点的插入和删除(只需要修改指针属性，不需要移动结点)，表的容量扩充十分方便； 缺点是不能进行随机访问，只能顺序访问，另外每个结点上增加指针属性，导致存储密度较低。
2． 答： 对单链表设置头结点的好处如下。
① 带头结点时，空表也存在一个头结点，从而统一了空表与非空表的处理。
② 在单链表中插入结点和删除结点时都需要修改前驱结点的指针属性，带头结点时任何数据结点都有前驱结点，这样使得插入和删除结点操作更简单。
3． 答： 各种链表中p结点为尾结点的条件如下。
① 单链表： p．next==None。
② 双链表： p．next==None。
③ 循环单链表： p．next==h。
④ 循环双链表： p．next==h。
4． 答： 以下分3种链表进行讨论。
① 单链表： 当已知指针p指向某结点时，能够根据该指针找到其后继结点，但是由于不知道其头结点，所以无法访问到p指针指向的结点的前驱结点，因此无法删除该结点。
② 双链表： 由于这样的链表提供双向链接，因此根据已知结点可以查找到其前驱和后继结点，从而可以删除该结点。其时间复杂度为O(1)。
③ 循环单链表： 根据已知结点的位置，可以直接找到其后继结点，又因为是循环单链表，所以可以通过查找得到p结点的前驱结点，因此可以删除p所指结点。其时间复杂度为O(n)。
5． 答： 在带头结点的双链表中，尾结点的后继指针为None，头结点的前驱指针不使用； 在带头结点的循环双链表中，尾结点的后继指针指向头结点，头结点的前驱指针指向尾结点。当需要快速找到尾结点时，可以使用循环双链表。
6． 解： 先在有序顺序表L中查找有序插入x的位置i(即在L中从前向后查找到刚好大于或等于x的位置i)，再调用L．Insert(i，x)插入元素x。对应的算法如下： 

def Insertx(L，x):

i=0

while i<L.getsize() and L［i］<x:#查找刚好≥x的元素序号i

i+=1

L.Insert(i,x)

上述算法的时间复杂度为O(n)，空间复杂度为O(1)。
7． 解： 采用《教程》中例2．3的3种解法，仅将保留元素的条件改为“元素值≥0”即可。对应的3种算法如下： 

def Delminus1(L):#算法1

k=0

for i in range(0,L.getsize()):

if L［i］>=0:#将元素值≥0的元素插入data中

L［k］=L［i］

k+=1#累计插入的元素个数

L.size=k;#重置长度



def Delminus2(L):#算法2

k=0

for i in range(0,L.getsize()):

if L［i］>=0:#将元素值≥0的元素前移k个位置

L［i-k］=L［i］

else:#累计删除的元素个数

k+=1

L.size-=k#重置长度



def Delminus3(L):#算法3

i=-1

j=0

while j<L.getsize():#j遍历所有元素

if L［j］>=0:#找到元素值≥0的元素a［j］

i+=1 #扩大元素值≥0的区间

if i!=j:#i不等于j时将data［i］与data［j］交换

L［i］,L［j］=L［j］,L［i］

j+=1#继续遍历

L.size=i+1#重置长度

上述3种算法的时间复杂度均为O(n)，空间复杂度均为O(1)。
8． 解： 采用《教程》中例2．3的解法3（即区间移动法），将“元素值!=x”改为“元素值<0”，并且移动后顺序表的长度不变。对应的算法如下： 

def Move(L):

i=-1

j=0

while j<L.getsize():#j扫描所有元素

if L［j］<0: #找到需要前移的元素a［j］

i+=1#扩大负元素的区间

if i!=j:#i不等于j时将data［i］与data［j］交换

L［i］,L［j］=L［j］,L［i］#将序号为i和j的两个元素交换

j+=1#继续遍历

上述算法的时间复杂度为O(n)，空间复杂度为O(1)。
9． 解： 将集合A中的所有元素添加到C中，再将集合B中不属于A的元素添加到集合C中，最后返回C，如图1．1所示。对应的算法如下： 

def Union(A，B):

C=SqList()

for i in range(0,A.getsize()):#将A中的所有元素添加到C中

C.Add(A［i］)

for j in range(0,B.getsize()):#将B中不属于A的元素添加到C中

e=B［j］

if A.GetNo(e)==-1:#时间为O(n)

C.Add(e)

return C#返回C




图1．1两个无序集合求并集

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(m+n)，其中m和n分别表示A和B中的元素个数。
10． 解： 由于顺序表A、B是有序的，采用二路归并方法，当A、B都没有遍历完时，将较小元素添加到C中，相等的公共元素仅添加一个，再将没有归并完的其余元素均添加到C中，最后返回C，如图1．2所示。对应的算法如下： 

def Union(A ,B):

C=SqList()

i=j=0

while i<A.getsize() and j<B.getsize():

if A［i］<B［j］:#将较小元素A［i］添加到C中

C.Add(A［i］)

i+=1

elif B［j］<A［i］:#将较小元素B［j］添加到C中

C.Add(B［j］)

j+=1

else:#公共元素只添加一个

C.Add(A［i］)

i+=1

j+=1

while i<A.getsize():#若A未遍历完,将余下的所有元素添加到C中

C.Add(A［i］)

i+=1

while j<B.getsize():#若B未遍历完,将余下的所有元素添加到C中

C.Add(B［j］)

j+=1

return C



图1．2两个有序集合求并集


上述算法的时间复杂度均为O(m+n)，空间复杂度为O(m+n)，其中m和n分别表示A和B中的元素个数。
11． 解： 将集合A中所有不属于集合B的元素添加到C中，最后返回C。对应的算法如下： 

def Diff(A，B):

C=SqList()

for i in range(0,A.getsize()):  #将A中不属于B的元素添加到C中

if B.GetNo(A［i］)==-1:#时间为O(n)

C.Add(A［i］)

return C#返回C

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(m)，其中m和n分别表示A和B中的元素个数。
12． 解： 差集C中的元素是属于A但不属于B的元素，由于顺序表A、B是有序的，采用二路归并方法，在归并中先将A中小于B的元素添加到C中，当B遍历完后，再将A中较大的元素(如果存在这样的元素)添加到C中，最后返回C。对应的算法如下： 

def Diff(A，B):

C=SqList()

i=j=0

while i<A.getsize() and j<B.getsize():

if A［i］<B［j］:#将较小元素A［i］添加到C中

C.Add(A［i］)

i+=1

elif B［j］<A［i］:#忽略较小元素B［j］

j+=1

else:#忽略公共元素

i+=1

j+=1

while i<A.getsize(): #若A未遍历完，将余下的所有元素添加到C中

C.Add(A［i］)

i+=1

return C

上述算法的时间复杂度均为O(m+n)，空间复杂度为O(m)，其中m和n分别表示A和B中的元素个数。
13． 解： 将集合A中所有属于B的元素添加到集合C中，最后返回C。对应的算法如下： 

def Inter(A，B):

C=SqList()

for i in range(0,A.getsize()):  #将A中属于B的元素添加到C中

if B.GetNo(A［i］)!=-1:#时间为O(n)

C.Add(A［i］)

return C#返回C

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(MIN(m，n))，其中m和n分别表示A和B中的元素个数。
14． 解： 由于顺序表A、B是有序的，采用二路归并方法，在归并中仅将A、B的相同值元素添加到C中，最后返回C。对应的算法如下： 

def Inter(A，B):

C=SqList()

i=j=0

while i<A.getsize() and j<B.getsize():

if A［i］<B［j］:#忽略较小元素A［i］

i+=1

elif B［j］<A［i］:#忽略较小元素B［j］

j+=1

else:#仅将公共元素添加到C中

C.Add(A［i］)

i+=1

j+=1

return C

上述算法的时间复杂度均为O(m+n)，空间复杂度为O(MIN(m，n))，其中m和n分别表示A和B中的元素个数。
15． 解： 设置(pre，p)指向L中相邻的两个结点，初始时pre指向头结点，p指向首结点。用p遍历L： 
① 若p结点值为x，通过pre结点删除p结点，置p结点为pre结点的后继结点。
② 若p结点值不为x，pre和p同步后移一个结点。
对应的算法如下： 

def Delx(L，x):

pre=L.head

p=pre.next#p指向首结点

while p!=None:#遍历所有数据结点

if p.data==x:#找到值为x的p结点

pre.next=p.next#通过pre结点删除p结点

p=pre.next#置p结点为pre结点的后继结点

else:#p结点不是值为x的结点

pre=pre.next#pre和p同步后移一个结点

p=pre.next

上述算法的时间复杂度均为O(n)，空间复杂度为O(1)。
16． 解法1： 删除插入法。若单链表L的首结点是负整数结点，先跳过单链表L开头的连续负整数结点，让last指向其最后一个负整数结点； 若单链表L的首结点不是负整数结点，则让last指向头结点。将pre置为last，p指向pre结点的后继结点，用(pre，p)同步指针遍历余下的结点： 
① 若p结点值<0，通过pre结点删除p结点，再将p结点插入last结点之后，然后置last=p，p继续指向pre结点的后继结点，以此类推，直到p为空。
② 否则，pre和p同步后移一个结点。
对应的算法如下： 

def Move1(L):#解法1

last=L.head

p=L.head.next

while p!=None and p.data<0:#跳过开头的负整数结点

last=last.next#last、p同步后移一个结点

p=p.next

pre=last;

while p!=None:#查找负整数结点p

if p.data<0:#找到负整数结点p

pre.next=p.next#删除p结点

p.next=last.next#将p结点插入last结点之后

last.next=p

last=p

p=pre.next

else:#p结点不是负整数结点

pre=pre.next#last、p同步后移一个结点

p=pre.next

解法2： 分拆合并法。扫描单链表L，采用尾插法建立由所有负整数结点构成的单链表A，采用尾插法建立由所有其他结点构成的单链表B(A、B均带头结点)。将B链接到A之后，再将L的头结点作为新单链表的头结点。对应的算法如下： 

def Move2(L):#解法2

p=L.head.next

A=LinkNode()#建立单链表A的头结点

B=LinkNode()#建立单链表B的头结点

ta,tb=A,B#ta、tb分别为A和B的尾结点

while p!=None:

if p.data<0:#找到负整数结点p

ta.next=p#将p结点链接到A的末尾

ta=p

p=p.next

else:#不是负整数结点p

tb.next=p#将p结点链接到B的末尾

tb=p

p=p.next

ta.next=tb.next=None#两个单链表的尾结点的next置为None

ta.next=B.next#将B链接到A的后面

L.head.next=A.next#重置L

17． 解： 本题先将集合A中的所有元素复制到C中，再将集合B中不属于A的元素添加到集合C中，最后返回C，算法执行后A、B集合没有被破坏。对应的算法如下： 

def Union(A，B):

C=LinkList()

t=C.head#t指向C的尾结点(采用尾插法建立C)

p=A.head.next

while p!=None:#将A复制到C中

s=LinkNode(p.data)

t.next=s; t=s;

p=p.next

q=B.head.next;

while q!=None:#将B中不属于A的元素复制后添加到C中

p=A.head.next;

while p!=None and p.data!=q.data:

p=p.next;

if p==None:#结点q值不出现在A中

s=LinkNode(q.data)

t.next=s; t=s;

q=q.next

t.next=None;

return C#返回C

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(m+n)，其中m和n分别表示A和B中的元素个数。
18． 解： 本题采用二路归并+尾插法建立并集C单链表，由A、B集合的相关结点重组成C，算法执行后A、B集合被破坏。对应的算法如下： 

def Union(A,B):

C=LinkList()

t=C.head#t指向C的尾结点

p=A.head.next

q=B.head.next

while p!=None and q!=None:

if p.data<q.data:#将较小结点p添加到C中

t.next=p

t=p

p=p.next

elif q.data<p.data:#将较小结点q添加到C中

t.next=q

t=q

q=q.next

else:#公共结点只添加一个

t.next=p

t=p

p=p.next

q=q.next

t.next=None

if p!=None: t.next=p#若A未遍历完，将余下的所有结点链接到C中

if q!=None: t.next=q#若B未遍历完，将余下的所有结点链接到C中

return C

上述算法的时间复杂度为O(m+n)，空间复杂度为O(1)，其中m和n分别表示A和B中的元素个数。
说明： 这里单链表C是利用A和B单链表的结点重构得到的，并没有新建结点，算法执行后A和B单链表不复存在。若采用结点复制的方法，不破坏A和B单链表，对应的时间复杂度为O(m+n)，空间复杂度为O(m+n)。
19． 解： 本题将集合A中所有不属于集合B的元素添加到C中，最后返回C。对应的算法如下： 

def Diff(A,B):

C=LinkList()

t=C.head#t指向C的尾结点(采用尾插法建立C)

p=A.head.next;

while p!=None:#将A中不属于B的元素添加到C中

q=B.head.next

while q!=None and q.data!=p.data:

q=q.next

if q==None:#结点p不在B中

s=LinkNode(p.data)

t.next=s; t=s;

p=p.next

t.next=None;

return C#返回C

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(m)，其中m和n分别表示A和B中的元素个数。
20． 解： 采用二路归并+尾插法建立差集C单链表，差集C中的元素是属于A但不属于B的元素，在归并中先将A中小于B的元素添加到C中，当B遍历完后，再将A中较大的元素(如果存在这样的元素)添加到C中，最后返回C。对应的算法如下： 

def Diff(A,B):

C=LinkList()

t=C.head#t指向C的尾结点

p=A.head.next

q=B.head.next

while p!=None and q!=None:

if p.data<q.data:#将较小结点p添加到C中

t.next=p

t=p

p=p.next

elif q.data<p.data:#忽略较小结点q

q=q.next

else:#忽略公共结点

p=p.next;

q=q.next;

t.next=None

if p!=None: t.next=p#若A未遍历完，将余下的所有结点链接到C中

return C

上述算法的时间复杂度均为O(m+n)，空间复杂度为O(m)，其中m和n分别表示A和B中的元素个数。
21． 解： 本题将集合A中所有属于B的元素添加到集合C中，最后返回C。对应的算法如下： 

def Inter(A,B):

C=LinkList()

t=C.head#t指向C的尾结点(采用尾插法建立C)

p=A.head.next;

while p!=None:#将A中属于B的元素添加到C中

q=B.head.next;

while q!=None and q.data!=p.data:

q=q.next

if q!=None:#结点p值在B中出现

s=LinkNode(p.data)

t.next=s; t=s;

p=p.next

return C#返回C

上述算法的时间复杂度均为O(m×n)，空间复杂度为O(MIN(m，n))，其中m和n分别表示A和B中的元素个数。
22． 解： 采用二路归并+尾插法建立交集C单链表，在归并中仅将A、B的相同值元素添加到C中，最后返回C。对应的算法如下： 

def Inter(A,B): 

C=LinkList()

t=C.head#t指向C的尾结点

p=A.head.next

q=B.head.next

while p!=None and q!=None:

if p.data<q.data:#忽略较小结点p

p=p.next

elif q.data<p.data:#忽略较小结点q

q=q.next

else:#仅将公共结点添加到C中

t.next=p

t=p

p=p.next

q=q.next

return C

上述算法的时间复杂度均为O(m+n)，空间复杂度为O(MIN(m，n))，其中m和n分别表示A和B中的元素个数。
23． 解： 在递增有序的整数双链表L中，值相同的结点一定是相邻的。首先让pre指向首结点，p指向其后继结点，然后循环，直到p为空为止： 
①  若p结点值等于前驱结点（pre结点）值，通过pre结点删除p结点，置p=pre．next。
②  否则，pre、p同步后移一个结点。
对应的算法如下： 

def Delsame(L):

pre=L.dhead.next

p=pre.next

while p!=None:#p遍历所有其他结点

if p.data==pre.data:#p结点是重复的要删除的结点

pre.next=p.next#通过pre结点删除p结点

if p.next!=None:

p.next.prior=pre

p=pre.next

else:#p结点不是重复的结点

pre=p#prep同步后移一个结点

p=pre.next

24． 解： 本算法仍采用二路归并的思路。若k<1或者k>A．getsize()+B．getsize()，表示参数k错误，抛出异常； 否则，用p、q分别扫描有序双链表A、B，用cnt累计比较次数(从0开始)，处理如下： 
① 当两个顺序表均没有扫描完时，比较它们的当前元素，每比较一次，cnt增1，当k==cnt时，较小的元素就是返回的最终结果。
② 否则，如果没有返回，让p指向没有比较完的结点，继续遍历并且递增cnt，直到找到第k个结点p后返回其值。
对应的算法如下： 

def topk(A,B,k):

assert k>=1 and k<=A.getsize()+B.getsize()

p=A.dhead.next

q=B.dhead.next

cnt=0

while p!=None and q!=None:#A、B均没有遍历完

cnt+=1#比较次数增加1

if p.data<q.data:#p结点较小

if cnt==k: return p.data #已比较k次，返回p结点值

p=p.next

else:#q结点较小

if cnt==k:return q.data#已比较k次，返回q结点值

q=q.next

if q!=None: p=q#p指向没有比较完的结点

cnt+=1#从p开始累计cnt

while cnt!=k and p!=None:#遍历剩余的结点

p=p.next

cnt+=1

return p.data

1．3第3章栈和队列
1．3．1练习题

1． 简述线性表、栈和队列的异同。
2． 有5个元素，其进栈次序为abcde，在各种可能的出栈次序中，以元素c、d最先出栈(即c第一个且d第二个出栈)的次序有哪几个？
3． 假设以I和O分别表示进栈和出栈操作，则初态和终态为栈空的进栈和出栈的操作序列可以表示为仅由I和O组成的序列，称可以实现的栈操作序列为合法序列(例如IIOO为合法序列，IOOI为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则。
4． 什么叫“假溢出”？如何解决假溢出？
5． 假设循环队列的元素存储空间为data［0．．m-1］，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置(例如data［0．．5］，队头元素为data［2］，则front=2，队尾元素为data［3］，则rear=4)，则在少用一个元素空间的前提下表示队空和队满的条件各是什么？
6． 在算法设计中，有时需要保存一系列临时数据元素，如果先保存的后处理，应该采用什么数据结构存放这些元素？如果先保存的先处理，应该采用什么数据结构存放这些元素？
7． 给定一个字符串str，设计一个算法采用顺序栈判断str是否为形如“序列1@序列2”的合法字符串，其中序列2是序列1的逆序，在str中恰好只有一个@字符。
8． 设计一个算法利用一个栈将一个循环队列中的所有元素倒过来，队头变队尾，队尾变队头。
9． 对于给定的正整数n(n>2)，利用一个队列输出n阶杨辉三角形，5阶杨辉三角形如图1．3(a)所示，其输出结果如图1．3(b)所示。


图1．35阶杨辉三角形及其生成过程


10． 有一个整数数组a，设计一个算法将所有偶数位元素移动到所有奇数位元素的前面，要求它们的相对次序不改变。例如，a={1，2，3，4，5，6，7，8}，移动后a={2，4，6，8，1，3，5，7}。
11． 设计一个循环队列，用data［0．．MaxSize-1］存放队列元素，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空(False)或可能满(True)，这样加上front==rear可以作为队空或队满的条件，要求设计队列的相关基本运算算法。
1．3．2练习题参考答案
1． 答： 线性表、栈和队列的相同点是它们元素的逻辑关系都是线性关系； 不同点是运算不同，线性表可以在两端和中间任何位置插入和删除元素，而栈只能在一端插入和删除元素，队列只能在一端插入元素、在另外一端删除元素。
2． 答： abc进栈，c出栈，d进栈，d出栈，下一步的操作如下。
①  ba出栈，再e进栈e出栈，得到出栈序列cdbae。
②  b出栈，e进栈e出栈，再a出栈，得到出栈序列cdbea。
③  e进栈e出栈，再ba出栈，得到出栈序列cdeba。
可能的次序有cdbae、cdeba、cdbea。
3． 答： 合法的栈操作序列必须满足以下两个条件。
①  在操作序列的任何前缀(从开始到任何一个操作时刻)中，I的个数不得少于O的个数。
②  整个操作序列中I和O的个数相等。
4． 答： 在非循环顺序队中，当队尾指针已经到了数组的上界，不能再做进队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的方式之一是采用循环队列。
5． 答： 在一般教科书中设计循环队列时，让队头指针f指向队头元素的前一个位置，让队尾指针r指向队尾元素，这里是队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置。这两种方法本质上没有差别，实际上最重要的是能够方便设置队空、队满的条件。
对于题目中指定的循环队列，f、r的初始值为0，仍然以f==r作为队空的条件，(r+1)%m==f作为队满的条件。
元素x进队的操作是data［r］=x; r=(r+1)%m。队尾指针r指向队尾元素的下一个位置。
元素x出队的操作是x=data［f］; f=(f+1)%m。队头元素出队后，下一个元素成为队头元素。
6． 答： 如果先保存的后处理，应该采用栈数据结构存放这些元素。如果先保存的先处理，应该采用队列数据结构存放这些元素。
7． 解： 设计一个栈st，遍历str，将其中'@'字符前面的所有字符进栈，再扫描str中'@'字符后面的所有字符，对于每个字符ch，退栈一个字符，如果两者不相同，返回False。当循环结束时，若str扫描完毕并且栈空，返回True，否则返回False。对应的算法如下： 

def match(str):

st=SqStack()                  #定义一个顺序栈

 i=0

 while i<len(str) and str［i］!='@':

st.push(str［i］)

i+=1

if i==len(str):#没有找到@，返回False

return False;

i+=1#跳过@

while i<len(str) and not st.empty():  #str没有扫描完毕并且栈不空，循环

if str［i］!=st.pop():#两者不等返回False

return False

i+=1

if i==len(str) and st.empty():#str扫描完毕并且栈空返回True

return True

else:#其他返回False

return False

8． 解： 设置一个栈st，先将循环队列qu中的所有元素出队并进到st栈中，再将栈st中的所有元素出栈并进到qu队列中。对应的算法如下： 

def Reverse(qu):

st=SqStack()#定义一个顺序栈

while not qu.empty():

st.push(qu.pop())

while  not st.empty():

qu.push(st.pop())

9． 解： 由n阶杨辉三角形的特点可知，其高度为n，第r(1≤r≤n)行恰好包含r个数字，在每行前后添加一个0(第r行包含r+2个数字)，采用迭代方式，定义一个队列qu，由第r行生成第r+1行。


图1．4生成前3行的过程


①  先输出第1行，仅输出1，将0、1、0进队。
②  当队列qu中包含第r行的全部数字时(队列中共r+2个元素)，生成并输出第r+1行的过程是进队0，出队元素s(第1个元素为0)，再依次出队元素t(共执行r+1次)，e=s+t，输出e并进队，重置t=s，最后进队0，这样输出了第r+1行的r+1个元素，队列中含r+3个元素。图1．4所示为生成前3行的过程。
对应的算法如下： 

def YHTriangle(n):

qu=CSqQueue()                 #定义一个循环队列

print(1)                        #输出第1行

qu.push(0)                      #第1行进队

qu.push(1)

qu.push(0)

for r in range(2,n+1):          #输出第2~n行

qu.push(0)

s=qu.pop()

for c in range(r):           #输出第r行的r个数字

t=qu.pop()

e=s+t

print(e,end=' ')

qu.push(e)

s=t

qu.push(0)

print()

10． 解： 采用两个队列来实现，先将a中的所有奇数位元素进qu1队中，所有偶数位元素进qu2队中，再将qu2中的元素依次出队并放到a中，qu1中的元素依次出队并放到a中。对应的算法如下： 

def Move(a):

qu1=CSqQueue()              #存放奇数位元素

 qu2=CSqQueue()                #存放偶数位元素

 i=0

 while i<len(a):

qu1.push(a［i］)#奇数位元素进qu1队

i+=1

if i<len(a):

qu2.push(a［i］)#偶数位元素进qu2队

i+=1

 i=0

 while not qu2.empty():            #先取qu2队列的元素

a［i］=qu2.pop()

i+=1

 while not qu1.empty():          #再取qu1队列的元素

a［i］=qu1.pop()

i+=1

11． 解： 初始时tag=False，front=rear=0，成功的进队操作后tag=True(任何进队操作后队列不可能空，但可能满)，成功的出队操作后tag=False(任何出队操作后队列不可能满，但可能空)，因此这样的队列的四要素如下。
①  队空条件： front==rear and tag==False
②  队满条件： front==rear and tag=True
③  元素x进队： rear=(rear+1)%MaxSize; data［rear］=x; tag=True;
④  元素x出队： front=(front+1)%MaxSize; x=data［front］; tag=False;
设计对应的循环队列类如下： 

MaxSize=100                    #全局变量，假设容量为100

class QUEUE:#队列类

def __init__(self):                #构造方法

self.data=［None］*MaxSize      #存放队列中的元素

self.front=0                  #队头指针

self.rear=0                   #队尾指针

self.tag=False#为False表示可能队空，为True表示可能队满

def empty(self):#判队空

return self.front==self.rear and self.tag==False

def full(self):#判队满

return self.front==self.rear and self.tag==True 

def push(self,x): #进队算法

assert not self.full()           #检测队满

self.rear=(self.rear+1)%MaxSize;

self.data［self.rear］=x

tag=True#至少有一个元素,可能满

def pop(self): #出队算法

assert not self.empty()         #检测队空

self.front=(self.front+1)%MaxSize

x=self.data［self.front］

tag=False#出队一个元素,可能空

return x   #成功出队

def gethead(self):#取队头元素

assert not self.empty()        #检测队空

head=(self.front+1)%MaxSize  #求队头元素的位置

return self.data［head］

1．4第4章串和数组
1．4．1练习题

1． 设s为一个长度为n的串，其中的字符各不相同，则s中的互异非平凡子串(非空且不同于s本身)的个数是多少？
2． 在KMP算法中计算模式串的next时，当j=0时为什么要取next［0］=-1？
3． KMP算法是BF算法的改进，是不是说在任何情况下KMP算法的性能都比BF算法好？
4． 设目标串s="abcaabbabcabaacbacba"，模式串t="abcabaa"，计算模式串t的nextval函数值，并画出利用改进的KMP算法进行模式匹配时每一趟的匹配过程。
5． 为什么数组一般不使用链式结构存储？
6． 如果某个一维整数数组A的元素个数n很大，存在大量重复的元素，且所有值相同的元素紧跟在一起，请设计一种压缩存储方式使得存储空间更节省。
7． 一个n阶对称矩阵存入内存，在采用压缩存储和采用非压缩存储时占用的内存空间分别是多少？
8． 设计一个算法，计算一个顺序串s中最大字符出现的次数。
9． 设计一个算法，将一个链串s中的所有子串"abc"删除。
10． 假设字符串s采用String对象存储，设计一个算法，在串s中查找子串t最后一次出现的位置。例如，s="abcdabcd"，t="abc"，结果为4。
(1) 采用BF算法求解。
(2) 采用KMP算法求解。
11． 设计一个算法，将含有n个整数元素的数组a［0．．n-1］循环右移m位，要求算法的空间复杂度为O(1)。
12． 设计一个算法，求一个n行n列的二维整型数组a的左上角－右下角和右上角－左下角两条主对角线的元素之和。
1．4．2练习题参考答案
1． 答： 由串s的特性可知，一个字符的子串有n个，两个字符的子串有n-1个，3个字符的子串有n-2个，……，n-2个字符的子串有3个，n-1个字符的子串有两个，所以非平凡子串的个数=n+(n-1)+(n-2)+…+2=n(n+1)/2-1。
2． 答： 在KMP算法中，当目标串s与模式串t匹配时，若si=tj，执行i++，j++(称为情况1)； 若si≠tj(失配处)，i位置不变，置j=next［j］(称为情况2)。若失配处是j=0，即si≠t0，那么从si开始的子串与t匹配一定不成功，下一趟匹配应该从si+1开始与t0比较，即i++，j=0，为了与情况1统一，置next［0］=-1（即j=next［0］=-1），这样再执行i++，j++ → j=0，从而保证下一趟从si+1开始与t0进行匹配。
3． 答： 不一定。例如，s="aaaabcd"，t="abcd"，采用BF算法时需要4趟匹配，比较字符的次数为10。采用KMP算法，求出t对应的next={-1，0，0，0}，同样也需要4趟匹配、10次字符比较，另外还要花时间求next数组，所以并非在任何情况下KMP算法的性能都比BF算法好，只能说在平均情况下KMP算法的性能好于BF算法。
4． 答： 模式串t的nextval函数值如表1．1所示，利用改进KMP算法的匹配过程如图1．5所示。


表1．1模式串t的nextval函数值




j
0
1
2
3
4
5
6
t［j］
a
b
c
a
b
a
a
next［j］
-1
0
0
0
1
2
1
nextval［j］
-1
0
0
-1
0
2
1



图1．5KMP算法的匹配过程


5． 答： 因为数组的主要操作是存取元素，通常没有插入和删除操作，使用链式结构存储时需要额外占用更多的存储空间，而且不具有随机存取特性，使得相关操作更复杂。
6． 答： 采用元素类型形如“［整数，个数］”的列表压缩存储，例如数组A为{1，1，1，5，5，5，5，3，3，3，3，4，4，4，4，4，4}，共有17个元素，对应的压缩存储为［［1，3］，［5，4］，［3，4］，［4，6］］，在压缩列表中只有8个整数。从中看出，重复元素越多，采用这种压缩存储方式越节省存储空间。
7． 答： 若采取压缩存储，其容量为n(n+1)/2； 若不采用压缩存储，其容量为n2。
8． 解： 置最大字符mch为s的首字符，mcnt表示其出现次数，i扫描其他字符，x为序号为i的字符。
①  若x>mch，则x为新的最大字符，置x=mch，mcnt=1。
②  若x==mch，当前最大字符x的出现次数mcnt增加1。
最后返回mcnt。对应的算法如下： 

def maxcount(s):

mcnt=1;

mch=s［0］

for i in range(s.getsize()):

if s［i］>mch:

mch=s［i］

mcnt=1

elif s［i］==mch:

mcnt+=1

return mcnt

9． 解： 用pre、p一对同步指针遍历链串s(初始时pre=s．head，p=pre．next)，当p结点及其后继两个结点合起来为"abc"时，通过pre结点删除该子串，p=pre．next继续遍历删除，否则pre、p同步后移一个结点。对应的算法如下： 

def delabc(s):

pre=s.head

 p=pre.next

 if p==None or p.next==None or p.next.next==None:

return

 while p!=None and p.next!=None and p.next.next!=None:

if p.data=='a' and p.next.data=='b' and p.next.next.data=='c':

pre.next=p.next.next.next   #查找到"abc"子串实施删除

p=pre.next

else:

pre=pre.next       #pre、p同步后移一个结点

p=pre.next

10． 解： 用lasti记录串s中子串t最后一次出现的位置(初始为-1)，修改BF和KMP算法，在s中找到一个t后用lasti记录其位置，此时i指向s中t子串的下一个字符，将j置为0继续查找。对应的算法如下： 

MaxSize=100

#(1)小题的算法