福建農(nóng)林大學(xué)考試試卷 (a)卷

《福建農(nóng)林大學(xué)考試試卷 (a)卷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、福建農(nóng)林大學(xué)考試試卷（A）卷2007——2008學(xué)年第二學(xué)期課程名稱：數(shù)據(jù)結(jié)構(gòu)考試時(shí)間120分鐘計(jì)算機(jī)科學(xué)技術(shù)專業(yè)2006年級(jí)班學(xué)號(hào)姓名題號(hào)一二三四五六七八九總得分得分評(píng)卷人簽字復(fù)核人簽字得分一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）1.順序棧中壓入元素時(shí)，是（）。A)先存入元素后移動(dòng)指針???B)先移動(dòng)指針后存入元素C)無(wú)所謂誰(shuí)先誰(shuí)后????D)同時(shí)進(jìn)行2.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。A)隨機(jī)存取B)順序存取C)索引存取D)HASH存取3.若一個(gè)棧的輸入序列是1,2,3…n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（）。A)不確定???B)n

2、-i????C)n-i+1???D)i4.在以下的敘述中，正確的是（）。A)線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B)二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表C)棧的操作方式是先進(jìn)先出D)隊(duì)列的操作方式是先進(jìn)后出5.某二叉樹的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（）。A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca6.樹的基本遍歷策略可分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹

3、。結(jié)論（）是正確的。A)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同B)樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D)樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同7.時(shí)間復(fù)雜度均為O(nlog2n)且不穩(wěn)定的排序方法是（）。A)快速排序B)選擇排序C)歸并排序D)冒泡排序8.用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。試題第8頁(yè)(共8頁(yè))A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷9.堆排序的時(shí)間復(fù)雜度為（）。A)O(n2)B)O(log2n)C)O(n)D)O(nlog2n)10．已知

4、Huffman樹的總結(jié)點(diǎn)數(shù)為m，葉子數(shù)為n。則m與n的關(guān)系是（）。 A)m=2n+1B)m=n+1C)m=2n–1D)m=n-1得分二、填空題（本大題共20個(gè)空，每空2分，共40分）1．在一個(gè)長(zhǎng)度為n的線性表中刪除第i個(gè)元素(1≤i≤n)，需向前移動(dòng)個(gè)元素。2.下面程序段的時(shí)間復(fù)雜度是。longi=1,s=0.0;while(s

5、。6．圖的廣度優(yōu)先遍歷算法利用隊(duì)列來(lái)完成，圖的深度優(yōu)先遍歷算法利來(lái)完成。7．一棵二叉排序樹上按方式進(jìn)行遍歷，會(huì)得到一個(gè)已排序好的結(jié)點(diǎn)序列。8．線性表長(zhǎng)度為n，排序碼位數(shù)為d，基數(shù)為b，進(jìn)行基數(shù)排序時(shí)間復(fù)雜度是。9．對(duì)長(zhǎng)度為n的線性表進(jìn)行分塊查找，其ASL的最小值是。10．線性表長(zhǎng)度為n，對(duì)其進(jìn)行歸并排序時(shí)間復(fù)雜度是。以下為算法填空11．二叉樹用以下靜態(tài)二叉鏈表作為存儲(chǔ)結(jié)構(gòu)#definen0100//數(shù)組最大下標(biāo)#definedatatypecharstructnode試題第8頁(yè)(共8頁(yè)){datatypedata;intlch,rch;//lch指向左子樹，rch指向右子樹}

6、tree[n0+l];introot;//根結(jié)點(diǎn)指針下面是先序遍歷二叉樹的非遞算法。一維數(shù)組s作為棧，t為棧頂指針。voidpreorder（）{ints[n0+l],t=; intp=root;while(p

7、

8、)if(p){printf(“%c”,)s[++t]=tree[p].rch;p=tree[p].;}elsep=s[];}12.以下mergeSort是歸并排序算法，merge是將兩個(gè)相鄰有序表歸并的算法，mergepass是一趟歸并的算法，填空完成算法。voidmeger(ElementR[],ElementS[],inta,intb,intc){inti=a,

9、j=b+1,k=a;while(i<=b&&j<=c)if(R[i].key