數(shù)據(jù)結(jié)構(gòu)練習(xí)題

數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:<<數(shù)據(jù)結(jié)構(gòu)>>綜合練習(xí)2得分評(píng)卷一．單選題（本大題共6小題，每空2分，共12分，答案填在括號(hào)處）1．下面程序段的時(shí)間復(fù)雜度T(n)=()for(inti=1;i<=m;i++)a[i]=0;.n，其輸出序列為p1,p2,...,pn，若p1=n，則pi(1<i<=n)為()+1D.不確定4．循環(huán)隊(duì)列用數(shù)組q[m]存放其元素值，已知其頭尾指針?lè)謩e是front和rear，front指向?qū)︻^的前一位置，則當(dāng)前隊(duì)列為滿的條件是()==rear+1==rear==rear+1==(rear+1)%m5．一棵滿二叉樹(shù)有n個(gè)結(jié)點(diǎn)，其中m個(gè)是樹(shù)葉，深度為h，則()=2m=2h=n-1=2h-16．在n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為()得分評(píng)卷二．填空題（本大題共6小題，每空1分，共7分，答案填在橫線處）1．在具有n個(gè)結(jié)點(diǎn)的順序表(a1,a2,…,an)中刪除一個(gè)結(jié)點(diǎn)，表中結(jié)點(diǎn)平均移動(dòng)次數(shù)為_(kāi)___________。2．在一個(gè)棧頂指針為ls的鏈棧中壓入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行_和______________操作。3．在矩陣的壓縮存儲(chǔ)中，只需將對(duì)稱矩陣a[n][n]的下三角壓縮到sa[n*(n+1)/2]即可(下標(biāo)從0開(kāi)始)，假設(shè)sa[0]的地址是1000，每個(gè)元素占4個(gè)字節(jié)，行優(yōu)先存儲(chǔ)，則a[8][7]的地址是_________。4．樹(shù)的存儲(chǔ)可采用雙親鏈表表示法，孩子鏈表表示法（或雙親孩子鏈表表示法），還可采用_____。5．一棵完全二叉樹(shù)有2011結(jié)點(diǎn)，則該樹(shù)中有______個(gè)葉子結(jié)點(diǎn)。6．在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，利用空指針域來(lái)存放結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這些被利用起來(lái)的指針?lè)Q為線索，那么線索的數(shù)目是____________個(gè)。得分評(píng)卷三．判斷題（本大題共4小題，每題1分，共4分，對(duì)打V，錯(cuò)打X，答案填在括號(hào)內(nèi)）1．線性表的順序存儲(chǔ)要求結(jié)點(diǎn)間的內(nèi)存地址必須是一片連續(xù)的存儲(chǔ)單元。()2．順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。()3．兩個(gè)順序棧共享一個(gè)空間不存在棧滿的問(wèn)題。()4．將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后，樹(shù)中的葉子數(shù)與二叉樹(shù)的葉子數(shù)相等。()得分評(píng)卷四．綜合題（本大題共3小題，每題5分，共15分）1．二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)如下，畫(huà)出該二叉樹(shù)。這種存儲(chǔ)的優(yōu)缺點(diǎn)是什么1234567891011121314abcdefgh2．假設(shè)用于通信的電文僅由5個(gè)字母組成L={a,b,c,d,e}，出現(xiàn)的概率為F={12%,40%,15%,8%,25%}，試為這5個(gè)字母設(shè)計(jì)哈夫曼編碼，并求出平均碼長(zhǎng)。3．無(wú)向圖G有幾個(gè)連通分量采用鄰接矩陣存儲(chǔ)，從V1出發(fā)按下標(biāo)增序給出深度優(yōu)先搜索和廣度優(yōu)先搜索序列。得分評(píng)卷五．算法題（本大題共2小題，每題6分，共12分）1．已知一個(gè)非空單鏈表，試設(shè)計(jì)一個(gè)算法復(fù)制該鏈表的一個(gè)拷貝。其結(jié)點(diǎn)結(jié)構(gòu)為如下，結(jié)構(gòu)名為link