《數(shù)據(jù)結(jié)構(gòu)》 期末試題及答案 共3套

《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷1一，簡(jiǎn)答題(每題5分，共20分)1、具有n個(gè)結(jié)點(diǎn)的k又樹(shù)，若采用k又鏈表存儲(chǔ)，則空鏈域有多少個(gè)？(要求寫(xiě)出求解步驟)。2、分析二叉排序樹(shù)的性能(最好、最壞和平均查找性能)。3、希爾排序基本思想。4、圖遍歷中，設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組visited]]的作用。二、單項(xiàng)選擇題(每題1分，共10分)1、在一棵平衡二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是()A)-l~lB)-2~2C)1-2D)0~l2、在單鏈表中，下列說(shuō)法正確的是()A)單鏈表中頭結(jié)點(diǎn)是必不可少的；B)單鏈表中頭指針是必不可少的；C)在單鏈表中可以實(shí)現(xiàn)隨機(jī)存??；D)單鏈表的存儲(chǔ)密度小于順序表3、假設(shè)以數(shù)組A[M]存放循環(huán)隊(duì)列的元素，其頭尾指示器分別為front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為()oA)rear-front+1B)(rear-front+l)%MC)(front-rear+M)%MD)(rear-front+M)%M4、已知廣義表L=((a,b,c),(d,e,f)),運(yùn)用下列()運(yùn)算可以得到結(jié)果:eoA)head(tail(L))B)tail(head(L))C)head(tai1(head(tai1(L))))D)head(tai1(tai1(head(L))))5、線(xiàn)索二叉樹(shù)中，某結(jié)點(diǎn)p是葉子結(jié)點(diǎn)，下列()表達(dá)式的值為真。A)p->lchild==NULLB)p->ltag==1&&p->rtag==1C)p->ltag==0D)p->lchild==NULL&&p->rchild==NULL6、一個(gè)具有567個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為()A)9B)10C)11D)127、具有n個(gè)頂點(diǎn)的強(qiáng)連通圖，至少有()條邊A)n-1B)nC)n(n-l)D)n(n-l)/28、在含n個(gè)頂點(diǎn)和。條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為()A)eB)2eC)n2-eD)n2-2e

《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷2參考答案一、簡(jiǎn)答題1、n個(gè)結(jié)點(diǎn)的k叉樹(shù)采用k叉鏈表存儲(chǔ)，鏈域總數(shù)為k*n,又：『B+1.B為分支總數(shù)即非空鏈域總數(shù),B=n-1,所以空鏈域總數(shù)為:（k-l）*n+U2、訪(fǎng)問(wèn)標(biāo)志數(shù)組的作用是：保證圖中的每個(gè)頂點(diǎn)都被訪(fǎng)問(wèn)到，且僅訪(fǎng)問(wèn)一次。3、折半查找的前提條件是1）列表元素順序存儲(chǔ)：2）列表元素按關(guān)鍵字有序存儲(chǔ)：4、冒泡排序最好情況：移動(dòng)元素次數(shù)為0,關(guān)鍵字比較次數(shù)為：n-I次；冒泡排序最壞情況：移動(dòng)元素次數(shù)為3n*（n-l）/2,關(guān)鍵字比較次數(shù)為n*（n-l）/2o二、選擇題二、選擇題LA2.D3.D二、選擇題LA2.D3.D二、選擇題LA2.D3.D4.C5.C二、選擇題LA2.D3.D4.C5.C6.A7.D8.B9.DI0.B三、填空題三、填空題三、填空題1、O(log2n三、填空題1、O(log2n)5、最少k,最多2k-l2、p->itag==1&&p->rtag==13、n-14、稠密6、1.4237、高度為48、快速排序四、構(gòu)造題1.1）該樹(shù)的孩子兄弟表示法為：（2分）2）轉(zhuǎn)化的二叉樹(shù)為：（2分）3）先序遍歷序列為：ABECFGD（2分）后序遍歷序列為:EBFGCDA（2分）2.I）此為有向圖的鄰接表表示法，該圖為:2）深度優(yōu)先搜索得到的遍歷序列為：VI,V4,V5,V6,V2,V7,V3;深度優(yōu)先生成樹(shù)為：3）其鄰接矩陣表示法為：頂點(diǎn)數(shù)組：鄰接矩陣:1VI00011012V200010003V300000114V400000005V501000106V600000007V700111003、1）構(gòu)造的哈希表為：（4分）2)地址0I23456789元素63362240136比較次數(shù)112112(2分)查找成功時(shí)的ASL=(l+l+2+l+l+2)/6=8/6or4/3(2分)查找不成功時(shí)的ASL=(4+3+24-1+1+4+3)/7=18/74、據(jù)題意，欲得到遞增有序，需要建大根堆（I分）。建初堆過(guò)程如下:初始狀態(tài)（從13開(kāi)始調(diào)整（1初始狀態(tài)（從13開(kāi)始調(diào)整（1分））初始狀態(tài)（從13開(kāi)始調(diào)整（1分））初始狀態(tài)（從13開(kāi)始調(diào)整（1分））（調(diào)整完畢，從15開(kāi)始調(diào)整（1初始狀態(tài)（從13開(kāi)始調(diào)整（1分））（調(diào)整完畢，從15開(kāi)始調(diào)整（1分））（調(diào)整完畢，從36開(kāi)始調(diào)整（1分））（調(diào)整完畢，從36開(kāi)始調(diào)整（1分））（調(diào)整完畢，從36開(kāi)始調(diào)整（1分））（調(diào)整完畢，建好初堆（1分））（調(diào)整完畢，從36開(kāi)始調(diào)整（1分））（調(diào)整完畢，建好初堆（1分））1)非遞歸算法：intBinSearch(RecordLislL,KeyTypek){low=1;high=L.length;while(low<=high){mid=(Iow+high)/2;if(L->r[midJ.key==k)returnmid;elseif(k<L->r[mid].key)high=mid-l;elselow=mid+l；)return0;)2)遞歸算法intBinSearch(RecordListL,KeyTypek,intlow,inthigh)//首次調(diào)用，low=1,high=L.length;{if(low<=high){mid=(low+high)/2;if(L->r[mid].kcy==k)returnmid;elseif(k<L->r[mid].key)retum(BinSearch(L,k,low,mid-l));elsereturn(BinSearch(L,k,mid+l,high));2、二叉樹(shù)中每個(gè)結(jié)點(diǎn)的level域置值算法：利用二叉樹(shù)的先序遍歷給每個(gè)結(jié)點(diǎn)的level域置值。voidSctLcvcl（BiTrecbt,intlayer）〃首次調(diào)用時(shí)，bt參數(shù)為二叉樹(shù)的根指針，layer參數(shù)值為1。{if（bt）{bt->lcvcl=laycr;SetLevel(bt->lchild?layer+1)；SctLcvel(bt-)rchild,laycr+1)；}注：此題也可以借助層次遍歷完成。數(shù)據(jù)結(jié)構(gòu)試卷3.（判斷題）在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中,其結(jié)點(diǎn)總數(shù)2n+lo（）（本題2.0分）rA、正確⑤B、錯(cuò)誤學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（判斷題）鏈表由頭指針唯一確定。（）（本題2.0分）'?A、正確CB、錯(cuò)誤學(xué)生答案：A標(biāo)準(zhǔn)答案：A解析：得分：2.（判斷題）完全二叉樹(shù)的葉子結(jié)點(diǎn)只能出現(xiàn)在最后一層上。（）（本題2.0分）rA、正確出B、錯(cuò)誤學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（判斷題）由樹(shù)轉(zhuǎn)化來(lái)的二叉樹(shù)一定沒(méi)有右子樹(shù)。（）（本題2.0分）⑸A、正確°B、錯(cuò)誤學(xué)生答案：A標(biāo)準(zhǔn)答案：A解析:得分：2.（判斷題）折半查找要求數(shù)據(jù)必須有序,且采用順序存儲(chǔ)結(jié)構(gòu)。（）（本題2.0分）④A、正確rB、錯(cuò)誤學(xué)生答案：A標(biāo)準(zhǔn)答案：A解析：得分：2.（判斷題）有回路的圖不能進(jìn)行拓樸排序。（）（本題2.0分）⑤A、正確CB、錯(cuò)誤學(xué)生答案：A標(biāo)準(zhǔn)答案：A解析：得分：2.（判斷題）在順序存儲(chǔ)的線(xiàn)性表中,邏輯上相鄰的兩個(gè)數(shù)據(jù)元素在物理位置上并不一定緊鄰。（）（本題2.0分）CA、正確⑤B、錯(cuò)誤學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（判斷題）鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表可以隨機(jī)存取。（）（本題2.0分）CA、正確④B、錯(cuò)誤學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（判斷題）散列表的查找效率主要取決于建表時(shí)所選取的散列函數(shù)和處理沖突的方法。（）（本題2.0分）eA、正確rB、錯(cuò)誤學(xué)生答案：A標(biāo)準(zhǔn)答案：A解析：得分：2.（判斷題）對(duì)于同一組記錄,生成的二叉排序樹(shù)的形態(tài)與記錄的輸入次序無(wú)關(guān)。（）（本題2.0分）A、正確⑤B、錯(cuò)誤學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（單選題）設(shè)有一個(gè)二維數(shù)組A[10][15],數(shù)組按行存放,假設(shè)A[0][0]存放位置在644,每個(gè)元素占一個(gè)空間,則A[4][5]在（）位置。（本題2.0分）rA、672CB、626⑤C、709rD、724學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：212.（單選題）順序查找方法適用于存儲(chǔ)結(jié)構(gòu)為（）的線(xiàn)性表。（本題2.0分）rA、壓縮存儲(chǔ)B、散列存儲(chǔ)C、順序存儲(chǔ)1D、以上都不是學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：213.(單選題)下面程序段的時(shí)間復(fù)雜度是()。for(i=0;i<n;i++)for(j=0;j<n;j++)(本題2.0分)CA、0(n)CB、O(n+n+l)CC、O(n+n)⑤D、O(n*n)學(xué)生答案：D標(biāo)準(zhǔn)答案：D解析：得分：214.(單選題)具有線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是()(本題2.0分)rA、樹(shù)B、圖9、對(duì)關(guān)鍵字序列（20,15,14,18,36,40,10,21）進(jìn)行快速排序，以第一個(gè)關(guān)鍵字為基準(zhǔn)得到的一趟劃分后的結(jié)果是（）oA）（10,15,14,18,20,36,40,21）B）（10,15,14,18,20,40,36,21）C）（10,15,14,20,18,40,36,21）D）（15,10,14,18,20,36,40,21）1（）、下列四種排序方法中，不穩(wěn)定的方法是（）。A）冒泡排序B）直接插入排序C）歸并排序D）快速排序三、填空題（每空2分，共20分）1、一個(gè)算法中，基本操作的語(yǔ)句頻度為（r+n210g2n+142//,該算法的時(shí)間復(fù)雜度為（）2、65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，按層次，從左到右編號(hào)，則最后一個(gè)非葉子結(jié)點(diǎn)的編號(hào)為（）oTOC\o"1-5"\h\z3、折半查找的兩個(gè)前提條件分別是（）和（）4、一個(gè)有序表為{4,8,12,16,20,24,28},采用折半查找法查找值為24時(shí)需要比較（）次。5、有向圖的鄰接表表示法中，第i條鏈上邊表結(jié)點(diǎn)的個(gè)數(shù)為該頂點(diǎn)的（）o6、已知一個(gè)帶頭結(jié)點(diǎn)的鏈棧，其頭指針為top；指針s指向一個(gè)新結(jié)點(diǎn)，要將結(jié)點(diǎn)S進(jìn)棧，則進(jìn)棧的語(yǔ)句應(yīng)為：（）和（）o7、有一種排序算法，其時(shí)間復(fù)雜度為O（/）,關(guān)鍵字比較次數(shù)與待排序記錄的初始排列順序無(wú)關(guān)且排序不穩(wěn)定，則該排序算法是（）8、對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，會(huì)得到一個(gè)（）序列。四、構(gòu)造題（每題6分，共30分）1、假定用于通信的某電文僅由8個(gè)字母構(gòu)成，各字母在電文中出現(xiàn)的頻率分別為（12,5,3,7,14,21,9,15）。請(qǐng)完成：1）構(gòu)造哈夫曼樹(shù)；2）為這8個(gè)字母設(shè)計(jì)不等長(zhǎng)的Huffman編碼，并計(jì)算WPLo2、己知一個(gè)圖的頂點(diǎn)為A、B、C、D,其鄰接矩陣的下三角元素全為0（包括主對(duì)角線(xiàn)元素），其他元素均為1。請(qǐng)畫(huà)出該圖，并給出其鄰接表。'?C、棧和隊(duì)列rD、以上都不對(duì)學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：2.（單選題）長(zhǎng)度為n的線(xiàn)性表,實(shí)施順序查找,在查找不成功時(shí),與關(guān)鍵字的比較次數(shù)為（）。（本題2.0分）rA、1⑸B、n+1Cc、n-1「D、n學(xué)生答案：B標(biāo)準(zhǔn)答案：B解析：得分：2.（單選題）設(shè)一個(gè)棧的輸入序列為12345,則借助一個(gè)棧所得到的輸出序列不可能是（）。（本題2.0分）rA、54321B、45321C、43512'D、12345學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：2.（單選題）一個(gè)隊(duì)列的入隊(duì)序列是A,B,C,D,則隊(duì)列的輸出序列是（）。（本題2.0分）rA、D,C,B,ArB、A,BCD⑤C、A,D,C,BCD、CBD,A學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：218.（單選題）將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始,每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)編號(hào)為1,則編號(hào)為17的結(jié)點(diǎn)的左孩子的編號(hào)為（）（本題2.0分）rA、4849C、34CD、35學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：219.（單選題）非空的循環(huán)單鏈表head的尾指針p滿(mǎn)足（）（本題2.0分）「A、p->next==NULLrB、p==NULLp->next==headp==head學(xué)生答案：C標(biāo)準(zhǔn)答案：C解析：得分：2.（單選題）若線(xiàn)性表最常用的操作是存取第i個(gè)元素及其前趨的值,則采用（）存儲(chǔ)方式節(jié)省時(shí)間。（本題2.0分）rA、單鏈表B、雙鏈表'C、單循環(huán)鏈表°D、期表學(xué)生答案：D標(biāo)準(zhǔn)答案：D解析：得分：2.（填空題）有一個(gè)不含頭結(jié)點(diǎn)的單鏈表,頭指針為head,則判斷其是否為空的條件為—o（本題2.0分）我的答案：head.next二二head標(biāo)準(zhǔn)答案：Head==NULL解析：得分：點(diǎn)評(píng)：.（填空題）在順序表（即順序存儲(chǔ)的線(xiàn)性表）中刪除一個(gè)元素,需要平均移動(dòng)—的元素。（本題2.0分）我的答案：1標(biāo)準(zhǔn)答案：n/2或一半解析:得分：點(diǎn)評(píng)：.（填空題）一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,利用選擇排序的方法，第一趟排序結(jié)果為（本題2.0分）我的答案：40,38,46,56,79,84標(biāo)準(zhǔn)答案：38,79,56,46,40,84解析：得分：點(diǎn)評(píng)：.（填空題）對(duì)于關(guān)鍵字序列（12,13,11,18,60,15,7,18,,100）,用篩選法建堆，必須從鍵值為—的結(jié)點(diǎn)開(kāi)始。（本題2.0分）我的答案：60標(biāo)準(zhǔn)答案：60解析：得分：點(diǎn)評(píng):25.（填空題）我們學(xué)過(guò)的構(gòu)造散列函數(shù)的方法有數(shù)字分析法、一分段疊加法、—、偽隨機(jī)數(shù)法。（本題4.0分）我的答案：（1）平方取中法（2）直接定址法標(biāo)準(zhǔn)答案：平方取中法除留余數(shù)法解析：得分：點(diǎn)評(píng)：.（填空題）在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹(shù)時(shí),只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè)—上,才會(huì)被加入到生成樹(shù)中。（本題2.0分）我的答案：連通分量標(biāo)準(zhǔn)答案：同一個(gè)連通分量或同一個(gè)集合解析：得分：點(diǎn)評(píng)：.（填空題）棧和隊(duì)列是運(yùn)算—的線(xiàn)性表。（本題2.0分）我的答案：受限標(biāo)準(zhǔn)答案：受限的解析：得分：點(diǎn)評(píng)：.（填空題）設(shè)有向圖的鄰接矩陣為A,如果圖中不存在弧＜Vi,Vj〉,則A[i,j]的值為（本題2.0分）我的答案：1標(biāo)準(zhǔn)答案：0解析：得分：點(diǎn)評(píng):29.（填空題）n個(gè)頂點(diǎn)的連通無(wú)向圖的生成樹(shù)含有一條邊。（本題2.0分）我的答案：n-1標(biāo)準(zhǔn)答案：n-1解析：得分：點(diǎn)評(píng)：.（簡(jiǎn)答題）給定關(guān)鍵字序列｛32,13,49,55,22,38,21）,散列函數(shù)為H（k）=k%7,散列表的地址從0到6,用線(xiàn)性探測(cè)法解決沖突,建立散列表ht。（本題20.0分）我的答案：k:32134955223821k%7：46061301地址：01234526關(guān)鍵字：49552238322113標(biāo)準(zhǔn)答案：解析：???0???1?,?2????3??4一?5???6????49|552238322113得分：點(diǎn)評(píng)：.（簡(jiǎn)答題）給定葉子結(jié)點(diǎn)權(quán)值：（3,35,13,15,20,5,9）,構(gòu)造哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度。（本題20.0分）我的答案：樹(shù)帶權(quán)路徑長(zhǎng)度254得分：點(diǎn)評(píng)：3、用普利姆算法從頂點(diǎn)A出發(fā),構(gòu)造圖1所示連通網(wǎng)的最小生成樹(shù)（寫(xiě)出過(guò)程）。圖14、一個(gè)線(xiàn)性序列{38,25,74,63,52,48},假定采用散列函數(shù)Hash（key尸key%7來(lái)計(jì)算散列地址，將其散列存儲(chǔ)在A[0?9]中，采用線(xiàn)性探測(cè)再散列解決沖突。構(gòu)造哈希表，并計(jì)算等概率情況下的查找成功和不成功的平均查找長(zhǎng)度。5、對(duì)序列{57,40,38,11,13,34,48,75,6,19,9,7},采用堆排序算法進(jìn)行遞減排序，請(qǐng)構(gòu)造相應(yīng)的初始堆即建初堆（只寫(xiě)初堆結(jié)果即可）。五、算法設(shè)計(jì)題（每題10分共20分）注：算法設(shè)計(jì)題只要求給出描述算法的子函數(shù)，不需要編寫(xiě)完整的實(shí)現(xiàn)程序。1、在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)列中只有尾指針rear,請(qǐng)給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過(guò)程。隊(duì)列的定義如下：typedefstructNode（QueueElementTypedata;/*數(shù)據(jù)域*/structNode*next;/*指針域*/）LinkQueueNode,*LinkQueue;2、假設(shè)二叉樹(shù)上的結(jié)點(diǎn)值各不相同，設(shè)計(jì)一個(gè)在二叉樹(shù)中求值為e的結(jié)點(diǎn)的雙親結(jié)點(diǎn)。函數(shù)名已給出，如下：/*若。有雙親，則返回雙親結(jié)點(diǎn)指針；若e是根結(jié)點(diǎn)或二叉樹(shù)中無(wú)e結(jié)點(diǎn)，則返回NULL*/BiTNode*Parent（BiTreebt,ElemTypee）《數(shù)據(jù)結(jié)構(gòu)》期末考試

試卷1參考答案一、簡(jiǎn)答題(5分*4=20分)1、n個(gè)結(jié)點(diǎn)的k叉樹(shù)，共nk個(gè)鏈域；分支樹(shù)為n-1個(gè)，即n-1個(gè)非鏈域，則空鏈域有nk-n+1個(gè)2、當(dāng)二叉排序樹(shù)的左右子樹(shù)比較均衡時(shí),查找性能最好，此時(shí)時(shí)間復(fù)雜度為O(nlogn)；當(dāng)二叉排序樹(shù)每個(gè)結(jié)點(diǎn)為單分支時(shí)，查找性能最差，與順序查找類(lèi)似，此時(shí)時(shí)間復(fù)雜度為0(/)。但二叉排序的平均查找時(shí)間復(fù)雜度為O(nlogn)。3、按某個(gè)間隔，將待排序記錄序列分割成若干個(gè)子序列，分別進(jìn)行直接插入排序：繼續(xù)縮小間隔，對(duì)每個(gè)子序列進(jìn)行直接插入排序；最后再對(duì)全部記錄進(jìn)行一次直接插入排序。4、防止重復(fù)訪(fǎng)問(wèn)；防止遺漏訪(fǎng)問(wèn)。二、選擇題(I分*10=10分)(1-5)ADDC(6-10)BBDB三、填空題(2分*10=20分)1、O(n)或O(n+logn)3、元素有序順序存儲(chǔ)5、出度7、簡(jiǎn)單選擇排序2、324、26、s->next=top->next;top->next=s;8、遞增或非遞減或從小到大四、構(gòu)造題(6分*6=3。分)1、(該哈夫曼樹(shù)有多種形態(tài))WPL=21*2+(14+15+9+12+7)*3+(5+3)*4=2454、構(gòu)造的哈希表為：6338257452480123456789①①①②④②ASLsucc=(1+1+1+2+2+4)/6=11/ASLuncuss=(2+1+1+6=5+4+3)/7=5、五、算法題(10分*2=20分)1、intEntcrQucuc(LinkQucucrcar,ElcmTyp({LinkQueueNode*newNocle;newNode=(LinkQueue)malloc(sizeof(Liiif(!newNode)returnfalse;newNode->data=x;newNode->next=rear->next;rear->next=newNode;rear=newNode;622/7Jx)〃進(jìn)隊(duì)nkQueueNode));returntrue;intDeleteQueue(LinkQueuerear,ElemType*x)〃出隊(duì)(if(rcar->ncxt==rcar)returnfalse;p=rear->next->next;rear->next->next=p->nexl;*x=p->data;free(p);returntrue;IBiTNode*Parent(BiTreebt,ElemTypee)//找e結(jié)點(diǎn)的雙親(BiTNode*p=NULL;if(bt==NULL)returnNULL;if(bt->LChild->data==e||bt->RChild->data==e)〃訪(fǎng)問(wèn)根returnbt;p=Parenl(bl->LChild,e);〃在左子樹(shù)上找if(!p)p=parent(bt->RChild,e)〃在右子樹(shù)上找returnp;《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷2

一、簡(jiǎn)答題（每題5分，共20分）1、一棵有n個(gè)結(jié)點(diǎn)的k叉樹(shù)采用k叉鏈表存儲(chǔ)，空鏈域的總數(shù)目是多少？寫(xiě)出求解過(guò)程。2、在圖的遍歷中，設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組的作用是什么？3、折半查找的前提條件是什么？4、分析冒泡排序的最好性能和最壞性能（性能即關(guān)鍵字比較次數(shù)和移動(dòng)元素的次數(shù)）。二、單項(xiàng)選擇題（每題1分，共10分）TOC\o"1-5"\h\z1、棧和隊(duì)列的共同特點(diǎn)是（）oA）只允許在端點(diǎn)處插入和刪除元素B）都是先進(jìn)后出C）都是先進(jìn)先出D）沒(méi)有共同點(diǎn)100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)采用順序存儲(chǔ)，從1開(kāi)始按層次編號(hào)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)應(yīng)該是（）oA）100B）49C）5（）D）513、在順序存儲(chǔ)的線(xiàn)性表上R[3]上，從前向后進(jìn)行順序查找。若查找第一個(gè)元素的概率是1/2,查找第二個(gè)元素的概率是1/3,查找第三個(gè)元素的概率是1/6?則查找成功的平均查找長(zhǎng)度為（）。A）7/3B）2C）3D）5/34、在一個(gè)有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的入度之和為（）A）n-sB）nC）sD）s-15、設(shè)某二叉樹(shù)中度數(shù)為。的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為Ni,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,則下列等式成立的是（）。A）N0=Ni+lB）No=Ni+N2C）No=N2+1D）N0=2Ni+16、設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。A）5B）6C）7D）87、己知單鏈表中的指針p所指的結(jié)點(diǎn)不是鏈尾結(jié)點(diǎn)，若在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)，應(yīng)執(zhí)行（）oA)s->next=pA)s->next=p;p->next=s;C)s->next=p->next;p=s;A)s->next=p;p->next=s;C)s->next=p->next;p=s;B)p->next=s;s->next=p;D)s->next=p->next;p->next=s;8、設(shè)用鄰接矩陣A表示有向圖A)s->next=p;p->next=s;C)s->next=p->next;p=s;A）第i行非0元素的個(gè)數(shù)之和B）第i列非0元素的個(gè)數(shù)之和C）第i行0元素的個(gè)數(shù)之和D）第i列0元素的個(gè)數(shù)之和9、排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是（）排序方法的基本思想。A）堆排序B）直接插入排序C）快速排序D）冒泡排序10、設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。A）快速排序B）堆排序C）歸并排序