高中信息技术沪教版（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()