沪教版（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乘客表
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)