數(shù)據結構練習題

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