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

《数据结构：Python语言描述吕云翔习题答案.pdf》由会员分享，可在线阅读，更多相关《数据结构：Python语言描述吕云翔习题答案.pdf（132页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构：Python语言描述参考答案习题11.A2.C3.C4.A5.C6.B7.B8.C9.D10.C11.A12.B13.C14.D、1.集合；线性结构；树形结构；图形结构2.集合；线性结构；树形结构；图形结构3.有穷性；确切性；输入；输出；可行性4.时间和空间复杂度5.一对一；一对多；多对多6.逻辑关系7.没有；一8.一个；一个；后继；任意个9.任意个10.物理11.时间复杂度；空间复杂度12.问题规模三、1.#simple but ineffic ientdef prime(m):flag=Trueif(m=1):flag=Falsefor i in range(2,m):if(m

2、%i=0):flag=Falsebreakreturn flagn=int(input()print(prime(n)2.n=int(input()fac t=1tot=0for i in range(l,n+1):fac t*=itot+=fac tprint(sum=%d%tot)3.#same as O2.py#bec ause Q-2 is same as Q-34.def max(n):sum=0i=0while(sum n):i+=1sum+=ireturn in=int(input()print(i=%d*%max(n)5.#n*n multiplic ation table#n

3、 less than 10n=int(input()for i in range(1,n+1):for j in range(i,n+1):print(%d*%d=%0 2 d，%(i,j,i*j),end=n)print。习题21.B2.A3.C4.C5.B6.B7.A二、1.n+l ；n2.顺序;链式3.O(n)；O(n)4.0(1)；0(1)5.O(n)；0(1)6.0(1)；0(1)7.0(1)；O(n)c lass SqList(objec t):def_ init_(self,maxSize):self.c urLen=0self.maxSize=maxSizeself.listl

4、tem=None*self.maxSizedef c lear(self):self.c urLen=0def isEmpty(self).return self.c urLen=0def length(self)return self.c urLendef get(self,i):if i self.c urLen-1:raise Exc eptionC4ndex out of range1)return self.listltemfidef insert(self,i,x):passOl-pynew remove func tiontudef remove(self,i):if i sel

5、f.c urLen-1:raise Exc eption(index out of range)self.c urLen-=1for k in range(i,self.c urLen):self.listltemfk=self.listltemk+lfree half of the storage spac e of the arraywhile spac e usage less than 40 perc enttnif seif.c urLen/seif.maxSize 0.4:self.maxSize=int(self.maxSize/2)temp=self.listltemself.

6、listitem=None*self.maxSizefor i in range(self.c urLen):self.listltemfi=tempfidef indexOf(self,x):passdef display(self):fbr i in range(self.c urLen):print(self.listltemi,end=)print。)2.c lass Sequenc eSet(objec t):O2.pyc onstruc torH ldefinit_(self,arr):self.maxSize=int(len(arr)*1.5)self.setArray=None

7、J*self.maxSizeself.c urLen=0c ount=0for i in range(len(arr):if arrlij not in self.setAnay:self.setArrayc ount=arric ount+=1self.c urLen=c ountdef c lear(self):self.c urLen=0def isEmpty(self):return self.c urLen=0def length(self)return self.c urLendef get(self,i):passdef insert(self,i,x):passdef remo

8、ve(self,i):passdef indexOf(self,x):passdef display(self).for i in range(self.c urLen):print(self.setArrayi,end=)print()arr=input().split()test=Sequenc eSet(arr)test.displayOtest c ase#input3 2 6 4 6 4 3 9 8 1 8 4 7 4 2 0 1 1 29#output3 2 6 4 9 8 1 70n i3.c lass SqList(objec t):def_ init_(self,arr):s

9、elf.maxSize=int(len(arr)*1.5)self.listltem=None*self.maxSizeself.c urLen=0c ount=0for i in range(len(arr):self.listltemc ount=arric ount+=1self.c urLen=c ountdef display(self)*fbr i in range(self.c urLen):print(self.listltemi,end=)print。)O3.pyreturn max number of listitemHIdef getMax(self)*maxNum=se

10、lf.listItemOfor i in range(self.c urLen):if maxNum self.listltemij:maxNum=self.listltemireturn maxNumarr=input().split(*)test=SqList(arr)print(test.getMax()test c ase#input7.05 6.34 9.55 4.10 3.83 0.20 9.04 2.68 3.99 4.86#output9.55nt4.c lass Sequenc eSet(objec t):definit(self,arr):self.maxSize=int(

11、len(arr)*1.5)self.setAiTay=NoneJ*self.maxSizeself.c urLen=0c ount=0for i in range(len(arr):if aiTiJ not in self.setArray:self.setArrayc ountl=arric ount+=1self.c urLen=c ountdef display(self)*for i in range(self.c urLen):print(self.setArrayi,end=)print。)O4.pyc opy into c urrent setArraydef c opy(sel

12、f,s):temp=self.setArrayself.setArray=None*(self.maxSize+s.maxSize)c ount=0for i in range(self.c urLen+s.c urLen):if i self.c urLen:sei f.set Array i=tempielif s.setArrayi-self.c urLenJ not in self.setArray:self.setArrayself.c urLen+c ount=s.setArrayi-self.c urLenc ount+=1self.c urLen+=c ountarrl=inp

13、ut(,enter arrlXn.splitC)setl=Sequenc eSet(arrl)setl.displayOarr2=input(*enter air2n).split()set2=Sequenc eSet(arr2)set2.display()setl.c opy(set2)print(after c opying)setl.displayOtest c ase#input16 11 24 3 10 1521 199 1912 1 13 12 17 10 23 2 19 2#output16 II 24 3 10 15 21 19912 1 13 17 10 23 2 1916

14、11 24 3 10 15 21 199 12 1 13 17 23 25.c lass SqList(objec t):definit(self,arr):self.maxSize=int(len(arr)*1.5)self.listltem=None*self.maxSizeself.c urLen=0c ount=0for i in range(len(arr):self.listltemc ount=an-ijc ount+=1self.c urLen=c ountdef display(self).for i in range(self.c urLen):print(self.lis

15、tltemi,end=)print()O5.pyA-B=A.diff(B)An element that exists in A but does not exist in Bdef diff(self,arr):temp=for i in range(self.c urLen):if self.listltemi not in arr.listltem:temp.append(self.listltemi)return SqList(temp)n,testM,arrl=inputfenter setln).split()setl=SqList(arrl)arr2=input(*enter s

16、et2n,).split(,*)set2=SqList(arr2)retl=setl.diff(set2)print(setl-set21)retl.display()ret2=set2.diff(setl)print(set2-set 1f)ret2.display()#input1611 243 10 1521 199 1912 1 13 12 17 10 23 2 192#outputsetl-set216 11 243 15 21 9set2-setl12 1 13 12 17 23 2 2!(6.c lass Node(objec t):definit_(self,data=None

17、,next=None):self.data=dataself.next=nextc lass LinkList(objec t):def_ init_(self):self.head=Node()#order True or Falsedef c reate(self,1,order):if order:self.c reate_tail(l)else:self.c reate_head(l)def c reate_tail(self,1):for item in 1:self.insert(self.length(),item)def c reate_head(self,1):for ite

18、m in 1:self.insert(O,item)def c lear(selO：self.head.data=Noneself.head.next=Nonedef isEmpty(self):return self.head.next=Nonedef length(self)：p=self.head.nextlength=0while p is not None:p=p.nextlength+=1return length#get i-th elementdef get(self,i):p=self.head.nextj=owhile j i or p is None:raise Exc

19、eption()return p.data#insert x as the i-th elementdef insert(self,i,x):p=self.headJ=-1while p is not None and j i-1 or p is None:raise Exc eption()s=Node(x,p.next)p.next=s#remove the i-th elementdef remove(self,i):p=self.headj=-1while p is not None and j i-1 or p.next is None:raise Exc eption()p.nex

20、t=p.next.nextdef indexOf(self,x):p=self.head.nextj=owhile p is not None and not(p.data=x):p=p.nextj+=1if p is not None:return jelse:return-1def display(self):p=self.head.nextwhile p is not None:print(p.data,end=)p=p.nextprint。)M,O6.pyA-B=A.diff(B)An element that exists in A but does not exist in Bde

21、f diff(self,arr):p=self.headtemp=LinkList()c ount=0while p.next is not None:if aiT.indexOf(p.next.data)=-1:temp.insert(c ount,p.next.data)c ount+=1p=p.nextreturn tempHtest,narrl=inputfenter setlVn.splitC*)setl=Link.List()setl.c reate(arr 1,True)arr2=input(*enter set2n,).split(,*)set2=LinkList()set2.

22、c reate(arr2,True)retl=setl.diff(set2)print(setl-set2)retl.displayOret2=set2.diff(setl)print(,set2-setl)ret2.display()test c ase#input208 11 125 16 13 13 1012 14 11 15 3 85 3 14 15#outputsetl-set220 16 13 13 10set2-setl14 15 3 3 14 15tn7-a.c lass SqList(objec t):def _ init_(self,maxSize):passomit ot

23、her func tions H,”07-a.pyEstatic methoddef Josephus(n,m,s):arr=None*nfor i in range(n):arri=i+1ptr=s-1for i in range(n):for j in range(m-l):while arrptr=-1:ptr=(ptr+1)%nc ontinueptr=(ptr+1)%nwhile arrfptr=-1:ptr=(ptr+1)%nc ontinueprint(arrptr,end=)arr ptr=-1print。)ifname=main：n=int(input()m=int(inpu

24、t()s=int(input()SqList.Josephus(n,m,s)test c ase 1#input841#output4 8 5 2 1 3 7 6test c ase 2#input1879output154 11 1 9 18 103 148657 132 12 16 177-b.c lass Node(objec t):definit_(self,data=None,next=None):self.data=dataself.next=nextc lass LinkList(objec t):def_ init_(self)：passomit other func tion

25、sH,07-b.py static methoddef Josephus(n,m,s):head=Node(1)p=q=headfor i in range(n-l):q=Node(i+2)p.next=qp=qq.next=headfbr i in range(s-l):p=p.nextq=pfor i in range(n):for j in range(m-l):p=p.nextq=pq=q.nextprint(q.data,n,end=)p.next=q.nextprint。)n,testM,if _ name_ =_ mainn=int(input()m=int(input()s=i

26、nt(input()LinkList.Josephus(n,m,s)test c ase 1#input841#output4 8 5 2 1 3 7 6H ttest c ase 2#input1879output15 4 11 1 9 18 10 3 14 8 65 7 13 2 12 16 178.from abc import ABCMeta,abstrac tmethod,abstrac tpropertyc lass IList(metac lass=ABCMeta):abstrac tmethoddef c lear(self)：”将线性表置成空表”passabstrac tme

27、thoddef isEmpty(self)：“判断线性表是否为空表 passabstrac tmethoddef length(self)：返回线性表的长度”passabstrac tmethoddef get(self,i):”读取并返回线性表中的第i 个数据元素passabstrac tmethoddef insert(self,i,x):”插入x 作为第i 个元素”passabstrac tmethoddef remove(self,i)：，删除第i 个元素passabstrac tmethoddef indexOf(self,x):返回元素x 首次出现的位序号”passabstrac

28、tmethoddef display(self)：”，输出线性表中各个数据元素的值passc lass Node(objec t):def_ init_(self,data=None,next=None):self.data=dataself.next=nextc lass LinkList(IList):definit(sel0:self.head=N ode()#构造函数初始化头结点def c reate(self,l,order):if order:self.c reate_tail(l)else:self.c reate_head(l)def c reate_tail(self,l):

29、for item in 1:self.insert(self.length(),item)def c reate_head(self,l):fbr item in 1:self.insert(O,item)def c lear(self)：将线性表置成空表”self.head.data=Noneself.head.next=Nonedef isEmpty(self)*判断线性表是否为空表return self.head.next=Nonedef length(self)*“返回线性表的长度”p=self.head.nextlength=0while p is not None:p=p.next

30、length+=1return lengthdef get(self,i)：”读取并返回线性表中的第i 个数据元素”p=self.head.next#p 指向单链表的首结点j=#从首结点开始向后查找，直到p 指向第i 个结点或者p 为 nullwhile ji or p is None:#i 不合法时抛出异常raise Exc eption(“第“+i+”个数据元素不存在”)return p.datadef insert(self,i,x):(带头结点)插入x 作为第i 个元素”，p=self.headj=-1while p is not None and j i-l or p is None

31、:raise Exc eption(插入位置不合法”)s=Node(x,p.next)p.next=sH ldef insert(self,i,x):#(不带头结点)插入x 作为第i 个元素p=self.headj=-1while p is not None and j i-l or p is None:raise Exc eption(插入位置不合法”)s=Node(data=x)ifi=0:s.next=self.headelse:s.next=p.nextp.next=sdef remove(self,i):删除第i 个元素”p=self.headj=-1#寻找第i 个结点的前驱结点wh

32、ile p is not None and ji-l or p.next is None:raise Exc eption(删除位置不合法”)p.next=p.next.nextdef indexOf(self,x):”返回元素x 首次出现的位序号”p=self.head.nextj=0while p is not None and not(p.data=x):p=p.nextj+=1if p is not None:return jelse:return-1def display(self):“，输出线性表中各个数据元素的值”，p=self.head.nextwhile p is not N

33、one:print(p.data,end=*)p=p.nextL=LinkList()for i in range(8):s=input()L.insert(i,s)#依次输入：赵壹、钱贰、孙叁、李肆、周伍、吴陆、郑柒、王捌#注意每输入一个人名后键入一次回车#(1)print(l)班级学生：,end=)L.displayOprint(班级人数：,end=)print(L.length()#(2)prim32y李肆在表中的位置:,L.indexOf(“李肆”)#(3)L.insert(L.indexOf(“王捌”)+1，“冯玖”)L.remo ve(L.indexOf(赵壹)print(”(3)

34、现在该班级学生：”,end=)L.displayOprint()9.from abc import ABCMeta,abstrac tmethod,abstrac tpropertyc lass IList(metac lass=ABCMeta):abstrac tmethoddef c lear(self)“将线性表置成空表 passabstrac tmethoddef isEmpty(self):”判断线性表是否为空表passabstrac tmethoddef length(self)：”，返回线性表的长度”，passabstrac tmethoddef get(self,i):”读取并

35、返回线性表中的第i 个数据元素passabstrac tmethoddef insert(self,i,x):”插入x 作为第i 个元素”passabstrac tmethoddef remove(self,i)：“删除第i 个元素”passabstrac tmethoddef indexOf(self,x):“返回元素X首次出现的位序号.passabstrac tmethoddef display(self).“输出线性表中各个数据元素的值passc lass Node(objec t):def_ init_(self,data=None,next=None):self.data=datas

36、elf.next=nextc lass LinkList(IList):def_ init_(self).self.head=N ode()#构造函数初始化头结点def c reate(self,1,order):if order:self.c reate_tail(l)else:self.c reate_head(l)def c reate_tail(self,l):for item in 1:self.insert(self.length(),item)def c reate_head(self,l):fbr item in 1:self.insert(0,item)def c lear(

37、self)*“将线性表置成空表”self.head.data=Noneself.head.next=Nonedef isEmpty(self)：”判断线性表是否为空表”return self.head.next=Nonedef length(self)：”返回线性表的长度”p=self.head.nextlength=0while p is not None:p=p.nextlength+=1return lengthdef get(self,i)：”读取并返回线性表中的第i 个数据元素”p=self.head.next#p 指向单链表的首结点j=o#从首结点开始向后查找，直到p 指向第i 个

38、结点或者p 为 nullwhile ji or p is None:#i 不合法时抛出异常raise Exc eption(“第“+i+”个数据元素不存在”)return p.datadef insert(self,i,x):”带头结点)插入x 作为第i 个元素”，p=self.headj=-1while p is not None and j i-l or p is None:raise Exc eption(插入位置不合法”)s=Node(x,p.next)p.next=stndef insert(self,i,x):#(不带头结点)插入x 作为第i 个元素p=self.headj=-1w

39、hile p is not None and j i-l or p is None:raise Exc eption(插入位置不合法”)s=Node(data=x)ifi=0:s.next=self.headelse:s.next=p.nextp.next=stndef remove(self,i):“删除第i 个元素”p=self.headj=-1#寻找第i 个结点的前驱结点while p is not None and ji-l or p.next is None:raise Exc eption(删除位置不合法”)p.next=p.next.nextdef indexOf(self,x)

40、:”返回元素x 首次出现的位序号中p=self.head.nextj=0while p is not None and not(p.data=x):p=p.nextj+=1if p is not None:return jelse:return-1def display(self)*输出线性表中各个数据元素的值 p=self.head.nextwhile p is not None:print(p.data,end=)p=p.nextc lass PloyNode(objec t):def _ init_(self,a,i):self.a=a#系数self.i=i#指数def add(pl,p

41、2):L=LinkList()i=j=0while ipl.length()andjy.i:L.insert(L.length(),PloyNode(x.a,x.i)i+=1else:L.insert(L.length(),PloyNode(y.a,y.i)j+=1while ipl.length():x=pl.get(i)L.insert(L.length(),PloyNode(x.a,x.i)i+=1while jl:for i in range(M-l):p=p.nextprint(p.data,“出局”)J.remove(p.data)p=p.nextprint(p.data,胜出)习

42、题3、1.B2.B；A；B；D；C3.B4.A5.D6.C7.D8.B9.D10.D11.D12.C13.B14.B15.B二、1.线性；任何；栈顶；队尾；队首2.栈顶；栈底3.队列4.前一个5.n-16.移动栈顶指针；存入元素7.移动队首指针；取出元素8.if(top!=n)data+top=x;9.23 123*2-4/3 4 5*7/+108 9/+10.假上溢三、1.c lass SqStac k(objec t):definit(self,maxSize):self.maxSize=maxSizeself.stac kElem=None for i in range(self.max

43、Size)self.top=0def c lear(self)：self.top=0def isEmpty(self):return self.top=0def length(self):return self.topdef peek(self):if not self.isEnipty():return sei f.stac kElem sei f.top-1else:return Nonedef push(self,x):if self.top=self.maxSize:raise Exc eption(rstac k is full)self.stac kElemfself.top=xs

44、elf.top+=1def pop(self)：if self.isEmpty():return Noneself.top-=1return self.stac kElemself.topdef display(self):for i in range(self.top-1,-1,-1):print(self.stac kElemi,end=)print。)def c onvert(num,base):#0 num baseA32stac k=SqStac k(32)while num!=0:stac k.push(num%base)num=num/baseif stac k.isEmptyO

45、：print(O)else:stac k.displayOnum=int(input()#base=2,3,.9base=int(input()c onvert(num,base)2.c lass SqStac k(objec t):def _ init_(self,maxSize):self.maxSize=maxSizeself.stac kElem=None for i in range(self.maxSize)!self.top=0def c lear(self)：self.top=0def isEmpty(self):return self.top=0def length(self

46、):return self.topdef peek(self):if not self.isEmptyO：return self.stac kElemself.top-1else:return Nonedef push(self,x):if self.top=self.maxSize:raise Exc eption(rstac k is full)self.stac kElemfself.top=xself.top+=1def pop(selO：if self.isEmptyO：return Noneself.top-=1return self.stac kElemself.topdef d

47、isplay(self):fbr i in range(self.top-1,-1,-1):print(self.stac kElemi,end=)print。)def isMatc hed(str):#len(str)=100stac k=SqStac k(lOO)leftright=,)c hec k=left+rightfor i in str:if i not in c hec k:c ontinueif i in left:stac k.push(i)c ontinueif i in right:if stac k.isEmplyO：return Falsep=stac k.popO

48、if left.index(p)=right.index(i):c ontinuereturn Falseif stac k.isEmplyO：return Truereturn Falsestr=input()print(isMatc hed(str)3.#rec ursive algorithmdef FibByRec(n):if n matrixrp:flag=1breakif flag=0:print(r,p,matrixrp)#test c ase*input4645 67 87 34 56 2693 75 85 75 92 7594 85 96 75 78 7523 17 75 2

49、8 98 61tnn,output1 3 751 5 752 3 752 5 752.c lass SeqString(objec t):def _ init_(self,obj=None):if obj is None:self.c urLen=0self,str Value=else:self.c urLen=len(obj)self.strValue=None*self.c urLenfor i in range(self.c urLen):self.strValuei=objidef c lear(self).self.c urLen=0def isEmpty(self):return

50、 self.c urLen=0def length(self)：return self.c urLendef c harAt(self,i):if i=self.c urLen:raise IndexError(*index out of range1)return self.strValueidef display(self):for i in range(self.c urLen):print(self.strValuei,end=*)print()def c ount(self)：spac e=0for i in range(self.c urLen):if self.strValuei