高中信息技术沪教版（2019）选修1 数据与数据结构第二单元 初识数据结构本章综合与测试优秀当堂达标检测题

这是一份高中信息技术沪教版（2019）选修1 数据与数据结构第二单元 初识数据结构本章综合与测试优秀当堂达标检测题，共12页。试卷主要包含了约瑟夫环是一个数学的应用问题等内容，欢迎下载使用。
第二单元单元练习及参考答案 1.设有一个正整数序列组成的有序表(按递增次序有序，且允许有相等的整数存在),请编写能实现下列功能的程序:(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个)；(2)将比正整数x小的数按递减次序排列；(3)将比正整数x大的偶数删除。(4)比较使用数组和链表实现上述功能的优劣。2.把二次多项式ax2+bx+c设计成一种抽象数据类型，该类型的数据对象为三个系数项a,b和c,操作部分为:(1)初始化a,b和c的值;(2)做两个多项式加法；(3)根据给定x的值计算多项式的值;(4)计算方程ax2+bx+c=0的两个实数根；(5)按照ax**2+bx+c的格式输出二次多项式。 3.某航空公司有一个自动预订飞机票的系统，假设该系统中有一张用单链表表示的乘客表，见表2-7。表中结点按乘客姓氏的字母次序进行链接(指针暂用序号表示)，请为该系统编写有新乘客订票时修改乘客表的程序。表2-7乘客表datalinkLiu7Chen4Wang5Bao2Mai8Dong6Xi0Deng5Chang3 *4.约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1,2,3,…，n分别表示)围坐在一张圆桌周围。编号为k的人从1开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个出列；依此规律重复下去，直到圆桌周围的人全部出列。请用单链表设计一个程序求出出列顺序(单链表最后一个结点的指针指向链表的首结点)。   参考答案1.import randomclass SeqList( object)： def _init_ (self, max=100):self.max = max  #默认顺序表最多容纳10个元素#初始化顺序表数组    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#统计线性表中元素的个数 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#对数据进行排序 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大的，不重复的数据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的数据递减排列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,因为循环中是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之后的偶数 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)：#创建10个随机数的数据   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()  #输出排序前的数据seq. sortList()  #对数据进行排序seq.printList()  #出排序后的数据x=int(input("请输入要比较的数字："))seq. compareList(x) #和x比较，统计比x大的数据个数print(“将比x小的数按递减次序排列：")seq.printList()print("将比x大的偶数删除：")seq. deleteKey(x)  #删除比x大的偶数seq. printList() 2.把二次多项式ax2+bx+c设计成一种抽象数据类型，类型的数据对象为三个系数项a,b和c,操作部分为:☞初始化a,b和c的值;☞做两个多项式加法；☞根据给定x的值计算多项式的值；☞计算方程ax2+bx+c=0的两个实数根；☞按照ax**2+bx+c的格式输出二次多项式。参考答案:先创建链表，命名为 NodeList.py,程序在第3题也需要使用 #NodeList. py class Node:,,,data:结点保存的数据_next:保存下一个结点对象,,, def _init_(self, data,pnext=None):  self. data = data  self. Next=pnextdef _repr_(self):  return str( self.data)class NodeList:,,,head:头结点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方程系数   ,,,#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.某航空公司有一个自动预订飞机票的系统，假设该系统中有一张用单链表表示的乘客表，如下表所示。表中结点按乘客姓氏的字母次序进行链接(指针暂用序号表示)，请为该系统编写有新乘客订票时修改乘客表的程序。datalinkLiu7Chen4Wang5Bao2Mai8Dong6Xi0Deng5Chang3 参考答案：#本题需要用到第二题链表的创建 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("输入姓名(输入#结束)：\n”)while (Is! = ‘#’):  try:Insert(1s)Head= nodelist.headwhile(head! =None)：          print( head.data)          head! =head._next1s= input("输入姓名(输入#结束)：\n”) except Exception as e:Print(e)break4.约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1,2,3分别表示)围坐在一张圆桌周围。编号为k的人从1开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人出列；依此规律重复下去，直到圆桌周围的人全部出列。请用单链表设计一个程序求出出列顺序(单链表最后一个结点的指针指向链表的首结点)。    class Node()：#定义结点       def_init_(self, value,next=None):          self.value=value          self.next=next def createLink(n)：#创建链表    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(“请输入总人数："))m=int(input("请输入m:”))p=int(input("请输入开始的位置p:"))Josephus(n,m,p)Print(‘------------------------’)