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

第二单元

单元练习及参考答案

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乘客表

*4.约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1,2,3,…，n分别表示)围坐在一张圆桌周围。编号为k的人从1开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个出列；依此规律重复下去，直到圆桌周围的人全部出列。请用单链表设计一个程序求出出列顺序(单链表最后一个结点的指针指向链表的首结点)。

参考答案

1.

import random

class 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 ')

     return

else:

self.data[ self. num]= value

    self. num+=1

#表任意位置插入操作:

 def insert( self, i, value):

   if not isinstance(i, int):

      raise  TypeError

if 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]= value

self. num +=1

#对数据进行排序

 def sortlist( self):

i=0

j=0

temp=0

for 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=0

if( 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+1

Print(self.data[i])

Print(“一共有”,t,”个”)

#小于key的数据递减排列

def dijian( self, key):

  t=0

for i in range(0,self.num):

if( self.data[i] <key):

t=t+1

t=t-1

K=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]= temp

t=t-1

#删除某一位置的操作

def remove( self,i):

 if not isinstance(i, int)：

    raise TypeError

 if i< 0 and i >= self.num:

 raise IndexError

for 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-=1

def 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=0

while(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=pnext

def _repr_(self):

  return str( self.data)

class NodeList:

,,,

head:头结点

Length:链表长度

 ,,,

def _init_(self):

self.head=Nine

self.length =0

#判断链表是否为空

 def isEmpty( self):

    return (self.length== 0)

#最后一位添加元素

 def append( self, dataOrNode):

item=Node

if isinstance( dataOrNode,Node):

      item=dataOrNode

else:

item=Node(dataOrNode)

if not self. head:

self. head=item

self.length+=1

else:

node=self. head

while node._next

      Node=node._next

node._next=item

    self.length + =1

#删除元素

def delete( self, index):

 if self.isEmpty():

        print("ERROR: NODELIST EMPTY")

        return

if index <0 or index > self length:

   print(“error: out of index")

    return

if index == 0:

    self. head =self.head. _next

    self.length-=1

return

j=0

Node=self.head

prev=self.head

while node. _next and j< index:

prev=node

node=node._next

self.length -=1

#更新元素

def update( self, index, data):

   if self.isEmpty() or index <0 or index > self.length:

      print(‘ERROR: OUT OF INDEX’)

      return

j=0

Node=self.head

while node._ next and j< index:

 node=node._next

     j+=1

if j== index:

   node.data=data

#获取元素

def getltem( self, index):

   if self.isEmpty() or index <0 or index >=self.length:

      print("ERROR: OUT OF INDEX”)

      return

j=0

node=self.head

while node._next and j< index:

     node=node._next 

     j+=1

return node.data

#找到特定元素的位置

def getIndex( self, data)：

    j=0

if self. isEmpty():

        print("ERROR: NODELIST EMPTY")

return

node=self.head

while node:

        if node.data = data:

   return  j

node=node._next

j+=1

if j==self.length:

print("%s not found"% str( data))

return

#在 index的位置插入元素

def insert( self, index, dataOrNode):

   if self.isEmpty():

print("ERROR: NODELIST EMPTY")

return

if index <0 or index > self length:

        print("ERROR: OUT OF INDEX”)

 return

item = Node

If isintance( dataOrNode,Node):

item =Node( dataOrNode)

if index ==0:

   item._next= self.head

   self. head=item

   self.length += 1

 return

j=0

node=self. head

prev=self. head

while node._next and j< index:

prev=node

node=node._next

j+=1

if j== index:

  item. _next =node

prev. _next=item

self.length += 1

#清空

def clear( self):

   self. head =None

 self.length=0

def _repr_(self):

if self isEmpty()

       print("ERROR: NODELIST EMPTY")

       return

node=self. head

nlist=” ”

while node

nlist += str( node.data)+” “

        node=node._ next

     return nlist

def _getitem_(self,ind):

if self.isEmpy() or ind <0 or ind >= self.length:

      print("ERROR: OUT OF INDEX")

      return

return self. getltem( ind)

def _setitem_( self, ind, val)：

  if self.isEmpty() or ind <0 or ind >= self.length:

      print("ERROR: OUT OF INDEX")

      return

self.update( ind, val)

 def_len_(self):

 return self.length

#------------------------------以下是二次多项式的运算-------------------------------------

import Nodelist

class Fomula:

,,,

a,b,c方程系数

   ,,,

#init

def _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

 #add

def add( self, fomula2):

  f1 =self.nodelist.head

  f2 =fomula2.nodeList.head

 while (f1! =None)

    f1.data += f2. data

f1=f1.next

f2=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._next

ratio-=1

return value

 #calculate result

 def calResult( self):

 f= self.nodeList. head

 list=[]

while(f! =None):

         list append( f.data)

         f=f._ next

temp=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]]

#Demonstration

def show( self):

f =self.nodelist. head

list=[]

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.某航空公司有一个自动预订飞机票的系统，假设该系统中有一张用单链表表示的乘客表，如下表所示。表中结点按乘客姓氏的字母次序进行链接(指针暂用序号表示)，请为该系统编写有新乘客订票时修改乘客表的程序。

参考答案：

#本题需要用到第二题链表的创建 Nodelist.py

import NodeList

nodelist= 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. next

Position+=1

else:

nodeList. insert( position, curString)

    break

if (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.head

while(head!= None):

       print( head.data)

       head =head. next

1s= input("输入姓名(输入#结束)：\n”)

while (Is! = ‘#’):

  try:

Insert(1s)

Head= nodelist.head

while(head! =None)：

          print( head.data)

          head! =head._next

1s= input("输入姓名(输入#结束)：\n”)

 except Exception as e:

Print(e)

break

4.约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知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 False

if n==1:

            return Node(1)

else:

root = Node( 1)

      tmp=root

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

          tmp.next = Node(i)

tmp=tmp.next

tmp.next=root

      return root

 def showLink(root):   #打印链表

   tmp=root

while True:

       Print(rmp.value)

       tmp=tmp.next

         if tmp == None or tmp == root:

break

def josephus(n,k,p)：#具体的出圈

  if k==1:

print(‘最后出列’，n)

      return

root=createLink( n)

    tmp=root

pT =1

    while (pT< p):

    tmp=tmp.next

pT+ =1

while True:

   for i in range(k-2):

   tmp=tmp.next

print(‘出列:’，tmp.next.value)

  tmp.next=tmp.next.next

  tmp=tmp. next

  if tmp.ext =tmp:

     break

print(‘最后出列：’,tmp.value)

If _name_==”_main_”:

n=int(input(“请输入总人数："))

m=int(input("请输入m:”))

p=int(input("请输入开始的位置p:"))

Josephus(n,m,p)

Print(‘------------------------’)