數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)3

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)(三)

【知識(shí)要點(diǎn)】

一、“數(shù)據(jù)合并”問題簡(jiǎn)化成合并兩個(gè)有序數(shù)據(jù)序列的問題，對(duì)如何使用數(shù)組解決數(shù)據(jù)合并問題進(jìn)行了分析

并設(shè)計(jì)了算法。下面將對(duì)算法進(jìn)行修改和優(yōu)化，避免插入數(shù)據(jù)時(shí)其他數(shù)據(jù)元素的移動(dòng)，并編程實(shí)現(xiàn)該功能。

算法設(shè)計(jì)：

①初始化3個(gè)數(shù)組a,b,c,元素個(gè)數(shù)分別為m,n和n+m。數(shù)組a和數(shù)組b用來存儲(chǔ)已有的兩個(gè)有

序數(shù)據(jù)(降序)，數(shù)據(jù)使用隨機(jī)函數(shù)randint(start,end)產(chǎn)生；數(shù)組c用于保存合并后的所有數(shù)據(jù)(降序)，

所有數(shù)組元素的值初始化為0。②使用變量i指向數(shù)組a當(dāng)前未處理數(shù)據(jù)中要處理的數(shù)據(jù)元素的位置，初始

化為0;變量j指向數(shù)組b當(dāng)前未處理數(shù)據(jù)中要處理的數(shù)據(jù)元素的位置，初始化為0；變量k指向數(shù)組c中

可加入元素的位置，初始化為0。③重復(fù)以下操作，直至數(shù)組a或數(shù)組b中的數(shù)據(jù)元素全部合并入數(shù)組c

中：比較a[i]和b[j]的大小，若a[i]2b[j],則將a[i]放入數(shù)組c中,并將i和k的值增加1；否則，將

b[j]放入數(shù)組c中，并將j和k的值增加1。④如果數(shù)組a或數(shù)組b中尚有未處理的數(shù)據(jù)元素，那么將剩余

數(shù)據(jù)元素按原有順序依次存入數(shù)組c中，合并完成，輸出數(shù)組c。

fromrandomimportrandint

a=[0]*20;b=[0]*15;c=[0]*35#創(chuàng)建數(shù)組

a[0]=randint(95,100)

foriinranged,20):#隨機(jī)產(chǎn)生降序數(shù)據(jù)序列一

a[i]=a[il]randint(1,5)

b[0]=randint(95,100)

foriinranged,15):#隨機(jī)產(chǎn)生降序數(shù)據(jù)序列二

b[i]=b[il]randint(1,5)

print(，z原始數(shù)據(jù)序列一為：〃,a)

printCz原始數(shù)據(jù)序列二為：〃,b)

方法一：通過雙指針逐個(gè)遍歷二數(shù)組元素，將較大的存入合并數(shù)組中

i=0;j=0;k=0

while(i<20andj>15):#合并數(shù)據(jù)直至某個(gè)數(shù)組數(shù)據(jù)合并完成

ifa[i]>=b[j]:

c[k]=a[i];i=i+l;k=k+l

else:

c[k]=b[j];j=j+l;k=k+l

whilei<20:#當(dāng)數(shù)據(jù)序列一中還有數(shù)據(jù)時(shí)的處理

c[k]=a[i];i=i+l;k=k+l

whilej<15:#當(dāng)數(shù)據(jù)序列二中還有數(shù)據(jù)時(shí)的處理

c[k]=b[j];j=j+l;k=k+l

print(〃合并后的數(shù)據(jù)序列為：〃,c)

方法二：將b數(shù)組元素依次插入a數(shù)組中

forminrange(len(b)):

a.append(b[m])

tmp=a[l]

n=len(a)2

whiletmp>a[n]andn>0:

a[n+l]=a[n]

n=nl

a[n]=tmp

print(a)

⑵將兩個(gè)有序鏈表中的數(shù)據(jù)合并到一個(gè)鏈表中。

fromrandomimportrandint

data_[];head_a=l

data_b=[];head_b=l

tmp=randint(95,100)

data_a.append([tmp,head_a])

head_a=0

foriinrange(1,20):

tmp=data_a[il][0]randint(1,5)

data_a.append([tmp,data_a[il][1]])

data_a[il][l]=i

print(〃鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列一〃)

print(data_a)

tmp=randint(95,100)

datab.append([tmp,head_b])

head_b=0

foriinrange(1,25):

tmp=data_b[il][0]randint(1,5)

data_b.append([tmp,data_b[il][1]])

data_b[il][l]=i

print(〃鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列二〃)

print(data_b)

k_a=heada;q_a=head_a;k_b=head_b

while(k_a!=1andk_b!=1):

ifdata_a[k_a][0]>=data_b[k_b][0]:

Q_a=k_a

k_a=data_a[k_a][1]

else:

ifk_a=head_a:#在鏈表data_a的頭部插入節(jié)點(diǎn)

data_a.append([data_b[k_b][0],head_a])

head_a=len(data_a)1

q_a二head_a

k_b=data_b[k_b][1]

else:#在鏈表data_a的非頭部插入節(jié)點(diǎn)

data_a.append([data_b[k_b][0],k_a])

data_a[q_a][1]=len(data_a)1

q_a=data_a[q_a][1]

kb=data_b[k_b][1]

whilekb!=1:

data_a.append([data_b[k_b][0]1])

data_a[q_a][1]=len(data_a)1

q_a=data_a[q_a][1]

kb=data_b[k_b][1]

print(〃鏈表結(jié)構(gòu)的合并后數(shù)據(jù)序列〃)

print(data_a)

print(〃按鏈表鏈接順序輸出數(shù)據(jù)序列〃)

tmp=heada

whiledata_a[tmp][1]!=1:

print(data_a[tmp][0],end=〃〃)

tmp二data_a[tmp][1]

print(data_a[tmp][0])

(3)算法總結(jié)(請(qǐng)根據(jù)代碼，講變量名填入空格)

①初始化兩個(gè)空鏈表和,并使用和作為兩個(gè)鏈表的頭指針，其中

()作為存儲(chǔ)結(jié)果的鏈表。

②模擬生成兩個(gè)降序序列數(shù)據(jù)，每個(gè)序列中第一個(gè)數(shù)據(jù)使用隨機(jī)函數(shù)產(chǎn)生，其他數(shù)據(jù)則由前

一個(gè)數(shù)據(jù)減去一個(gè)隨機(jī)值(「5)產(chǎn)生，產(chǎn)生的數(shù)據(jù)作為新節(jié)點(diǎn)的數(shù)據(jù)區(qū)域的值，生成新的節(jié)點(diǎn)在尾部插入。

③使用變量______與指向兩個(gè)鏈表中未合并的數(shù)據(jù)序列中最前面(值最大)的節(jié)點(diǎn)，初始

化,，由于在鏈表data_a中需要進(jìn)行插入節(jié)點(diǎn)的操作，必須記錄插入位置的前驅(qū)

節(jié)點(diǎn)，使用變量_______，初始化q_a二head。重復(fù)以下操作，直到或指向空(即某個(gè)鏈表

元素全部處理完)：比較data_a[k_a][0]和data_b[k_b][0]的大小。若,則

修改q_a與k_a相等，再將k_a指向下一個(gè)節(jié)點(diǎn)；否則將鏈表data_b中指向的節(jié)點(diǎn)插入到鏈表

data_a中，作為q_a指向節(jié)點(diǎn)的后繼節(jié)點(diǎn)，再將k_b指向鏈表中的下一個(gè)節(jié)點(diǎn)。

④若k_b未指向空，則將鏈表data_b剩余節(jié)點(diǎn)按順序插入鏈表的尾部。

⑤輸出鏈表data_a中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)域的值。

【例題剖析】

3.合并兩個(gè)有序鏈表。將兩個(gè)由升序序列數(shù)據(jù)組成的鏈表進(jìn)行合并，要求新鏈表中的數(shù)據(jù)仍為升序序列。

程序運(yùn)行的界面如下圖所示：

實(shí)現(xiàn)上述功能的Python程序如下：

classNode：

def_init_(self,data=0,next=None)：

self.data=data

self.next=next

classSolution：

defmergeLists(self,hl：Node,h2：Node)：

head=Node()

node=head

whilehlandh2：

數(shù)據(jù)序列a為：

if①：

3681018

node.next=hl

數(shù)據(jù)序列b為：

hl=hl.next

27915

else：

合并后的數(shù)據(jù)序列為：

node.next=h2

236789101518

h2=h2.next

②

ifhl：

node.next=hl

else：

node.next=h2

node=head

returnhead,next

#生成鏈表a并輸出鏈表中數(shù)據(jù)，代碼略

#生成鏈表b并輸出鏈表中數(shù)據(jù)，代碼略

x=Solution()

xhead=x.mergeLists(ptrl,ptr2)

print(〃合并后的數(shù)據(jù)序列為：〃)

whilexhead：

print(xhead.data,end=〃〃)

?

請(qǐng)?jiān)趧澗€處填入合適的代碼：

答案：①hl.data<h2.data?node=node,next?xhead=xhead.next

解析：本題主要考查的是鏈表的綜合應(yīng)用。根據(jù)if下面的語句可知，if條件為指針hl指向的節(jié)點(diǎn)的值小

于指針h2指向的節(jié)點(diǎn)的值，因此①處代碼為hl.data<h2.data。將a、b鏈表中的較小值的節(jié)點(diǎn)處理后，還

應(yīng)將node指針移至剛插入到鏈表中的新節(jié)點(diǎn)，因此，劃線②處的代碼為node=node.next；劃線③處while

循環(huán)的功能是輸出合并后的鏈表，xhead為鏈表的頭指針，輸出當(dāng)前節(jié)點(diǎn)的data值后，將指針移動(dòng)到下一

個(gè)節(jié)點(diǎn)，因此③處應(yīng)填入的代碼為xhead=xhead.nexto

【習(xí)題鞏固】

1.有如下Python程序段：

a=[2,2,6,3,1,5,6,2]

pos=0

foriinrange(1,len(a)):

ifa[i]>a[pos]:

pos=i

則程序執(zhí)行后,pos的值為()

A.0B.2C.3D.6

2.有如下Python程序段:

a=[1,2,3,4,5,5]

x,j=4,len(a)2

whilej>=0anda[j]>x:

a[j+l]=a[j]

j二l

a[j+l]=x

則程序執(zhí)行后,a[4]的值為()

A.2B.3C.4D.5

3.有如下Python程序段：

fromrandomimportrandom

i=0

a=[0]*6

whilei<=5:

a[i]=(int(random()*6+5))*(i%2+l)

forjinrange(i):

ifa[j]==a[i]:

i=il

break

i=i+1

程序執(zhí)行后，數(shù)組a各元素的數(shù)據(jù)可能是

A.[6,12,5,18,8,10]B.[7,18,10,10,6,12]

C.[8,15,6,16,7,12]D.[5,16,12,18,9,10]

4.有如下程序段：

importrandom

a=[0]*6

foriinrange(6):

a[i]=random,randint(1,5)*2+1

i=0

whilei<5:

ifa[i]>a[i+l]:

a[i],a[i+l]=a[i+l],a[i]

a[i]+=l

i+=l

print(a)

以上程序運(yùn)行后，列表a的值可能是：()

A.[2,5,10,10,10,9]B.[3,8,7,13,3,9]C.[8,12,3,5,3,11]D.[6,10,9,7,10,8]

5.有如下Python程序段

defbianli(head):

pt=head

whilept!=1:

print(data[pt][0],data[pt][1],〃>〃,end='')

pt二data[pt][1]

print()

data=[「A',1],[,B',2],['C',3],['D',1]]

head=0

bianli(head)#遍歷鏈表，顯示初始狀態(tài)為“A1>B2>C3>D1>”

qt=head

pt=data[qt][1]

bianli(head)#遍歷鏈表，顯示最終狀態(tài)為“A2>C1>B3>D1>”

執(zhí)行該程序段后，鏈表遍歷結(jié)果由初始狀態(tài)變?yōu)樽罱K狀態(tài)，上述程序段中方框處可選代碼為：

①data[data[qt][1]][1]=pt②data[qt][1]=data[pt][1]③data[pt][1]=

data[data[pt][1]][1]

則方框處代碼的正確順序是

A.①②③B.①③②C.②①③D.②③①

6.小華規(guī)劃自駕旅游路線，出發(fā)地為杭州，目的地為北京，規(guī)劃過程中經(jīng)過了多次更改。

第一次依次加入的途徑地為上海、蘇州、南京、濟(jì)南、石家莊；

第二次在南京和濟(jì)南之間加入了途徑地青島，取消了途徑地南京；

第三次則在石家莊和北京之間加入了途徑地天津。

請(qǐng)使用鏈表編程實(shí)現(xiàn)其更改過程，并輸出三次更改路線后的結(jié)果。

完善代碼如下：

a=["杭州"，"上海","蘇州南京濟(jì)南"，"石家莊"，"北京"，"青島"，"天津"]

head=O

b=[l,1,1,1,1,1,1,1,1]

foriinrange(6):#第一次規(guī)劃

m

k=head#第二次規(guī)劃

whilek!=l:

ifa[k]二二〃南京〃:

break

(2)

(3)

b[k]=7

k=head

whilek!=l:

ifa[k]=〃南京〃：

break

q=k

k=b[k]

(4)

k=head#第三次規(guī)劃

whilek!=l:

ifa[k]=〃石家莊〃：

break

k=b[k]

b[8]=b[k]

b[k]=8

k=head

while(k!=l):

print(a[k],end=，/〃)

(5)

7.某投資者小趙將一段時(shí)間內(nèi)的證券操作記錄保存在文件“record,csv”中，部分界面如第4題圖a所

zj\O

使用pandas模塊對(duì)證券操作記錄進(jìn)行數(shù)據(jù)處理。

學(xué)習(xí)鏈表數(shù)據(jù)結(jié)構(gòu)后，小趙同學(xué)想篩選出證券操作盈利的記錄，并將結(jié)果以鏈表形式存儲(chǔ)。

(1)代碼實(shí)現(xiàn)如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。

importcsv

csvFile=open(z，record.csv〃，〃r〃，encoding=〃UTF8〃)

reader=csv.reader(csvFile)

a=[]#數(shù)據(jù)區(qū)域

foriteminreader:

a.append(item)

csvFile.close

points=[l]*len(a)#指針區(qū)域，與數(shù)據(jù)區(qū)域a中的數(shù)據(jù)---對(duì)應(yīng)

head二①

P=1

foriinrange(1,len(a)):

iffloat(a[i][5])>0:

ifhead=l:

P=i

else:

P=i

print（〃顯示證券操作盈虧為正的記錄：〃）

print（a[0]）#顯示標(biāo)題

p=head

whilep!=l:

print（a[p]）

_______④________

8.小明來到探險(xiǎn)島尋寶，島上共有N個(gè)寶藏（標(biāo)號(hào)為0至NDo每個(gè)寶藏有一條路連接下一個(gè)寶藏，寶

藏號(hào)和下一個(gè)寶藏號(hào)使用鏈表存儲(chǔ)。小明想知道，從其中一個(gè)寶藏出發(fā)，最多可以找到多少個(gè)寶藏。

例如，共有5個(gè)寶藏，輸入“1,3,4,4,1,”表示0~4各寶藏點(diǎn)連接的下一個(gè)寶藏依次是：

L3,4,4,1（如下表）。則最多可以找到4個(gè)寶藏，路徑為：0號(hào)1號(hào)3號(hào)4號(hào)。

程序代碼如下：

（1）若有4個(gè)寶藏，且每個(gè)寶藏的連接情況為：2,0,0,1,那么小明最多可以挖到的寶藏?cái)?shù)是o

（2）請(qǐng)將代碼補(bǔ)充完整。

s二input（〃請(qǐng)輸入寶藏連接的情況：〃）

t=0;c=，z/z;a=[]

寶藏號(hào)01234

下一個(gè)寶藏號(hào)13441

else:

a.append([t,int(c)])

〃〃

c二

①

max=0

forheadinrange(0,t):#枚舉尋找寶藏起點(diǎn)

g=[]

p=head

whilepnoting:

g.append(p)

②

iflen(g)>max:

print(max)

9.雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)節(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接前驅(qū)和直接后

繼。在Python中可以使用二維列表來模擬雙向鏈表，用包含3個(gè)元素的列表來表示每一個(gè)節(jié)點(diǎn)，其中第

一個(gè)元素存儲(chǔ)數(shù)據(jù)，后兩個(gè)元素分別存儲(chǔ)指向前驅(qū)和后繼的指針。若沒有前驅(qū)或后繼節(jié)點(diǎn)，則對(duì)應(yīng)的指針

值為lo下列程序生成了一些隨機(jī)正整數(shù)，并依次存儲(chǔ)到一個(gè)雙向鏈表a中?，F(xiàn)在要求刪除其中值為偶數(shù)

的節(jié)點(diǎn)，請(qǐng)?jiān)趧澗€處填入合適的代碼。

importrandom

a=□

head=1

foriinrange(8):

node二[random,randint(1,9),1,head]

a.append(node)

ifhead!=1:#非空鏈表

a[head][1]=len(a)1

head二①

p-head

whilep!=1:

ifa[p][0]%2==0:

ifa[p][1]!=1:#有前驅(qū)節(jié)點(diǎn)

a[a[p][l]][2]=②

ifa[p][2]!=1:#有后繼節(jié)點(diǎn)

a[a[p][2]][1]=a[p][1]

ifhead=p:#刪除頭節(jié)點(diǎn)

head=(3)

p=a[p][2]

10.王老師在處理最近一次的技術(shù)考試成績(jī)，在這次考試中，每位同學(xué)的信息通用成績(jī)是通過機(jī)器分開掃描

并存放在csv文件中，如圖a所示為csv文件的部分截圖。由于機(jī)器老化，在識(shí)別準(zhǔn)考證號(hào)時(shí)，部分準(zhǔn)考

證號(hào)的識(shí)別出現(xiàn)了亂碼(亂碼顯示為“？”)。王老師編寫了一個(gè)Python程序處理這些成績(jī)，這個(gè)程序?qū)崿F(xiàn)

了以下功能：1.將csv文件中的數(shù)據(jù)用鏈表形式存儲(chǔ)在列表中，并按準(zhǔn)考證號(hào)升序排序。每位同學(xué)有兩行

數(shù)據(jù)，信息成績(jī)?cè)谇?，通用成?jī)?cè)诤螅?.將這些亂碼數(shù)據(jù)去除；3.排序完成后將全年級(jí)的信息成績(jī)和通用

成績(jī)分開，前半部分為信息成績(jī)，后半部分為通用成績(jī)。圖b為處理完的鏈表按順序輸出的部分截圖。

definsertnode(num,grade,p):

node=[num,grade,p]

a.append(node)

return①

csv_file=open(，score2.csv，,*r*)#打開存有準(zhǔn)考證號(hào)和成績(jī)的文件

flines=csv_file.readlines()#將文件中的數(shù)據(jù)按行讀入flines中，返回一個(gè)列表

csv_file.close()

a=[];head=l

foriinranged,len(flines)1,2):#跳過第一行標(biāo)題

xx=flines[i].stripC\n).splitC,J)#每行數(shù)據(jù)去除換行符號(hào),返回以:為分隔符的列

表

ty=flines[i+l].strip(J\n).split[,')

if'?'inxx[0]:#若準(zhǔn)考證存在亂碼

continue

p=head

pre=head

whilep!=landxx[0]>a[p][0]:

pre=p

②

文件懈能杳有

ifp=head:準(zhǔn)考證號(hào)，成績(jī)

202008480,18

head=insertnode(xx[0],xx[l],p)202008480,33

202008319,19

202008319,23

pre=head202008333,20

202008333,20

202083775,22

else:202083775,27

202007294,23

202007294,18

a[pre][2]=insertnode(xx[0],xx[l],p)202007439,24

202007439,32

202009871,24

202009871,14

202008445,25

a[pre][2]=insertnode(ty[0],ty[1],p)202008445,28

#將信息和通用成績(jī)分開存儲(chǔ)第10題圖ascore2.csv文件

cur=head

last=a[cur][2][12020021781,’42L516]

tmp=last「2020036271’49L512]

「2020036291’481296]

whilea[cur][2]!=1anda[last][2]!=1:

[1202007230,,’41L476]

a[cur][2]=a[last][2];cur=a[cur][2][1202007288,,'471,82]

a[last][2]=a[cur][2];last=a[last][2][,202007289,,,31]510]

a[cur][2]-④[,202007290,,’48]6]

[1202007294,,,231126]

p=head#輸出鏈表

[,2020073231,'33L100]

whilep!=l:

第10題圖b輸出鏈表數(shù)據(jù)部分截圖

print(a[p])

p=a[p][2]

H.掃描算法是一種電梯的調(diào)度算法，電梯在最底層(1樓)和最頂層(20樓)之間連續(xù)往返掃描并運(yùn)行，

在運(yùn)行過程中優(yōu)先處理與當(dāng)前電梯運(yùn)行方向相同的請(qǐng)求，比如：當(dāng)前電梯在3樓，方向?yàn)橄蛏希藭r(shí)有3

個(gè)人請(qǐng)求使用電梯：7樓去16樓、2樓去9樓、6樓去1樓，則電梯先向上運(yùn)行，依次在7樓和16樓

?？浚蝗缓笤傧蛳逻\(yùn)行，依次在6樓和1樓停靠，最后再向上運(yùn)行，依次在2樓和9樓?？俊Ｐ∶骶帉?/p>

Python程序?qū)崿F(xiàn)這個(gè)調(diào)度算法，運(yùn)行界面如圖所示，請(qǐng)回答下列問題。

(1)Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。

defscan(now,d):#scan函數(shù)的功能：從當(dāng)前樓層開始,按當(dāng)前運(yùn)行方向掃描一趟

i二0

whilei<=len(ask)1:

ifask[i][2]==dand①:

stop[ask[i][0]]=1

stop[ask[i][1]]=1

ask.pop(i)#刪除索引為i的列表元素

當(dāng)前樓層：3方向：向上

else:

上

靠

樓層716

i=i+1

下

樓層

靠61

上

樓層

ask=[[7,16,0],[2,9,0],[6,1,0]]靠29

direct={1:〃向上”,1：〃向下〃}

now=3:d=1

print(〃當(dāng)前樓層:",now,"方向:",direct[d])

foriinrange(len(ask)):

t=②

t=t//abs(t)

ask[i][2]=t#t表示該請(qǐng)求的電梯運(yùn)行方向

whilelen(ask)>0:

stop=[0]*21#標(biāo)記120各樓層是否停靠

scan(now,d)

print(〃\n〃，direct[d],停靠樓層：〃，end=〃〃)

ifd==1:

st=1;ed=21

nownext=20

else:

st=20;ed=0

now_next=1

foriinrange(st,ed,d):

ifstop[i]==1:

print(i,end二〃〃)

now=now_next

(2)若電梯當(dāng)前在3樓，方向?yàn)橄蛏希?/p>

ask=[[7,16,0],[6,1,0],[2,9,0],[17,1,0],[10,15,0]],

則第一趟向上運(yùn)行依次?？康臉菍邮牵?按停靠順序填寫數(shù)字)。

12.某校工會(huì)組織包粽子比賽，為體現(xiàn)團(tuán)隊(duì)協(xié)作，每個(gè)工會(huì)小組派5名選手參加，以接力賽形式完成15個(gè)

粽子的制作，要求每名選手至少包1個(gè)，最多包5個(gè)，且只能上場(chǎng)一次。現(xiàn)在高二年級(jí)組5名選手的包粽

子成績(jī)保存在文檔data,txt中，如第18題圖a所示：

您data.txt-記事本

文件(F)編輯(E)格式(可直看(V)都助(H)

066140240342448-

160121192274360

4OU1^1QUOccc

356116178276396萬某總時(shí)耗：988

|462126200280370|第12題圖aI各選手需包粽子數(shù)目：23334I第12題圖b

文檔數(shù)據(jù)共5行，6歹U,每行數(shù)據(jù)分別是某選手編號(hào)、該選手累計(jì)包1到5個(gè)粽子的耗時(shí)(由于勞累因素

等影響，連續(xù)包的粽子越多，速度越慢或不變，絕不會(huì)變快)。請(qǐng)利用python編程設(shè)計(jì)方案，分配每位選

手需要包的粽子個(gè)數(shù)，使小組接力用時(shí)最短(接力時(shí)換人時(shí)間忽略不計(jì))。運(yùn)行界面如第18題圖b所示:

f=openC(1)"r")#數(shù)據(jù)文件與程序文件在同一目錄

a=[]

c=[l]*5#每位選手至少包1個(gè)粽子

forlineinf.readlines():

t=line.split()#將以空格分隔的數(shù)字字串存儲(chǔ)在列表t

score=list(map(int,t))#將列表各元素轉(zhuǎn)換成整數(shù)存儲(chǔ)在列表score中

a.append(score)

pos=l

ans=0

b=[[0],[0],[0],[0],[0]]胱[i][j]表示第i位選手包第j個(gè)粽子所需的時(shí)間

foriinrange(0,5):

b[i].append(a[i][1])

forjinrange(2,6):

b[i].append(^2))

foriinrange(10):#每位選手至少包1個(gè)粽子，另10個(gè)粽子需分配

minx=1000000

forjinrange(5):

ifb[j][c[j]+l]<minxandc[j]+l<-5:

pos=j

⑶

c[pos]+=l

foriinrange(5):

ans+=_______(4)________

print(〃方案總時(shí)耗：”,ans)

print(〃各選手需包粽子數(shù)目：〃,c[0],c[1],c[2],c[3],c[4])

13.一個(gè)整數(shù)序列，如果兩個(gè)相鄰元素的差恰好正負(fù)(負(fù)正)交替出現(xiàn)，則稱為該序列為搖擺序列。小王同

學(xué)想求出某個(gè)數(shù)列的最長(zhǎng)搖擺子序列。以序列[3,14,7,6,9,12,10,8,13,5]為例,整體不是搖擺序列，但子

序列[3,14,7,9]、[3,14,6,12]等都屬于搖擺子序列，其中最長(zhǎng)的搖擺子序列是[3,14,6,12,8,13,5]。根據(jù)

第16題圖a分析得知，當(dāng)序列有一段連續(xù)的遞增(或遞減)時(shí)，可形成搖擺子序列，我們只需要找到每一

次轉(zhuǎn)折中的拐點(diǎn)元素。小王編寫了一個(gè)Python程序?qū)崿F(xiàn)該功能：程序運(yùn)行時(shí)，輸入一串用逗號(hào)分隔和結(jié)束

的數(shù)字，可以得到最長(zhǎng)搖擺序列的長(zhǎng)度，以及具體的序列。程序運(yùn)行界面如下圖所示：

(1)若輸入數(shù)據(jù)“2,4,5,3,2,1”，則最長(zhǎng)搖擺子序列為—

(2)實(shí)現(xiàn)上述功能的Python代碼如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。

deff(n):

f=1

globalansftglobal表示此處的ans就是全局變量ans

ans=str(a[n1])

請(qǐng)輸入以逗號(hào)分隔和結(jié)束的數(shù)據(jù)(木超過加個(gè)數(shù))；3,14,7,6,9,12,10,8,13,

foriinrange(n2,1,1):最長(zhǎng)搖擺子序列長(zhǎng)度為6

最長(zhǎng)搖擺子序列為?3,14,6,12,8,13

ifb[i]:

f=f+1

①

returnf

s二input(〃請(qǐng)輸入以逗號(hào)分隔和結(jié)束的數(shù)據(jù)(不超過20個(gè)數(shù))：〃)

a=[0]*20;b=[False]*20;flag,n,i,t,ans=0,0,0,

forchins:

?ci〃〃

ifch==,:

a[i]=int(t);n+=1;i+=1;t=

else:

t二t+ch

foriinrange(1,n):

gd=True

ifflag==0:

ifa[i]>a[i1]:

flag=1

elifa[i]<a[i1]:

flag=2

else:

gd=False

elifflag=1anda[i]<a[i1]:

flag=2

elif②:

flag=1

else:

gd=False

iff(n)<3:

print(〃不構(gòu)成搖擺子序列”)

else:

print("最長(zhǎng)搖擺子序列長(zhǎng)度為"，str(f(n)))

print("最長(zhǎng)搖擺子序列為："，ans)

參考答案

1.B2.C3.A4.C5.D

6.(1)b[i]=i+1(2)k=b[k](3)b[7]=b[k](4)b[q]=b[k](5)k=b[k]

7.(1)①1(2分)②head=i(2分)③points[p]=i(2分)@p=points[p](2分)

根據(jù)程序可知，先讀取文件csv中的數(shù)據(jù)存入列表a中，Points為一維列表，存儲(chǔ)指針。head的初值為1,

表示鏈表初始狀態(tài)的頭指針。列表a為二維列表，其中a[0]為標(biāo)題項(xiàng)，因此從第1項(xiàng)開始遍歷，當(dāng)

float(a[i][5])>0成立，說明盈虧為正，此時(shí)將head更新為i,即第一個(gè)為盈虧為正的索引即為頭指針,

②處答案為head=i。將p的值賦值為i,即p為前驅(qū)節(jié)點(diǎn)。指向下一