資源簡介

中小學教育資源及組卷應用平臺
第二單元
單元練習及參考答案
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乘客表
data
link
Liu
7
Chen
4
Wang
5
Bao
2
Mai
8
Dong
6
Xi
0
Deng
5
Chang
3
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]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]
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
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.某航空公司有一個自動預訂飛機票的系統，假設該系統中有一張用單鏈表表示的乘客表，如下表所示。表中結點按乘客姓氏的字母次序進行鏈接(指針暫用序號表示)，請為該系統編寫有新乘客訂票時修改乘客表的程序。
data
link
Liu
7
Chen
4
Wang
5
Bao
2
Mai
8
Dong
6
Xi
0
Deng
5
Chang
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(‘------------------------’)
21世紀教育網
www.21cnjy.com
精品試卷·第
2
頁
（共
2
頁）
HYPERLINK
"http://21世紀教育網(www.21cnjy.com)
"
21世紀教育網(www.21cnjy.com)

展開更多......

收起↑