數(shù)據(jù)結(jié)構(gòu)試題2010度

1、煙臺(tái)大學(xué)20 09 20 10 學(xué)年第 二 學(xué)期數(shù)據(jù)結(jié)構(gòu) 試卷A（注：第三大題答案請(qǐng)寫在后面的空白答題紙上）一、選擇題(每小題2分，共20分) 1. 以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式，解釋錯(cuò)誤的是 ( )A、集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散B、線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條"鎖鏈"C、樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹D、圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接2. 若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲(chǔ)結(jié)構(gòu)為( ) A、順序存儲(chǔ)結(jié)構(gòu) B、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C、索引存儲(chǔ)結(jié)構(gòu)

2、 D、散列存儲(chǔ)結(jié)構(gòu) 3. 在長(zhǎng)度為n的順序表的第i (1in+1)個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為( ) A、n-i+1 B、n-i C、i D、i-1 4. 對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為( ) A、順序表 B、用頭指針表示的單循環(huán)鏈表 C、用尾指針表示的單循環(huán)鏈表 D、單鏈表 ABCDEF圖15. 一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ） A 、e d c b a B、d e c b a C、d c e a b D、a b c d e 6. 已知圖1如右所示，若從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（ ）

3、A、 A，B，E，C，D，F(xiàn) B、 A，C，F(xiàn)，E，B，DC、 A，E，B，C，F(xiàn)，D D、 A，E，D，F(xiàn)，C，B7. n個(gè)頂點(diǎn)的有向圖中含有向邊的數(shù)目最多為 ( ) A、n-1 B、n C、n(n-1)/2 D、n(n-1) 8. 若一個(gè)棧的輸入順序是1，2，n，輸出序列的第一個(gè)元素是n，則第i（1in）個(gè)輸出元素是（ ）A、n-i B、n-i-1 C、i+1 D、n-i+112345圖29. 已給圖2，（ ）是該圖的正確的拓?fù)渑判蛐蛄?A、1，2，3，4，5 B、1，3，2，4，5 C、1，2，4，3，5 D、1，2，3，5，410. 為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運(yùn)算

4、是( ) A、插入 B、刪除 C、串聯(lián)接 D、子串定位 二、填空題(每小題2分，共30分)1. 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的_實(shí)現(xiàn)。2. 若一個(gè)算法中的語句頻度之和為T(n)=n+4nlogn，則算法的時(shí)間復(fù)雜度為_。 3. 數(shù)組A1.10,-2.6,2.8以行優(yōu)先順序存儲(chǔ)，設(shè)基地址為100，每個(gè)元素占3個(gè)存儲(chǔ)單元，則元素A5,0,7的存儲(chǔ)地址是 。4. 在無向圖的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于_。 5. 對(duì)帶有頭結(jié)點(diǎn)的鏈隊(duì)列l(wèi)q，判定隊(duì)列中只有一個(gè)數(shù)據(jù)元素的條件是_。6. 設(shè)數(shù)組data0.m作為循環(huán)隊(duì)列sq的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指

5、針front的值為 。7. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e3，e5，e4,e6,e2,e1,則棧S的容量至少應(yīng)該是 。8. 設(shè)有順序棧s0.m-1，若棧底設(shè)在下標(biāo)最大的一端，則棧滿的條件是 （設(shè)棧頂指針為top，指向棧頂元素的位置）。9. 有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，A1,1為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則A7,5的地址為 。10. 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找，查找元素11，需進(jìn)行 次

6、元素之間的比較。 11. 深度為h的完全二叉樹至少有_個(gè)結(jié)點(diǎn)。12. 在對(duì)一組記錄（18，6，27，12，52，15，47，29）進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄15插入到有序表時(shí)，為尋找插入位置需比較 次。13. 在直接插入排序和快速排序中，若初始數(shù)據(jù)基本有序，則選用_；在冒泡排序和堆排序中，若要求數(shù)據(jù)的穩(wěn)定性，則選用_。14. 廣義表運(yùn)算式TAIL(a,b)，(c,d) 的運(yùn)算結(jié)果為 。15. 一組記錄的關(guān)鍵字為(42,59,36,28,10,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 。三應(yīng)用題（每小題5分，共35分）11. 設(shè)有序列(45，24，53，12，

7、28，90)，請(qǐng)構(gòu)成一棵二叉排序樹，并求其查找成功時(shí)的平均查找長(zhǎng)度。2. 對(duì)關(guān)鍵字序列(56，20，23，75，29，61，36，87) 進(jìn)行堆排序，使之按關(guān)鍵字遞增次序排列，請(qǐng)寫出排序過程中建初始堆的過程。3. 已知散列表長(zhǎng)度為13，散列函數(shù)為H(key)=key % 11，處理沖突的方法為線性探測(cè)法，請(qǐng)畫出依次插入關(guān)鍵字(10,8,40,27,21,57,46,23,19,56)以后的散列表，并計(jì)算查找成功和不成功時(shí)的平均查找長(zhǎng)度。4. 已知某二叉樹按中序遍歷次序是BDCEAFHG，按后序遍歷次序是 DECBHGFA，試畫出該二叉樹的形狀，并寫出它的前序掃描序列。5. 以數(shù)據(jù)集（17，9，

8、2，6，3，24，10）為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵哈夫曼樹。1234561921161471511465圖36. 已知如圖3所示的無向帶權(quán)圖，請(qǐng)用普里姆（Prim）算法求其從頂點(diǎn)1開始的最小生成樹，畫出生成過程。v6v5v310345632v1v2v4圖4128 已知一個(gè)網(wǎng)絡(luò)如圖4所示，利用Dijkstra算法求頂點(diǎn)v1到各頂點(diǎn)的最短路徑。四算法設(shè)計(jì)題（共2小題，共15分）1已知一個(gè)線性表中的元素按值非遞減有序排列，以鏈?zhǔn)酱鎯?chǔ)編寫一個(gè)算法刪除表中多余的值相同的元素。（8分）2寫出求一棵二叉樹的高度的算法。（7分）煙臺(tái)大學(xué)20 1o 20 11 學(xué)年第 二 學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷A參考答案及評(píng)分標(biāo)準(zhǔn)考試

9、方式： 閉卷 （開卷、閉卷、其他）院系： 計(jì)算機(jī)學(xué)院 年級(jí)： 02級(jí)專 專業(yè)： 計(jì)算機(jī) .注：標(biāo)準(zhǔn)答案、參考答案要點(diǎn)及評(píng)分標(biāo)準(zhǔn)須寫清題號(hào)、每小題得分、共得分等。 此格式為題頭，如本頁(yè)不夠，后面請(qǐng)附相同規(guī)格（A4）的紙張。.一、選擇題(每小題2分，共20分) 1.A 2.D 3.A 4.C 5.C 6.D 7.D 8.D 9.A 10.D二、填空題(每小題2分，共30分) 1. 物理 2. nlogn 3. 913 4. 1 5. lq->front->next=lq->rear 6. (sq.front+1)%(m+1) 7. sq.front=(sq.front+1)%(m

10、+1) 8. 4 9. top=0 10. 3 11. 2h-1 12. 4 13. 直接插入、冒泡452453122890 14. (c,d) 15.(10,28,36,42,59,84)三、應(yīng)用題(每小題5分，共35分)1.ASLsucc=(1*1+2*2+3*3)/6=7/35620237529613687562023872961367556206187292336752.568761752923362087756156292336203.地址0123456789101112元素2357465627408191021查找成功時(shí)的1724632109查找不成功時(shí)的ABFCHGDE4. 5.

11、 前序序列：ABCDEFGH6115712316544121611231651231654457123165446.V1V2V3V4V5V602/V1312µµ3/V17µµ6/V313111310/V413/V37.四算法設(shè)計(jì)題（共2小題，共15分）1. void DeleteEqual2(LinkekList L) 2. int BinTreeDepth(BitTree T) /刪除元素非遞減排列的鏈表L中所有值相同的元素 if(T=NULL)return 0; p=L->next;q=p->next; elsel=BinTreeDepth(T->lchild); while(p->nex