第二單元單元練習(xí)及參考答案 1.設(shè)有一個正整數(shù)序列組成的有序表(按遞增次序有序，且允許有相等的整數(shù)存在),請編寫能實現(xiàn)下列功能的程序:(1)確定在序列中比正整數(shù)x大的數(shù)有幾個(相同的數(shù)只計算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的數(shù)有5個)；(2)將比正整數(shù)x小的數(shù)按遞減次序排列；(3)將比正整數(shù)x大的偶數(shù)刪除。(4)比較使用數(shù)組和鏈表實現(xiàn)上述功能的優(yōu)劣。2.把二次多項式ax2+bx+c設(shè)計成一種抽象數(shù)據(jù)類型，該類型的數(shù)據(jù)對象為三個系數(shù)項a,b和c,操作部分為:(1)初始化a,b和c的值;(2)做兩個多項式加法；(3)根據(jù)給定x的值計算多項式的值;(4)計算方程ax2+bx+c=0的兩個實數(shù)根；(5)按照ax**2+bx+c的格式輸出二次多項式。 3.某航空公司有一個自動預(yù)訂飛機(jī)票的系統(tǒng)，假設(shè)該系統(tǒng)中有一張用單鏈表表示的乘客表，見表2-7。表中結(jié)點按乘客姓氏的字母次序進(jìn)行鏈接(指針暫用序號表示)，請為該系統(tǒng)編寫有新乘客訂票時修改乘客表的程序。表2-7乘客表datalinkLiu7Chen4Wang5Bao2Mai8Dong6Xi0Deng5Chang3 *4.約瑟夫環(huán)(約瑟夫問題)是一個數(shù)學(xué)的應(yīng)用問題：已知n個人(以編號1,2,3,…，n分別表示)圍坐在一張圓桌周圍。編號為k的人從1開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。請用單鏈表設(shè)計一個程序求出出列順序(單鏈表最后一個結(jié)點的指針指向鏈表的首結(jié)點)。   參考答案1.import randomclass SeqList( object)： def _init_ (self, max=100):self.max = max  #默認(rèn)順序表最多容納10個元素#初始化順序表數(shù)組    self. num =0    self.data [None] *self.max def is_empty(self)：#判定線性表是否為空   return self. num is 0 def is_full(self)):  #判定線性表是否全滿   return self. num is self. max#統(tǒng)計線性表中元素的個數(shù) def  Count(self):    return self. num#表末尾插入操作 def  appendLast( self,value):   if self. num >= self.max:     print(‘The list is full ')     returnelse:self.data[ self. num]= value    self. num+=1#表任意位置插入操作: def insert( self, i, value):   if not isinstance(i, int):      raise  TypeErrorif i <0 and i self.num:      raise  IndexError for j in range( self. num, i-1, -1):       self.data[j]= self.data[i-1]    self data[i]= valueself. num +=1#對數(shù)據(jù)進(jìn)行排序 def sortlist( self):i=0j=0temp=0for i in range( self num-1):        for j in range( i+1, self. num): if( self.data[j]<self.data[i]):                temp=self.data[i]                self.data[i]=self.data[j]                Self.data[j]=temp#找比key大的，不重復(fù)的數(shù)據(jù)def compareList( self, key):    t=0if( self.data[0]>key)t=t+1  Print(self.data[0])for i in range(1,self.num-1):if( self.data[i]>key and self. data[i]!=self.data(i-1]):t=t+1Print(self.data[i])Print(“一共有”,t,”個”)#小于key的數(shù)據(jù)遞減排列def dijian( self, key):  t=0for i in range(0,self.num):if( self.data[i] <key):t=t+1t=t-1K=int(t/2)temp=0 #print(“------------k, t------------”,k,t)for i in range(0,k):temp=self.data[i]    self.data[i]= self.data[t]    sel.data[t]= tempt=t-1#刪除某一位置的操作def remove( self,i): if not isinstance(i, int)：    raise TypeError if i< 0 and i >= self.num: raise IndexErrorfor j in range(i,self.num-1)：#此處是self.num-1,因為循環(huán)中是j+1   #print(j, self data[j],self. data[j+1])   self.data[j]=self.data[j+1]) self.num-=1def delete( self, index)： for i in range( index, self.num-1)：    self.data[i] =self.data[i+ 1]  self.num-=1#刪除key之后的偶數(shù) def deleteKey( self, key):  i=0while(i <self.num)：   if( self.data[i]> key and self.data(i)% 2== 0)：     self. delete(i)  else:i+=1#輸出操作 def printlist( self):   for i in range(0, self. num):     print( self data[i])#print()Print(“----------------------------”)#銷毀操作def destroy( self): self. _init_()seq=SeqList(20) for i in range(10)：#創(chuàng)建10個隨機(jī)數(shù)的數(shù)據(jù)   t=random.randint(1, 100)#print(t)seq.appendLast(t)# print("*******")Seq.appendLast( seq.data[0])Seq.appendLast( seq.data[1])Seq.appendLast( seq.data[2])Seq.appendLast( seq.data[3])Seq.appendLast( seq.data[2])Seq.appendLast( seq.data[2])#seq.printList()  #輸出排序前的數(shù)據(jù)seq. sortList()  #對數(shù)據(jù)進(jìn)行排序seq.printList()  #出排序后的數(shù)據(jù)x=int(input("請輸入要比較的數(shù)字："))seq. compareList(x) #和x比較，統(tǒng)計比x大的數(shù)據(jù)個數(shù)print(“將比x小的數(shù)按遞減次序排列：")seq.printList()print("將比x大的偶數(shù)刪除：")seq. deleteKey(x)  #刪除比x大的偶數(shù)seq. printList() 2.把二次多項式ax2+bx+c設(shè)計成一種抽象數(shù)據(jù)類型，類型的數(shù)據(jù)對象為三個系數(shù)項a,b和c,操作部分為:?初始化a,b和c的值;?做兩個多項式加法；?根據(jù)給定x的值計算多項式的值；?計算方程ax2+bx+c=0的兩個實數(shù)根；?按照ax**2+bx+c的格式輸出二次多項式。參考答案:先創(chuàng)建鏈表，命名為 NodeList.py,程序在第3題也需要使用 #NodeList. py class Node:,,,data:結(jié)點保存的數(shù)據(jù)_next:保存下一個結(jié)點對象,,, def _init_(self, data,pnext=None):  self. data = data  self. Next=pnextdef _repr_(self):  return str( self.data)class NodeList:,,,head:頭結(jié)點Length:鏈表長度 ,,,def _init_(self):self.head=Nineself.length =0#判斷鏈表是否為空 def isEmpty( self):    return (self.length== 0)#最后一位添加元素 def append( self, dataOrNode):item=Nodeif isinstance( dataOrNode,Node):      item=dataOrNodeelse:item=Node(dataOrNode)if not self. head:self. head=itemself.length+=1else:node=self. headwhile node._next      Node=node._nextnode._next=item    self.length + =1#刪除元素def delete( self, index): if self.isEmpty():        print("ERROR: NODELIST EMPTY")        returnif index <0 or index > self length:   print(“error: out of index")    returnif index == 0:    self. head =self.head. _next    self.length-=1returnj=0Node=self.headprev=self.headwhile node. _next and j< index:prev=nodenode=node._nextself.length -=1#更新元素def update( self, index, data):   if self.isEmpty() or index <0 or index > self.length:      print(‘ERROR: OUT OF INDEX’)      returnj=0Node=self.headwhile node._ next and j< index: node=node._next     j+=1if j== index:   node.data=data#獲取元素def getltem( self, index):   if self.isEmpty() or index <0 or index >=self.length:      print("ERROR: OUT OF INDEX”)      returnj=0node=self.headwhile node._next and j< index:     node=node._next       j+=1return node.data#找到特定元素的位置def getIndex( self, data)：    j=0if self. isEmpty():        print("ERROR: NODELIST EMPTY") returnnode=self.headwhile node:        if node.data = data:   return  jnode=node._nextj+=1if j==self.length:print("%s not found"% str( data))return#在 index的位置插入元素def insert( self, index, dataOrNode):   if self.isEmpty():print("ERROR: NODELIST EMPTY")returnif index <0 or index > self length:        print("ERROR: OUT OF INDEX”) returnitem = NodeIf isintance( dataOrNode,Node):item =Node( dataOrNode)if index ==0:   item._next= self.head   self. head=item   self.length += 1 returnj=0node=self. headprev=self. headwhile node._next and j< index:prev=node node=node._nextj+=1if j== index:  item. _next =nodeprev. _next=itemself.length += 1#清空def clear( self):   self. head =None self.length=0def _repr_(self):if self isEmpty()       print("ERROR: NODELIST EMPTY")       returnnode=self. headnlist=” ”while nodenlist += str( node.data)+” “        node=node._ next     return nlistdef _getitem_(self,ind):if self.isEmpy() or ind <0 or ind >= self.length:      print("ERROR: OUT OF INDEX")      returnreturn self. getltem( ind)def _setitem_( self, ind, val)：  if self.isEmpty() or ind <0 or ind >= self.length:      print("ERROR: OUT OF INDEX")      returnself.update( ind, val) def_len_(self): return self.length#------------------------------以下是二次多項式的運算-------------------------------------import Nodelistclass Fomula:,,,a,b,c方程系數(shù)   ,,,#initdef _init_(self, a, b, c): nodeA= NodeList. Node( a) nodeB =Nodelist. Node( b) nodeC =NodeList.Node( c) nodeList =Nodelist.NodeList() nodeList. append( nodeA) nodeList. append( nodeB) nodeList append( nodeC) Self.nodeList= nodeList #adddef add( self, fomula2):  f1 =self.nodelist.head  f2 =fomula2.nodeList.head while (f1! =None)    f1.data += f2. dataf1=f1.nextf2=f2.next # calculate the sum def calValue( self, x): value=0     ratio= 2     f= self.nodelist.head     while (f!=None):        value += f.data *(x** ratio)    f=f._nextratio-=1return value #calculate result def calResult( self): f= self.nodeList. head list=[]while(f! =None):         list append( f.data)         f=f._ nexttemp=list[1]**2-4*list[0]*list[2] if temp<0    return” ERROR: NO ANSWER” elif temp==0   return -list[1]/(2* list[0])else:   return[(-list[1]+temp**0.5)/2/list[0],(-list[1]-temp**0.5)/2/list[0]]#Demonstrationdef show( self):f =self.nodelist. headlist=[]while (f! =None):        list.append( f data)        f=f._next     return str( list [0]+”x**2+”+str( list[1]+”x+”+str( list[ 2]) If _name_==”_main_”:print( fomula. Show())  print( fomula. calResult())  print( fomula. calValue(2))  fomulaNew=fomula(2, 4, 0)  fomula.add(fomulaNew)print( fomula show())  print( fomula. calResult())  print( fomula. calRValue( 2)) 3.某航空公司有一個自動預(yù)訂飛機(jī)票的系統(tǒng)，假設(shè)該系統(tǒng)中有一張用單鏈表表示的乘客表，如下表所示。表中結(jié)點按乘客姓氏的字母次序進(jìn)行鏈接(指針暫用序號表示)，請為該系統(tǒng)編寫有新乘客訂票時修改乘客表的程序。datalinkLiu7Chen4Wang5Bao2Mai8Dong6Xi0Deng5Chang3 參考答案：#本題需要用到第二題鏈表的創(chuàng)建 Nodelist.pyimport NodeListnodelist= Nodelist, Nodelist()def insert( curString)：  if nodeList. isEmptyo()：     nodeList. append( curString)else:head= nodeList.head    position =0    While(head!=None):if (curString > head.data):           head = head. nextPosition+=1 else:nodeList. insert( position, curString)    breakif (head == None):    nodeList.append(curString) def init():   initialSet =["Liu", "Chen","Wang","Bao", "Mai","Dong","Xi", "Deng",”Chang”]   for i in range( initialSet. _len_()):   insert(initialSet[i])If _name_==”_main_”:init()head nodeList.headwhile(head!= None):       print( head.data)       head =head. next1s= input("輸入姓名(輸入#結(jié)束)：\n”)while (Is! = ‘#’):  try:Insert(1s)Head= nodelist.headwhile(head! =None)：          print( head.data)          head! =head._next1s= input("輸入姓名(輸入#結(jié)束)：\n”) except Exception as e:Print(e)break4.約瑟夫環(huán)(約瑟夫問題)是一個數(shù)學(xué)的應(yīng)用問題：已知n個人(以編號1,2,3分別表示)圍坐在一張圓桌周圍。編號為k的人從1開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。請用單鏈表設(shè)計一個程序求出出列順序(單鏈表最后一個結(jié)點的指針指向鏈表的首結(jié)點)。    class Node()：#定義結(jié)點       def_init_(self, value,next=None):          self.value=value          self.next=next def createLink(n)：#創(chuàng)建鏈表    if n<=0: return Falseif n==1:            return Node(1) else:root = Node( 1)      tmp=root      for i in range(2, n+1):          tmp.next = Node(i)tmp=tmp.nexttmp.next=root      return root def showLink(root):   #打印鏈表   tmp=rootwhile True:        Print(rmp.value)       tmp=tmp.next         if tmp == None or tmp == root:breakdef josephus(n,k,p)：#具體的出圈  if k==1:print(‘最后出列’，n)      returnroot=createLink( n)    tmp=rootpT =1    while (pT< p):    tmp=tmp.nextpT+ =1while True:   for i in range(k-2):   tmp=tmp.nextprint(‘出列:’，tmp.next.value)  tmp.next=tmp.next.next  tmp=tmp. next  if tmp.ext =tmp:     breakprint(‘最后出列：’,tmp.value)If _name_==”_main_”:n=int(input(“請輸入總?cè)藬?shù)："))m=int(input("請輸入m:”))p=int(input("請輸入開始的位置p:"))Josephus(n,m,p)Print(‘------------------------’)                                         

相關(guān)試卷

粵教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.3.1 數(shù)據(jù)結(jié)構(gòu)精品綜合訓(xùn)練題：

這是一份粵教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.3.1 數(shù)據(jù)結(jié)構(gòu)精品綜合訓(xùn)練題，共11頁。試卷主要包含了選擇題，操作題等內(nèi)容，歡迎下載使用。

高中信息技術(shù)學(xué)考復(fù)習(xí)9基本數(shù)據(jù)結(jié)構(gòu)訓(xùn)練含答案：

這是一份高中信息技術(shù)學(xué)考復(fù)習(xí)9基本數(shù)據(jù)結(jié)構(gòu)訓(xùn)練含答案，共7頁。試卷主要包含了下列有關(guān)字符串的說法正確的是，有如下Pythn程序段，下列有關(guān)列表的說法正確的是，year等內(nèi)容，歡迎下載使用。

高中信息技術(shù)滬教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.問題分析課后復(fù)習(xí)題：

這是一份高中信息技術(shù)滬教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.問題分析課后復(fù)習(xí)題，共60頁。PPT課件主要包含了第三章房間篇，◇物業(yè)服務(wù)等內(nèi)容，歡迎下載使用。

英語朗讀寶

相關(guān)試卷 更多

1.1初識多媒體技術(shù)同步練習(xí)滬科版信息技術(shù)選修2

1.1初識多媒體技術(shù)同步練習(xí)滬科版信息技術(shù)選修2
4.1初識面向?qū)ο蟪绦蛟O(shè)計思想同步練習(xí)滬科版信息技術(shù)選修1

4.1初識面向?qū)ο蟪绦蛟O(shè)計思想同步練習(xí)滬科版信息技術(shù)選修1
高中信息技術(shù)浙教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)第五章 數(shù)據(jù)結(jié)構(gòu)與算法5.1 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系優(yōu)秀同步達(dá)標(biāo)檢測題

高中信息技術(shù)浙教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)第五章 數(shù)據(jù)結(jié)構(gòu)與算法5.1 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系優(yōu)秀同步達(dá)標(biāo)檢測題
高中浙教版 (2019)3.3 棧精品同步練習(xí)題

高中浙教版 (2019)3.3 棧精品同步練習(xí)題
資料下載及使用幫助
版權(quán)申訴
版權(quán)申訴
若您為此資料的原創(chuàng)作者，認(rèn)為該資料內(nèi)容侵犯了您的知識產(chǎn)權(quán)，請掃碼添加我們的相關(guān)工作人員，我們盡可能的保護(hù)您的合法權(quán)益。
入駐教習(xí)網(wǎng)，可獲得資源免費推廣曝光，還可獲得多重現(xiàn)金獎勵，申請 精品資源制作， 工作室入駐。
版權(quán)申訴二維碼
高中信息技術(shù)滬教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)電子課本

本章綜合與測試

版本： 滬教版 (2019)

年級： 選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

切換課文
所有DOC左下方推薦
歡迎來到教習(xí)網(wǎng)
  • 900萬優(yōu)選資源，讓備課更輕松
  • 600萬優(yōu)選試題，支持自由組卷
  • 高質(zhì)量可編輯，日均更新2000+
  • 百萬教師選擇，專業(yè)更值得信賴
微信掃碼注冊
qrcode
二維碼已過期
刷新

微信掃碼，快速注冊

手機(jī)號注冊
手機(jī)號碼

手機(jī)號格式錯誤

手機(jī)驗證碼 獲取驗證碼

手機(jī)驗證碼已經(jīng)成功發(fā)送，5分鐘內(nèi)有效

設(shè)置密碼

6-20個字符，數(shù)字、字母或符號

注冊即視為同意教習(xí)網(wǎng)「注冊協(xié)議」及「隱私條款」
QQ注冊
手機(jī)號注冊
微信注冊

注冊成功

返回
頂部