933計(jì)算機(jī)基礎(chǔ)_課件期末試題歷年真題數(shù)據(jù)結(jié)構(gòu)2009b

1、大學(xué)計(jì)算機(jī)學(xué)院“數(shù)據(jù)結(jié)構(gòu)”試題（B）學(xué)號(hào)班號(hào)要求：所有的題目的解答均寫在試題紙上。一、單項(xiàng)選擇題（每小題 2 分，共 20 分）1. 計(jì)算機(jī)所處理的數(shù)據(jù)一般具備某種內(nèi)在聯(lián)系，這是指。A.數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系C. 元素內(nèi)部具有某種結(jié)構(gòu)2. 不是算法的基本特性。 A.可行性C.在規(guī)定的時(shí)間內(nèi)完成B.元素和元間存在某種關(guān)系D.數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系B.長(zhǎng)度有限D(zhuǎn).確定性3. 線性表采用鏈表A.必須是連續(xù)的時(shí)，其地址。B.一定是不連續(xù)的C.部分地址必須是連續(xù)的D.連續(xù)與否均可以4.已知一個(gè)棧的進(jìn)棧序列是 1，2，3，n，其輸出序列是 p1，p2，pn，若 p1=n，則 pi 的值。A.i

2、C.n-i+1B.n-iD.不確定5. 若串 s=software，其子串的個(gè)數(shù)是。A.8C.36B.37D.96. 設(shè)二維數(shù)組 Amn，每個(gè)數(shù)組元素占用 k 個(gè)單元，第一個(gè)數(shù)組元素的地地址是 Loc(a00)，求按列優(yōu)先順序存放的數(shù)組元素 aij(0im-1，0jn-1)的址為。A.Loc(a00)+(i-1)*n+j-1*kC.Loc(a00)+j*m+i*kB.Loc(a00)+i*n+j*kD.Loc(a00)+(j-1)*m+i-1*k7. 對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)和 e 條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為 ；所有鄰接表中的結(jié)點(diǎn)總數(shù)是 。 A. nC. n-1 A. e

3、/2C. 2e8. 采用鄰接表A. 先序遍歷C. 后序遍歷B. n+1D. n+eB. eD. n+e的圖的深度優(yōu)先遍歷算法類似于二叉樹的。B. 中序遍歷D. 按層遍歷3. D4. C5. C6. D7. A C8. A9. B10. A1. B2. B2數(shù)據(jù)結(jié)構(gòu)試題9. 有一個(gè)長(zhǎng)度為 12 的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為。A. 35/12C. 39/12B. 37/12D. 43/1210.A.在待排序的元素序列基本有序的前提下，效率最高的排序方法是。B. 選擇排序D. 歸并排序排序C. 快速排序二、填空題（每小題 2 分，共 10

4、 分）1.2.3.廣義表(a,()的長(zhǎng)度是 ，深度是 。在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無關(guān)的查法方法是。在排序、排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有。G 是一個(gè)非連通無向圖，共有 28 條邊，則該圖至少有個(gè)頂點(diǎn)。對(duì)n 個(gè)頂點(diǎn)的連通圖來說，它的生成樹一定有條邊。三、問答題（每小題 8 分，共 40 分）1.分析以下算法的時(shí)間復(fù)雜度。void func(n)i=1,k=100;while (in)k+;i+=2;簡(jiǎn)述線性表、棧和隊(duì)列的異同？具有 n 個(gè)結(jié)點(diǎn)的滿二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是多少？一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示

5、出來。試求出2.3.4.空格處的內(nèi)容，并畫出該二叉樹。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A5. 已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找 90 時(shí)，需進(jìn)行外多少次查找可確定成功？查找 47 時(shí)需進(jìn)行多少次查找可確定成功？查找 100 時(shí)，需進(jìn)行多少次查找才能確定不成功？3數(shù)據(jù)結(jié)構(gòu)試題四、算法設(shè)計(jì)題（30 分）1.已知單鏈表 L(結(jié)點(diǎn))是一個(gè)非有序表，設(shè)計(jì)一個(gè)算法，刪除表中 data 值在大于或等于 min 小于或等于 max 之間的結(jié)點(diǎn)(若表中有這樣的結(jié)點(diǎn))，同時(shí)被刪結(jié)點(diǎn)的空

6、間，這里 min 和 max 是兩個(gè)給定的參數(shù)。并分析算法的時(shí)間復(fù)雜度。（15 分）2. 假設(shè)二叉樹采用二叉鏈結(jié)構(gòu)，t 指向根結(jié)點(diǎn)，p 所指結(jié)點(diǎn)為任一給定的結(jié)點(diǎn)，設(shè)計(jì)一個(gè)算法，輸出從根結(jié)點(diǎn)到 p 所指結(jié)點(diǎn)之間路徑。（15 分）參考一、單項(xiàng)選擇題（每小題 2 分，共 20 分）1. B2. B3. D4. C5. C6. D7. A C8. A9. B10. A二、填空題（每小題 2 分，共 10 分）1. 2，22.哈希（散列）查找方法3.排序、選擇排序、快速排序、堆排序4.圖 G 是非連通無向圖，至少有兩個(gè)連通分量，其中通分量最少的頂點(diǎn)數(shù)是由 28 條邊組成的無向圖，其頂點(diǎn)數(shù)為 n，邊數(shù)為

7、e，則 e n(n 1) ，e=28，則 n8；另一2個(gè)連通分量只有一個(gè)頂點(diǎn)，該圖至少有 9 個(gè)頂點(diǎn)。5. n-1三、問答題（每小題 8 分，共 40 分）設(shè) while 循環(huán)執(zhí)行 T(n)次，i=2T(n)+1n，則 T(n)data,*pre=L,*q;while (p!=NULL)if (p-data=min & p-datanext=p-next; p=p-next; free(q);elsepre=p;p=p-next;算法的時(shí)間復(fù)雜度為 O(n)。2. 解：算法如下：void path(BTree* t,BTree *p)BTree* StMaxSize,*s; tagMaxSize;top=-1,i; s=t;dowhile(s!=NULL)/掃描左結(jié)點(diǎn)，入棧top+; Sttop=s; tagtop=0;s=s-lchild;if(top-1)if(tagtop=1)/左右結(jié)點(diǎn)均已過，則要該結(jié)點(diǎn)if (Sttop=p) /該結(jié)點(diǎn)就是要找的結(jié)點(diǎn)prf(路徑:);/輸出從棧底到棧頂?shù)脑芈窂絝or (i=1;idata);prf(n);b