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

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