資源簡介

綜合測(cè)試卷-2023—2024學(xué)年浙教版高中信息技術(shù)（2019）選擇性必修1
一、選擇題
1．定義如下函數(shù)：
def f(s,r):
if s-r**2<0 or r==0
return r+1
else:
return f(s-r**2,r-1)
執(zhí)行語句k=f(50,5)后，k的值為（ ）
A．4 B．3 C．2 D．1
2．棧s的最大長度為4，初始已有兩個(gè)元素在棧內(nèi)，棧底為a，棧頂為b，經(jīng)過一系列入棧、出棧操作，若元素入棧的順序是c，d，e，f，則可能的出棧序列為（ ）
A．c，a，b，e，f，d B．b，d，f，e，c，a
C．a(chǎn)，b，d，c，e，f D．b，e，f，c，d，a
3．某二叉樹的前序遍歷結(jié)果為ABCEDF，在該二叉樹基礎(chǔ)上添加一個(gè)節(jié)點(diǎn)后的中序遍歷為BGCADEF，則添加節(jié)點(diǎn)后的后序遍歷結(jié)果為（ ）
A．CGBDFEA B．GCBADFE C．CGBEFDA D．GCBDFEA
4．使用數(shù)組存儲(chǔ)某二叉樹的形式如圖所示，下列描述正確的是（ ）
0 1 2 3 4 5 6
A B C D
A．該二叉樹的后序遍歷為BDCA B．該二叉樹的深度為2
C．該二叉樹是一棵完全二叉樹 D．該二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)為3
5．小張準(zhǔn)備去多個(gè)城市旅游，他設(shè)計(jì)的行程若采用鏈表結(jié)構(gòu)表示，如圖a所示。

圖a 圖b
若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節(jié)點(diǎn)的next值賦為“杭州”所在節(jié)點(diǎn)的next值
②“上海”所在節(jié)點(diǎn)的next值賦為5
③“杭州”所在節(jié)點(diǎn)的next值賦為“上海”所在節(jié)點(diǎn)的next值
④“杭州”所在節(jié)點(diǎn)的next值賦為-1
鏈表更新順序正確的是（ ）
A．③② B．③① C．①④ D．②④
6．有如下phthon程序，程序運(yùn)行后，變量c的值為：（ ）
d=[1，7，5，2，3]
flag=False；last=i=c=0
while i<4 and flag==False：
flag=True
c+=1
for j in range（4，i，-1）：
if d[j] < d[j-1]：
d[j]，d[j-1]=d[j-1]，d[j]
flag=False；last=j
c+=1
i=last
A．6 B．7 C．8 D．9
7．有一棵完全二叉樹，已知其中序遍歷結(jié)果是CADGBEIHJ，則其前序遍歷結(jié)果應(yīng)該為（ ）
A．ABCDEFGHI B．EGACDBHIJ C．EACGBDIHJ D．EACDBHIJ
8．如下Python程序段：
import random
a=[1,3,5,7,9,11,13,15]
key=random.randint(1,8)*2
i,j=0,len(a)-1
s=0
while i<=j:
m=(i+j+1)//2
if a[m]==key:
break
if a[m]>key:
j=m-1;s-=1
else:
i=m+1;s+=1
print(s)
上述程序執(zhí)行完以后，s的值有幾種可能（ ）
A．4種 B．5種 C．7種 D．8種
9．找出序列中的最大數(shù)，并將其放到序列的最后面。實(shí)現(xiàn)上述功能的代碼如下：
#鏈表a中存儲(chǔ)了序列數(shù)據(jù)，head為其頭指針，代碼略
pre=p=head
maxpre=maxp=head
while p!=-1:
if a[p][0]>a[maxp][0]:
maxp=p ; maxpre=pre
pre=p
p=a[p][1]
if maxp==head:
head=a[head][1]
elif maxp!=pre:
①
a[pre][1]=maxp
②
#遍歷輸出鏈表a
劃線處的代碼應(yīng)為（ ）
A．①a[maxp][1]=a[maxpre][1] ②a[maxp][1]=a[p][1]
B．①a[maxp][1]=a[maxpre][1] ②a[maxp][1]=p
C．①a[maxpre][1]=a[maxp][1] ②a[maxp][1]=a[p][1]
D．①a[maxpre][1]=a[maxp][1] ②a[maxp][1]=p
10．假設(shè)隊(duì)列的空間足夠，隊(duì)首指針head和隊(duì)尾指針tail經(jīng)過“出隊(duì)、入隊(duì)、出隊(duì)、出隊(duì)、入隊(duì)、入隊(duì)、出隊(duì)”這一系列操作后，head=7，tail=9。則操作前的head和tail的值分別為（ ）
A．11 12 B．2 5 C．3 6 D．3 5
11．某二叉樹的樹形結(jié)構(gòu)如圖所示，其后序遍歷結(jié)果為DBGEFCA，前序遍歷的結(jié)果為（ ）
A．ABCDEFG B．ABDCEGF C．DBEGCFA D．ABDCGFE
12．棧s的最大長度為3，初始為空，經(jīng)過一系列的入棧、出棧操作，若元素入棧的順序是a，b，c，d，e，則可能的出棧序列為（ ）
A．a(chǎn)，e，d，c，b B．c，a，b，d，e
C．a(chǎn)，d，c，e，b D．e，d，c，b，a
13．某單向鏈表如下圖所示，若要將數(shù)據(jù)data3和data4同時(shí)從鏈表中移除，至少需要修改幾個(gè)節(jié)點(diǎn)的指針（ ）
A．1 B．2 C．3 D．4
14．棧S初始狀態(tài)為空棧，將序列3,2,5,7,1中元素逐一入棧，當(dāng)棧空或入棧元素比桟頂元素大時(shí)則入棧，否則出棧至符合條件再入棧。序列所有元素入棧完畢后，棧內(nèi)剩余元素出棧，直至棧空。則出棧的順序是（ ）
A．17523 B．37521 C．37512 D．32751
15．某對(duì)分查找算法Python程序段如下：
from random import randint
a=[8, 12,15,18, 18, 25, 25, 35, 47]
i=0; j=8
key=randint(8, 48)
while i<=j:
m=(i+j)//2
if key<=a[m]:
j=m-1
else:
i=m+l
print(i)
該程序執(zhí)行完成后輸出值為3，以下說法錯(cuò)誤的是（ ）
A．key值可能是16到18的整數(shù)
B．該程序m=(i+j)//2被執(zhí)行4次
C．該程序可實(shí)現(xiàn)查找第一個(gè)大于等于key值的位置
D．若key〈=a[m]改為key16．某二叉樹的樹形結(jié)構(gòu)如圖所示，其前序遍歷結(jié)果為BADCFGE，則字符“G”所在的位置為（ ）
A．① B．② C．③ D．④
17．某種特殊的隊(duì)列Q，支持以下三個(gè)操作：
操作Q1：若隊(duì)列非空，隊(duì)首元素出隊(duì)，并輸出；
操作Q2：若隊(duì)列非空，隊(duì)首元素出隊(duì)；
操作Q3：一個(gè)元素入隊(duì)；
以上任意一種操作后，若隊(duì)列非空，新的隊(duì)首元素仍為隊(duì)列中所有元素的最小值。
若隊(duì)列Q初始狀態(tài)為空，依次進(jìn)行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列說法正確的是（ ）
A．當(dāng)前隊(duì)列中的元素個(gè)數(shù)為2
B．輸出的元素個(gè)數(shù)為2
C．第一個(gè)輸出的元素肯定比當(dāng)前隊(duì)首元素大
D．隊(duì)列初始狀態(tài)是否為空對(duì)輸出結(jié)果有影響
18．定義如下函數(shù)：
def f（x,y）:
if x<=2 or y>20:
return x+y
return f（x-1,y+1）
執(zhí)行語句k=f（5,1）后，k的值為（ ）
A．6 B．7 C．8 D．9
19．以下兩個(gè)程序段的功能相同，實(shí)現(xiàn)的功能是：刪除列表a（元素個(gè)數(shù)為n）中的重復(fù)元素（只保留一個(gè)），并將剩下的元素降序輸出。
# 程序段① # 對(duì)列表a進(jìn)行降序排序，代碼略 i=1 while i0: print（i,end=""）
關(guān)于上述兩個(gè)程序段及功能的描述，正確的是（ ）
A．同樣的數(shù)據(jù)規(guī)模，兩個(gè)程序段的時(shí)間效率一樣
B．程序段①加框處語句是否執(zhí)行不受列表a原數(shù)據(jù)的影響
C．程序段②加框處語句修改為“for i in range（1,max_num+1）”，輸出結(jié)果不變
D．在實(shí)現(xiàn)該功能的過程中，程序段②比程序段①需要更多的存儲(chǔ)空間
20．有如下程序段：
def fun（k）: if k==1: return ″1″ elif k%2==0: return fun（k-1）+str（k%2） else: return str（k%2）+fun（k-1）
執(zhí)行語句s=fun（5），則s的值為（ ）
A．″00111″ B．″11010″ C．″11100″ D．″10110″
二、填空題
21．迭代算法與遞歸算法都需要 某些代碼，兩者既有區(qū)別又有密切的聯(lián)系。迭代是重復(fù) 的活動(dòng)，其目的通常是逼迫 ，其結(jié)束方式，通常使用 結(jié)束循環(huán)。
遞歸的重復(fù)方式是重復(fù) ，其結(jié)束方式是遇到 的情況時(shí)逐層返回。
22．結(jié)合分治策略，遞歸也可以用 三個(gè)字概況。分：將原有問題 成K個(gè)子問題；治：對(duì)這K個(gè)子問題 。如果子問題的規(guī)模仍然不夠小，則將其再分解為K個(gè)子問題，如此進(jìn)行下去，直到問題足夠小時(shí)，就很容易求出子問題的解。合：將求出的小規(guī)模問題的解 為一個(gè)更大規(guī)模問題的解，自下而上逐步求出原問題的解。
23．在數(shù)學(xué)與計(jì)算機(jī)領(lǐng)域中，遞歸函數(shù)是指用 定義該函數(shù)的方法。
24．def f(x,y):
ans=y;
for i in range(1,y-x+1):
ans = ans + f(x+i,y-i)
return ans;
def init():
x = int(input())
y = int(input())
print(f(x,y))
init()
(1)
輸入：4
5
輸出：
(2)
輸入：3
6
輸出：
25．小明同學(xué)所在城市的地鐵線路局部圖，如圖所示。他計(jì)劃從A站出發(fā)去B站附近的圖書館學(xué)習(xí)。假設(shè)地鐵各線路每兩站間行車用時(shí)相等，記為t1，停靠站時(shí)間忽略不計(jì)；換乘地鐵的用時(shí)也都相等，記為t2。
（1）如果t1＝t2，小明同學(xué)希望盡快到達(dá)B站，試為他推薦一條最佳乘車路線。
（2）設(shè)t1＝2min，t2＝lmin，則小明從A站出發(fā)到達(dá)B站的最短用時(shí)為 min。
三、操作題
26．某快遞驛站有A、B兩類貨架，收到的包裹重量小于等于10存放于A貨架，其余存放于B貨架。編寫程序模擬生成取件碼和顧客的取件過程，取件碼是根據(jù)當(dāng)前已處理的包裹數(shù)量生成，如A-0001表示當(dāng)天第一個(gè)處理的包裹存放在A貨架，B-0003表示當(dāng)天第三個(gè)處理的包裹存放在B貨架。取件碼與顧客手機(jī)號(hào)關(guān)聯(lián)，程序根據(jù)輸入的手機(jī)號(hào)顯示其所有包裹的取件碼，并允許顧客一次性提取或者部分提取。程序的部分運(yùn)行界面如圖a和圖b所示。
圖a 圖b
（1）當(dāng)前已處理的包裹取件碼是A-0158，若下一個(gè)包裹重量是12，其取件碼為 。
（2）定義函數(shù)save（pnum，code），參數(shù)pnum為手機(jī)號(hào)，code為取件碼。函數(shù)功能是將一條包裹信息存儲(chǔ)到列表goods和列表dic中。如圖a的包裹數(shù)據(jù)，手機(jī)號(hào)“1801215”在兩個(gè)列表中的數(shù)據(jù)分別為goods[4]=["B-0005"，-1]、goods[9]=["A-0010"，4]和dic[2]=["180****1215"，9，2]。
①若調(diào)用該函數(shù)繼續(xù)存儲(chǔ)手機(jī)號(hào)“180****1215”的包裹，其取件碼是“B-0011”，則對(duì)應(yīng)dic[2]的值變?yōu)閇"180****1215"， ， ]。
②函數(shù)save代碼如下，程序中加框處代碼有錯(cuò)，請(qǐng)改正 。
def save（pnum，code）：
goods．a(chǎn)ppend（[code，-1]）
n=len（goods）-1
print（n，"號(hào)包裹的手機(jī)號(hào)："，pnum，"取件碼："，code）
num=search（dic，pnum）#函數(shù)返回手機(jī)號(hào)pnum在dic中的索引號(hào)，未找到返回-1
if num==-1：
dic.append（[pnum，n，1]） #新增一個(gè)包裹信息
else：
goods[n][1]=dic[num][1]
dic[num][1]=n

（3）實(shí)現(xiàn)取件功能的部分Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
x=input（"請(qǐng)輸入您的手機(jī)號(hào)："）
num=search（dic，x）
if num！=-1：
#輸出手機(jī)號(hào)為x的當(dāng)前所有包裹信息，代碼略
op=int（input（"輸入0取全部包裹，輸入1取部分包裹："））
if op==0：
print（"您的包裹已經(jīng)取完！"）
del dic[num] #刪除dic中索引為num的元素
else：
order=input（"請(qǐng)輸入本次的取件碼，只輸入#表示結(jié)束取件："）
while order！="#"：

p，q=head，head
while goods[q][0]！=order：
p=q

if p==head：
dic[num][1]=goods[q][1]
else：
goods[p][1]=goods[q][1]
dic[num][2]-=1
if dic[num][2]==0：
print（"您的包裹已經(jīng)取完！"）
break
#輸出手機(jī)號(hào)為x的當(dāng)前所有包裹信息，代碼略
order=input（"請(qǐng)輸入本次的取件碼，只輸入#表示結(jié)束取件："）
else：
print（"查無此號(hào)，請(qǐng)檢查后重新輸入！"）
27．為了進(jìn)一步改善山區(qū)居民的生活，移動(dòng)公司要將移動(dòng)信號(hào)覆蓋到某個(gè)山區(qū)小村，需要在現(xiàn)有信號(hào)基站到目標(biāo)山區(qū)中間的若干山峰上建設(shè)基站。經(jīng)過前期勘探，依次記錄了n個(gè)山峰的信息，山峰編號(hào)依次為0到n﹣1，其中編號(hào)為0的山峰作為起點(diǎn)（信號(hào)接入位置），編號(hào)為n﹣1的山峰作為終點(diǎn)（目標(biāo)覆蓋區(qū)域），起點(diǎn)和終點(diǎn)必須建有基站。
工程師篩選中間基站建設(shè)位置的的過程中，若某一環(huán)節(jié)需要根據(jù)海拔高度篩選。從起點(diǎn)基站開始逐個(gè)山峰根據(jù)海拔高度，確定是否可以建設(shè)基站。具體規(guī)則如下：
①相鄰兩個(gè)基站的高度差的絕對(duì)值不能超過設(shè)定值d
②若最后一個(gè)選擇的山峰與終點(diǎn)的高度差超過d，則需要在兩座山峰之間建增加一個(gè)輔助基站，該基站建設(shè)高度為兩座山峰的平均值，編號(hào)為n。
小夢(mèng)編寫了一個(gè)Python程序用于模擬這一過程。程序中n個(gè)山峰的海拔高度已存入列表a，用鏈表存儲(chǔ)從起點(diǎn)到終點(diǎn)符合“海拔要求”的基站編號(hào)信息。
例如有7座山峰，海拔高度為a＝[100，80，90，88，80，66，60]，設(shè)定值d＝10。則依次選擇的山峰的編號(hào)為0，2，3，4，7，6，海拔高度依次為100，90，88，80，70，60，其中編號(hào)為4的山峰高度為80，與終點(diǎn)（6號(hào)山頂）山峰的高度60超過d，則需增加一個(gè)編號(hào)為7，高度為70的輔助基站。執(zhí)行效果如圖所示。

（1）如果編號(hào)0到4的山峰的海拔高度依次為60，50，30，40，60，且d＝10，則選定的基站的高度依次為 。
（2）請(qǐng)?jiān)趧澗€處填入合適的代碼。 、 、

28．某會(huì)務(wù)組根據(jù)參會(huì)者到達(dá)指定上車點(diǎn)時(shí)間和每位參會(huì)者可以等待的時(shí)間信息，安排車輛接送參會(huì)者去賓館（不考慮車子座位數(shù)量）。參會(huì)者到達(dá)上車點(diǎn)的時(shí)間和可以等待的時(shí)間用長度為7的字符串表示，例如“08：15 2”表示參會(huì)者當(dāng)天8點(diǎn)15分到達(dá)上車點(diǎn)，最多等待2分鐘（每個(gè)人的等待時(shí)間都小于10），那么該參會(huì)者最晚8點(diǎn)17分出發(fā)去賓館（若8點(diǎn)17分剛到的參會(huì)者也一同出發(fā)）。編寫Python程序，統(tǒng)計(jì)接送n個(gè)參會(huì)者所需的最少車輛數(shù)。運(yùn)行程序，顯示所有參會(huì)者提交的信息，按到達(dá)時(shí)間先后排列，再顯示所需的最少車輛數(shù)，程序運(yùn)行結(jié)果如圖所示。
（1）若將圖中第4行“08：154”數(shù)據(jù)改為“08：151”，程序輸出的結(jié)果是否會(huì)發(fā)生改變 （A．會(huì)改變B．不會(huì)改變）
（2）實(shí)現(xiàn)上述功能的部分Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
a=［'08：15 4'，'08：14 3'，'08：23 4'，'08：15 2'，'08：12 2'，'08：17 1'，'08：17 3'，'08：19 4'，'08：21 4'，'08：17 1'］
def tran（str1）：
ss=int（str1［：2］）*60+int（str1［3：6］）
return ss
for i in range（len（a）-1）：
for j in range（len（a）–1，i，-1）：
if a［j］a［j］，a［j-1］=a［j-1］，a［j］
n=len（a）
b=［］
c=［］
for i in range（n）：
b.append（tran（a［i］［：5］））
c.append（b［-1］+int（a［i］［6：］））
for j in range（i，0，-1）：
①
if c［k］>c［j］：
b［k］，b［j］=b［j］，b［k］
c［k］，c［j］=c［j］，c［k］
else：
break
sum=0
flag=［False for i in range（n）］
for i in range（n）：
if flag［i］==False：
for j in range（i，n）：
if ② ：
flag［j］=True
③
print（'接送所有參會(huì)者最少需要%d輛車'%sum）
29．臨近年關(guān)，學(xué)校為活躍新年氣氛，舉辦迎新年聯(lián)歡活動(dòng)，最后一個(gè)節(jié)目為“我是大贏家”抽獎(jiǎng)活動(dòng)，為增強(qiáng)互動(dòng)效果，最后中大獎(jiǎng)的中獎(jiǎng)?wù)哂山處焸冏约夯?dòng)產(chǎn)生，游戲規(guī)則是：全校所有教工，每人獲得一個(gè)隨機(jī)編號(hào)，編號(hào)不得重復(fù)，然后按照編號(hào)大小順時(shí)針手拉手圍成一個(gè)圈，最后一個(gè)老師與第一個(gè)老師手拉手，接下來由第1個(gè)人指定m的值，從編號(hào)為１的人開始報(bào)數(shù)（1,2,3…），報(bào)到m的人出圈，不再參加互動(dòng)游戲，接著再由出圈人的上一位老師新指定m的值，并重新開始報(bào)數(shù)，逆時(shí)針報(bào)到m的人出列，游戲過程中出圈的人由老師們自己決定，如此繼續(xù)，順時(shí)針出一個(gè)人，逆時(shí)針出一個(gè)人，直到圈中只剩下一個(gè)人，他就是今天的最大贏家。小明編寫了一個(gè)Python程序?qū)崿F(xiàn)上述功能，程序運(yùn)行時(shí)，輸入?yún)⒓佑螒虻娜藬?shù)，每次有人出圈后，再輸入下一個(gè)要出圈的人數(shù)。
#刪除索引為P 的游戲者
def delete(a,head,p):
if a[p][1]!=-1:
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
if head==p:
head=a[head][2]
return head
n=int(input("請(qǐng)輸入?yún)?shù)游戲的人數(shù)"))
a=[[i+1,i-1,i+1] for i in range(n)]
a[0][1]=n-1
a[n-1][2]=0
p=head=0
while :
m=int(input("請(qǐng)輸入順時(shí)針數(shù)第幾位人出局"))
for i in range(m-1):
head=delete(a,head,p)
p=a[p][1] #退回到上一位游戲者
if a[head][1]!=head:
m=int(input("請(qǐng)輸入逆時(shí)針數(shù)第幾位人出局"))
for i in range(m-1):
p=a[p][1]
head=delete(a,head,p)
#退回到上一位游戲者
print (a[head])
30．小萌通過“問卷星”收集到一些學(xué)生數(shù)據(jù)，如圖a所示。在按關(guān)鍵字“用戶名”進(jìn)行排序的過程中，對(duì)數(shù)據(jù)進(jìn)行整理，刪除重復(fù)數(shù)據(jù)，處理結(jié)果如圖b所示。

圖a

圖b
（1）在數(shù)據(jù)整理時(shí)，常見的數(shù)據(jù)問題有 （多選，選填字母）。
A．?dāng)?shù)據(jù)缺失 B．?dāng)?shù)據(jù)重復(fù) C．邏輯錯(cuò)誤 D．格式不一致
（2）實(shí)現(xiàn)上述功能的Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
a=[]
csv_file=open("xuehao.csv", "r", encoding='utf-8')
flines=csv_file. readlines() #將文件中所有數(shù)據(jù)按行讀入flines中
csv_file. close() #關(guān)閉文件
# 將每個(gè)數(shù)據(jù)行中的各項(xiàng)信息以“，”作為分隔符切割成字符串存入列表a中
for line in flines:
tmp=list(line. strip("\n"). split(","))
a. append(tmp)
n=len(a)
i=1; m=n-l #變量m表示刪除重復(fù)數(shù)據(jù)后的實(shí)際數(shù)據(jù)個(gè)數(shù)
while i for j in range(m, i, -1):
if :
tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp
elif a[j][4]==a[j-1][4]:
a[j]=a[m]

i+=1
for i in range (m+1):
print (a[i])
參考答案：
1．B
2．B
3．D
4．A
5．A
6．C
7．B
8．A
9．D
10．C
11．D
12．C
13．A
14．B
15．D
16．C
17．D
18．A
19．D
20．C
21． 重復(fù)執(zhí)行 反饋過程 所需目標(biāo)或結(jié)果 計(jì)數(shù)器 調(diào)用函數(shù)自身 滿足終止條件
22． “分”“治”“合” 分解 分別求解 合并
23．函數(shù)自身
24． 9 22
25． A-L-K-H-G-B 或 A-L-K-J-I-B 12
26． B-0159 10 3 dic[num][2]+=1或dic[num][2]=dic[num][2]+1 head=dic[num][1] q=goods[q][1]
27． 60 50 40 50 60 i=i+1 link[p][1]=n temp=link[temp][1]
28． A k=j-1 flag［j］== False and b［j］<=c［i］或b［j］<=c［i］ sum+=1或sum=sum+1
29． a[a[p][2]][1]=a[p][1]或等同答案 a[head][2]!=head: 或len(a)!=1 或等同答案 p=a[p][2]或等同答案 p=a[p][2]或等同答案
30． ABCD a[j][4]

展開更多......

收起↑