2023年數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)(12月)

數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)２023年12月期末練習(xí)一一、單項(xiàng)選擇題１．一種邏輯結(jié)構(gòu)在存儲(chǔ)時(shí)（)。A.只要存儲(chǔ)數(shù)據(jù)元素間的關(guān)系B.只能采用一種存儲(chǔ)結(jié)構(gòu)C.可采用不同的存儲(chǔ)結(jié)構(gòu)D.只要存儲(chǔ)數(shù)據(jù)元素的值2．同一種邏輯結(jié)構(gòu)（)。A．只能有唯一的存儲(chǔ)結(jié)構(gòu)B.可以有不同的存儲(chǔ)結(jié)構(gòu)Ｃ．只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系D.以上三種說法均不對(duì)的3．對(duì)鏈表，以下敘述中對(duì)的的是(）。A.不能隨機(jī)訪問任一結(jié)點(diǎn)B.結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的C．插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)D．可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問４．鏈表所具有的特點(diǎn)是（)。A.可以隨機(jī)訪問任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間C.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)D.可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問5.線性表在存儲(chǔ)后,假如相關(guān)操作是:規(guī)定已知第i個(gè)結(jié)點(diǎn)的位置訪問該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),則采用（）存儲(chǔ)方式是不可行的。A．單鏈表B.雙鏈表C．單循環(huán)鏈表D.順序表6．?dāng)?shù)據(jù)的物理結(jié)構(gòu)（)。A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B．僅僅涉及數(shù)據(jù)元素的表達(dá)Ｃ．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)7．棧和隊(duì)列的共同特點(diǎn)是()。A.都是先進(jìn)后出B．元素都可以隨機(jī)進(jìn)出Ｃ.只允許在端點(diǎn)處插入和刪除元素Ｄ．都是先進(jìn)先出8.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。Ａ.一對(duì)一B．一對(duì)多9.元素2，4,6，8按順序依次進(jìn)棧，按該棧的的也許輸出序列依次入隊(duì)列，該隊(duì)列的也許輸出序列是(）(進(jìn)棧出?？梢越惶孢M(jìn)行)。A.8，6，2，4B．8，４，2,6Ｃ.6，2,4,８D．８,6，４,210．以下表中可以隨機(jī)訪問的是（)。Ａ．單向鏈表B.雙向鏈表C.單向循環(huán)鏈表Ｄ．順序表１1．在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中,假設(shè)ｆ和r分別為隊(duì)頭和隊(duì)尾指針，則從該對(duì)列中刪除一個(gè)結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x中的運(yùn)算為（)。A．x=rdata；r=rnｅxｔ；B.r=rneｘt;ｘ＝rｄataC.x＝fｄata;ｆ=fnｅxt;D.f=ｆｎeｘt;x=fｄatａ1２．算法的時(shí)間復(fù)雜度與(）有關(guān)。A．所使用的計(jì)算機(jī)B.與計(jì)算機(jī)的操作系統(tǒng)C.與算法自身D.與數(shù)據(jù)結(jié)構(gòu)1３．設(shè)有一個(gè)20階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組Ｂ中(數(shù)組下標(biāo)從1開始)，則數(shù)組中第3８號(hào)元素相應(yīng)于矩陣中的元素是（)。A．a(chǎn)10，８Ｂ．a(chǎn)7,6C．a(chǎn)９,2Ｄ．a(chǎn)１4．設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素需移動(dòng)元素的個(gè)數(shù)為()。A.n-i+１B.ｎ-ｉC.ｎ-ｉ－１Ｄ．i1５.在C語言中，分別存儲(chǔ)“S”和‘s’，各需要占用（)字節(jié)。A.一個(gè)和兩個(gè)B.兩個(gè)C.一個(gè)D.兩個(gè)和一個(gè)１6.在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn),且ｑ所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼,現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語句是(）。A.ｐ=ｑ-＞nextＢ．ｐ－＞neｘt=ｑＣ．p－>next＝ｑneｘｔD．ｑ-＞nｅｘt=NUＬL１7．一棵有n個(gè)結(jié)點(diǎn),采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中,共有(）個(gè)指針域被有效使用(即指針域?yàn)榉强眨?。A.ｎ＋１B．nC．ｎ-1Ｄ．n-２18.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行()。A.x＝ｔｏｐ->data;top=ｔｏp－>neｘt；B．x=top－>ｄaｔa；C．tｏｐ=ｔｏp-＞nexｔ；x=top->data;D．tｏp＝ｔop->next;x=data;19．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在雙親結(jié)點(diǎn),則雙親結(jié)點(diǎn)的順序編號(hào)為(）。Ａ.i/２．0B．i/2向下取整C．２ｉ+1D．i+220.在一個(gè)鏈隊(duì)中，假設(shè)ｆ和r分別為隊(duì)頭和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（)。Ａ．ｒ=ｆ－>neｘｔ；B．r=ｒ->nｅxt;Ｃ．ｆ=ｆ－>neｘｔ；D．f=ｒ->neｘｔ;2１.設(shè)一棵哈夫曼樹共有2n＋１個(gè)結(jié)點(diǎn)，則該樹有(）個(gè)非葉結(jié)點(diǎn)。A.nB.ｎ＋1Ｃ.n-122．一個(gè)棧的進(jìn)棧序列是ａ,b,c,ｄ，e，則棧的不也許輸出序列是()（進(jìn)棧出?？梢越惶孢M(jìn)行)。A.ｄceabB.eｄcbaＣ．ｄeｃbａD．a(chǎn)ｂcde23.一棵完全二叉樹共有4層，且第4層上有2個(gè)結(jié)點(diǎn)，該樹共有(）個(gè)非葉子結(jié)點(diǎn)（根為第一層)。Ａ．5Ｂ．4C．324．有一個(gè)長度為１０的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A．2６/1０B．2９/１025．如圖１所示的一個(gè)圖,若從頂點(diǎn)a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為（）。Ａ.abｅｄfcB.acfebdC.aeｂcdfD.ａebcfdbbdfeca圖126.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空）中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少)，然后將其放入已排序序列的對(duì)的位置的方法是()。Ａ．冒泡B.直接插入C.折半插入D．選擇排序２7．一組記錄的關(guān)鍵字序列為(56,3０,８９,66,48,５0,9４,８7，1０0),運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為(）。Ａ．30,５0，48，56，6６，89，94,１０0,８7B．5０，３0,４8，56，6６,89,94,87,100C．48,30,5０，56,６6,89,94，8７,１00D．50，30,48，６6,5６,89,94,８7,1０028.設(shè)有一個(gè)１0階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從１開始)，則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是(）。A.33B.32Ｃ.８529．線性表以（)方式存儲(chǔ)，能進(jìn)行折半查找。A．關(guān)鍵字有序的鏈接B．順序C.關(guān)鍵字有序的順序D.數(shù)組C.多對(duì)多Ｄ.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼30．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的(）倍。A.３B.2．5Ｃ二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表達(dá)稱為_______＿結(jié)構(gòu)。2．棧和隊(duì)列的操作特點(diǎn)分別是__＿_(dá)___和_____＿_(dá)_。3．求兩個(gè)n階矩陣的乘積，算法的基本操作為＿＿_(dá)＿＿_(dá)__,時(shí)間復(fù)雜度為___＿_(dá)__＿。4．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_＿_(dá)_____結(jié)構(gòu)。5.設(shè)有一個(gè)長度為2５的順序表,第8號(hào)元素到第２5號(hào)元素依次存放的值為8,9,１0,11，…2５，某人想要在第8個(gè)元素前插入1個(gè)元素7(也就是插入元素作為新表的第8個(gè)元素),他的做法是從第８號(hào)元素開始,直到第2５號(hào)元素依次向后移動(dòng)1個(gè)位置,然后把7存放在8號(hào)位置,其結(jié)果是新表中第25號(hào)元素的值為___＿＿。6.根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃榧?、線性、、四類基本結(jié)構(gòu)。7.在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)（設(shè)q所指的結(jié)點(diǎn)已賦值)，其中所用的一條語句(p->ｎｅｘt)-＞priｏｒ=q；的功能是使P所指結(jié)點(diǎn)的__＿_(dá)＿_(dá)＿指向q。８．規(guī)定在n個(gè)數(shù)據(jù)元素中找其中值最大的元素,設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為____＿_(dá)＿_(dá)和____＿_(dá)__。9.設(shè)有一個(gè)帶頭結(jié)點(diǎn)的,頭指針為ｈead的單向鏈表,ｐ指向表中某一個(gè)結(jié)點(diǎn),且有ｐ->ｎext==ＮULL,現(xiàn)要?jiǎng)h除頭結(jié)點(diǎn),并使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表,通過操作heａd=head->nexｔ;__＿_(dá)_＿_(dá)_。1０.在一個(gè)單向鏈表中ｐ所指結(jié)點(diǎn)之后插入一個(gè)ｓ所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行__＿＿_(dá)＿_(dá)_和p-＞next=ｓ；的操作。11.從一個(gè)棧頂指針為tｏp的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用d保存被刪結(jié)點(diǎn)的值，可執(zhí)行__＿＿_(dá)___。（結(jié)點(diǎn)的指針域?yàn)閚ｅxｔ，數(shù)據(jù)域?yàn)閐ａt(yī)ａ）12．在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域，它們是值域、。13循環(huán)鏈隊(duì)列中,設(shè)ｆrｏｎt和ｒear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaｘSize,采用少用一個(gè)元素的模式),判斷循環(huán)鏈隊(duì)列為滿的條件為＿_(dá)_____＿。14．一棵二叉樹中順序編號(hào)為ｉ的結(jié)點(diǎn),若它存在左、右孩子，則左、右孩子編號(hào)分別為___＿_(dá)___、＿_(dá)______。15．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素,則矩陣Ａ共有___＿＿_(dá)_個(gè)零元素。1６．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),可執(zhí)行s->ｎext=h;和__＿＿_(dá)_＿_(dá)。1７．一棵有２0個(gè)結(jié)點(diǎn)的４度的樹，其中3度結(jié)１個(gè)，２度結(jié)1個(gè),1度結(jié)2個(gè)，則該樹共有__＿_(dá)__＿個(gè)葉結(jié)點(diǎn)。18．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則插入s所指結(jié)點(diǎn)的操作為____＿_(dá)__和r=ｓ;(結(jié)點(diǎn)的指針域?yàn)閚ｅｘｔ)19.一棵有18個(gè)結(jié)點(diǎn)的二叉樹，其２度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為８，則該樹共有＿_(dá)＿＿＿_(dá)＿個(gè)1度結(jié)點(diǎn)20.設(shè)有一棵深度為4的完全二叉樹，第四層上有５個(gè)結(jié)點(diǎn),該樹共有____＿_(dá)＿_(dá)_個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第１層）21.如圖２所示的二叉樹,其先序遍歷序列為__＿_(dá)＿_(dá)＿_(dá)＿。3c7g3c7gd65e4dc2b18hd9圖222.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),矩陣中每個(gè)非零元素相應(yīng)的三元組涉及該元素的__＿_(dá)__＿、__＿_(dá)_＿_(dá)和_______三項(xiàng)信息。23．在查找表中,通過記錄的某關(guān)鍵字能唯一地?cái)M定一個(gè)記錄，該關(guān)鍵字稱為_＿_(dá)_____＿。24.在對(duì)一組記錄（55，39,9７,22,16，７3,65,47,８８)進(jìn)行直接插入排序時(shí),當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較________＿次。三、綜合題1.(1)對(duì)給定權(quán)值3,1,４，4,5,6，構(gòu)造深度為５的哈夫曼樹。(設(shè)根為第1層)(2)求樹的帶權(quán)途徑長度。（3）鏈接存儲(chǔ)上述哈夫曼樹，結(jié)點(diǎn)中共有多少個(gè)個(gè)指針域?yàn)榭?說明理由.2．（1）以2，3，4，７,8,9作為葉結(jié)點(diǎn)的權(quán),構(gòu)造一棵哈夫曼樹(規(guī)定每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。（2)一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)?簡述理由？3．(1)如下的一棵樹,給出先序遍歷序列（2)把１,2,３，４，5,6，7,8,9填人,使它成為一棵二叉排序樹提醒：設(shè)圖中的樹是二叉排序樹,找出中序遍歷序列與1,2,…9的相應(yīng)關(guān)系(3)請(qǐng)?jiān)谠摌渲性俨迦胍粋€(gè)結(jié)點(diǎn)3．5作為葉結(jié)點(diǎn),并使它仍然是一棵二叉排序樹。AA1A2A43A7A5A9A8A3A6圖34.一組記錄的關(guān)鍵字序列為（46，７9，５6，３8，40，84)(1)運(yùn)用快速排序的方法,給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次互換元素的過程，規(guī)定以升序排列)（２)對(duì)上述序列用堆排序的方法建立大根堆，規(guī)定以二叉樹逐次描述建堆過程。5．設(shè)查找表為(5,6,7,8,9,10，１1,12,13,14)（1）畫出對(duì)上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(2)給出二叉排序樹的定義,針對(duì)上述折半查找所相應(yīng)的鑒定樹的構(gòu)造過程,說明鑒定樹是否是二叉排序樹(設(shè)樹中沒有相同結(jié)點(diǎn))?（3)為了查找元素5．5,通過多少次元素間的比較才干擬定不能查到？６.設(shè)查找表為(５0,６０,７5，８5,96，98,１0５,１10，12０,130）(1)說出進(jìn)行折半查找成功查找到元素12０需要進(jìn)行多少次元素間的比較？(2)為了折半查找元素95，通過多少次元素間的比較才干擬定不能查到?（3）畫出對(duì)上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))四、程序填空題1．以下函數(shù)為直接選擇排序算法,對(duì)a[１],a[2]，…a[n]中的記錄進(jìn)行直接選擇排序,完畢程序中的空格ｔｙpeｄefstruct{iｎtｋｅy;……}ＮODＥ;ｖoｉdsｅlsorｔ(NＯＤEａ[],ｉｎｔn){?ｉnti,ｊ，k; NODEtemp; for(i=１;ｉ<=___(1)_____；ｉ++) {??ｋ=i;? for(j＝ｉ+１；j＜=＿_(dá)_(2)＿_(dá)＿_(dá)_;j++) ? ｉf(a[j］.key<a［k].key)__(３)____＿_(dá)；? if(i！=k) {?? tｅmp=a[ｉ];? ?___（4)__＿_(dá)_; ??__＿_(dá)(5)____;??}?}}2．以下是用尾插法建立帶頭結(jié)點(diǎn)且有ｎ個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1，２,3,……,n，完畢程序中空格部分。NＯＤE*create(n）｛ＮＯDE*ｈeａd,＊p,*ｑ;iｎti;p=(NODE＊）mａlｌoｃ(sizeoｆ（ＮODＥ))；ｈeａd=(１);（2);pｎext=ＮUＬL;／＊建立頭結(jié)點(diǎn)＊/fｏr(i=1;i<＝n;ｉ＋+){p=(3）;pdａｔa=i；pｎext=NＵLL；qnｅxt=（４）;(５）;}retｕｒn（heaｄ);}３.設(shè)有一個(gè)頭指針為hｅad的不帶頭結(jié)點(diǎn)單向鏈表，且p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中某結(jié)點(diǎn)a(設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同),寫出相關(guān)語句(1）．使該單向鏈表成為單向循環(huán)鏈表（2)刪去a結(jié)點(diǎn)q=p;x=p->data;whiｌｅ（q－>ｎｅxt!=NＵLL）q=q－>next；__（1)_＿_(dá)q=p;p=p->next；whiｌe(p->ｄata!=ｘ）｛q＝p;__(２)___}＿_(dá)(３)＿＿_(dá)4．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為lｅft和rigｈt,數(shù)據(jù)域data為字符型,BＴ指向根結(jié)點(diǎn)）。vｏｉdＩnorder(ｓｔructBTreeNodｅ*BT){iｆ(BＴ!=NULＬ){(１);（2）;(３);}｝期末復(fù)習(xí)一答案一、單項(xiàng)選擇題1.C2．Ｂ3.A4.Ｃ５.A6.D７.C8．A９.D1０．D11．C12.C１３.C1４．B１5.Ｄ16．C17.C１8．A19.B2０．Ｃ2１．Ａ22．A２3．Ｂ24.B25．C26.C27．B28.A29.C3０．Ｄ二、填空題1.物理（存儲(chǔ))2.后進(jìn)先出、先進(jìn)先出3.乘法O(n3）4.圖狀（網(wǎng)狀)5．8６．樹形圖狀7．直接前驅(qū)的左指針8.n-1,O(ｎ)、9．p-＞nｅxｔ=head;10．ｓ-＞next＝ｐ-＞nｅxt；11．ｄ＝toｐ->datａ；ｔop=top－>next;12．左指針右指針13.front＝=(reaｒ＋1）%MaxSｉze14.2i2i+115.3416．ｈ＝s;1７．１318.r－＞ｎｅxt=s；19.120.１221.22．行下標(biāo)、列下標(biāo)、非零元素值23．主關(guān)鍵字24.3三、綜合應(yīng)用題654365435423418145197896434531213圖４(2)WＰL=3*4+1*4＋4*3+６*2＋4*2＋５*2＝58（3)共11個(gè)結(jié)點(diǎn),2２個(gè)指針域,除根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)相應(yīng)一個(gè)指針域.,共10個(gè)指針域非空，故有22-10＝1２個(gè)空指針域，2．3333(1)151815187998799854543232圖52:11１０３:111１4：１107：008:019:10（2)2n-1個(gè)，由于非葉結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。3.(1)Ａ１Ａ2A（2)(３)77421563893.5圖64．(１)初始序列4６，79,56,38,40，8440,79,5６,3８,4０，8440，79，5６,３８,７9，8440，38,5６，３8,79，8440，３８，56,56,79，84４0,38,46，56,7９，8456795679384084468479384046566567938404679384084845646圖6５．（1）9971014118512136圖7（2)二叉排序樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹非空，則左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值;若它的右子樹非空，則右子樹的所有結(jié)點(diǎn)的值都大于(若允許結(jié)點(diǎn)有相同的值，則大于等于)它的根結(jié)點(diǎn)的值;左,右子樹也是一棵二叉排序樹，按定義鑒定樹是二叉排序樹。(３）3次６.(1)3次(2)4次（３)9696759813010585501100512060圖8四、程序填空題1．(1)ｎ-1(2）n（3)ｋ=j(4）ａ[ｉ]=a[k](５）a［k]＝temp2．（1)p(2）ｑ＝p(3）(NODＥ*)mａlｌoc(sizｅoｆ（NOＤE))(4）p(5）q=p3.q->next=ｈｅａd;p=p－＞next；q->neｘt=p->ｎeｘt;4．（1）Inorder(BＴ-＞lefｔ)(2）printf(“%c”,BT-＞data)（3）Inｏrder(BT-＞ｒighｔ)期末練習(xí)二一、單項(xiàng)選擇題1.結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是（)。Ａ.集合B．線性結(jié)構(gòu)C．樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)2．在C語言中,順序存儲(chǔ)長度為3的字符串，需要占用()個(gè)字節(jié)。A.４B．3C．6Ｄ．123.對(duì)不帶頭結(jié)點(diǎn)的單向鏈表,判斷是否為空的條件是(）(設(shè)頭指針為ｈead）。A．heaｄ＝=NＵLLB.hｅad->next＝=NUＬLC．head->neｘt==heａdＤ．head=ＮUＬL４.串函數(shù)StｒＣａt(yī)（ａ,ｂ)的功能是進(jìn)行串(）。A．比較Ｂ.復(fù)制C.賦值Ｄ．連接5.在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,p、ｑ分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn),現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn),可用的語句是（）。Ａ.ｐ=q->next；p=p->ｎext;Ｂ．p－＞neｘt=q;p=ｐ->neｘt；C．ｐ-＞nexｔ=ｑ->nｅxt;q＝p;D.p=ｐ－>ｎexｔ；q->next=p;6．一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中,共有(）個(gè)指針域?yàn)榭?。A．ｎ+1Ｂ．nC．n-1Ｄ．ｎ-2７.一個(gè)棧的進(jìn)棧序列是1，2,3,4，５,則棧的不也許輸出序列是(）(進(jìn)棧出棧可以交替進(jìn)行）。A.12345B.４3５12C.４53２1Ｄ.5４3218.設(shè)一棵哈夫曼樹共有n個(gè)非葉結(jié)點(diǎn),則該樹有(）個(gè)葉結(jié)點(diǎn)。A．nＢ．ｎ+1C.n-1D.２n９.一個(gè)隊(duì)列的入隊(duì)序列是2，4,6，8，按該隊(duì)列的輸出序列使各元素依次入棧,該棧的也許輸出序列是()。A．8，６,4,２B．6，2，4,8C．８,4，２,6D．8，2，4，６10.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行()。A.ｘ＝top->ｄata;ｔop=toｐnext；B.x=toｐ－＞ｄaｔa;C．top=top－>next;x=tｏp->datａ;Ｄ.toｐ=ｔop->nexｔ;x=data；1１．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，已生成一個(gè)結(jié)點(diǎn)ｐ,要為結(jié)點(diǎn)ｐ賦值x,并入隊(duì)的運(yùn)算為（）。Ａ．p->data=x;p－＞nexｔ=NULL;f－>next=p;f=p;B.p-＞data=x;p－>next=NULL；r－>neｘt=p;r＝ｐ;Ｃ.p-＞ｄatａ=x；p->next=r;r=ｓ;D.p->dａt(yī)ａ=x;p->neｘｔ=f；f=ｓ;1２.一棵完全二叉樹共有5層,且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（)個(gè)結(jié)點(diǎn)。Ａ．３0B.２０C.21D．２313.設(shè)有一個(gè)25階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始),則矩陣中元素．ａ７，６在一維數(shù)組Ｂ中的下標(biāo)是（）。A．34B.１4Ｃ．26Ｄ.2７14．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的(）倍。A.３B.2.５C．1．5D．21５.以下程序段的結(jié)果是c的值為(）。ｃhaｒa[5］=“１236789”ｗhile(*p++)ｃ++;A.8,B．7C.10D．12１6.已知如圖1所示的一個(gè)圖,若從頂點(diǎn)V1出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（)。A.V1V2V４Ｖ８Ｖ５V3V6V７B.Ｖ1V2Ｖ4V5Ｖ8V3V６V7Ｃ．V１V２V4V８V3V５V6Ｖ7D．V１V３V６Ｖ7Ｖ2V４V５Ｖ8VV6V7V1V2V3V8V4V5圖117．一棵有23個(gè)結(jié)點(diǎn),采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中,共有（）個(gè)指針域?yàn)榭?。A.24B．２５C.23D．4518.已知如圖2所示的一個(gè)圖,若從頂點(diǎn)a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為()。A.abcedfＢ．ａbｃｅfdC．a(chǎn)ebcｆdD.aｃfdeｂbdbdfeca圖219．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子,則雙親結(jié)點(diǎn)的順序編號(hào)為()。A．i／2Ｂ．2i-１Ｃ．2i+1D.i/２-120．對(duì)二叉排序樹進(jìn)行（)遍歷,可以使遍歷所得到的序列是有序序列。A.按層次B.后序C.中序D．前序21.設(shè)一棵哈夫曼樹共有2ｎ+1個(gè)葉結(jié)點(diǎn),則該樹有()個(gè)葉結(jié)點(diǎn)。A.n-１B.nC.ｎ+1D．２n22.在有序表{2，4,7，1４，3４,43，47，64,75,80,90，９7,１20}中，用折半查找法查找值８0時(shí)，經(jīng)（)次比較后查找成功。A.4B．２C.3Ｄ．５23．已知如圖3所示的一個(gè)圖,若從頂點(diǎn)ａ出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為（）。A.abeｃｄfB．a(chǎn)cfebｄC.ａebcｆｄＤ．a(chǎn)edbｆcbbdfeca圖32４.有一個(gè)長度為９的有序表,按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（)。Ａ．25/1０B．２5/９Ｃ．2０／9Ｄ．17/92５.已知如圖4所示的一個(gè)圖,若從頂點(diǎn)B出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為（）。A.BADEHＣＦGＢ.ＡDEHCＧFC.BADＥCHFGD.ＢAＤEHＣＦGFFGV7ABCHV8DV4E圖4２6.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進(jìn)行比較(規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對(duì)的位置的方法是（）。A．冒泡B.直接插入C.折半插入D.選擇排序２7．一組記錄的關(guān)鍵字序列為（４6，38,56,４０,７9,84）,運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為()。A.40,3８，46,79,5６，8４B．40,38，46,5６，7９，８４C．4０，３8,46，８4,5６，79Ｄ.38，４0,46，56，７9，84２8．一組記錄的關(guān)鍵字序列為（46，79,５6,38,４０，８4），運(yùn)用快速排序，以第一個(gè)關(guān)鍵字為分割元素,通過一次劃分后結(jié)果為（）。A．40,38，46，7９，5６,84B．40,3８,４6，５6，79,８４Ｃ.４0,38，4６,8４，5６,７9D．38，４0，46，56,79，8４２9．在有序表{21，23，2８,３3，43,45,46,７3,77,78，８9,99，106}中，用折半查找值43時(shí)，經(jīng)（)次比較后查找成功。A．6B.3Ｃ．8Ｄ．430．排序方法中,從尚未排序序列中挑選元素,并將其依次放入已排序序列(初始為空)的一端的方法，稱為()排序。A.歸并B.插入C．快速D．選擇二、填空題1.本書中介紹的樹形結(jié)構(gòu)和_＿＿＿_(dá)_＿屬非線性結(jié)構(gòu)。２.在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域,它們是_____＿_(dá)、、右指針。3．設(shè)有一個(gè)長度為18的順序表，要在第4個(gè)元素之前插入２個(gè)元素（也就是插入元素作為新表的第5個(gè)和第4個(gè)元素),則最少要移動(dòng)元素的個(gè)數(shù)為（)。4．一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn),若它存在左、右孩子,則左、右孩子編號(hào)分別為＿_(dá)__＿＿、＿_(dá)＿_(dá)_＿＿_(dá)。５.在雙向鏈表中，要?jiǎng)h除p所指的結(jié)點(diǎn),可以先用語句(p->priｏr)－>ｎext=p－>ｎext;然再用語句_______＿。６.串的兩種最基本的存儲(chǔ)方式是_____＿＿_(dá)和___＿_(dá)__＿。７．在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行s-＞next=ｐ-＞next;和_____＿＿的操作.8.一棵有２ｎ-1個(gè)結(jié)點(diǎn)的二叉樹,其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為２,則該樹共有__＿_(dá)___個(gè)葉結(jié)點(diǎn)。9.一個(gè)棧和一個(gè)隊(duì)列的輸入序列都為aｂcdefｇ,它們也許有相同的輸出序列嗎？________＿。(若沒有則回答沒有,若有則寫出序列,進(jìn)棧出棧可以交替進(jìn)行)。1０.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有________個(gè)指針域?yàn)榭铡?1.從一個(gè)棧頂指針為tｏp的鏈棧中取棧頂元素,用d保存棧頂元素的值，可執(zhí)行＿＿_(dá)____＿。(結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐atａ)12.＿＿_(dá)＿_(dá)_＿_(dá)遍歷二叉排序樹可得到一個(gè)有序序列。1３.循環(huán)鏈隊(duì)列中,設(shè)fronｔ和ｒｅaｒ分別為隊(duì)頭和隊(duì)尾指針,（最多元素為MaｘSｉze,),判斷循環(huán)鏈隊(duì)列為空的條件是_＿_(dá)_＿_(dá)＿_(dá)為真。1４.如圖5所示的二叉樹，其后序遍歷序列為。eefgibachd圖５15.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表,設(shè)a是稀疏矩陣A相應(yīng)的三元組表類型(結(jié)構(gòu)體類型）變量，ａ中的一個(gè)成員項(xiàng)是三元組類型的結(jié)構(gòu)體數(shù)組dａｔａ，按書中定義,若a.daｔａ[0].i=2;a．ｄata[0].j=３;a.dａt(yī)a[０］．v=１6;它提供的Ａ數(shù)組的相關(guān)信息有___＿_(dá)__１6.如圖6所示的二叉樹,其先序遍歷序列為_＿_(dá)______。ggfabdec圖６1７.設(shè)有一棵深度為5的完全二叉樹,該樹共有２0個(gè)結(jié)點(diǎn),第五層上有個(gè)葉結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）18.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是___＿＿_(dá)的。(回答對(duì)的或不對(duì)的）19．中序遍歷______＿＿樹可得到一個(gè)有序序列。20．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是＿_(dá)______＿_(dá)的。（回答對(duì)的或不對(duì)的）21.如圖７所示的二叉樹，其后序遍歷序列為___＿_(dá)____。3c3c7gd6f5e4dc2b1a8hd9圖722.對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序,記錄序列按＿＿_(dá)＿_(dá)＿_(dá)_＿排序結(jié)果是唯一的。23.給定一組權(quán)重值,構(gòu)造哈夫曼樹，哈夫曼樹的高度一定是唯一的,這種說法是_＿＿_(dá)______的。(回答對(duì)的或不對(duì)的)24．按某關(guān)鍵字對(duì)記錄序列排序，若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1.（１）說明什么是頂點(diǎn)活動(dòng)網(wǎng)(AOV網(wǎng))和拓?fù)湫蛄?2)設(shè)有向圖G如下，寫出3種拓?fù)湫蛄?(3)在圖G中增長一條邊，使圖G僅有一條拓?fù)湫蛄衋abcd圖８２．設(shè)查找表為（16,１5，20,５３,64,７),（１)用冒泡法對(duì)該表進(jìn)行排序（規(guī)定升序排列),寫出每一趟的排序過程，通常對(duì)ｎ個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡?第ｊ趟要進(jìn)行多少次元素間的比較?(2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所相應(yīng)的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn)）3．如下是一棵二叉排序樹,A1,A2,…A9代表１,2，３,…9中各個(gè)不同數(shù)字,(1)給出對(duì)該樹中序遍歷的結(jié)果（2）A3,A５，A7的值各為多少?(3）請(qǐng)?jiān)谠摌渲性俨迦胍粋€(gè)結(jié)點(diǎn)9.5作為葉結(jié)點(diǎn)，并使它仍然是一棵二叉排序樹AA1A2A4A7A5A9A8A3A6圖94.(1)設(shè)有查找表{５,１4,2,6,１８，7,4,１6,3｝，依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹。(2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果。５.（1)設(shè)有查找表{17,26,14,1６,15,3０,18,19，28},依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹．(2)對(duì)上述二叉樹給出后序遍歷的結(jié)果(3).對(duì)上述二叉樹給出中后序遍歷的結(jié)果（４)）在上述二叉樹中查找元素15共要進(jìn)行多少次元素的比較?6．(1)對(duì)給定權(quán)值2,1,３，3，4，5，構(gòu)造哈夫曼樹。(２)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)途徑長度。四、程序填空題1．以下函數(shù)是二叉排序樹的查找算法,若二叉樹為空，則返回根結(jié)點(diǎn)的指針,否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p(查找成功p指向查到的樹結(jié)點(diǎn)，不成功ｐ指向?yàn)镹UＬL)完畢程序中的空格tｙｐedefstｒｕctBnoｄe{iｎtｋeｙ;struｃｔBnｏde*left；structBnode*ｒigｈt；}Bｎｏde；Bnoｄe*BＳearｃh（Ｂnｏde*bｔ,iｎtk)／*bt用于接受二叉排序樹的根結(jié)點(diǎn)的指針,k用以接受要查找的關(guān)鍵字*/｛Bnｏde*p;ｉｆ(bｔ==__＿(１)__＿_(dá)_)return（bt);p=ｂt;whｉｌe(p->key!=__(2）______) ?{if(k<p－>ｋey)??___(3)__＿_(dá)_；else＿＿_(dá)(4）＿_(dá)___;?if（p==ＮULＬ)bｒeak;}rｅturn(__＿(5)_____）；}}３.設(shè)有一個(gè)頭指針為hｅaｄ的不帶頭結(jié)點(diǎn)單向鏈表,ｐ、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中結(jié)點(diǎn)a,（設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同）,寫出相關(guān)語句（1).使該單向鏈表成為單向循環(huán)鏈表(２）插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p;x＝p-＞ｄatａ;whilｅ(__(１)＿_(dá)_）q=q->next;q-＞nexｔ=hｅaｄ;ｑ=p;p＝p－＞nｅxt；ｗhilｅ(p->ｄata!＝x）{q=p;_＿（2)＿_(dá)＿｝s-＞neｘt=p;__(3）_＿_(dá)答案一、單項(xiàng)選擇題1．C2．A3.A４．D5．D6.A7．B8．B9．A１0.A11．Ｂ12．C13．D14．Ｄ１5．B1６.A17.A１8.B19．A２0．Ｃ21.Ｃ２2．Ａ23．D24．B25．Ｃ2６．C27．B28.B29．Ｂ３0.Ｄ二、填空題1．圖狀結(jié)構(gòu)2．值域左指針3．15４.2i和2i+15.(p->nexｔ)->prｉor=p->prior；６．順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)7.p－>nexｔ=ｓ;８．n9.ａｂcdefg１０.ｎ+111．d=ｔｏｐ->data;12.中序13．fronｔ＝＝rｅar１4.ｇdbｅihfcａ15．A的第一個(gè)非零元素的下標(biāo)為２，3，元素為1６16.aｂdefcg17．５18．對(duì)的1９.二叉排序20．不對(duì)的２1.22.主關(guān)鍵字23．不對(duì)的24．關(guān)鍵字相等的記錄三、綜合應(yīng)用題1.(1)原序列1６15205３６4７151６2053７６4ｎ-1趟１51620753６4n-j次1516７205364１５71６205３64７1516２０5３6４71571520641653圖1０2．(1）原序列16152053６471516２０53764n-１-j次1５1６720536415７１６2053647１516205３6471571520641653圖11（3）平均查找長度=（1＊1+２*2+3*3）/6=14/6３.24246167318514圖12(2）中序遍歷中序2,3，４,5，6,7，14,16，１８4．(1)2246167318514圖13(2）中序遍歷中序2,3,4，5，6，7,14，16,18５．535341811763312wｐｌ1=4５1871871131233465圖１5wｐl２=４5535341811763312wpl1＝45四、程序填空題１.(１）NＵLL（2)k(3）p=p->left(4)p=p－>ｒighｔ(５)ｐ２.（１）＆a（2)dｎext=NULＬ(3）p->daｔa（4）p=p->neｘｔ(５)p!＝NULL3.（1）q－>next!=NULL（2)p＝p－>ｎext;(3)ｑ->nexｔ=s；4.(1）Pｏｓtorder(BT->ｌeft）（2）Pｏｓｔordｅr(ＢT-＞righｔ）(3)printｆ(“％c”,BＴ->ｄatａ)期末練習(xí)三一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表達(dá)是指()。A.數(shù)據(jù)元素之間的關(guān)系B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)Ｃ．?dāng)?shù)據(jù)元素的類型Ｄ.數(shù)據(jù)的邏輯結(jié)構(gòu)2．在數(shù)據(jù)結(jié)構(gòu)和算法中,與所使用的計(jì)算機(jī)有關(guān)的是（)。Ａ.數(shù)據(jù)元數(shù)間的抽象關(guān)系B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．算法的時(shí)間復(fù)雜度D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)3.結(jié)構(gòu)中的元素之間存在多對(duì)多的關(guān)系是()。A．集合B.線性結(jié)構(gòu)Ｃ.樹形結(jié)構(gòu)D．圖狀結(jié)構(gòu)４.對(duì)順序表，以下敘述中對(duì)的的是（）。A．用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素B．各個(gè)數(shù)據(jù)元素的首地址是連續(xù)的C.數(shù)據(jù)元素不能隨機(jī)訪問D.插入操作不需要移動(dòng)元素5.設(shè)有一個(gè)長度為2０的順序表，要在第5個(gè)元素之前插入1個(gè)元素(也就是插入元素作為新表的第5個(gè)元素）,則移動(dòng)元素個(gè)數(shù)為（)。A.１5B.１６C.５D.6．設(shè)有一個(gè)長度為２5的順序表，要?jiǎng)h除第10個(gè)元素（下標(biāo)從1開始），需移動(dòng)元素的個(gè)數(shù)為（）。A．9B．10C.15D.7．在一個(gè)尾指針為ｒear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個(gè)s所指的結(jié)點(diǎn),并作為第一個(gè)結(jié)點(diǎn),可執(zhí)行()。A．rｅarnｅxt=s;snexｔ＝rearnextB.rearnｅxt=snｅｘt;C．rear＝snｅxtD.sｎexｔ=reaｒｎeｘt;rearｎｅxt＝ｓ;8.設(shè)單向鏈表中,指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的直接后繼，則所需修改指針的操作為()。A.p－>next=ｐ->neｘt->next;?Ｂ.p=p->nexｔ;C.ｐ=p－＞neｘt->ｎeｘt； D.p－>ｎext＝p;9．元素ａ,b，c,ｄ按順序依次進(jìn)棧，則該棧的也許輸出序列是()（進(jìn)棧出棧可以交替進(jìn)行）。Ａ.ｃ,ａ,b,dＢ．ｄ,b,c,aC.a,ｃ,ｂ,ｄＤ．d，c,ａ,ｂ1０．元素1，3,5，7按順序依次進(jìn)棧，按該棧的也許輸出序列依次入隊(duì)列，該隊(duì)列的也許輸出序列是(）。(進(jìn)棧出?？梢越惶孢M(jìn)行）。A．7，5，3,1B．7,3,1，５C．7,5,1,3D．5,１，3，711.從一個(gè)棧頂指針為ｔop的鏈棧中取棧頂元素,用變量x保存該元素的值,則執(zhí)行（）。Ａ．ｘ＝ｔoｐ->datａ;tｏp=topnｅxt;Ｂ．ｘ=toｐ->dａt(yī)a;C．top=ｔｏp－>nｅxt;x=tｏｐ－＞ｄatａ；Ｄ．ｔｏp=top-＞neｘｔ;x=daｔａ;１2．對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行進(jìn)棧操作,設(shè)Ｐ為待進(jìn)棧的結(jié)點(diǎn),則執(zhí)行（）。Ａ.ｐ＝tｏp->next;top=topnｅｘt;B．ｐ-＞ｎext=top；C.ｐ->neｘt＝ｔoｐ;ｔop=p;Ｄ.tｏｐ=ｐ;1３．設(shè)有一個(gè)對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始），Ｂ數(shù)組共有55個(gè)元素,則該矩陣是（)階的對(duì)稱矩陣。A.5B．20Ｃ.10Ｄ．１5１4．設(shè)有一個(gè)18階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始),則數(shù)組中第33號(hào)元素相應(yīng)于矩陣中的元素是()。B.ａ7,6Ａ.a10，8C.a9,215.設(shè)有一個(gè)１8階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組Ｂ中（數(shù)組下標(biāo)從１開始)，則數(shù)組中第53號(hào)元素相應(yīng)于矩陣中的元素是(）。A．a(chǎn)8,５,B．a(chǎn)10，８C．ａ8,1,Ｄ.a7,61６．設(shè)有一個(gè)1７階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始)，則矩陣中元素a16在一維數(shù)組B中的下標(biāo)是（）。Ａ.4５，Ｂ.18C1７.以下程序段的結(jié)果是ｃ的值為（）。char*ａ[５]=｛“1237８”，“1237”,“１２36789”，“１237”，inti，ｃ=0;for(ｉ=0;ｉ＜５:i++)ｉｆ(SｔrCmp(a［i],“１237”A.２，B.５C．０Ｄ.１2３7１8．串函數(shù)StｒCmp(“ABＣd”,“ABCD”)的值為()。A.０B.-1１9．一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中,共有n個(gè)指針域被有效使用（即指針域?yàn)榉强眨?。該二叉樹?)個(gè)結(jié)點(diǎn)。A．n+１Ｂ．nC．ｎ-1Ｄ．n-22０．一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中有n個(gè)指針域?yàn)榭?該二叉樹共有()個(gè)結(jié)點(diǎn)。A.n+1Ｂ．nC.ｎ-1D.ｎ-22１.在一棵二叉樹中,若編號(hào)為ｉ的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號(hào)為（）。A.ｉ/２.０B.i/2+1C.２i+122．設(shè)一棵哈夫曼樹共有ｎ個(gè)非葉結(jié)點(diǎn)，則該樹有()個(gè)結(jié)點(diǎn)。A．2nB．２n+2Ｃ.２ｎ－1D.2ｎ+123．設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為２,該樹結(jié)點(diǎn)中共有2n個(gè)指針域?yàn)榭?。則該樹有(）個(gè)葉結(jié)點(diǎn)。Ａ．2nＢ.2n＋1C2４．一棵結(jié)點(diǎn)數(shù)31<ｎ<40的完全二叉樹,最后一層有4個(gè)結(jié)點(diǎn),則該樹有（)個(gè)葉結(jié)點(diǎn)Ａ．1８B．１7C.362５．已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為(）。A.ａcｅdｆｂB.aecｆdbC．a(chǎn)ecdfbＤ．ａcebfdbbdfeca圖１２6.已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（）。A.abedｆcＢ．a(chǎn)cfeｂｄＣ.aebcfdＤ.aｅdfｂｃ２7.一組記錄的關(guān)鍵字序列為（42,37，6２,４0,３2，９２)，運(yùn)用快速排序算法,以第一個(gè)關(guān)鍵字為分割元素，算法通過一次劃分后結(jié)果為（)。Ａ．３２,37，40，42，62，92B．37,３2，４０，42,62，92C．32,40,3７,42,62，9２D.32，37，42,40，62，9228.一組記錄的關(guān)鍵字序列為（46,20,30,79，5６，3８,4０,84,９0,1１0),運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素,通過一次劃分后結(jié)果為（）。Ａ.２0,30，４0，38，46，7９,56，８4,90，1０0Ｂ.４0,20，3０,3８,46，５6,７9，84,９０,110C.3０，20,40,3８，46,8４,56，79，９０,100Ｄ．2０,３０３8，４0，46，5６,７9,8４，90,10029．一組記錄的關(guān)鍵字序列為(8０,57,４1,39，46,4７)，運(yùn)用堆排序(堆頂元素是最小元素）的方法建立的初始堆為()。A.39,46,41，57,８0，47B．39,４7，46，80，4１,57C．41，３９,4６，47,5７，80Ｄ.３9，80,46，47,41,５7bbdfeca圖230．一組記錄的關(guān)鍵字序列為（７５,６3,95，8０，53,４5，38，2０)，運(yùn)用堆排序（堆頂元素是最大元素)的方法建立的初始堆為（）。A.９5,80,75,63，53，4５,38，２0B.95，63，75,8０，53,45，38,２0c.95,80,4５,63,53,75，3８,20D.9５,8０，７5,20，53,4５，3８,63二、填空題1.數(shù)據(jù)元素可以有一個(gè)或＿_(dá)_____＿組成。2.數(shù)據(jù)元素之間的抽象關(guān)系稱為________結(jié)構(gòu)。3.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為線性結(jié)構(gòu)。而數(shù)據(jù)元素存在＿＿_(dá)＿_(dá)__的關(guān)系稱為圖狀結(jié)構(gòu)。４.規(guī)定在ｎ個(gè)數(shù)據(jù)元素中找值最大的元素,其基本操作為＿_(dá)_＿＿_(dá)__。算法的時(shí)間復(fù)雜度為＿_(dá)_＿_(dá)＿＿。5.設(shè)有一個(gè)長度為2５的順序表,要?jiǎng)h除前3個(gè)元素,則最少要移動(dòng)元素的個(gè)數(shù)為()。6．設(shè)有一個(gè)長度為２5的順序表,第8號(hào)元素到第２5號(hào)元素依次存放的值為8,9,10,1１,…,2５，某人想要?jiǎng)h除第８個(gè)元素，他的做法是從第25號(hào)元素開始,直到第9號(hào)元素依次向前移動(dòng)1個(gè)位置,其結(jié)果新表中第9號(hào)元素的值為（）。7.在雙向鏈表中，要?jiǎng)h除ｐ所指的結(jié)點(diǎn),其中所用的一條語句(p-＞pｒior)->ｎｅxt=p-＞neｘt；的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向＿_(dá)_＿_(dá)__＿。8．在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)(設(shè)q所指的結(jié)點(diǎn)已賦值),可以先用語句q-＞next=p->nｅxt;（p－>neｘt)->prｉｏr=q；然后再用語句q－>priｏr＝p;和語句__＿_(dá)_＿_(dá)_。9．設(shè)有一個(gè)頭指針為hｅａd的單向鏈表，p指向鏈表中的某結(jié)點(diǎn)，若要使該鏈表成為單向循環(huán)鏈表,可用語句whilｅ（ｐ->next!＝ＮULＬ）ｐ=p->nexｔ；和＿＿_(dá)___＿＿。10.在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。則可以用操作_____＿_(dá)_。（用一條語句)１１．向一個(gè)棧頂指針為ｔop的鏈棧中插入一個(gè)ｐ所指結(jié)點(diǎn)時(shí),某人用語句top=p;p->neｘｔ=tｏｐ；這樣做的結(jié)果使p所指向的結(jié)點(diǎn)的指針域指向了__＿_(dá)_＿_(dá)。12．向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)ｐ所指結(jié)點(diǎn)時(shí)，可執(zhí)行__＿_(dá)_＿_(dá)_操作。(填兩條語句,結(jié)點(diǎn)的指針域?yàn)閚ext）１3．在一個(gè)鏈隊(duì)中,設(shè)froｎt和ｒear分別為隊(duì)頭和隊(duì)尾指針,則s所指結(jié)點(diǎn)(數(shù)據(jù)域已賦值)的入隊(duì)操作為ｓ->ｎext＝NＵLL;.＿＿_(dá)__＿_(dá)_和rear＝s;１４．在一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)中,設(shè)ｆront和reaｒ分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為ｐ＝front->neｘt；_＿＿_(dá)___=ｐ->neｘt；(結(jié)點(diǎn)的指針域?yàn)閚ext，p為輔助用指針）１5．設(shè)有ｎ階對(duì)稱矩陣A,用一維數(shù)組ｓ壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開始,元素ｓ[26］相應(yīng)于A中的元素為_______。１6.設(shè)有n階對(duì)稱矩陣A，用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開始，最后一個(gè)元素的下標(biāo)為2７，則n＝_______。17.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，設(shè)a是稀疏矩陣Ａ相應(yīng)的三元組表類型（結(jié)構(gòu)體類型)變量,a中的一個(gè)成員項(xiàng)是三元組類型的結(jié)構(gòu)體數(shù)組data,按書中定義，若data的下標(biāo)從零開始,最后一個(gè)元素下標(biāo)為１0，又ｄata[10]．i=8；a.data［10].j=5;a.ｄata[10］．v=3６;它提供的A數(shù)組的相關(guān)信息有_______。１８.一棵３度的樹,其中3度結(jié)１個(gè)，2度結(jié)2個(gè)，１度結(jié)２個(gè)，則該樹共有__＿_(dá)___個(gè)葉結(jié)點(diǎn)。１9．設(shè)有一棵有78個(gè)結(jié)點(diǎn)的完全二叉樹，該樹共有＿_(dá)_＿_(dá)____層。(根所在結(jié)點(diǎn)為第1層)2０.一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹,其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為２,則該樹共有＿_(dá)_____個(gè)結(jié)點(diǎn)。21.對(duì)于一棵具有_______＿個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n+１個(gè)指針域空．22.如圖２所示的二叉樹,其中序遍歷序列為____＿_(dá)＿_(dá)＿。２3．如圖２所示的二叉樹，其中序遍歷序列為__＿_(dá)__＿_(dá)_。4g4g3f9a7b58e6c圖33c3c7gd65e4dc2b18hd9圖424.二叉排序樹或者是一棵空樹,或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹非空,則左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值;若它的右子樹非空，則右子的所有結(jié)點(diǎn)的值都大于(若允許結(jié)點(diǎn)有相同的值,則大于等于）它的根結(jié)點(diǎn)的值。這種說法是____＿＿＿_(dá)__的。(回答對(duì)的或不對(duì)的)三、綜合題1.（１）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac,試畫出該二叉樹。(2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出a、b、ｃ、d、e的大小關(guān)系。（３）給出該樹的前序遍歷序列。2.(1)以３，4，5，8，９，10作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2)一棵哈夫曼樹有2ｎ-1個(gè)結(jié)點(diǎn)，它是共有多少個(gè)權(quán)重值構(gòu)造而成的？簡述理由？3.(1)運(yùn)用篩選過程把序列{42，82，67,１０2，16,32，57，52}建成堆(小根堆)，畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程）。(2)寫出對(duì)上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。4．（1)簡述拓?fù)渑判虻沫h(huán)節(jié)。（２)說明有向圖的拓?fù)湫蛄胁灰欢ㄊ俏ㄒ坏囊蛩?。?)如何運(yùn)用拓?fù)渑判蛩惴ㄨb定圖是否存在回路。（４）設(shè)有向圖G如下，寫出一方面刪除頂點(diǎn)１的３種拓?fù)湫蛄小?1234543465圖５5．設(shè)查找表為(1１,12,13,14,15,１6,１7,18,19,2０,21),元素的下標(biāo)從0開始。（1）畫出對(duì)上述查找表進(jìn)行折半查找所相應(yīng)的鑒定樹（樹中結(jié)點(diǎn)用數(shù)值表達(dá)）(2)說明成功查找到元素15,１9各需要通過多少次比較？（3)說明查找不到元素10，１5.5各需要通過多少次比較?(4）給出中序遍歷鑒定樹的序列。6.設(shè)有序表為（21，22，２3，2４,25，26，２7,28,29，30,31,32)，元素的下標(biāo)從0開始。（1）說出有哪幾個(gè)元素需要通過4次元素間的比較才干成功查到。(2)畫出對(duì)上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹（樹結(jié)點(diǎn)用數(shù)值表達(dá)）(3）設(shè)查找元素為5,需要進(jìn)行多少次元素間的比較才干擬定不能查到。(4）求在等概率條件下，成功查找的平均比較次數(shù)?四、程序填空題１.以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在ａ[1],…ａ[ｎ]中,以ａ[0]作為輔助工作單元，以下程序是要把a(bǔ)[ｉ]插入到已有序的序列a[1],…a[i－1]中。voidbinｓort（NODEａ[],iｎtn)｛iｎtx,ｉ，j,ｓ，k,m;ｆor(i=2;i<=_＿(1)_＿_(dá)；i++）{a［0]=a[i]；ｘ=a[ｉ]．key；s=１;j＝i-1;while(s＜=j）｛ｍ＝__(２)_＿_(dá)ｉf(x＜a[m].kｅy)__(3)__＿elｓe＿_(dá)(4）＿_(dá)_}for(ｋ=i-1；k>=ｊ+1;ｋ--)_＿(5）___=a［k］;a[j+1]=ａ[0];}}2．以下程序是快速排序的算法設(shè)待序的記錄序列存放在a[stａｒｔ］,…a[enｄ］中,按記錄的關(guān)鍵字進(jìn)行快速排序,先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用ｖoｉdqｕicｋsort(NODEa［］，intstａrt,inｔend){inti，ｊ；NODEｍｉd；ｉf(sｔaｒt＞=end)ｒetｕｒn;ｉ=stａｒt;j＝end;mid=a[i];