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

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