數(shù)據(jù)結(jié)構(gòu)試卷及參考答案

1、數(shù)據(jù)結(jié)構(gòu)試卷（七）數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題一、選擇題(30分)1設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。(A)2n(B)n(C)n2(D)n(n1)2設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。(A)n(B)n1(C)2n(D)2n13設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。(A)40，42，60，55，80，85

2、(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，804（）二叉排序樹可以得到一個(gè)從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷5設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。(A)2i1(B)2i(C)i2(D)2i16程序段s=i=0；doi=i1；s=si；while(inext

3、==0(C)headnext==head(D)head!=08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。(A)20(B)256(C)512(D)10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134)則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。(A)1(B)2(C)3(D)46.高度為h的完全二叉樹中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。

4、7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這

5、種序列。10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語句。structrecdintkeydatatypeothersvoidquickpass(structrecdr[]intsinttintstructrecdx=r[s]i=swhile(ix.key)j=j1if(ij)r[i]=r[j]i=i1while(____________________)i=i1if(ij)r[j]=r[i]j=j1________