數(shù)據(jù)結(jié)構(gòu)期末試題(05A)

一．單項選擇題（每題2分，共20分）1．順序表是線性表的（）①鏈式存儲結(jié)構(gòu)②順序存儲結(jié)構(gòu)③索引存儲結(jié)構(gòu)2.對于順序表的優(yōu)缺點，以下說法錯誤的是①無需為表示結(jié)點間的邏輯關系而增加額外的存儲空間②可以方便地隨機存取表中的任一結(jié)點④散列存儲結(jié)構(gòu)（）③插人和刪除運算較方便④由于順序表要求占用連續(xù)的空間，存儲分配只能預先進行(靜態(tài)分配)3.單鏈表中，增加頭結(jié)點的目的是為了()①使單鏈表至少有一個結(jié)點②標示表結(jié)點中首結(jié)點的位置③方便運算的實現(xiàn)④說明單鏈表是線性表的鏈式存儲實現(xiàn)4.循環(huán)隊列的隊滿條件為（在犧牲一個存儲空間的情況下）()①rear%maxsize==(front+1)%maxsize;②(rear+1)%maxsize==front+1③(rear+1)%maxsize==front④rear==front5.循環(huán)隊列的人隊操作應為()①rear=rear+1data[rear]=xrear=rear+1②data[rear]=x③rear=(rear+1)%maxsize④data[rear]=xdata[rear]=xrear=(rear+1)%maxsize6．設有一順序棧已含3個元素，如下圖所示，元素a4正等待進棧。那么下列4個序列（）中不可能出現(xiàn)的出棧序列是0123maxsize-1a1a2a3sq↑top①a3,a1,a4,a2②a3,a2,a4,a1③a3,a4,a2,a1④a4,a3,a2,a1()7．以下說法錯誤的是①二叉樹可以是空集②二叉樹的任一結(jié)點都有兩棵子樹③二叉樹與樹具有相同的樹形結(jié)構(gòu)④二叉樹中任一結(jié)點的兩棵子樹有次序之分8．深度為5的二叉樹最多有()個結(jié)點(設樹的層數(shù)為6)①64②63③32④319．將含有83個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點編號，那么編號為41的雙結(jié)點編號為()①42②40③21④2010．在圖1的二叉樹中，（）不是完全二叉樹。二．填空題（1-3題每空2分，4-6題每空1分，共20分）1．下面程序段的時間復雜度T(n)=___________。for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}2．以下運算實現(xiàn)在順序棧上的進棧，請在_______處用適當?shù)囊蕴畛洌ù娣艞Ｔ氐臄?shù)組為ElmList）。template<classELEM>voidPush(ELEMitem){if(top>=maxsize-1}{cerr<<“棧滿”<<endl;return;}________________=item;________________；}3.以下運算實現(xiàn)在循環(huán)隊上的出隊列，請在_______處用適當句子予以填充。（存放隊列元素的數(shù)組為ElmList）template<classELEM>ELEMQueue::DeQueue(){if(curr_len==________________){cerr<<“隊空”<<endl;return；}ELEMtemp=_____________;____________returntemp;}____;4.二叉樹第i(i>=0)層上至多有______個結(jié)點。5.對任何二叉樹，若度為2的節(jié)點數(shù)為n2，則葉子數(shù)n0=______。6．一棵樹的形狀如圖2所示，它的根結(jié)點是________，葉子結(jié)點是________，這棵樹的度是________，這棵樹的深度是________，結(jié)點F的孩子結(jié)點是________，結(jié)點G的父結(jié)點是________。三．問答題（每題10分，共40分）1．數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容有哪些，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)有哪些，存儲結(jié)構(gòu)有哪些？2．畫出圖3所示二叉樹的中序線索二叉鏈表存儲結(jié)構(gòu)示意圖。3．已知一棵二叉樹的前根序列和中根序列分別為ABDGHECFIJ及GDHBEACIJF，請畫出這棵二叉樹。4．給定權(quán)值7，18，3，32，5，26，12，8，構(gòu)造相應的哈夫曼樹，并求這棵哈夫曼樹的帶權(quán)路徑長度WPL。四．算法設計題（每題10分，共20分）1．設A=（a1,a2,a3,......an）和B=(b1,b2,...,bm)是兩個線性表（假定所含數(shù)據(jù)元素均為整數(shù)）。若n=m且ai=bi(i=1,...,n),則稱