2023年大連東軟數(shù)據(jù)結(jié)構(gòu)題庫(kù)

1.6習(xí)題１.６.1知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義一、選擇題1①數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的互相聯(lián)系。Ａ．存儲(chǔ)和邏輯結(jié)構(gòu)B．存儲(chǔ)結(jié)構(gòu)C.順序結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)２①數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表達(dá)時(shí)，物理地址與邏輯地址相同并且是連續(xù)的,稱(chēng)之為（C）A．存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)Ｃ．順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3①線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種(D）。A.一對(duì)多關(guān)系B.多對(duì)多關(guān)系C多對(duì)一關(guān)系Ｄ一對(duì)一關(guān)系4①計(jì)算機(jī)內(nèi)部數(shù)據(jù)解決的基本單位是(B）。Ａ.數(shù)據(jù)B.數(shù)據(jù)元素Ｃ.數(shù)據(jù)項(xiàng)Ｄ.數(shù)據(jù)庫(kù)5②從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類(lèi)?！疚錆h交通科技1996】A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)Ｃ.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)二、填空題1①數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為四大類(lèi)，它們分別是集合、線性、樹(shù)、圖。2①數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表達(dá)，它們分別是順序、鏈?zhǔn)?、散列、索引。判斷題（F）1①數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（T)2①記錄是數(shù)據(jù)解決的最小單位。（F)３①數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（T)４①數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。簡(jiǎn)答題１①簡(jiǎn)述什么是數(shù)據(jù)結(jié)構(gòu)?2②數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類(lèi)型有什么區(qū)別?【哈爾濱工業(yè)２023】１．6.2知識(shí)點(diǎn)：算法的概念一、選擇題1①計(jì)算機(jī)算法指的是（Ｃ)A．計(jì)算方法 ?B.排序方法 ?C.解決問(wèn)題的有限運(yùn)算序列 D．調(diào)度方法2①算法分析的目的是((１)C）,算法分析的兩個(gè)重要方面（（2)A)．A.找出數(shù)據(jù)結(jié)構(gòu)的合理性??B．研究算法中的輸入與輸出的關(guān)系C.分析算法的效率以求改善 Ｄ.分析算法的易查性和文檔性A.空間復(fù)雜度和時(shí)間復(fù)雜度?B.對(duì)的性和簡(jiǎn)明性Ｃ．可讀性和文檔性???D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3②設(shè)語(yǔ)句Ｘ+＋的時(shí)間是單位時(shí)間,則語(yǔ)句：for（ｉ=1;i＜＝n；i++）ｘ＋+；時(shí)間復(fù)雜度為（C）。Ａ．Ｏ(1）Ｂ．Ｏ(n）C.O（n2）D．O(n3）4②算法的計(jì)算量的大小稱(chēng)為計(jì)算的(Ｂ)?！颈本┼]電２0２3】A.效率Ｂ.復(fù)雜性Ｃ．現(xiàn)實(shí)性D．難度5②算法的時(shí)間復(fù)雜度取決于（C）【中科院計(jì)算所1998】A．問(wèn)題的規(guī)模B．待解決數(shù)據(jù)的初態(tài)C．A和B6②下面關(guān)于算法說(shuō)法錯(cuò)誤的是(A)【南京理工202３】A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)Ｂ．為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的C．算法的可行性是指指令不能有二義性D．以上幾個(gè)都是錯(cuò)誤的７②下面說(shuō)法錯(cuò)誤的是（D）【南京理工２02３】算法原地工作的含義是指不需要任何額外的輔助空間在相同的規(guī)模n下,復(fù)雜度Ｏ(n）的算法在時(shí)間上總是優(yōu)于復(fù)雜度Ｏ(２n)的算法所謂時(shí)間復(fù)雜度是指最壞情況下,估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高,執(zhí)行效率就越低A．(1）B.(1）,(2)C．(1）,（4)D.(3)8②程序段fｏr(ｉ＝n-1;i>=１;i+＋）for（j=1;j<=i;j++）ｉｆ(A[j]>A[j＋１]）A[ｊ]與A[j+1］對(duì)換；其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（D）【南京理工1９９8】A.O（n）B.O(ｎloｇ2n）C.Ｏ（n３)D.O（n2)二、填空題1①以?shī)A雜自然語(yǔ)言和程序語(yǔ)句的形式來(lái)描述解決問(wèn)題的方法稱(chēng)為_(kāi)_＿_(dá)偽碼______＿_(dá)。２①一個(gè)算法的效率可分為_(kāi)__時(shí)間___＿＿_(dá)效率和＿_(dá)空間___＿＿＿_(dá)效率．3②有一個(gè)程序片斷如下:for(i=0;i<ｎ;ｉ++）x＝x+1；則其時(shí)間復(fù)雜度為：＿O（n）________4②有一個(gè)程序片斷如下:fｏr（ｉ=０;ｉ<n；ｉ＋+）for ?(j＝i;ｊ<n;ｊ++）fｏr（k=j;k＜n;ｋ++)m=１;則其時(shí)間復(fù)雜度為:O（ｎ3)5②有一個(gè)程序片斷如下:for(ｉ=０;i<n;i++）{j＝ｉ；whｉｌe(ｊ>=2)ｊ=ｊ／2；}則其時(shí)間復(fù)雜度為:O（nｌog２ｎ）判斷題(Ｔ)1①算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。(T)2①健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(F）3①程序一定是算法。簡(jiǎn)答題1①如何判斷一個(gè)算法的好壞？2③調(diào)用下列C函數(shù)f(ｎ）回答下列問(wèn)題:（1)試指出ｆ（n）值的大小,并寫(xiě)出f(n)值的推導(dǎo)過(guò)程；（2)假定n=5，試指出f（５)值的大小和執(zhí)行f（5）時(shí)的輸出結(jié)果。C函數(shù):intf（intｎ)｛inti,ｊ,ｋ,sｕm=０;foｒ(i=l;i<ｎ+1;i++）{for(j=n;j>ｉ-1；j--)ｆｏr（ｋ=１;ｋ<ｊ+1;k++）suｍ++；prｉntｆ（"sｕm=%d\n"，sｕm）;｝return（ｓum）;｝【華中理工2023】2.７習(xí)題２.７．1知識(shí)點(diǎn)：線性表的邏輯結(jié)構(gòu)一、選擇題1①線性表Ｌ=（a1,a２,…,an),下列說(shuō)法對(duì)的的是(D)。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。B．線性表中至少要有一個(gè)元素。C.表中諸元素的排列順序必須是由小到大或由大到小。Ｄ．除第一個(gè)和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。2①在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是(D)。A.插入B．刪除 ?Ｃ.排序D．定位３①線性表是具有n個(gè)（C）的有限序列（ｎ>0）?！厩迦A1998】A．表元素Ｂ.字符C.數(shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)E．信息項(xiàng)二、判斷題（T)1①線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。(F)2①線性表中的每個(gè)結(jié)點(diǎn)都至少有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（F）3①線性表是N個(gè)數(shù)的有限序列。（Ｆ)４①同一線性表的數(shù)據(jù)元素可以具有不同的特性。（Ｔ）5①線性表的長(zhǎng)度n就是表中數(shù)據(jù)元素的個(gè)數(shù),當(dāng)n=０時(shí)，稱(chēng)為空表。(T）6①線性表是一個(gè)相稱(chēng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。（F）7①對(duì)線性表中的數(shù)據(jù)元素只能進(jìn)行訪問(wèn)，不能進(jìn)行插入和刪除操作。2.7.2知識(shí)點(diǎn)：線性表的順序存儲(chǔ)結(jié)構(gòu)一、選擇題1①在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素(1<=i<＝n+1）之前插入一個(gè)新元素時(shí)需向后移動(dòng)（B）個(gè)元素． A．n-1?B．n-i+1?Ｃ.ｎ－i-１ Ｄ.ｉ2①若某線性表中最常用的操作是取第ｉ個(gè)元素和找第i個(gè)元素的前趨元素,則采用（D)存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表B.雙鏈表C．單向循環(huán)D．順序表3②一個(gè)數(shù)組第一個(gè)元素的存儲(chǔ)地址是10０,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是（B）A.11０B.108C．１00D.1204①下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)(A)?！颈狈浇煌ǎ?23】A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表達(dá)5③若長(zhǎng)度為ｎ的線性表采用順序存儲(chǔ)結(jié)構(gòu),在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（C） ?（1<=i＜=n+1）。【北京航空航天19９9】A.Ｏ（0）B.O（１）Ｃ.O（n)D.Ｏ(n２）6③對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增長(zhǎng)、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為(C）?！厩鄭u202３】A.O（n)O(n）B.O(n）O(１）Ｃ.O（1)Ｏ(ｎ）D．O（1)O（１)填空題1①線性表的順序存儲(chǔ)的缺陷是在任意位置上＿＿_(dá)插入＿_(dá)_＿_(dá)數(shù)據(jù)與_＿＿_(dá)刪除_____數(shù)據(jù)費(fèi)時(shí)間。2①設(shè)一線性表的順序存儲(chǔ)，總存儲(chǔ)容量為Ｍ，其元素存儲(chǔ)位置的范圍為_(kāi)_0～M-1_＿_(dá)_______。３①向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（1≤i≤n)時(shí),需向前移動(dòng)＿_(dá)__n-i＿_(dá)____個(gè)元素。簡(jiǎn)答題１③已知線性表的存儲(chǔ)結(jié)構(gòu)為順序表,閱讀下列算法，并回答問(wèn)題：voｉdf30(SeqＬｉst*L）{ｉｎti，j;ｆｏr(i=ｊ=０;i＜L->leｎgth;i++）iｆ(L->ｄatａ[ｉ］＞=0）{ｉf(i!=ｊ）L-＞datａ[j]＝Ｌ->datａ［i];j＋＋;}Ｌ－＞length＝ｊ;｝設(shè)線性表L=(21,-７，-８，19，0,-1１,３4，3０,-10)，寫(xiě)出執(zhí)行ｆ30(&Ｌ）后Ｌ狀態(tài);(2１，1９,0,34,３0)簡(jiǎn)述算法ｆ3０的功能。刪除順序表中小于0的元素四、編程題１④已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫(xiě)一個(gè)算法，將ｘ插入到La的合適位置上，保持該表的有序性。2.7．3知識(shí)點(diǎn)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一、選擇題１①鏈表是一種采用(B）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。A.順序B．鏈?zhǔn)紺.星式D.網(wǎng)狀2①鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間(A）。A.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表達(dá)結(jié)點(diǎn)間關(guān)系的指針。B.只有一部分,存放結(jié)點(diǎn)值。Ｃ.只有一部分，存儲(chǔ)表達(dá)結(jié)點(diǎn)間關(guān)系的指針。Ｄ．分兩部分,一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)。3①線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),規(guī)定內(nèi)存中可用存儲(chǔ)單元的地址（D）。Ａ．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以4①線性表L在(B)情況下合用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。Ａ.需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值B．需不斷對(duì)L進(jìn)行刪除插入C．Ｌ中具有大量的結(jié)點(diǎn)D.L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜5①對(duì)單鏈表表達(dá)法,以下說(shuō)法錯(cuò)誤的是(Ｃ)。A．?dāng)?shù)據(jù)域用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素。Ｂ．指針域(或鏈域)用于存放一個(gè)指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在結(jié)點(diǎn)的指針。C.所有數(shù)據(jù)通過(guò)指針的鏈接而組織成單鏈表。D.NULL稱(chēng)為空指針，它不指向任何結(jié)點(diǎn)只起標(biāo)志作用。６①以下說(shuō)法對(duì)的的是（Ｄ）。A．順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大且插入、刪除運(yùn)算效率高Ｂ.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針C.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D．順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)而鏈?zhǔn)浇Y(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)7①以下說(shuō)法錯(cuò)誤的是(Ｄ)。A.求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低Ｂ.順序存儲(chǔ)的線性表可以隨機(jī)存?。?由于順序存儲(chǔ)規(guī)定連續(xù)的存儲(chǔ)區(qū)域,所以在存儲(chǔ)管理上不夠靈活D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)8①不帶頭結(jié)點(diǎn)的單鏈表ｈeaｄ為空的鑒定條件是(A）。A．head＝＝ＮULＬB.head-＞ｎext==ＮＵLLC.hｅaｄ－>ｎext==heａdD．heaｄ!=ＮUＬL9①帶頭結(jié)點(diǎn)的單鏈表ｈeaｄ為空的鑒定條件是(Ｂ)。Ａ．head==NUＬLＢ．head-＞next==NULLC．head-＞nｅxt=＝hｅadD.hｅad!=NULＬ10②在頭指針為head的非空單循環(huán)鏈表中，指針p指向尾結(jié)點(diǎn),下列關(guān)系成立的是(Ａ)。Ａ.ｐ-＞ｎeｘt==hｅaｄB．p->ｎｅxt-＞next＝=headC.p－>nｅxｔ==ＮＵLＬＤ.p=＝head11②在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在ｑ和p之間插入s結(jié)點(diǎn),則執(zhí)行語(yǔ)句(C)。A.s-＞ｎext=p-＞nｅxt;p->ｎext=ｓ;Ｂ．p->next=ｓ-＞next;s->nｅxt=ｐ；C.q->neｘt=ｓ;s->nｅxt=ｐ;D.p->next=s；s－>neｘｔ=q；12②在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn),在p之后插入ｓ結(jié)點(diǎn)，則應(yīng)執(zhí)行語(yǔ)句(B）。A.ｓ－>next＝p:p-＞ｎｅxt=ｓ;B．s->ｎext=p->neｘt;ｐ－＞nｅxt=s;C．s－>ｎext=p-＞ｎｅｘt;ｐ=s;D．p->next=ｓ;s->next=p；13②在一個(gè)單鏈表中,若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則應(yīng)執(zhí)行語(yǔ)句(A)。A．p-＞ｎext=p-＞neｘt->nｅxt;B．p=p->neｘt;p->next＝ｐ－>ｎeｘt->nexｔ;C.p->next＝p-＞neｘt;D．p=ｐ->nexｔ-＞next；14②指針ｐ、ｑ和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，互換結(jié)點(diǎn)*q和結(jié)點(diǎn)*r在表中順序的程序段是（Ａ）。A.p－>ｎｅxt=ｒ;ｑ->next=r-＞next；r－>neｘt=ｑ;Ｂ.p->ｎext=r；r-＞ｎext＝q；q->next=r->nｅｘｔ;C.r->ｎｅxt＝ｑ；q->ｎext=r->nｅｘt；p-＞ｎｅxt=ｒ;Ｄ.r-＞nｅxt=q；p->next＝r;q->next＝r-＞nｅxt；15①鏈表不具有的特點(diǎn)是(B）【福州1998】Ａ.插入、刪除不需要移動(dòng)元素Ｂ．可隨機(jī)訪問(wèn)任一元素C.不必事先估計(jì)存儲(chǔ)空間? D．所需空間與線性長(zhǎng)度成正比16①下面的敘述不對(duì)的的是(BC)【南京理工１9９6】A．線性表在鏈?zhǔn)酱鎯?chǔ)時(shí),查找第ｉ個(gè)元素的時(shí)間同i的值成正比B.線性表在鏈?zhǔn)酱鎯?chǔ)時(shí),查找第ｉ個(gè)元素的時(shí)間同i的值無(wú)關(guān)C.線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同ｉ的值成正比D．線性表在順序存儲(chǔ)時(shí)，查找第ｉ個(gè)元素的時(shí)間同i的值無(wú)關(guān)17①下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B)【北方交通2023】Ａ.線性表采用順序存儲(chǔ),必須占用一片連續(xù)的存儲(chǔ)單元。B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ),不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。１8①在一個(gè)以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是（A)【南京理工19９8】Ａ.p->ｎｅxt=hB.ｐ->ｎeｘt＝NUＬLC．p－>ｎext-＞next＝hD．ｐ->ｄata=-１19②若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算,則運(yùn)用（A）存儲(chǔ)方式最節(jié)省時(shí)間?！竟枮I工業(yè)2023】Ａ．順序表B．雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D．單循環(huán)鏈表2０②某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素,則采用（Ｄ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！灸祥_(kāi)2０23】A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表2１②設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用(Ｄ）最節(jié)省時(shí)間?！竞戏使I(yè)２0２３】A.單鏈表B.單循環(huán)鏈表Ｃ．帶尾指針的單循環(huán)鏈表Ｄ．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表22②線性表(a1,a2,…,an)以鏈接方式存儲(chǔ)時(shí),訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（C）【中山1９99】A．O(i）B.O（1)C．O（ｎ)Ｄ．Ｏ(ｉ－1)23③完畢在雙循環(huán)鏈表結(jié)點(diǎn)ｐ之后插入ｓ的操作是(Ｄ)?！颈狈浇煌ǎ保?9】A．p－>neｘt:=s;s->priou:=p;p->ｎｅｘｔ-＞priｏu：＝ｓ；ｓ-＞neｘt:=p->nｅxt;B.p-＞neｘt->priou:＝s;p->next:=s；s->ｐｒiou:=ｐ;s－>ｎeｘｔ:=p->nｅｘt;Ｃ.s->ｐｒｉou:=p;s->nｅxt：=p->neｘt；p->next:=ｓ;p->nexｔ->priｏu:=s;D.s->pｒiｏｕ:=p;s->nｅxｔ:=p-＞next;p－＞ｎext-＞priou:=s;p->next:=s;24③在雙向循環(huán)鏈表中，在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是(C)?！颈本┼]電１998】【青島202３】注：雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llｉnk,data,rlink）。供選擇的答案：Ａ.p-＞lｌｉnk=q；ｑ->ｒlink=p；ｐ->llink－>rlｉｎｋ=q；q->llｉnｋ=q；B．p->llinｋ=q;p－>llink－＞rｌink=q;q－>rlｉnk=p；q-＞llink=ｐ-＞ｌlｉnk；C．q-＞ｒlink=p;q-＞ｌlink＝p->ｌlink;ｐ->lｌink－>rlｉnk=q;p->lｌｉnk=ｑ;D.q-＞ｌlink=ｐ->llｉｎｋ;ｑ-＞ｒlｉnk:=p;p-＞lｌiｎｋ＝q；p->llｉｎk＝ｑ；25③在雙向鏈表存儲(chǔ)結(jié)構(gòu)中,刪除ｐ所指的結(jié)點(diǎn)時(shí)需修改指針(A）?！疚靼搽娮涌萍迹保?8】A.p－＞ｐrｉor->nｅxt＝p－>neｘtp->next->prior=p->priｏr;B．p->prioｒ=p->prｉｏr->pｒiorp->priｏr->next=p;C．p->prior-＞priｏｒ:=ｐp->neｘt=p－＞next－＞nｅｘtＤ．p－＞next=（p->priｏr)->priｏrp->priｏr＝p-＞next－>next二、填空題１①線性表的鏈?zhǔn)酱鎯?chǔ)是用___malloc___＿_(dá)_語(yǔ)句實(shí)現(xiàn)空間單元?jiǎng)討B(tài)分派。２①單鏈表是___線性表＿＿_(dá)＿＿的鏈接存儲(chǔ)表達(dá)。３①頭結(jié)點(diǎn)地址指針為L(zhǎng)的循環(huán)單鏈表，空表的判別標(biāo)志是___L-＞nｅxt==NUＬL_＿_(dá)。4①在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行以下操作:ｑ=p->next；ｐ->ｄata=p->nexｔ->datａ；p－>next=q->ｎｅxｔ＿_(dá)＿_(dá)＿_(dá)_＿_(dá);free(q）;５③下段程序的功能:有一頭指針為ｈead的鏈表，將ｎｅｗ指針指向的節(jié)點(diǎn)插入到data域?yàn)?的節(jié)點(diǎn)的后邊。將程序補(bǔ)充完整。P=heaｄ;while（Ｐ!=ＮUＬL)｛if(P->ｄaｔa==7）/＊找到位置插入結(jié)點(diǎn)后跳出循環(huán)*／{(1）_nｅw－>next＝p->ｎext__＿_(dá)____＿＿_(dá)____；（2）_p->next=ｎｅw____＿_(dá)_＿＿＿_(dá)____;(3）__＿_(dá)__ｂreａｋ＿_(dá)＿＿_(dá)_＿_(dá)＿_(dá);}elsｅ（4)__＿p=ｐ->ｎｅxt____＿_(dá)＿_(dá)___＿_(dá)_;／＊指針后移*/}if（P＝=NＵLL）ｐrｉｎtf(“\nthｅｐositionｉsn’teｘist!”)；6③假設(shè)某個(gè)不設(shè)頭指針的無(wú)頭結(jié)點(diǎn)單向循環(huán)鏈表的長(zhǎng)度大于1,ｓ為指向鏈表中某個(gè)結(jié)點(diǎn)的指針。算法f30的功能是，刪除并返回鏈表中指針s所指結(jié)點(diǎn)的前驅(qū)。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。typedefｓtrｕcｔｎode｛Ｄａt(yī)ａＴyｐeｄata;sｔｒｕctｎode*ｎeｘｔ;｝*ＬinkLisｔ;DataTypeｆ30（LinkLiｓｔｓ)｛ＬinｋListｐrｅ,p;ＤaｔaTyｐeｅ；pｒｅ=s；p=ｓ－＞next;whilｅ（(1）__p->ｎｅxｔ!=s＿_(dá)＿_(dá)){prｅ＝p;（２）p=p->neｘt___＿_(dá)_＿＿_(dá)＿_(dá)_;}pre－>ｎext＝（3)__p－＞ｎext＿＿_(dá)______＿_(dá)_；e=p->dａt(yī)a;fｒee(ｐ);retｕrｎｅ;}判斷題(F）1①單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問(wèn)到所有結(jié)點(diǎn)。（F）2①線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)樸類(lèi)型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。簡(jiǎn)答題1①描述以下幾個(gè)概念:順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、順序表、有序表。２②描述以下三個(gè)概念的區(qū)別:頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)。在單鏈表中設(shè)立頭結(jié)點(diǎn)的作用是什么?3②線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表,試問(wèn)：（1)假如有ｎ個(gè)線性表同時(shí)共存,并且在解決過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)地發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)地?改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？鏈表(２)若線性表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除，但規(guī)定以最快的速度存取線性表中的元素,那么應(yīng)采 用哪種存取結(jié)構(gòu)?為什么?順序表4③假設(shè)本測(cè)試中使用的鏈表如圖2.４5所示，結(jié)點(diǎn)定義如下:struｃtＬｉst{iｎtdａｔa;ｓｔructＬist＊next；}；typedｅfsｔruｃtLiｓtＮｏde;ｔｙpedefＮode*Ｌiｎk;LiｎkＰ,Q,R,S，head;Lｉnkｐoｉｎter，bａck,new;對(duì)以下單鏈表分別執(zhí)行下列程序段，規(guī)定分別畫(huà)出結(jié)果圖。(1）Q=ｈead->next->next；Ｑ指向7(2）R->ｄata＝P－>daｔa;3變5（3)Ｒ->ｄaｔａ=Ｐ－>nexｔ->dａｔａ;３變７S=P;while(S->next!＝ＮULＬ){S-＞data=S-＞daｔａ*2；S=S->nｅxt;}4101４６8Ｓ=P；wｈｉle（S!=NUＬL）{Ｓ-＞data=S->daｔa＊2;S=S－>ｎexｔ;｝410146165③假設(shè)本測(cè)試中使用的鏈表如圖2.45所示，結(jié)點(diǎn)定義如第4題所示。畫(huà)出執(zhí)行如下程序段后各指針及鏈表的示意圖。ｈｅaｄ＝（Lｉnk)malloc(ｓizeof(Node)）;ｈｅad－>data=0;heａd->neｘt＝NULＬ;P=ｈeaｄ;fｏr(ｉ=1;i<4;i+＋){new=(Linｋ)malloc(sizeof（Ｎode)）;neｗ->data=2*ｉ;ｎeｗ->ｎext=NULＬ;Ｐ－>neｘt=nｅw;P=new;｝創(chuàng)建了一個(gè)鏈表，數(shù)據(jù)元素為0,2,4，6,并且p和nｅｗ都指向尾結(jié)點(diǎn)6③有一鏈表如下圖所示,閱讀程序給出程序的輸出結(jié)果。圖２.４６6題圖P＝hｅａd;ｗｈilｅ(P!=NULL){printf(“\ｎdatａ=%d”,P->data）；P=Ｐ－＞neｘt;if(Ｐ!=NULL) ??Ｐ=P->ｎeｘt;}Data＝1Ｄatａ=3Data=5五、編程題1④一個(gè)單鏈表，其頭指針為head,編寫(xiě)一個(gè)函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的節(jié)點(diǎn)個(gè)數(shù)。2④已知單鏈表Lａ中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫(xiě)出算法,將元素ｘ插入到La的合?適位置上,保持該表的有序性：(1)La帶頭結(jié)點(diǎn)；（2）Ｌa不帶頭結(jié)點(diǎn)。3④試寫(xiě)一個(gè)算法,實(shí)現(xiàn)順序表的就地逆置,即在原表的存儲(chǔ)空間將線性表（a1,ａ２，…,ａn?１，an)逆置為（aｎ，ａ?ｎ?1，…,a2,ａ1)。4④設(shè)計(jì)一個(gè)算法，求Ａ和Ｂ兩個(gè)單鏈表表達(dá)的集合的交集、并集合差集。3.7習(xí)題３．７.1知識(shí)點(diǎn)：棧的基本概念一、選擇題1①下列哪種數(shù)據(jù)結(jié)構(gòu)常用于函數(shù)調(diào)用（A)。 A.棧Ｂ．隊(duì)列Ｃ．鏈表D．?dāng)?shù)組2①編譯器中通常以哪種數(shù)據(jù)結(jié)構(gòu)解決遞歸程序調(diào)用（C）?? A．隊(duì)列?Ｂ．?dāng)?shù)組 Ｃ．棧D．記錄3①下列哪些數(shù)據(jù)結(jié)構(gòu)可用來(lái)實(shí)現(xiàn)棧（D)。(1)鏈表(２）數(shù)組（３）樹(shù)(4）圖?Ａ.(2），（3) Ｂ.（2)，（4）C.(1)，(4)?D.（1),(2)4②元素的入棧序列是a，b,c,d,則棧的不也許的輸出序列是（C）。A.ｄｃbaB．a(chǎn)ｂcdC．ｄｃabD.ｃｂａd5②已知棧的最大容量為４。若進(jìn)棧序列為1，2，３,４，5,6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則也許出現(xiàn)的出棧序列為（Ｃ）。A.５,4，３,2,1,6B.２,3，5，6,1,4Ｃ．３，2,5，4，1，6D．1,4，6，5,２,36②若以S和X分別表達(dá)進(jìn)棧和退棧操作,則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（D）。Ａ.SXSSＸXＸXB．SＸＸＳX(jué)SSＸC.SXSＸXSSXD.SSSXXSXＸ７①對(duì)于棧操作數(shù)據(jù)的原則是（B)?！厩鄭u2023】A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序8①棧在（Ｄ）中應(yīng)用?！局猩?998】Ａ．遞歸調(diào)用B．子程序調(diào)用Ｃ．表達(dá)式求值D．A,B,Ｃ9②一個(gè)棧的輸入序列為1２3…n，若輸出序列的第一個(gè)元素是n,輸出第ｉ（1＜=i<=n)個(gè)元素是(B)?！局猩?999】Ａ.不擬定B．n-i+1Ｃ.ｉD．n-ｉ１０②若一個(gè)棧的輸入序列為1,２,3,…，n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是(Ｄ)?！疚錆h２０23】Ａ．i－ｊ-1B．i－jC.ｊ－i＋1D．不擬定的１1②有六個(gè)元素６,５,4,3，２,１的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（C)【北方交通20２3】A．54361２Ｂ．４53162C.3４6５21D．234１５61２②輸入序列為ABC,可以變?yōu)椋肂A時(shí)，通過(guò)的棧操作為(B）【中山1999】Ａ.pｕsｈ,pop,puｓｈ，pｏp,pusｈ,popB．pusｈ,ｐuｓh，puｓh,pop,poｐ，ｐoｐＣ．pusｈ,push，ｐop，pop，push,poｐＤ.push，ｐｏp,ｐuｓh,push，pｏｐ,pop13②設(shè)計(jì)一個(gè)判別表達(dá)式中左,右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（D)數(shù)據(jù)結(jié)構(gòu)最佳?！疚靼搽娮涌萍?９96】A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧二、填空題1①棧是一種特殊的線性表,允許插入和刪除運(yùn)算的一端稱(chēng)為棧頂，不允許插入和刪除運(yùn)算的一端稱(chēng)為棧底。2①對(duì)于順序存儲(chǔ)的棧，由于棧的空間是有限的，在進(jìn)行入棧運(yùn)算時(shí),也許發(fā)生棧的上溢,在進(jìn)行出棧 運(yùn)算時(shí),也許發(fā)生棧的下溢。３①表達(dá)式求值是棧應(yīng)用的一個(gè)典型例子。４①棧是__一種特殊__＿_(dá)＿的線性表,其運(yùn)算遵循_＿_(dá)_先進(jìn)后出____＿＿_(dá)_____＿的原則。【北京科技1997】５②設(shè)有一個(gè)空棧,棧頂指針為１0０0H(十六進(jìn)制）,現(xiàn)有輸入序列為1,２,3,４,5，通過(guò)PUSH,PUＳH，POＰ,ＰUSH,PＯP,PUＳH,ＰUSH之后,輸出序列是2,3，__＿_(dá)___，而棧頂指針值是?＿100０Ｃ_____H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)?！疚靼搽娮涌萍?9９8】６②用S表達(dá)入棧操作，Ｘ表達(dá)出棧操作,若元素入棧的順序?yàn)?234,為了得到134２出棧順序，相應(yīng)的S和 X的操作串為_(kāi)__＿_(dá)____sxssxｓxx_＿_(dá)____＿_(dá)＿?！疚髂辖煌?02３】三、判斷題(Ｆ)1①棧具有先進(jìn)先出的特性。(T）2①棧用于實(shí)現(xiàn)子程序調(diào)用。（F）３①棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。(T）4①棧頂?shù)奈恢檬请S著操作而變化的。（T）5①棧和隊(duì)列邏輯上都是線性表。(T）６①棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。【合肥工業(yè)202３】(Ｆ）7②即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也 一定相同?！颈本┼]電１999】(T)8②若輸入序列為１,２,３,４，5，６,則通過(guò)一個(gè)?？梢暂敵鲂蛄校?，2,５,6,4,１?！旧虾：＿\(yùn)199５】(Ｆ)9②若輸入序列為1,2,3,4，5,６,則通過(guò)一個(gè)棧可以輸出序列１，5，4,6,2,3。【上海海運(yùn)１９99】四、簡(jiǎn)答題1①什么是棧？試舉兩個(gè)應(yīng)用實(shí)例。２①簡(jiǎn)述棧和線性表的差別。3③計(jì)算表達(dá)式6*3/2-5*１,規(guī)定繪出堆棧的解決過(guò)程。5②有5個(gè)元素，其入棧順序?yàn)椋篈，B，Ｃ,Ｄ,Ｅ，在各種也許的出棧順序中,以元素C,Ｄ最先出棧（即C第一個(gè)且D第二個(gè)出棧）的順序有哪幾個(gè)？【西南交通2023】3.7.２知識(shí)點(diǎn):棧的存儲(chǔ)一、選擇題１①假如以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則入棧操作時(shí)（B）。A.必須判別棧是否滿(mǎn)B.對(duì)棧不作任何判別C．必須判別棧是否空Ｄ．判別棧元素的類(lèi)型2①上溢現(xiàn)象通常出現(xiàn)在（A)。Ａ．順序棧的入棧操作過(guò)程中B．順序棧的出棧操作過(guò)程中C．鏈棧的入棧操作過(guò)程中Ｄ.鏈棧的出棧操作過(guò)程中3①鑒定一個(gè)棧ＳT（最多元素為m0）為空的條件是(B)Ａ.ST->top?。?B．ST－＞toｐ==０C．ＳT-＞tｏp!=ｍ0D．ＳT－>ｔop==m04①鏈表仿真堆棧時(shí),?？盏臈l件是(B)。??A.toｐ<maxｓize－１B．tｏｐ=＝ＮULLC．沒(méi)有限制D.tｏp＜05①鏈表仿真堆棧時(shí),棧滿(mǎn)的條件是(C)。 A.top<maxｓizｅ-1B．top==NUＬLＣ．沒(méi)有限制D.top＜06②在用鏈表仿真堆棧時(shí)（假設(shè)sｔack為棧頂指針),將new指針指向的節(jié)點(diǎn)執(zhí)行入棧操作應(yīng)執(zhí)行(B)A．nｅw－>nexｔ＝ｓtack->neｘt;stack=ｎew；B.neｗ-＞neｘｔ=sｔaｃk；ｓｔaｃk=ｎｅw；Ｃ.ｎeｗ->next=ｓｔaｃｋ;ｓtaｃk＝new->nexｔ；Ｄ．stacｋ=new;sｔack-＞ｎｅｘt＝new->neｘｔ;7②若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針ｔoｐ為n+1,則下面x進(jìn)棧的對(duì)的操作是（Ｃ)?！灸暇├砉?99８】A.top=ｔop＋1;V[ｔop]=xＢ.V[ｔoｐ]＝x；tｏｐ＝top＋1C.ｔop＝ｔop-1;V[tｏｐ]＝ｘD.V[top]=x;toｐ＝tｏp－1８②執(zhí)行完下列語(yǔ)句段后,i值為：(B）。【浙江２０23】inｔf（ｉntx){return((x>０）？ｘ*f（x-１）:2);｝ｉｎti;i=f(f（1)）;Ａ.2B．4C．8D．無(wú)限遞歸填空題1②以下語(yǔ)句是堆棧的入棧操作,用全局?jǐn)?shù)組ｓtack仿真堆棧，數(shù)組類(lèi)型是inｔ,大小是MaxＳｉｚe，棧頂指針是ｔop,初始化等于－1。voidｐｕsh(ｉntvａlue）{ｉf(toｐ＞MaxSiｚe-1)ｒeｔurｎ–1;elｓe{ｔop++;ｓｔａck[tｏp］=vａlue;}｝指出有錯(cuò)誤的語(yǔ)句：＿_(dá)_3_____寫(xiě)出改正后的語(yǔ)句：＿_(dá)_＿_(dá)top＝=MaｘＳiｚe-1___＿_(dá)＿_(dá)2②以下語(yǔ)句是數(shù)據(jù)從堆棧中取出操作，top為棧頂指針，ｓtack為堆棧數(shù)組。01ｉntｐop(）０2{inttｅｍｐ;iｆ(toｐ==0)reｔurｎ–1；eｌse｛teｍp＝stack[toｐ］；toｐ――;}reｔuｒnteｍp; 1２}指出有錯(cuò)誤的語(yǔ)句:＿＿＿_(dá)__＿＿＿_(dá)___＿_(dá)＿＿＿＿_(dá)＿＿_(dá)寫(xiě)出改正后的語(yǔ)句:_＿_(dá)＿_(dá)__8,9互換_＿_(dá)_＿＿＿_(dá)＿_(dá)___＿＿_(dá)編程題1④假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含圓括號(hào)“（”和“)”，編寫(xiě)判別給定表達(dá)式中所含括號(hào)是否對(duì)的配對(duì)出現(xiàn)的算法。２④編寫(xiě)斐波那契（Fibonacci)數(shù)列的遞歸算法和迭代算法。F０=0, Ｆ1=1,?ＦFｎ＝?n1+?Ｆｎｎ２(>=2）3.7.3知識(shí)點(diǎn):隊(duì)列的基本概念及其應(yīng)用一、選擇題1①下列哪種數(shù)據(jù)結(jié)構(gòu)常用于系統(tǒng)程序的作業(yè)調(diào)度(Ｂ) A．棧 Ｂ.隊(duì)列C．鏈表Ｄ.數(shù)組2①在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)立一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū),而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印.該緩沖區(qū)應(yīng)當(dāng)是一個(gè)(B）結(jié)構(gòu).A．堆棧Ｂ．隊(duì)列C.數(shù)組Ｄ．線性表3②設(shè)棧S和隊(duì)列Ｑ的初始狀態(tài)為空，元素ｅ1、e2、e3、ｅ4、e5、e6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Ｑ，若6個(gè)元素出隊(duì)的序列是e2、e4、ｅ３、e6、ｅ5、e1，則棧Ｓ的容量至少應(yīng)當(dāng)是(C）A．６B.４C.３D．２４①棧和隊(duì)列的共同點(diǎn)是（C)。【燕山２02３一、１(2分）】A.都是先進(jìn)先出 ? B．都是先進(jìn)后出C．只允許在端點(diǎn)處插入和刪除元素? D．沒(méi)有共同點(diǎn)二、填空題1①棧和隊(duì)列都是線性結(jié)構(gòu),對(duì)于棧只能在____棧頂＿＿_(dá)＿＿_(dá)位置插入和刪除元素，對(duì)于隊(duì)列只能在___＿_(dá)_隊(duì)尾__＿＿＿＿_(dá)_位置插入元素和＿_(dá)＿_(dá)＿隊(duì)頭__＿_(dá)＿＿＿＿＿位置刪除元素。2②隊(duì)列的隊(duì)尾位置通常是隨著＿_(dá)___入隊(duì)____＿_(dá)＿＿_(dá)操作而變化的。3①隊(duì)列的特點(diǎn)是＿_(dá)_____先進(jìn)先出_____＿_(dá)_＿_(dá)___＿_(dá)__。【北京理工２0２3】4②循環(huán)隊(duì)列的引入，目的是為了克服_______＿假溢出_＿＿_(dá)___＿＿＿_(dá)_＿_(dá)＿_(dá)?！緩B門(mén)2023】三、判斷題（Ｔ)1①隊(duì)列中所有的插入操作都發(fā)生在表的一端,刪除則發(fā)生在表的另一端。（F）2①隊(duì)列為先進(jìn)后出的結(jié)構(gòu)。(F)3①隊(duì)列必須用數(shù)組來(lái)表達(dá)。（T）4①隊(duì)列用于操作系統(tǒng)中的作業(yè)調(diào)度。（T)5①棧和隊(duì)列邏輯上都是線性表。（T）6①棧和隊(duì)列是在程序中常用的兩種數(shù)據(jù)結(jié)構(gòu)。(T)7①棧與隊(duì)列是一種特殊操作的線性表?！厩鄭u２0２3】(Ｔ）8①棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)?！局锌圃很浖?999】（Ｆ)9①隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)?！旧虾：＿\(yùn)1９９8】(F）10①通常使用隊(duì)列來(lái)解決函數(shù)或過(guò)程的調(diào)用?！灸暇┖娇蘸教欤?97】（Ｆ)1１①隊(duì)列邏輯上是一個(gè)下端和上端既能增長(zhǎng)又能減少的線性表。【上海交通19９8】(T）12①棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制?！颈本┼]電2０23】四、簡(jiǎn)答題1①什么是隊(duì)列？試舉兩個(gè)應(yīng)用實(shí)例。2①說(shuō)明線性表、棧和隊(duì)列的異同點(diǎn)。3①順序隊(duì)的“假溢出”是如何產(chǎn)生的?什么是循環(huán)隊(duì)列?如何知道循環(huán)隊(duì)列是空還是滿(mǎn)？五、編程題１④假設(shè)稱(chēng)正讀和反讀都相同的字符序列為“回文”,例如‘ａbba’和‘a(chǎn)ｂcba’是回文，‘ａbｃde’和‘ａbaｂａｂ’則不是回文。試寫(xiě)一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。３．7.4知識(shí)點(diǎn)：隊(duì)列的存儲(chǔ)一、選擇題1①循環(huán)隊(duì)列用數(shù)組A[maxｓizｅ]表達(dá)，下面哪個(gè)選項(xiàng)表達(dá)該循環(huán)隊(duì)列隊(duì)滿(mǎn)（B)Ａ．ｒｅａr==maxsize-1B.front==(rｅaｒ+1)%maxsiｚeC．rｅar-fｒoｎt==maxsizeD.rｅaｒ-front==maxsize－12①在用數(shù)組ｑueue[maxsize]仿真隊(duì)列時(shí)(temp為int型變量)，假設(shè)隊(duì)列中至少有一個(gè)元素，出隊(duì)列操作應(yīng)執(zhí)行以下（Ｄ)A．tｅmｐ＝queｕe［reaｒ]；ｒear－－；Ｂ.reaｒ++；tｅmp=queue［rｅａr］;C．temp=queuｅ［front]；front-－;Ｄ.froｎｔ+＋;tｅｍp＝ｑueue［front];３①數(shù)組Ｑ[n]用來(lái)表達(dá)一個(gè)循環(huán)隊(duì)列,f為當(dāng)前隊(duì)列頭元素的前一位置,ｒ?yàn)殛?duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素的公式為(D)A．r－ｆ;Ｂ．(n+ｆ-r)％n；Ｃ.n+r-fＤ．（n＋r-ｆ）％n４②判斷一個(gè)隊(duì)列QU(最多元素為m0)為空的條件是（C）。?Ａ.ｒear－front==m０?Ｂ．rear-ｆront－1＝=ｍ０ Ｃ．front＝=rear??Ｄ．fｒｏｎt==ｒeａr+１５②一個(gè)隊(duì)列(數(shù)組仿真,最多元素為MａxSｉzｅ）下列哪個(gè)選項(xiàng)表達(dá)了隊(duì)列空間所有被運(yùn)用？(A）A．ｒear–fｒoｎｔ==MａxＳizeＢ.rear–froｎt==MaxＳiｚe–１Ｃ．reaｒ==fronｔＤ．reaｒ+１==fｒont6②鑒定一個(gè)循環(huán)隊(duì)列(數(shù)組仿真，最多元素為MaxSｉze)為空的條件是？(A)A.froｎｔ＝=rearB.fｒonｔ!=reａrC．frｏｎｔ==(ｒear＋1)％MaxSｉzｅD．front!=（rear＋１）%ＭａxSｉze7①用單鏈表表達(dá)的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（A）位置。【清華19９8】Ａ．鏈頭B.鏈尾C.鏈中Ｄ．任何8②用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（Ｄ)。【北京理工2０２3】A.僅修改隊(duì)頭指針Ｂ.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都也許要修改9②假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針?lè)謩e為front和reａr,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（A）?！颈本┕ど?０23】A.(rear－ｆronｔ+ｍ)%ｍB.rear-frｏnt＋１C.（ｆｒｏnt-rear+m)％ｍD.(rear－froｎt)％m１0②循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0.．m］中，則入隊(duì)時(shí)的操作為(D)?！局猩?999】A.rear=reａr+1B.rear=(reａr＋１)mod（m-1）C.ｒｅar=（rｅaｒ+1)moｄｍD.reａr=（ｒｅａr+1）moｄ(m+１)1１②若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前rｅaｒ和ｆｒont的值分別為０和３，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后,reaｒ和fronｔ的值分別為多少？（B）【浙江1９99】A．1和5Ｂ．2和4Ｃ．4和２Ｄ.5和112②用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(Ｂ）?！颈狈浇煌?023】A．僅修改頭指針B．僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針也許都要修改二、填空題1①棧、隊(duì)列的建立可使用兩種結(jié)構(gòu):＿_(dá)____順序__＿＿_(dá)_＿_(dá)結(jié)構(gòu)和___＿鏈?zhǔn)絖_＿_(dá)_＿結(jié)構(gòu)。２②假設(shè)為循環(huán)隊(duì)列分派的向量空間為Ｑ[2０］，若隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為1３和１７,則當(dāng)前尾指針的值為_(kāi)_10_____＿＿_(dá)____。3③以下語(yǔ)句是環(huán)狀隊(duì)列的出隊(duì)操作,用數(shù)組ｑｕeue仿真環(huán)狀隊(duì)列,數(shù)組類(lèi)型是int,大小是MaｘSize，隊(duì)尾指針是ｒｅar，隊(duì)頭指針是fｒont。ｉntｄelｑueｕe(）{intteｍｐ;if(ｆronｔ==rear）rｅｔurn–1;ｅｌse{ｆrｏｎt＋+；ｔeｍｐ=queｕe[ｆroｎt]；queuｅ[frｏnt］＝0；rｅturntｅmｐ；}｝指出有錯(cuò)誤的語(yǔ)句:_＿_(dá)______＿8____＿_(dá)＿＿_(dá)______寫(xiě)出改正后的語(yǔ)句：_____＿_(dá)_fronｔ=(fｒont+1)％ＭaxSizｅ___＿＿_(dá)_______＿_(dá)4②區(qū)分循環(huán)隊(duì)列的滿(mǎn)與空，只有兩種方法,它們是____設(shè)標(biāo)志＿_(dá)__和______少用一片空間____＿_(dá)_。【北京郵電２023】5②設(shè)循環(huán)隊(duì)列存放在向量sｑ.data[0..M]中,則隊(duì)頭指針sq．ｆroｎt在循環(huán)意義下的出隊(duì)操作可表達(dá)為_(kāi)_sq.front=(ｓq．fｒｏｎｔ+1)%（M+1)_＿_(dá)__，若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿(mǎn)和隊(duì)空（設(shè)隊(duì)尾指針sｑ．rｅar），則隊(duì)滿(mǎn)的條件為_(kāi)sq.ｆrｏnt＝=（sｑ.rｅaｒ+1)%(Ｍ＋１)___?！鹃L(zhǎng)沙鐵道1997】三、判斷題(T）1①棧和隊(duì)列的存儲(chǔ)方式既可是順序方式,也可是鏈接方式。（Ｔ)2①單鏈表形式的隊(duì)列,頭指針Ｆ指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。（Ｆ）３①循環(huán)隊(duì)列通常用指針來(lái)實(shí)現(xiàn)隊(duì)列的頭尾相接?！灸暇┖娇蘸教?９96】（Ｔ）４①循環(huán)隊(duì)列也存在空間溢出問(wèn)題?！厩鄭u2023】四、簡(jiǎn)答題1②設(shè)循環(huán)隊(duì)列的容量為４０（序號(hào)從0到39），現(xiàn)通過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有（1)ｆrｏnt=１１，rear＝1９;(2）ｆrｏnt＝19,rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)?8，3２2②假設(shè)CQ[0,…，10]是一個(gè)環(huán)狀隊(duì)列,初始狀態(tài)ｆront=rｅａr=１，畫(huà)出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出其元素，并說(shuō)明理由。(1）ｄ,ｅ，b,ｇ，ｈ入隊(duì)；(2)d,e出隊(duì)；(3)I，j，ｋ,l,m入隊(duì)；（４）b出隊(duì);(５)n,ｏ,p,q，r入隊(duì)。3③閱讀下列算法，并回答問(wèn)題(注：lnitＱuｅｕe、EnQｕeuｅ、ＤeQueｕe和QuｅuｅEmpｔy分別是隊(duì)列初始化、入列、出隊(duì)和判隊(duì)空的操作）。vｏｉdf31（Quｅue*Q,Qｕeue＊Q1,Queue＊Ｑ2）{iｎtｅ；lnitQｕｅｕｅ（Q1);lniｔQｕeue（Q2）；whilｅ（！QｕeueＥmpty（Q)）{e＝DｅＱuｅue（Q);if(e＞＝0)EnQueｕｅ(Q1，e);elseEｎQｕeue（Ｑ2,e）}}（1)Q、Ｑ1和Ｑ２都是隊(duì)列結(jié)構(gòu)，設(shè)隊(duì)列Q=（１，0,－5,2，-４，-6，９）,其中１為隊(duì)頭元素，寫(xiě)出執(zhí)行f3１（&Q，&Q1,&Ｑ２)之后隊(duì)列Q、Ｑ１和Q2的狀態(tài)；Q為空Q1=(１，0,2,9)Ｑ2=（-５,－4,-6)(2）簡(jiǎn)述算法f３1的功能。4③閱讀如下程序,并回答下列問(wèn)題(注:lnitQuｅuｅ、EnQｕｅue、DｅQｕeuｅ和ＱｕｅｕeＥｍｐty分別是隊(duì)列初始化、入列、出隊(duì)和判隊(duì)空的操作）。ｖoidｆ31（Queue*Q）{DatａTypee;if（!QueｕeＥmpty（Q）){e=DeQueuｅ(Ｑ)；f3１（Q);ＥnＱueuｅ（Q,e）;}｝設(shè)隊(duì)列Q=（1，3,5,２，4,６）。寫(xiě)出執(zhí)行算法f31后的隊(duì)列Q；Q=（6,4,3,5,3,１)簡(jiǎn)述算法f31的功能。將隊(duì)列反轉(zhuǎn)5③閱讀如下程序,它的功能是清空帶頭結(jié)點(diǎn)的鏈隊(duì)列Q。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容,使成為一個(gè)完整的算法。typedeｆstｒuctnｏdｅ｛DataＴypeｄaｔa;ｓtｒｕctnｏde＊ｎexｔ;}QuｅueNoｄe;tｙpedeｆstruct{QuｅuｅNｏdｅ*front；//隊(duì)頭指針QuｅueNoｄe*rｅar；／／隊(duì)尾指針}LiｎｋQueue;voidf3１（ＬinkＱuｅue＊Ｑ）｛QｕeueNode*p,*s;p＝（1）;whｉle(ｐ?。絅ＵLL）{s＝p；p＝p->nｅxt;ｆreｅ(s);（2）=NＵLL;Q->ｒｅar=（3）;}_＿＿_(dá)_＿p=Q->frｏnt->next＿_(dá)__＿＿_(dá)＿_(dá)_＿_(dá)_＿_(dá)____＿_(dá)_____Q->fｒｏnt－＞next=NULL____＿_(dá)________________Q－>reaｒ=Ｑ-＞ｆrｏnｔ____＿_(dá)＿_(dá)______＿_(dá)_＿_(dá)五、編程題1④假設(shè)將循環(huán)隊(duì)列定義為：以變量ｒeａr和lengtｈ分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給 出此循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件,并寫(xiě)出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。2④假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表達(dá)隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針）,試編寫(xiě)相應(yīng) 的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。４.9習(xí)題4.9.1知識(shí)點(diǎn):樹(shù)和二叉樹(shù)的基本概念一、選擇題1②在一棵具有ｎ個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中,分支結(jié)點(diǎn)的最大編號(hào)為(D)。假定樹(shù)根結(jié)點(diǎn)的編號(hào)為0。 A.(n-1）/2 B.n/2? ?Ｃ．n／２+１ Ｄ．ｎ／2-12②在一棵完全二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左子女結(jié)點(diǎn)的編號(hào)為（Ｃ)。假定根結(jié)點(diǎn)的編號(hào)為０。A.2i ?B．2i-１ ? ?Ｃ．2i+1? ????D.2i+23②在一棵具有３５個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，該樹(shù)的高度為（A）。假定空樹(shù)的高度為-１。A．5? ? B．6 ?? C.7???? ?D．8４②樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（Ｃ)。Ａ.０ Ｂ．１ ?? C．－1? ? D.2５②在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的第i層上（假定根結(jié)點(diǎn)為第０層,ｉ大于等于0而小于等于樹(shù)的高度),最多具有(A）個(gè)結(jié)點(diǎn)。?Ａ．2ｉ ? ? ? B．２i+1 Ｃ.2i?１?? ?? ? D．2n６②在一棵完全二叉樹(shù)中，假定根結(jié)點(diǎn)的編號(hào)為０，則對(duì)于編號(hào)為I(I＞０)的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為(B)。?A.(I+1)/2??? ??Ｂ．(I-1）／2?C．I/2?? ? ?? D.I/2－17③在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中,所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于(C)。A.nB.n-1Ｃ.n+1Ｄ.2*n8③在一棵高度為h（假定根結(jié)點(diǎn)的層號(hào)為0）的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（D）。?Ａ．2h?1??? ?? B．２h＋1 Ｃ.21h?? ? D．２h9②如下的4棵二叉樹(shù)中，（D）不是完全二叉樹(shù)。 Ａ ? ? B ? Ｃ? ? D圖4.471０題圖１0②深度為5的二叉樹(shù)至多有(C)個(gè)節(jié)點(diǎn)。?A.１6 ? Ｂ.3２?Ｃ．3１ ???? ??D．１0１1③對(duì)一棵滿(mǎn)二叉樹(shù)而言，ｍ個(gè)樹(shù)葉,ｎ個(gè)節(jié)點(diǎn),深度為h，則下列哪個(gè)等式對(duì)的(D)。A.n=h+m ? ?? B．h+m＝2n?C.m=n－1 ???D．ｎ＝２h-112②有一棵非空的二叉樹(shù),共有n個(gè)節(jié)點(diǎn)，其中分支度為２的結(jié)點(diǎn)有w個(gè)，則分支度為1的結(jié)點(diǎn)個(gè)數(shù)為(Ｂ）。 Ａ.ｎ-２ｗ ? ????B.ｎ－2ｗ－1?C．n-w+1 ??? D.ｎ-2w＋11３②具有n(n＞0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(C)。A．log2n? ???? Ｂ.loｇ2ｎ C．lｏg２n+１ ???D.（lｏｇ2n)+1１4②設(shè)樹(shù)Ｔ的度為4，其中度為１,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,２,1,1則T中的葉子數(shù)為(D)【南京理工2023】Ａ.５B．6C.7D．81５②在下述結(jié)論中，對(duì)的的是(D）?！灸暇├砉?9９９】（1）只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0;(２）二叉樹(shù)的度為2；（3)二叉樹(shù)的左右子樹(shù)可任意互換;(４）深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。A.（1)(2）（3）B．(２)(3）(4)Ｃ.（2)(４)D.（1）（4）16②若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，５個(gè)度為1的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)個(gè)數(shù)是(B)【北京工商２02３】A.9B．1１Ｃ．15D．不擬定17②一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（Ｅ）?！疚靼步煌?996】A．２50B．500Ｃ．2５４D.505Ｅ.以上答案都不對(duì)二、填空題１②由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有＿_(dá)_５_＿_(dá)種形態(tài)；16個(gè)結(jié)點(diǎn)可構(gòu)造出________種不同形態(tài)的二叉樹(shù)。2②將具有82個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始順序編號(hào)，根結(jié)點(diǎn)為第0號(hào),其他結(jié)點(diǎn)自上向下,同一層自 左向右連續(xù)編號(hào)。則第40號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為_(kāi)_＿14_____。3①在一棵樹(shù)中，_根___＿＿結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。４②假定一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為１８,則它的最小高度為＿_(dá)4___＿。假定根結(jié)點(diǎn)的高度為0。5②假定一棵三叉樹(shù)（即度為３的樹(shù))的結(jié)點(diǎn)個(gè)數(shù)為５0,則它的最小高度為＿_(dá)4_。假定根結(jié)點(diǎn)的高度為0。6②一棵高度為5的完全二叉樹(shù)中，最多包具有__63____個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為０。7②在一棵三叉樹(shù)中,度為3的結(jié)點(diǎn)數(shù)有2個(gè),度為2的結(jié)點(diǎn)數(shù)有1個(gè),度為１的結(jié)點(diǎn)數(shù)為2個(gè),那么度為０的結(jié)點(diǎn)數(shù)有___6＿_(dá)＿個(gè)。8②在一棵高度為3的四叉樹(shù)中,最多具有＿_(dá)2１__＿＿結(jié)點(diǎn)。9②一棵深度為6的滿(mǎn)二叉樹(shù)有____31_＿個(gè)分支結(jié)點(diǎn)和＿_(dá)3２＿_(dá)_＿個(gè)葉子。10②一棵具有25７個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為_(kāi)_＿9__＿。11②設(shè)一棵完全二叉樹(shù)具有１00０個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有__５00___＿個(gè)葉子結(jié)點(diǎn),有_＿_(dá)499９___個(gè)度為? 2的結(jié)點(diǎn)，有_＿1_＿_(dá)_個(gè)結(jié)點(diǎn)只有非空左子樹(shù),有＿_(dá)＿0___個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。１2②對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù),該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為_(kāi)_n-１_______。13②一棵具有ｎ個(gè)結(jié)點(diǎn)的二叉樹(shù)，若它有n0個(gè)葉子結(jié)點(diǎn),則該二叉樹(shù)上度為１的結(jié)點(diǎn)n1=_ｎ-2n０+1_＿_(dá)＿_(dá)。１4②假如結(jié)點(diǎn)A有3兄弟,并且B是A的雙親,則B的度是___4＿_(dá)_。15②對(duì)于一棵完全二叉樹(shù)，設(shè)一個(gè)結(jié)點(diǎn)的編號(hào)為i,若它的左孩子結(jié)點(diǎn)存在，則其編號(hào)為_(kāi)＿2*i_____＿；若右 ? 孩子結(jié)點(diǎn)存在，則其編號(hào)為_(kāi)2*i+1＿_(dá)____＿;而雙親結(jié)點(diǎn)的編號(hào)為＿_(dá)__ｉ/2＿＿_(dá)__。16②深度為ｋ的完全二叉樹(shù)至少有２ｋ-1個(gè)結(jié)點(diǎn),至多有２k-１個(gè)結(jié)點(diǎn)?！緩B門(mén)202３】【南京理工1999】17②已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn),3個(gè)度為２的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)有____12＿_(dá)_＿_(dá)個(gè)葉子結(jié)點(diǎn)?！緩B門(mén)202３】18②一棵有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)有___０____＿_(dá)個(gè)度為1的結(jié)點(diǎn)、有__(n+1)/2＿_(dá)_____個(gè)分支（非終端）結(jié)點(diǎn)和_＿(ｎ-1)／2__＿_(dá)＿＿_(dá)個(gè)葉子,該滿(mǎn)二叉樹(shù)的深度為_(kāi)__log2n+1?_＿_(dá)___。【華中理工2023】三、判斷題（Ｔ）1①二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。（F）2①二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。（F)3②對(duì)于一棵非空二叉樹(shù),它的根結(jié)點(diǎn)作為第一層,則它的第i層上最多能有２i-1個(gè)結(jié)點(diǎn)。(T)4②具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。（Ｔ）5①完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子,則它必是葉結(jié)點(diǎn)。（Ｆ）6②二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹(shù)時(shí)無(wú)所謂左、右子樹(shù)之分。(T)7②當(dāng)k≥１時(shí)，高度為ｋ的二叉樹(shù)至多有２1k?個(gè)結(jié)點(diǎn)。(Ｆ)8②一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù),它的高度是lｏg2n+1。(F)9①二叉樹(shù)就是結(jié)點(diǎn)度為2的樹(shù)。【長(zhǎng)沙鐵道１9９７】【中科院軟件所1997】(Ｆ)10②完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)?！厩鄭u2０２３】(T）11①樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。【燕山1998】（Ｆ）１2①樹(shù)與二叉樹(shù)是兩種不同的樹(shù)型結(jié)構(gòu)?！緰|南２023】四、簡(jiǎn)答題1③已知一棵度為ｍ的樹(shù)中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn),…,Nｍ個(gè)度為m的結(jié)點(diǎn)。試問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)?２③樹(shù)和二叉樹(shù)之間有什么樣的區(qū)別與聯(lián)系？【西北工業(yè)1９98】【廈門(mén)2023】【燕山20２3】４.９.2知識(shí)點(diǎn)：二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)一、選擇題1①在一棵樹(shù)的左子女-右兄弟表達(dá)法中,一個(gè)結(jié)點(diǎn)的右孩子是該結(jié)點(diǎn)的(Ａ）結(jié)點(diǎn)。?A．兄弟??Ｂ．子女C.祖先 D.子孫2②在一棵樹(shù)的靜態(tài)雙親表達(dá)中,每個(gè)存儲(chǔ)結(jié)點(diǎn)包含(Ｂ)個(gè)域。 A.1? B．2C.3 D．4３②在一棵二叉樹(shù)的二叉鏈表中,空指針域數(shù)等于非空指針域數(shù)加（A)。 A．２ B．１C．0 ?D．-１4②二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu),所以（C）。 A.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)C．順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)D．順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用5②運(yùn)用二叉鏈表存儲(chǔ)樹(shù),則根結(jié)點(diǎn)的右指針是(B)。【青島202３】A.指向最左孩子B．指向最右孩子C.空D.非空６②在下列存儲(chǔ)形式中,哪一個(gè)不是樹(shù)的存儲(chǔ)形式？（Ｄ）【北方交通2023】A.雙親表達(dá)法B.孩子鏈表表達(dá)法Ｃ.孩子兄弟表達(dá)法Ｄ.順序存儲(chǔ)表達(dá)法7②一棵有ｎ個(gè)結(jié)點(diǎn)的二叉樹(shù),按層次從上到下,同一層從左到右順序存儲(chǔ)在一維數(shù)組Ａ［1．.n］中，則二叉樹(shù)中第i個(gè)結(jié)點(diǎn)（i從1開(kāi)始用上述方法編號(hào)）的右孩子在數(shù)組Ａ中的位置是(Ｂ）【南京理工2023】A．A［2i]（２i＜=n）Ｂ.A[２i+1](２i+1<=n)C．A［i－2]D.條件不充足，無(wú)法擬定填空題１①二叉樹(shù)通常有___順序_＿＿_(dá)_＿存儲(chǔ)結(jié)構(gòu)和__＿_(dá)_鏈?zhǔn)絖______存儲(chǔ)結(jié)構(gòu)。判斷題（T)１②若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu),則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有ｎ-1個(gè)非空指針域。(T)2①樹(shù)適合于表達(dá)層次關(guān)系。(T）３②完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)?！灸暇┖娇蘸教欤?96】四、簡(jiǎn)答題1②描述二叉樹(shù)的順序存儲(chǔ)。2②描述二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)。4．９.3知識(shí)點(diǎn):樹(shù)、森林向二叉樹(shù)的轉(zhuǎn)換選擇題1②把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后,這棵二叉樹(shù)的形態(tài)是(Ａ）。 A．唯一的?????? ?B．有多種 C.有多種,但根結(jié)點(diǎn)都沒(méi)有左孩子??D.有多種,但根結(jié)點(diǎn)都沒(méi)有右孩子2②如下圖所示的二叉樹(shù)Ｔ2是由森林T１轉(zhuǎn)換而來(lái)的二叉樹(shù),那么森林Ｔ1有（C）個(gè)葉子結(jié)點(diǎn)。AABEDJIGHCF圖4.48２題圖 A.4 ?Ｂ．5C．６? Ｄ．7填空題1②設(shè)森林Ｆ中有4棵樹(shù)，第1、2、3、4棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為ｎ１、ｎ２、ｎ3、n4,當(dāng)把森林F轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的左子樹(shù)中有＿＿_(dá)＿ｎ1-1_＿_(dá)_＿_(dá)_＿＿_(dá)＿_(dá)個(gè)結(jié)點(diǎn)。２②將森林或樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí)，所有的水平線段以左邊結(jié)點(diǎn)為軸心_順時(shí)針＿_(dá)旋轉(zhuǎn)4５o。3②運(yùn)用樹(shù)的孩子兄弟表達(dá)法存儲(chǔ),可以將一棵樹(shù)轉(zhuǎn)換為＿二叉樹(shù)_＿_(dá)＿_(dá)___?！局貞c2023】三、判斷題(T）１②將森林或樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí)，在所有相鄰兄弟結(jié)點(diǎn)（森林中每棵樹(shù)的根結(jié)點(diǎn)可以當(dāng)作是兄弟結(jié)點(diǎn)）之間加一水平連線。（T)2②將森林或樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí),對(duì)每個(gè)非葉子結(jié)點(diǎn)ｋ，除了其最左邊的孩子結(jié)點(diǎn)外，刪去k與其他孩子結(jié)點(diǎn)的連線。（F)3②將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后,根結(jié)點(diǎn)沒(méi)有左子樹(shù)。（F)４②必須把一般樹(shù)轉(zhuǎn)換成二叉樹(shù)后才干進(jìn)行存儲(chǔ)?！灸暇┖娇蘸教?9９７】四、簡(jiǎn)答題1③把如圖所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。ABABDGJMIKLCEFH２③如何把森林轉(zhuǎn)換成二叉樹(shù)。4.4９1題圖4.9．４知識(shí)點(diǎn)：樹(shù)與二叉樹(shù)的遍歷圖一、選擇題1②已知某二叉樹(shù)的后序遍歷序列是dabｅｃ，中序遍歷序列是deｂａc，則它的前序遍歷序列是(Ｄ)。 Ａ．a(chǎn)cbeｄ B．ｄecaｂＣ．ｄeabc Ｄ.cｅdba2②在一棵非空的二叉樹(shù)的中序遍歷序列中，根節(jié)點(diǎn)的右邊(Ｂ)。A．只有左子樹(shù)上的所有節(jié)點(diǎn)B.只有右子樹(shù)上的所有節(jié)點(diǎn)C.只有左子樹(shù)上的部分節(jié)點(diǎn)Ｄ.只有右子樹(shù)上的部分節(jié)點(diǎn)3②下列二叉樹(shù)的后序遍歷序列是（C)。aabcdfgexyh圖4．5０3題圖 A.aｂdecfghxy ?Ｂ．ａbdｇｃehｆxyC．ｇｄbhｅxyfcａ D．ｄgbaｅhcｘfｙ４②任何一棵二叉樹(shù)的葉節(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)順序(A）。 Ａ．不發(fā)生改變? Ｂ．發(fā)生改變C．不能擬定?D．以上都不對(duì)5②線索二叉樹(shù)是一種(Ｃ)結(jié)構(gòu)。?A．邏輯 Ｂ．邏輯和存儲(chǔ)C．物理 ?Ｄ.線性6②將下圖的二叉樹(shù)按中序線索化，結(jié)點(diǎn)X的右指針和Ｙ的左指針?lè)謩e指向（C)?A.A,D B.B，CC.Ｄ，A D.C,ＡAABDCEXY圖４.５16題圖7②引入線索二叉樹(shù)的目的是(A）。【南京理工1９98】?Ａ．加快查找結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的速度?B．為了能在二叉樹(shù)中方便插入和刪除?C.為了能方便找到雙親? ???D．使二叉樹(shù)的遍歷結(jié)果唯一8②樹(shù)的后根遍歷序列等同于該樹(shù)相應(yīng)的二叉樹(shù)的(Ｂ）?！颈本├砉?023】Ａ.先序序列B.中序序列C．后序序列9②一棵二叉樹(shù)的前序遍歷序列為ABＣDEFG,它的中序遍歷序列也許是（B）【北京工業(yè)20２３】A.CABDEFGB.ABＣDEFGC.DAＣEＦＢGＤ.AＤCFＥG10②已知一棵二叉樹(shù)的前序遍歷結(jié)果為AＢCDEF,中序遍歷結(jié)果為ＣＢＡＥＤF,則后序遍歷的結(jié)果為（Ａ）?！菊憬?999】A.CBEFＤAＢ.FEDＣBAC．CBEDFAD.不定１1②某二叉樹(shù)中序序列為A，B，Ｃ,Ｄ，E，Ｆ，Ｇ，后序序列為B，D,Ｃ,A,F，Ｇ,E則前序序列是：（B）【南京理工2023】Ａ.E，G，F(xiàn),A,C，Ｄ，ＢB．E,A，C，B,Ｄ,G，F(xiàn)Ｃ.E，A,G，C，F(xiàn)，B，DD.上面的都不對(duì)１2②對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹(shù)為(ＢＦ)；對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為(B)。【中科院計(jì)算所1999】A．一般二叉樹(shù)B．只有根結(jié)點(diǎn)的二叉樹(shù)C.根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)D.根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)Ｅ.所有結(jié)點(diǎn)只有左子數(shù)的二叉樹(shù)F.所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)二、填空題1②在二叉樹(shù)的一維數(shù)組存儲(chǔ)方式中,父節(jié)點(diǎn)和右孩子的索引值之間滿(mǎn)足的關(guān)系是＿２倍加1_＿＿_(dá)___。2②在中序線索化二叉樹(shù)時(shí)，采用__中序______遍歷方法最合適。3②線索二叉樹(shù)中的左線索指向其＿_(dá)前驅(qū)＿_(dá)＿_(dá)＿_(dá),右線索指向其__后繼__＿_(dá)__?！竟枮I工業(yè)20２３】三、判斷題（T)1②