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

一、填空題

1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的

和數(shù)據(jù)的運算。2、若一個算法中的程序步為T(n)=10log2n+50n+10000，則算法的時間復(fù)雜度為

。3、順序表相對于鏈表的優(yōu)點有無需增加額外的存儲空間和

。4、當(dāng)線性表的長度變化較大，難以估計其存貯規(guī)模時，以采用

作為存貯結(jié)構(gòu)為好。5、具有72個結(jié)點的完全二叉樹的深度為

6、有n個葉子的哈夫曼樹的結(jié)點總數(shù)為________。7、樹中結(jié)點A有2005個兄弟，結(jié)點B是A的雙親，則結(jié)點B的度是________。8、已知一無向圖G=(V,E)，其中V={a,b,c,d,e}，E={(a,b),(a,d),(a,c)(d,c),(b,e)}，現(xiàn)用某一種遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是__________遍歷方法。9、設(shè)有一組記錄的關(guān)鍵字為{19,14,1,68,20,27,55,79}，用拉鏈法構(gòu)造哈希表，哈希函數(shù)為h(key)=key%13，哈希地址為1的鏈中有________個記錄。10、已知有序表為(16,18,28,35,47,52,62,88,90,118,256)，當(dāng)用二分法查找90時，需經(jīng)過________次查找成功。二、選擇題

1、在單鏈表指針為p的節(jié)點之后插入指針為s的結(jié)點，正確的操作是（）A)p->link=s;s->link=p->link;B)s->link=p->link;p->link=s;C)p->link=s;p->link=s->link; D)p->link=s->link;p->link=s;2、具有n個頂點的有向完全圖中，邊的總數(shù)為（）條。A）n（n+1）B）n（n-1）C）n（n-1）/2D）n（n+1）/23、散列函數(shù)不是一對一的關(guān)系，因此選用好的（）方法是散列文件的關(guān)鍵。A）散列函數(shù)B）除余法中的質(zhì)數(shù)C）沖突處理D）散列函數(shù)和沖突處理4、假設(shè)以行序為主序存儲二維數(shù)組A[i][j]（1≤i≤100，1≤j≤100），設(shè)每個數(shù)據(jù)元素占2個存儲單元，二維數(shù)組存儲的起始地址為10，則Loc(A[5][5])=( )A)808 B)818C)1010 D)10205、深度為6（根的層次為1）的二叉樹至多有（）個結(jié)點。A）64B）32C）31D）636、設(shè)一個棧輸入序列是1、2、3、4、5，則下列序列中不可能是棧的輸出序列是（）。A）32541B）15432C）14523D）231457、二叉樹的前序遍歷為EFHIGJK，中序遍歷序列為HFIEJKG。該二叉樹根結(jié)點的右子樹的根是（ ）A)E B)FC)G D)H8、下面幾個符號串編碼集合中，不是前綴編碼的是（）A){0,10,110,1111} B){11,10,001,101,0001}C){00,010,0110,1000D){b,c,aa,ac,aba,abb,abc}9、

m階B-樹中所有的非終端（除根外）結(jié)點中的關(guān)鍵字的個數(shù)必須大于或等于（

）。A）mB）m/2C）m/2+1D）m/2-1

C）

D）10、

下列四個序列中，哪一個是堆（）A)16,72,31,23,94,53 B)16,53,23,94,31,72C)16,31,23,94,53,72 D)16,94,23,31,53,72三、簡答題

1.用一維數(shù)組存放的一棵完全二叉樹如圖1所示： 圖1寫出前序、中序、后序遍歷該二叉樹時訪問結(jié)點的順序。前序序列：中序序列：后序序列：2.將圖2所示的兩棵樹組成的森林轉(zhuǎn)換為二叉樹。

D）

3.

以序列（72，87，61，23，94，16，05，58）為輸入，從空的優(yōu)先權(quán)隊列開始，依次插入這些元素，求結(jié)果優(yōu)先權(quán)隊列的狀態(tài)。

4、已知結(jié)點權(quán)值：4，2，5，7，5。畫出相應(yīng)哈夫曼樹并計算帶權(quán)路徑長度WPL。哈夫曼樹中結(jié)點用結(jié)點的權(quán)值表示.5、設(shè)數(shù)據(jù)集合d={1，12，5，8，3，10，7，13，9}，試完成下列各題：5、設(shè)數(shù)據(jù)集合d={1，12，5，8，3，10，7，13，9}，試完成下列各題：（1）依次取d中各數(shù)據(jù)，構(gòu)造一棵二叉搜索樹bt。（2）畫出在二叉樹bt中刪除12后的樹結(jié)構(gòu)。

6、對圖3的3階B-樹，依次執(zhí)行下列操作，畫出各步操作的結(jié)果。（1）插入90 ；（2）插入25；（3）插入45；（4）刪除60；

7.已知下圖所示的無向帶權(quán)圖：

（1）從結(jié)點2出發(fā)，用prim算法求其最小代價生成樹，并畫出過程示意圖。（2）時間復(fù)雜度為多少？

8、下圖的鄰接表表示一個給定的無向圖。

（1）給出從頂點v1開始，用深度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列；（2）給出從頂點v1開始，用廣度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列。

算法填空下面是在非空單鏈表(n個結(jié)點)中第k個結(jié)點之后插入一個元素值為x的算法。(如果k等于0，則在第1個結(jié)點之前插入x)。

template<classT>boolSingleList<T>::Insert(intk,constT&x){if(

){cout<<"OutOfBounds";returnfalse;}

;for(inti=1;i<k;i++)p=p->link;

;q->data=x;if(k){

；p->link=q;}else{q->link=first；first=q;}

;returntrue;}下面是二叉搜索樹的搜索算法。

template<classE,classK>boolBSTree<E,K>::Search(constK&k,E&e)const{BTNode<E>*p=root;while(p){if(

)p=p->lchild;elseif(k>p->element)

;else{e=p->element;returntrue;}}returnfalse;}程序閱讀題

類BinaryTree是指用二叉鏈表來存儲二叉樹，root表示其根結(jié)點，有程序如下：template<classT>intBinaryTree<T>::H()//定義為二叉樹類的公有函數(shù){ returnH(root);}template<classT>intBinaryTree<T>::H(BTNode<T>*t)//定義為二叉樹類的私有函數(shù){inthl,hr

; if(!t)return0;hl=H(t->lChild)

;hr=H(t->rChild)

;returnhl>hr?hl+1:hr+1;}問題：1）以上程序?qū)崿F(xiàn)了二叉樹類的什么