数据结构：Python语言描述吕云翔习题答案.docx

《数据结构：Python语言描述》参考答案

习题1

一、

1.A

2.C

3.C

4.A

5.C

6.B

7.B

8.C

9.D

10.C

11.A

12.B

13.C

14.D

二、

1.集合；线性结构；树形结构；图形结构

2.集合；线性结构；树形结构；图形结构

3.有穷性；确切性；输入；输出；可行性

4.时间和空间复杂度

5.一对一；一对多；多对多

6.逻辑关系

7.没有；一

8.一个；一个；后继；任意个

9.任意个

10.物理

11.时间复杂度；空间复杂度

12.问题规模

三、

1.

#simplebutinefficient

defprime(m):

flag=True

if(m==1):

flag=False

foriinrange(2,m):

if(m%i==0):

flag=False

break

returnflag

n=int(input))

print(prime(n))

2.

n=int(input))

fact=1

tot=0

foriinrange(1,n+1):

fact*=i

tot+=fact

print(sum=%d%tot)

3.

#sameas02.py

#becauseQ-2issameasQ-3

4.

defmax(n):

sum=0

i=0

while(sumn):

i+=1

sum+=j

retunj

n=int(input))

print(i=%d%max(n))

5.

#n*nmultiplicationtable

#nlessthan10

n=int(input())

foriinrange(1,n+1):

forjinrange(i,n+1):

print(%d*%d=%02d%(i,j,i*j),end=)

print()

习题2

1.B

2.A

3.C

4.C

5.B

6.B

7.A

二、

1.n+1;n

2.顺序；链式

3.O(n);O(n)

4.O(1);O(1)

5.O(n);O(1)

6.O(1);O(1)

7.O(1);O(n)

三、

1.

classSqList(object):

definit(self,maxSize):

self.curLen=0

self.maxSize=maxSize

self.listltem=[None]*self.maxSize

defclear(self):

self.curLen=0

defisEmpty(self):

returnself.curLen==0

deflength(self):

returnself.curLen

defget(self,i):

ifi0oriself.curLen-1:

raiseException(indexoutofrange)

returnself.listltem[i]

definsert(self,i,x):

pass

01.py

newremovefunction

defremove(self,i):

ifi0oriself.curLen-1:

raiseException(indexoutofrange)

self.curLen-=1

forkinrange(i,self.curLen):

self.listltem[k]=self.listltem[k+1]

freehalfofthestoragespaceofthearray

whilespaceusagelessthan40percent

ifself.curLen/self.maxSize0.4:

self.maxSize=int(self.maxSize/2)

temp=self.listItem

self.listItem=[None]*self.maxSize

foriinrange(self.curLen):

self.listltem[i]=temp[i]

defindexOf(self,x):

pass

defdisplay(self):

foriinrange(self.curLen):

print(self.listltem[i],end=)

print()

2.

classSequenceSet(object):

02.py

constructor

def__init__(self,arr):

self.maxSize