沪教版（2019）选修1第三单元 特殊的线性表 练习及参考答案

中小学教育资源及组卷应用平台
第三单元练习及参考答案
1.假设有如下功能的演唱会门票预订系统：
①按先到者先订的规则进行预订
②当门票都预订完后，允许在队伍中等待退票
请画出算法流程图并编程实现排队预订及等候退票功能。
参考答案
流程图如下所示；
参考代码如下所示：
#！/usr/bin/python
#-
-coding:utf-8-
-
total_tickets=3
#假设总票数为3
user_in_the_queue=[]
#定义排队队列，用列表模拟
def
get_ticket(user_name,amount)：
#如果还有票，返回购票数
#否则继续排队
global
total_
tickets
global
user_in_the_queue
left=total_tickets-amount
if
left>-1:
print(
user_name,
"get",amount,
"
tickets
successfully”)
total_tickets=total_tickets
-amount
return
else:
print(
user_name,
"can
not
get",amount,
"tickets,
wait
in
the
queue")
user_in_the_queue.append(user_name)
def
get_return_ticket(
user_name,
amount):
global
user_in_the_queue
first_user_in_the_queue=user_in_the_queue[len(user_in_the_queue)-1]
if
first_user_in_the_queue
==user_name:
get_ticket(
user_name,
amount)
else:
print(
user_name,
"can
not
get
ticket
first,
user
in
the
queue
now”)
user_in_the__queue.append(
user_name)
def
main():
user_name_a
="BoyA”
user_name_b
="BoyB”
user_name_c
="BoyC”
get_ticket(user_name_a,
3)
get_ticket(user_name_b,
3)
return_ticket(3)
get_return_ticket(user_name_c,
1)
get_return_ticket(user_name_b,
3)
def
return_ticket(amount):
global
total_tickets
total_tickets=total_tickets+amount
if
_name_==’_main_'：
main()
2.四方向迷官问题求解：假设有8X8的迷官如下所示(迷官用二维数组存放，可查阅资料了解二维数组)，1表示障碍不能通行，0表示通道可以通行。求解方法为：从人口开始出发沿着某一个方向向前试探，若能够通行，则继续试探前行：如果遇到障碍，马上原路返回，并在该路口做上记号，换另一个方向继续试探前行；重复上述步骤直到到达迷官的出口后结束。由于迷官错综复杂，靠人力来搜索迷官的所有通路是很费时、费力的一件事，因此可以借助计算机编程来完成。
入口00100010
00100010
00001100
01110000
00010000
01000100
01110110
00001000出口
①画出求解迷官问题中，栈的变化过程。
②设计解四方向迷宫问题的算法并编程实现。
提示：在编程时，为避免考虑第一行不能朝上走、第一列不能朝左走，最后一列不能朝右走，最下一行不能朝下走，可以在迷官外围设置一圈“围墙”，这样所有的位置都可考虑四个方向，围墙等同于障碍(用1表示)，如下所示。
1111111111
1001000101
1001000101
1000011001
1011100001
1000100001
1010001001
1011101101
1000010001
1111111111
参考答案:
参考代码如下所示：
#-
-coding:utf-8-
-
#！/usr/bin/python
import
sys
sys.setrecursionlimit(91832)
#set
the
maximum
depth
as
10000
Maze=[
[1,1,1,1,1,1,1,1,1,1],
[0,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,0,0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1]
]
used=[[
0
for
i
in
range(10)]
for
i
in
range(10)]
#use用于记录已走过的坐标，防止重走，同时便于回溯
dx=[
]
dy=[
]
def
movel(i,srex,srey,dstx,dsty)：#i表示第几步，当前坐标和终点坐标
print(i,
srex,
srey,
dstx,
dsty)
if
srex==dstx
and
srey==dsty:
print(‘run
away!’)
dx
append(
srex)
dy
append(
srey)
return
True
if
maze[srex+1][
srey]==0
and
used[
sex+1][srcy]==0:
print("down"，srcx+1，srcy)
dx.append(
srcx)
dy.append(
srcy)
srcx
+=1
used[srcx][srcy]=1
move(
i+1，srcx,
srcy,
dstx,
dsty)
used[srcx][srcy]=0
dx.
pop()
dy.
pop()
if
maze[srcx][srcy+1]==0
and
used[
srcx][
srcy+1]==0:
print("right"，srcx,
srcy+1)
dy.append(
srcx)
dy.append(
srcy)
srcy
+
=1
used[
srcx][srcy]=1
move(i+1，srcx,
srcy,
dstx,
dsty)
used[
srcx][srcy]=0
dx.
pop();
dy.pop();
if
maze[
srcx][
srcy-1]==0
and
used[
srcx][
srcy-1==0:
print("left",srcx,srcy+1)
dy.append(
srcx)
dy.append(
srcy)
srcy-=1
used[
srcx][srcy]=1
move(
i+1，srcx,
srcy,
dstx,
dsty)
dx.
pop()
dy.
pop()
if
maze[srcx-1][srcy]==0
and
used[srcx-1][srcy]==0:
print("up"，srcx,
srcy+1)
dx.append(srcx)
dy.append(srcy)
srcx-=
1
used[
srcx][srcy]=1
used[
srcx][srcy]=1
move(i+1，srcx,
srcy,
dstx,
dsty)
used[
srcx][srcy]=0
dx.
pop()
dy.pop()
def
main():
move(1,1,0,8,9)
#move(1,1,0,8,9)
for
i
in
range(len(dx)):
print('The{}step
is({},{})’.fomat(i+1,dx[i],dy[i]))
If
_name_=='_main_'：
main()
3.统计英文短文中某单词出现的次数
(3)假设有一篇英文短文，请画出算法流程图并编程实现以下操作：
①统计英文短文中某单词出现的次数。
②在英文短文中查找并替换某单词。
参考答案：
采用递归的方式实现，流程图如下所示：
参考代码如下所示：
#！/usr/bin/python
#coding=utf-8
def
main()；
english_paragraph="Hello,world.This
is
a
new
world
for
you."
#红色部分是编者假设的短文内容
find_word="word"
#红色部分是编者假设的查找字符
replaced_word="you"
#红色部分是编者假设的精换的字符
find(english_paragraph,find_word)
#查找字符
print("\r\n===========================\r\n”)
replace(english_paragraph,replaced_word,find_word)
#精换字符
def
alphabet_in_control_list(alphabet)：
control_list=["
",”,”,”.”,"\","\”]
if
alphabet
in
control_list:
return
True
return
False
def
find(english_paragraph,find_word)：
WillFind=”"
Total=0
for
alphabet
in
english_paragraph：
if
alphabet_in_control_list(alphabet)：
if
WillFind==find_word;
Total=Total+1
WillFind=””
else:
WillFind=WillFind+alphabet
print("find"，find_word,"in
paragraph,total:"，Total,".")
def
replace(english_paragraph,replaced_word,find_word)：
Will
Find=
“”
Replaced
Paragraph=""
for
alphabet
in
english_paragraph:
if
alphabet_in_control_list(alphabet):
if
Will
Find==find_word;
Replaced
Paragraph=Replaced
Paragraph+replaced_word+alphabet
else:
Replaced
Paragraph=Replaced
Paragraph+Will
Find+alphabet
Will
Find=””
else:
Will
Find=Will
Find+alphabet
print("replaced
result"，Replaced
Paragraph)
if
_name_=='_main_':
main()
栈dx存放路径点的x坐标；栈dy存放路径点的y坐标。
状态(1)为初始状态，dx,dy都是空栈。
状态(2)为从入口进入，入口的x坐标1和y坐标1分别进栈。
状态(4)为从(1,2)处继续向前试探，如果路堵死，则回到(1,1)处，(1,2)点的x坐标1和y坐标2分别出栈。再从(1,1)处试探另一条路径，通过这样反复搜索与回溯，最终找到从入口到出口的路径，而栈dx,dy中存放了路径点的x坐标值和y坐标值。
状态(3)为从(1,1)处继续向前试探，如果有路，则下一点的坐标入栈，即x坐标1和y坐标2分别进栈。
开始
n←1
读取英文段落的第n个字符
是否到达段落尾部？
是否标点符号？
WillFind是否要统计的单词？
把字符追到临时变量WillFind
Total←Total+1
清空临时变量WillFind
n←n+1
输出Total
结束
是
否
否
否
是
是
开始
n←1
读取英文段落的第n个字符
是否到达段落尾部？
是否标点符号？
WillFind是否要替换的单词？
ReplacedParagraph←ReplacedParaParagraph+WillFind+当前的标点符号
ReplacedParagraph←Replacedgraph+替换单词+当前的标点符号
清空临时变量WillFind
n←n+1
输出ReplacedParagraph
结束
是
否
否
否
是
是
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)