2023年電大數(shù)據(jù)結(jié)構(gòu)本期末復(fù)習(xí)材料

中央電大開(kāi)放本科計(jì)算機(jī)科學(xué)與技術(shù)數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習(xí)一、單項(xiàng)選擇題１.數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它（C）。Ａ．只能有一個(gè)數(shù)據(jù)項(xiàng)組成B.至少有二個(gè)數(shù)據(jù)項(xiàng)組成C.可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成D．至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型２．一種邏輯結(jié)構(gòu)（A）存儲(chǔ)結(jié)構(gòu)。Ａ.可以有不同的B.只能有唯一的C.的數(shù)據(jù)元素在計(jì)算機(jī)中的表達(dá)稱為D．的數(shù)據(jù)元素之間的關(guān)系稱為3.線性表的順序結(jié)構(gòu)中，(C)。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問(wèn)的C.邏輯上相鄰的元素在物理位置上也相鄰D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高４．以下說(shuō)法中不對(duì)的的是（B)。A．雙向循環(huán)鏈表中每個(gè)結(jié)點(diǎn)需要包含兩個(gè)指針域B．已知單向鏈表中任一結(jié)點(diǎn)的指針就能訪問(wèn)到鏈表中每個(gè)結(jié)點(diǎn)C.順序存儲(chǔ)的線性鏈表是可以隨機(jī)訪問(wèn)的Ｄ.單向循環(huán)鏈表中尾結(jié)點(diǎn)的指針域中存放的是頭指針5．以下表中可以隨機(jī)訪問(wèn)的是（Ｄ）。Ａ.單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D.順序表6．雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)類型為:struｃtnode｛ｉｎtdaｔa;strucｔｎｏde*nexｔ;/*指向直接后繼*／sｔructnodｅ*prior;}；設(shè)p指向表中某一結(jié)點(diǎn)，要顯示ｐ所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的數(shù)據(jù)元素，可用操作(B）。A．prｉntf(“%d”,p－＞neｘt->data)；B.pｒｉntｆ(“%d”,ｐ->prior->ｄａt(yī)ａ);C.priｎtｆ(“%ｄ”,ｐ->ｐriｏr->ｎｅxt);Ｄ．prｉｎtf(“%ｄ”,p->data);7.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為ｎ,對(duì)于刪除操作，設(shè)刪除位置是等概率的,則刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為（Ａ）。A．(ｎ+１)／2Ｂ.ｎC．2nD.n-i８.一個(gè)棧的進(jìn)棧序列是eｆgh，則棧的不也許的出棧序列是(D)（進(jìn)出棧操作可以交替進(jìn)行）。A．ｈgｆｅＢ.gfehC.fｇｅhD．ｅhfｇ9.設(shè)top是一個(gè)鏈棧的棧頂指針,棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成,設(shè)用x接受棧頂元素，則出棧操作為(A)。A.ｘ=ｔｏｐ－>daｔａ;toｐ=toｐ->ｎｅxt;B.ｔop＝top->next;x＝top->data;C．x=top->ｎext;ｔoｐ=top->data;D.toｐ->ｎｅxｔ=ｔop；ｘ=toｐ->daｔa；１0．設(shè)top是一個(gè)鏈棧的棧頂指針,棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成,設(shè)用x接受棧頂元素，則取棧頂元素的操作為（C)。A．ｔｏp－＞ｄaｔa=ｘ;B．toｐ=top－＞nｅxｔ;C.ｘ=tｏｐ->datａ;D.ｘ=top－>data;toｐ=top->ｎexｔ;１1．以下說(shuō)法對(duì)的的是（Ｃ)。Ａ．隊(duì)列是后進(jìn)先出B.棧的特點(diǎn)是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D.隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行13．串函數(shù)StｒCｍp(“abＡ”,”ａba”)的值為(D）。Ａ.1B．0C.“aｂAabａ”Ｄ.-114．cｈaｒ*ｐ；p＝StrCａt(yī)(“ABD”,”ABC”);Priｎtf(“％s”,ｐ);的顯示結(jié)果為(B)。A．-1B．ABDABＣC．ABD.115．設(shè)有一個(gè)12階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（矩陣A的第一個(gè)元素為a1，1，數(shù)組b的下標(biāo)從1開(kāi)始）,則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有(A)。A、７≤i≤10B、１1≤i≤15C、9≤i≤１４D、６≤i≤9１6.深度為5的滿二叉樹(shù)至多有（B）個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)為第一層)A．40B．３1C．34D.3517.已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（A)。A.2mＢ.ｍＣ．2ｍ+1Ｄ.m/218．已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則該圖的邊數(shù)為(D）。A．２ｍB.mＣ.２m+1D.m/2１９.以下說(shuō)法不對(duì)的的是（D)。A.連通圖G一定存在生成樹(shù)B.連通圖Ｇ的生成樹(shù)中一定包含G的所有頂點(diǎn)C．連通圖G的生成樹(shù)中不一定包含G的所有邊D．連通圖Ｇ的生成樹(shù)可以是不連通的20.以下說(shuō)法不對(duì)的的是(A)。A.連通圖Ｇ的生成樹(shù)一定是唯一的B.連通圖Ｇ一定存在生成樹(shù)C.連通圖G的生成樹(shù)中一定要包含Ｇ的所有頂點(diǎn)D．連通圖Ｇ的生成樹(shù)一定是連通并且不包含回路21.散列查找的原理是（Ａ）。A.在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C.按關(guān)鍵字值的比較進(jìn)行查找D．基于二分查找的方法22.有序表為{1，2,4,6，10,１８，20，32},用課本中折半查找算法查找值１８，經(jīng)(B)次比較后成功查到。Ａ.3B.２C．4D.523．排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?該排序算法是(A）。A.直接插入排序B.快速排序C．冒泡排序Ｄ．選擇排序24．在排序過(guò)程中，可以通過(guò)某一趟排序的相關(guān)操作所提供的信息,判斷序列是否已經(jīng)排好序,從而可以提前結(jié)束排序過(guò)程的排序算法是(A)。A．冒泡B.選擇C.直接插入Ｄ．折半插入2５．采用順序查找法對(duì)長(zhǎng)度為ｎ的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法）,最壞的情況下要進(jìn)行（B）次元素間的比較。A.n+2B.nＣ.n-１D.n/２26．用折半查找法,對(duì)長(zhǎng)度為12的有序的線性表進(jìn)行查找，最壞情況下要進(jìn)行(Ａ）次元素間的比較Ａ．４B．3Ｃ.５D.6２7.如圖若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為(D)。ababecdhgfB．a(chǎn)ｅbcghｄfC．a(chǎn)edfｂcghD.abecdfｇh圖12８.如圖若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點(diǎn)序列為（B)。bcbcgdafeB.aｅdｂｇfｃC．a(chǎn)ｃfｅbdgD.aecｂdgf2９.一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有（D）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）Ａ.10B．1３C．11D．1２3０.一棵哈夫曼樹(shù)總共有25個(gè)結(jié)點(diǎn)，該樹(shù)共有（A)個(gè)非葉結(jié)點(diǎn)（非終端結(jié)點(diǎn))。A.12B．13C.１4D.1531．針對(duì)線性表，在存儲(chǔ)后假如最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū),則采用(D）存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表３2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(Ｃ）。A．一定是不連續(xù)的B.必須是連續(xù)的C.可以連續(xù)也可以不連續(xù)D.部分地址必須是連續(xù)的３３.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的(D)結(jié)構(gòu)。A.物理B．存儲(chǔ)C.邏輯與物理D．邏輯34.帶頭結(jié)點(diǎn)的單向鏈表的頭指針為heaｄ，該鏈表為空的鑒定條件是(Ｃ)的值為真。Ａ.head＝＝NＵLLB.heａd－>next==hｅadC.heaｄ->next==NULＬD．heａd＝=head－>nｅｘt３5．以下特性中,（D）不是算法的特性。A．有窮性B．?dāng)M定性C.可行性D.有0個(gè)或多個(gè)輸出36.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n,對(duì)于插入操作，設(shè)插入位置是等概率的，則插入一個(gè)元素平均移動(dòng)元素的次數(shù)為(Ａ）。Ａ.n/２Ｂ.ｎC.ｎ-1D.n-i＋13７．設(shè)有一個(gè)長(zhǎng)度為n的順序表,要在第i個(gè)元素之前（也就是插入元素作為新表的第ｉ個(gè)元素),則移動(dòng)元素個(gè)數(shù)為(A)。A.ｎ-i＋１Ｂ．n-iC.n-i-1D.i38．一個(gè)棧的進(jìn)棧序列是５,６，7，8，則棧的不也許的出棧序列是（A）(進(jìn)出棧操作可以交替進(jìn)行）A.5,8,6，7Ｂ.7，6，８，５Ｃ．7,6，5,８D．8,7,6,５３9.棧的插入刪除操作在(D)進(jìn)行。A.棧底B.任意位置C．指定位置Ｄ．棧頂4０.棧和隊(duì)列的相同點(diǎn)是（Ｄ）。A．都是后進(jìn)先出Ｂ.都是后進(jìn)后出C.邏輯結(jié)構(gòu)與線性表不同D.邏輯結(jié)構(gòu)與線性表相同,都是操作規(guī)則受到限制的線性表4１.以下說(shuō)法對(duì)的的是（C)。A.棧的特點(diǎn)是先進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)后出B.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出Ｃ.棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出Ｄ.棧和隊(duì)列的特點(diǎn)都是先進(jìn)先出4２．在C語(yǔ)言中，運(yùn)用數(shù)組a存放字符串“Hello”，以下語(yǔ)句中對(duì)的的是(A）。A.chara[10］=“Hｅlｌo”;Ｂ．chara［1０];a=“Helｌo”;C.cｈａrａ[1０]=‘Helｌo’；D．ｃhaｒa[１0]＝{‘H’,’e’,’l’，’ｌ’,’o’};43.元素2，４,6,８按順序依次進(jìn)棧,則該棧的不也許輸出序列是（D）(進(jìn)棧出?？梢越惶孢M(jìn)行)。A．8，6，4，2B.2，4，６,8C．4,2,8,6D．8，6,2，444.設(shè)有一個(gè)15階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組ｂ中。(矩陣A的第一個(gè)元素為a1，1,數(shù)組ｂ的下標(biāo)從1開(kāi)始)，則數(shù)組元素ｂ［13]相應(yīng)A的矩陣元素是（A）。A.ａ5,３B.a６，４C．a(chǎn)7,2D．ａ6，８４5.設(shè)有一個(gè)1５階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開(kāi)始）,則矩陣中元素a7,6在一維數(shù)組Ｂ中的下標(biāo)是（Ｃ)。A.４2B.１3C．27D.324６.一棵完全二叉樹(shù)共有30個(gè)結(jié)點(diǎn),則該樹(shù)一共有（D)層(根結(jié)點(diǎn)所在層為第一層）。Ａ．6B．4C.3Ｄ．５4７.串函數(shù)StrCmｐ(“d”,“D”)的值為(B)。A.0B．１Ｃ．-1D．３48．以下說(shuō)法對(duì)的的是(D)。A.連通圖G的生成樹(shù)中不一定包含G的所有頂點(diǎn)B.連通圖G的生成樹(shù)中一定要包含G的所有邊Ｃ．連通圖G的生成樹(shù)一定是唯一的D.連通圖G一定存在生成樹(shù)49.在一棵二叉樹(shù)中,若編號(hào)為ｉ的結(jié)點(diǎn)存在右孩子,則右孩子的順序編號(hào)為（D)。Ａ.2ｉB.2i-1Ｃ.2i+2D．2i+150．對(duì)二叉排序樹(shù)進(jìn)行（Ｃ)遍歷,遍歷所得到的序列是有序序列。A.按層次Ｂ．前序Ｃ.中序D．后序5１.設(shè)一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，則該樹(shù)共有(Ｄ)個(gè)指針域?yàn)榭铡．2nB．2n+１Ｃ．2n+2D．n+152.以下排序算法中，在一趟排序過(guò)程中,除了其它相關(guān)操作外，只進(jìn)行一次元素間的互換的算法是（Ａ)。Ａ．直接選擇B．冒泡C.直接插入D．折半插入bdbdfeca圖１54.對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在等概率情況下，平均查找長(zhǎng)度為（B)。A．nB．（ｎ＋1)/２C．２nD．n－155．在有序表｛1，3，8，13，3３，42,46，６３，76,７8,86,97,100｝中,用折半查找值８6時(shí)，經(jīng)（D）次比較后查找成功。A.6B．3C．8D.４56.如圖若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為（A)。ababecdfgB.ａｅdcbgfC．ａｃfebdgＤ.aeｃbｄgf57.有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為（Ａ）。A.29/1０B．31／１０C．2６/10Ｄ．29/958.一棵哈夫曼樹(shù)有１2個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），該樹(shù)總共有(C)個(gè)結(jié)點(diǎn)。A．２2B.21C.２3D.２４59.一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85）,運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素，通過(guò)一次劃分后結(jié)果為（A)。A.3１,２9，37，４7，70，85B．２9，31,3７，4７,７0,８５Ｃ.31，29，37,70,47,85D.31，2９,37,85，４7,7060．隊(duì)列的刪除操作在(Ａ)進(jìn)行。Ａ．隊(duì)頭B.隊(duì)尾C.隊(duì)頭或隊(duì)尾Ｄ.在任意指定位置61．（A)是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A.數(shù)據(jù)對(duì)象B.數(shù)據(jù)元素C．?dāng)?shù)據(jù)結(jié)構(gòu)D．?dāng)?shù)據(jù)項(xiàng)62．設(shè)鏈表中的結(jié)點(diǎn)是NＯDE類型的結(jié)構(gòu)體變量,且有NODE*ｐ;為了申請(qǐng)一個(gè)新結(jié)點(diǎn),并由p指向該結(jié)點(diǎn)，可用以下語(yǔ)句(D)。A．p=(NODE*)mａlloc(siｚeof（p)）;B.p＝(*NＯDE)ｍａlloｃ(sizｅof(ＮODE));C．p＝(NＯDE)ｍalloc(sｉzeof(p)）；D.p＝(NODE＊)ｍaｌｌoc(sizｅｏf(NODＥ）);63．設(shè)順序存儲(chǔ)的線性長(zhǎng)度為n,要在第i個(gè)元素之前插入一個(gè)新元素，按課本的算法當(dāng)i=(C）時(shí),移動(dòng)元素次數(shù)為2A．n/２B．nC．n-1C．１６4.一個(gè)棧的進(jìn)棧序列是1,2,３,4，則棧的不也許的出棧序列是（D)(進(jìn)出棧操作可以交替進(jìn)行)A.3,2，4，1Ｂ．3,2，1,4C.４,3，2,1D.1，4，2，365．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域datａ和指針域ｎext組成,fｒｏnt和ｒｅａｒ分別為鏈隊(duì)列的頭指針和尾指針。設(shè)ｐ指向要入隊(duì)的新結(jié)點(diǎn)(該結(jié)點(diǎn)已被賦值）,則入隊(duì)操作為（Ａ）。A.ｒear->neｘt=p；ｒeａr＝p；Ｂ．rear－>neｘt=p;p=rｅar;Ｃ.p＝rｅａr－>nｅxt;rｅaｒ＝p;D.ｒｅar=p;reａｒ->next＝p;６6.以下說(shuō)法不對(duì)的的是(D)。Ａ．順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B．順序棧中,?？諘r(shí)再作出棧棧操作稱為“下溢”C.順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界,則隊(duì)列已空D．順序隊(duì)列中,當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界，則一定是隊(duì)列已滿67．設(shè)有一個(gè)2０階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中（矩陣A的第一個(gè)元素為a1１,數(shù)組b的下標(biāo)從1開(kāi)始),則矩陣元素ａ8，5在一維數(shù)組b中的下標(biāo)是(D)。A.30B.28C.４0Ｄ．３36８．已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則ｍ一定不也許是(D）。A．4B．８Ｃ．12D.９6９.以下說(shuō)法對(duì)的的是（C）。A．連通圖G的生成樹(shù)中可以包含回路B．連通圖G的生成樹(shù)可以是不連通的C．連通圖G的生成樹(shù)一定是連通而不包含回路的D.連通圖G的生成樹(shù)一定是唯一的7０．對(duì)ｎ個(gè)元素進(jìn)行冒泡排序，通常要進(jìn)行ｎ-1趟冒泡,在第ｊ趟冒泡中共要進(jìn)行（C)次元素間的比較。A.jB.j－1C．n－jＤ.n-j－171.在排序過(guò)程中，可以有效地減少一趟排序過(guò)程中元素間的比較次數(shù)的算法是(C）。Ａ.冒泡B.選擇C.折半插入D．直接插入7２.一棵哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)）,該樹(shù)總共有（B）個(gè)結(jié)點(diǎn)。Ａ．2ｎ－2B.2n-1C.2ｎD.2n+2７3．?dāng)?shù)據(jù)的（A）結(jié)構(gòu)與所使用的計(jì)算機(jī)無(wú)關(guān)。Ａ．邏輯B.物理C.存儲(chǔ)Ｄ．邏輯與存儲(chǔ)74．從n個(gè)數(shù)中選取最大元素（B)。A．基本操作是數(shù)據(jù)元素間的互換B．算法的時(shí)間復(fù)雜度是Ｏ(n)C.算法的時(shí)間復(fù)雜度是Ｏ(n2）D．需要進(jìn)行(ｎ+1）次數(shù)據(jù)元素間的比較75．設(shè)heaｄ為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點(diǎn),則滿足邏輯表達(dá)式（B)的值為真。A．p－>next=NULＬB．ｐ->ｎeｘt==heaｄＣ.p-＞nｅｘt=headＤ．p＝=NULＬ7６.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，要?jiǎng)h除第i個(gè)元素,按課本的算法，當(dāng)i＝(C)時(shí),移動(dòng)元素的次數(shù)為3。Ａ.3B．ｎ／２C.ｎ－３Ｄ.377．一個(gè)棧的進(jìn)棧序列是ａ,b，ｃ,d,則棧的不也許的出棧序列是（D）。A．ｄｃbaB.bcadC.cbadD.ａdbc78．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列,隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域daｔa和指針域next組成，fｒont和reaｒ分別為鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作,用ｘ保存出隊(duì)元素的值,p為指向結(jié)點(diǎn)類型的指針,可執(zhí)行如下操作：ｐ=frｏｎｔ->nｅxt;x=ｐ->data；然后指行（D)。Ａ．frｏnｔ=p->neｘt;B.fｒｏnt->neｘt＝p；Ｃ．front=ｐ;D.ｆronｔ－＞ｎext=p->ｎext;79.在C語(yǔ)言中,存儲(chǔ)字符串“ABCＤ”需要占用（Ｃ)字節(jié)。A.4Ｂ．2C.５D.380.設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。(矩陣A的第一個(gè)元素為a１，１,數(shù)組b的下標(biāo)從１開(kāi)始)，則矩陣元素a5,３相應(yīng)一維數(shù)組b的數(shù)組元素是(C）。A.b[18]B.b[8]C．b［13]D.b[1０］８1.設(shè)有一個(gè)1５階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。(矩陣A的第一個(gè)元素為a１,１，數(shù)組b的下標(biāo)從1開(kāi)始),則數(shù)組元素ｂ[13]相應(yīng)A的矩陣元素是(Ａ)。A．a(chǎn)5,３Ｂ．a(chǎn)6，4Ｃ．a(chǎn)7,2D．ａ６，882．深度為５的完全二叉樹(shù)共有２0個(gè)結(jié)點(diǎn),則第5層上有(C）個(gè)結(jié)點(diǎn)（根所在結(jié)點(diǎn)為第一層)。A.３Ｂ．８C.5D.68３．已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，且ｍ是以下4中情況之一,則m只也許是（D）。A.9B.7C.1５Ｄ.884．以下說(shuō)法對(duì)的的是（C)。A.連通圖G的生成樹(shù)中不一定包含G的所有頂點(diǎn)B．連通圖Ｇ的生成樹(shù)中一定要包含G的所有邊Ｃ.連通圖G一定存在生成樹(shù)Ｄ．連通圖Ｇ的生成樹(shù)一定是唯一的85．線性表只要以(Ｃ）方式存儲(chǔ)就能進(jìn)行折半查找。Ａ.鏈接B．順序Ｃ．關(guān)鍵字有序的順序Ｄ．二叉樹(shù)８6.對(duì)二叉排序樹(shù)進(jìn)行(C)遍歷，遍歷所得到的序列是有序序列。A．按層次B.前序C．中序Ｄ．后序87．對(duì)n個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了(C）次元素間的互換，則表白序列已經(jīng)排好序。A．1Ｂ.2Ｃ.０D.n－188.在對(duì)一組元素（64,48，106，33,25，82,70，55,９3)進(jìn)行直接插入排序時(shí)，當(dāng)進(jìn)行到要把第7個(gè)元素７0插入到已經(jīng)排好序的子表時(shí),為找到插入位置,需進(jìn)行(C）次元素間的比較(指由小到大排序)。A．6B.2C.3D.4ababecdfgA．a(chǎn)cｅbdｇfB．a(chǎn)ｃfedgｂC.abecdgfＤ.aｂｅｃfdg90．一棵哈夫曼樹(shù)有１0個(gè)非葉子結(jié)點(diǎn)（非終端結(jié)點(diǎn)），該樹(shù)總共有（A）個(gè)結(jié)點(diǎn)。Ａ.２1Ｂ．20C．22D.1９91．一棵哈夫曼樹(shù)有1２個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn)),該樹(shù)總共有(C）個(gè)結(jié)點(diǎn)。A．21B．2２C.23D.2４92.隊(duì)列的插入操作在(B)進(jìn)行。A.隊(duì)頭B.隊(duì)尾Ｃ．隊(duì)頭或隊(duì)尾D．在任意指定位置９3.隊(duì)列的刪除操作在（B)進(jìn)行。A.隊(duì)尾B．隊(duì)頭C.隊(duì)頭或隊(duì)尾D.在任意指定位置9４.鏈表所具有的特點(diǎn)是（C）。A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．占用連續(xù)的存儲(chǔ)空間C.插人刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)Ｄ.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)９5．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(C)的關(guān)系。Ａ.一對(duì)一B．一對(duì)多C.多對(duì)多Ｄ.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼9６.算法的時(shí)間復(fù)雜度與(C)有關(guān)。A.所使用的計(jì)算機(jī)Ｂ.與計(jì)算機(jī)的操作系統(tǒng)C.與算法自身D.與數(shù)據(jù)結(jié)構(gòu)97．４.在一個(gè)單鏈表中，p,q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且ｑ所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除ｑ所指結(jié)點(diǎn)，可用的語(yǔ)句是（)。Ａ.ｐ=q-＞rieｘtB．p->nｅxt=qC.p->next=q->nextD.q->ｎｅxt=NＵLL98.在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為(C)Ａ．ｒ=ｆ-＞nｅxt;B.r=r->neｘt;C.f=f->next;D.f=r－>next；9９.元素3,6，9按順序依次進(jìn)棧，則該棧的不也許輸出序列是(B）(進(jìn)棧出?？梢越惶孢M(jìn)行)Ａ.9，6,３B.９，3，６C.6，3，9Ｄ.3，9，6100．設(shè)有一個(gè)10階的對(duì)稱矩陣Ａ,采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始）,則矩陣中元素戊．s在一維數(shù)組B中的下標(biāo)是（)A.33B.32C.8５D.4110１．排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法,稱為(D)排序。A．歸并Ｂ.插人Ｃ.快速D.選擇1０2.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進(jìn)行比較(規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對(duì)的位置的方法是(Ｃ）。A.冒泡B.直接插入Ｃ.折半插入D．選擇排序二、填空題1．通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、__線性__、_樹(shù)形＿_(dá)、圖狀__四種類型。2.通常可以把一本具有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成＿_(dá)_樹(shù)形_結(jié)構(gòu)。3．設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ｅxt,頭指針為head，p指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表,可用語(yǔ)句___ｐ－>nｅxｔ=head;_____。4．要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn),若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行_s->nｅxt＝ｐ->next;＿_(dá)＿和p－>next=ｓ；的操作。5.設(shè)有一個(gè)單向循環(huán)鏈表,頭指針為head,鏈表中結(jié)點(diǎn)的指針域?yàn)椋睿鍃t,p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作_＿p->nexｔ=heａｄ；。6．設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作,用x保存出棧結(jié)點(diǎn)的值,棧結(jié)點(diǎn)的指針域?yàn)閚ｅxt,則可執(zhí)行x=hs->daｔa;＿_(dá)_hｓ=ｈｓ->ｎｅxt;__。7．在一個(gè)鏈隊(duì)中,f和r分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入一個(gè)ｓ所指結(jié)點(diǎn)的操作為_(kāi)_ｒ－>ｎｅxｔ=s_;ｒ=s；８．在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中,f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐atａ，指針域?yàn)閚ext,若要進(jìn)行出隊(duì)操作,并用變量x存放出隊(duì)元素的數(shù)據(jù)值,則相關(guān)操作為x=ｆ－＞ｄata；f＝f->next;。９．循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為ｒ,當(dāng)＿r==f＿時(shí)表白隊(duì)列為空。1０．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxＳｉｚｅ=８,采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=４，則當(dāng)隊(duì)尾指針rear=_4_時(shí)，隊(duì)列為空,當(dāng)ｒear＝_＿２＿_(dá)_時(shí),隊(duì)列有6個(gè)元素。11.稀疏矩陣存儲(chǔ)時(shí)，采用一個(gè)由＿_(dá)行號(hào)_＿、__＿列號(hào)_、__非零元__3部分信息組成的三元組唯一擬定矩陣中的一個(gè)非零元素。12．一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn),有６個(gè)葉結(jié)點(diǎn)，則該樹(shù)總共有＿＿11_＿_(dá)個(gè)結(jié)點(diǎn)。１3.一棵二叉樹(shù)順序編號(hào)為6的結(jié)點(diǎn)(樹(shù)中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉樹(shù)中相應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同),若它存在右孩子，則右孩子的編號(hào)為_(kāi)_＿_(dá)13____。14.按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有__先序_、＿＿中序＿、__后序__三種。15.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)__圖狀___結(jié)構(gòu)。1６．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為＿_(dá)物理(存儲(chǔ)）_結(jié)構(gòu)。１７．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為_(kāi)＿_(dá)樹(shù)形____＿結(jié)構(gòu)。efgibaefgibachd圖3gfabdgfabdec圖420.二叉樹(shù)為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是_＿_(dá)__錯(cuò)誤____＿的。(回答對(duì)的或不對(duì)的）21．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,當(dāng)插入一個(gè)新的隊(duì)列元素時(shí),尾指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí),頭指針的值增1。22．根據(jù)搜索方法的不同,圖的遍歷有__深度優(yōu)先、＿廣度優(yōu)先__＿兩種方法。23．循環(huán)隊(duì)列的引入，目的是為了克服假上溢。2４.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成_＿_(dá)_＿圖狀___結(jié)構(gòu)。25．結(jié)構(gòu)中的元素之間存在多對(duì)多的關(guān)系稱為_(kāi)__圖狀__＿結(jié)構(gòu)。2６．要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn),已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)椋頴xt,則可執(zhí)行_＿_(dá)＿ｑ-＞nexｔ=p－＞nexｔ;__。27.設(shè)有一個(gè)單向循環(huán)鏈表,結(jié)點(diǎn)的指針域?yàn)閚ｅxt，頭指針為ｈeａd，指針ｐ指向表中某結(jié)點(diǎn),若邏輯表達(dá)式_＿_(dá)p-＞neｘt=＝ｈeaｄ;__＿＿_(dá)的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。28.設(shè)有一個(gè)鏈棧，棧頂指針為ｈｓ,現(xiàn)有一個(gè)ｓ所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_s->ｎext=hs;和hs=s;29．順序存儲(chǔ)字符串“AＢCD”需要占用__＿５__個(gè)字節(jié)。3０．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaｘSiｚe=6，采用少用一個(gè)元素空間以有效地判斷?？栈驐M，若隊(duì)頭指針ｆroｎt=４，當(dāng)隊(duì)尾指針rｅar=_＿_(dá)_３____時(shí)隊(duì)滿，隊(duì)列中共有_＿_(dá)_5_＿＿＿個(gè)元素。3１.一棵二叉樹(shù)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5,單分支結(jié)點(diǎn)數(shù)為2，該樹(shù)共有__11____個(gè)結(jié)點(diǎn)32．設(shè)一棵完全二叉樹(shù),其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹(shù)一共有_____2１___個(gè)結(jié)點(diǎn)。３３．一棵二叉樹(shù)中順序編號(hào)為5的結(jié)點(diǎn)(樹(shù)中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉中相應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同），若它存在左孩子,則左孩子的編號(hào)為_(kāi)＿_(dá)_1０_＿＿＿。3４.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_(kāi)＿線性______結(jié)構(gòu)。３５．一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,則該樹(shù)共有_＿_(dá)２ｎ-１____個(gè)結(jié)點(diǎn)。３6.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__對(duì)的＿＿＿＿的。(回答對(duì)的或不對(duì)的)3７．串的兩種最基本的存儲(chǔ)方式分別是_順序存儲(chǔ)＿_(dá)___＿和＿＿_(dá)鏈?zhǔn)酱鎯?chǔ)_____。38．按某關(guān)鍵字對(duì)記錄序列排序，若關(guān)鍵字關(guān)鍵字相等的記錄的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。39.設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn),可用語(yǔ)句__＿_(dá)_＿＿ｐ=p-＞ｎeｘt;_。40.要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表,若結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為hｅad，尾指針為p，,則可執(zhí)行head＝head->ｎｅｘt；＿_(dá)＿_(dá)＿p->ｎｅｘt＝heａd；___。41．在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_結(jié)點(diǎn)的直接后繼，另一個(gè)指向__結(jié)點(diǎn)的直接前驅(qū)。4２.設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn),且有p－>ｎｅxt==ＮULL,通過(guò)操作___p－>next＝hｅad;__,就可使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表。43．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSiｚe，隊(duì)頭指針為f，隊(duì)尾指針為r,當(dāng)_（r＋1)%MaｘSｉｚe＝f_時(shí)表白隊(duì)列已滿。4４．從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值,可執(zhí)行ｘ=h－＞ｄａｔa；和___h=h-＞neｘt；。(結(jié)點(diǎn)的指針域?yàn)閚eｘt)4５．程序段inｔｃount＝0;cｈar＊s=”ＡＢCＤ”；whiｌｅ(*s!=’\０’){s++；couｎt+＋；}執(zhí)行后ｃｏｕnt＝＿_(dá)4_。46.兩個(gè)串相等的充足必要條件是_串長(zhǎng)度相等且相應(yīng)位置的字符相等。47．一棵二叉樹(shù)總結(jié)點(diǎn)數(shù)為11,葉結(jié)點(diǎn)數(shù)為5，該樹(shù)有__4＿_(dá)個(gè)雙分支結(jié)點(diǎn),__2__個(gè)單分支結(jié)點(diǎn)。48.對(duì)二叉樹(shù)的遍歷可分為_(kāi)_先序、中序、后序、層次四種不同的遍歷順序。４9.設(shè)一棵完全二叉樹(shù),其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9,該完全二叉樹(shù)一共有＿_(dá)＿_(dá)18__＿_(dá)個(gè)結(jié)點(diǎn)。50.雙向循環(huán)鏈表中，ｐ指向表中某結(jié)點(diǎn)，則通過(guò)p可以訪問(wèn)到ｐ所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)和直接前驅(qū)結(jié)點(diǎn)，這種說(shuō)法是__對(duì)的___＿_(dá)_的(回答對(duì)的或不對(duì)的)。51．棧和隊(duì)列的操作特點(diǎn)分別是＿_(dá)先進(jìn)后出（后進(jìn)先出）_和＿_(dá)先進(jìn)先出（后進(jìn)后出)＿_(dá)_。52.一棵有１4個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則它的最高層上有_＿_(dá)_7___個(gè)結(jié)點(diǎn)。efgibacefgibachd圖２５4.折半查找只合用于順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的有序表。55．哈希函數(shù)是記錄關(guān)鍵字值與該記錄___存儲(chǔ)地址__＿之間所構(gòu)造的相應(yīng)關(guān)系。56．深度為k的二叉樹(shù)最多有2k-１結(jié)點(diǎn)。５７．二叉樹(shù)排序中任一棵子樹(shù)都是二叉排序樹(shù)，這種說(shuō)法是__對(duì)的_＿_(dá)__的。(回答對(duì)的或不對(duì)的）58.串的兩種最基本的存儲(chǔ)方式是_＿＿順序存儲(chǔ)_和鏈?zhǔn)酱鎯?chǔ)__59．結(jié)構(gòu)中的元素之間存在多對(duì)多的關(guān)系稱為_(kāi)__＿_(dá)圖狀＿_(dá)_結(jié)構(gòu)。60.設(shè)有一個(gè)鏈棧,棧頂指針為ｈs,現(xiàn)有一個(gè)ｓ所指向的結(jié)點(diǎn)要入棧,則可執(zhí)行操作s-＞next=hs;_hs=s;。61．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxＳｉｚe＝6,采用少用一個(gè)元素空間以有效地判斷?？栈驐M，若隊(duì)頭指針ｆront=４,當(dāng)隊(duì)尾指針rｅar＝__３__時(shí)隊(duì)滿，隊(duì)列中共有___５__個(gè)元素。62．‘Ａ‘在存儲(chǔ)時(shí)占＿_(dá)1_個(gè)字節(jié)?！癆”在存儲(chǔ)時(shí)占__2__個(gè)字節(jié)。6３.程序段char*ｓ=”ａBcD”；n=0;ｗhｉlｅ（＊s!=’\０’）{ｉf(*s>＝’a’＆＆*s<=’z’)n+＋;s＋+;｝執(zhí)行后n=__＿2_＿_(dá)三、綜合題１.（1）已知某二叉樹(shù)的后序遍歷序列是ｄebca,中序遍歷序列是dbeａc,試畫出該二叉樹(shù)（2）若上述二叉樹(shù)的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒(méi)有相等的)，并恰好使該樹(shù)成為一棵二叉排序樹(shù),試給出a、b、c、d、ｅ的大小關(guān)系ababced答:(１)（２）d<ｂ<ｅ<a＜c(３）abdec２．（1)設(shè)ｈead１和ｐ１分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，ｈeａd2和p2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后,得到一個(gè)以head1為頭指針的單向循環(huán)鏈表,寫出其中兩個(gè)關(guān)鍵的賦值語(yǔ)句（不用完整程序,結(jié)點(diǎn)的鏈域?yàn)閚ext)。（2）單向鏈表的鏈域?yàn)閚ｅxt,設(shè)指針ｐ指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針s指向一個(gè)要插入鏈表的新結(jié)點(diǎn),現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后，某學(xué)生采用以下語(yǔ)句:p-＞ｎext＝ｓ;s-＞next=p-＞next；這樣做對(duì)的嗎?若對(duì)的則回答對(duì)的，若不對(duì)的則說(shuō)明應(yīng)如何改寫答：（1）p１-＞neｘt＝heａｄ2；ｐ2->ｎeｘt=head１;(2)不對(duì)，s-＞ｎeｘt＝p-＞next；ｐ-＞next＝s;３.(1）設(shè)有一個(gè)整數(shù)序列｛40,28,6,72,1０0,3,５４｝依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹(shù)40284028723100546答:（1)（2）ASL=（1x1+２x2＋3x3+4)/７=18／74.（１）畫出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的鑒定樹(shù)（以序號(hào)1，2,……10表達(dá)樹(shù)結(jié)點(diǎn))（2）對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長(zhǎng)度528452849631071（２)AＳL=(1x１+2ｘ2+3x4＋4x3）/１0=29/１05．（1)運(yùn)用篩選過(guò)程把序列{42,82，６7,10２，16,3２，５7,5２}建成堆（小根堆)，畫出相應(yīng)的完全二叉樹(shù)（不規(guī)定中間過(guò)程）（2）寫出對(duì)上述堆相應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的序列16423252571642325257678210242826752573216102初始樹(shù)堆初始樹(shù)堆（2）10２，5２，42,８２,16，67，32,５76．（1）運(yùn)用篩選法,把序列｛37,77,６２，97,1１，2７，５２，47}建成堆（小根堆）,畫出相應(yīng)的完全二叉樹(shù)（2）寫出對(duì)上述堆所相應(yīng)的二叉樹(shù)進(jìn)行前序遍歷得到的序列初始樹(shù)堆答:（1）初始樹(shù)堆373777624752271197(2）11，３7,4７,97,７7,27,6２，5２7．(1）一組記錄的關(guān)鍵字序列為{４5,40,65，４３,３５,9５}寫出運(yùn)用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)（2）同樣對(duì)序列{４5,40，65,4３,3５,95}運(yùn)用直接插入排序，寫出逐次插入過(guò)程(從第一個(gè)元素一直到第六個(gè)元素)。答：（1)４5４0６5４３35９5(2）4０４565433595３５4０6５４3３５9５404345６53５９５35４0654365953５404３４565953５404343659５8．設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表,頭指針為heaｄ,結(jié)點(diǎn)類型為NODＥ，每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域data和一個(gè)指針域nｅxt，該鏈表有兩個(gè)結(jié)點(diǎn)，p指向第二個(gè)結(jié)點(diǎn)（尾結(jié)點(diǎn)),按以下規(guī)定寫出相應(yīng)語(yǔ)句(不規(guī)定完整程序，(1)、（2)、(3)、(4）是一個(gè)連續(xù)的過(guò)程）。(１)新開(kāi)辟一個(gè)結(jié)點(diǎn),使指針s指向該結(jié)點(diǎn)，結(jié)點(diǎn)的數(shù)據(jù)成員data賦值為1(２）把該結(jié)點(diǎn)插入鏈表的尾部,釋放指針ｓ的指向(3)刪除鏈表的第一個(gè)結(jié)點(diǎn)（4)已知p1指向另一個(gè)新結(jié)點(diǎn),把它插入到p所指結(jié)點(diǎn)和尾結(jié)點(diǎn)之間答:(1)ｓ＝(NＯDE*)malloc(siｚeof(NODＥ)）;ｓ->data＝1；（2)p->neｘt=s;s－>nｅxｔ=ＮULL；free（s)(3)hｅａd=hｅad-＞neｘｔ；（4）p1->ｎeｘｔ=ｐ->neｘt；113727475211372747526277979.(1)運(yùn)用篩選過(guò)程把序列｛4２，82,６7,102,16，3２,57，5２}建成堆(小根堆),畫出相應(yīng)的完全二叉樹(shù)（不規(guī)定中間過(guò)程）（2)寫出對(duì)上述堆相應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的序列答：（1）16421642325257678210242826752573216102初始樹(shù)初始樹(shù)堆(２）１02,52，42，82,１6,６7,3２，5７1０.(1）設(shè)有序列{10，12，15,19,２2,2５,100，130,150，200｝畫出對(duì)上述序列進(jìn)行折半查找的鑒定樹(shù)(以序列中的元素作為樹(shù)的結(jié)點(diǎn)）2212221213019150251520010010答:（1）（2)4次;3次1１.(1）設(shè)有一個(gè)整數(shù)序列{５0,38,16,82，11０，１3，６4},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹(shù)（2）運(yùn)用上述二叉排序樹(shù),為了查找110，經(jīng)多少次元素間的比較能成功查到，為了查找15,經(jīng)多少次元素間的比較可知道查找失敗。答:5038503882131106416(2）三次;四次１2.(1)設(shè)有查找表{5，14,2,6,1８,7,4,16,３},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。24246167318514答：(1)（２)中序遍歷:中序2,3，4，5,6，7，1４,1６,1813.（１）已知某二叉樹(shù)的先序遍歷序列是aeｃdb，中序遍歷序列是eaｄcｂ,試畫出該二叉樹(shù)(2）給出上述二叉樹(shù)的后序遍歷序列(3）若上述二叉樹(shù)的各個(gè)結(jié)點(diǎn)的字符分別是1,2，3，4，５,并恰好使該樹(shù)成為一棵二叉排序樹(shù),試問(wèn)a、ｂ、c、d、e的值各為多少？aecbaecbd（2)edbca（3）e=1,a＝2,d＝3,c=4，ｂ＝514.(1)設(shè)有一個(gè)整數(shù)序列｛40，2８,6,7２,100，３，５4｝依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(shù)(2)對(duì)上述二叉排序樹(shù),在等概率條件下,求成功查找的平均查找長(zhǎng)度答:(１）404028723100546（2)AＳL=（1x１+2x2+３x3+4)/７=18/71５.(1）給定數(shù)列{8,17，５,９,２１,10，７，19,6}，依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(shù)(2）對(duì)上述二叉樹(shù)給出中序遍歷得到的序列851768517621971910（2)5，６，7,8，9,10，17,１8,19，211６．(1）運(yùn)用篩選過(guò)程把序列{42,8２，67,１02，1６,32,57，52}建成堆(小根堆），畫出相應(yīng)的完全二叉樹(shù)（不規(guī)定中間過(guò)程)(２）寫出對(duì)上述堆相應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的序列1642164232525767821024282675242826752573216102初始樹(shù)堆初始樹(shù)堆（2）10２,５２,42,82，16，67,３2，5７17．（1）以給定權(quán)重值１，2，12,13，20,2５為葉結(jié)點(diǎn)，建立一棵哈夫曼樹(shù)(２)若哈夫曼樹(shù)有n個(gè)非葉子結(jié)點(diǎn),則樹(shù)中共有多少結(jié)點(diǎn)。對(duì)給定的一組權(quán)重值建立的棵哈夫曼樹(shù)是否一定唯一答：（1)28284513213573209131525012321（2)2ｎ-1不一定唯一四、程序填空題１．以下函數(shù)在a［0]到a［ｎ-1]中,用折半查找算法查找關(guān)鍵字等于k的記錄,查找成功返回該記錄的下標(biāo),失敗時(shí)返回-１,完畢程序中的空格ｔypｅdefstrｕct{intkｅy；……}ＮOＤE;ｉｎｔBinary_Ｓearch(NODEa[]，intn，iｎtk)｛intｌｏw,mid,hiｇｈ;low=0；high=n-1;whｉｌe(__＿low<=hiｇｈ_＿＿_(dá)_）{mｉd=(lｏｗ+high)/２；if(a[ｍid].keｙ==k)rｅtuｒｎ__ｍｉd)＿_(dá)____; elsｅif（_＿_(dá)a[mid].keｙ<k；＿_(dá)___)low=ｍid+1; eｌse_＿h(yuǎn)igh＝mid-1___；?｝＿_(dá)＿returｎ-１____； }2．以下函數(shù)為直接選擇排序算法,對(duì)a[1],a[２],…a[n]中的記錄進(jìn)行直接選擇排序，完畢程序中的空格tｙpｅdefstｒuｃt{ｉntkeｙ；……}NODE;vｏiｄseｌsoｒt（NODEa［],intn)｛?ｉnｔi,j，k;?NODEtｅｍp；?fｏr(ｉ=１;i＜=_＿n-１__;i++)?{? k＝i；??ｆor(ｊ=i+1;j<＝＿_(dá)_ｎ＿_(dá)＿_(dá)_;ｊ++)???if(a[j].ｋｅy<ａ［ｋ]．