數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2001年7月試題

1、00 一年下半年全國(guó)高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試卷、單項(xiàng)選擇題1若給定有n個(gè)元素的向量，則建立一個(gè)有序單向鏈表的時(shí)間復(fù)雜性的量級(jí)是（）2A. 0（1）B.0（n）C.0（n）D.0（nlog 2n）2在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表達(dá)中查找值為m的某結(jié)點(diǎn),若查找成功，則平均比較（）A. nB.n/2C.（n-1）/2D.（n+1）/23 研究數(shù)據(jù)結(jié)構(gòu)就是研究（）A.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)4為了方便地對(duì)圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用（）方式。A、順序存儲(chǔ)B、鏈?zhǔn)酱鎯?chǔ)C、索引存儲(chǔ)D、散列存儲(chǔ)5.

2、 二維數(shù)組A1020, 510采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且 A10 , 5的存儲(chǔ)地址是1000,則A18 , 9的地址是（ ）A、 1208B、 1212C、 13686設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有（A、13B、127下列幾種結(jié)構(gòu)中屬于樹型結(jié)構(gòu)的是（D、 1364）個(gè)結(jié)點(diǎn)。D、25&設(shè)無(wú)向圖G= （V、E）和G ' = （V E'）,女口 G'為G的生成樹，則下面不正確的說(shuō)法是（）A、G '為G的連通分量B、G '為G的無(wú)環(huán)子圖C、G '為G的子圖D、G '為G的極小連通子圖且

3、 V ' =V9. 下列說(shuō)法中不正確的是（）A、無(wú)向圖的極大連通子圖稱為連通分量B、連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C、圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)D、有向圖的遍歷不可采用廣度優(yōu)先搜索方法10. 對(duì)有序表（18, 20, 25, 34, 48, 62, 74 , 85）用二分查找法查找 85,所需的比較次數(shù)為（）A、1次B、2次C、3次D、4次11 .散列表的平均查找長(zhǎng)度（）A、與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B、與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C、與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D、與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)12. 對(duì)ISA

4、M文件的刪除記錄時(shí)，一般（）B、需移動(dòng)記錄C、需改變指針D、一旦刪除就需做整理A、只需做刪除標(biāo)志13 順序文件適宜于()A、直接存取B、成批處理C、按關(guān)鍵字存取D、隨機(jī)存取14. 一個(gè)序列中有10000個(gè)元素，若只想得到其中前10個(gè)最小元素，最好采用()方法。A、快速排序B、堆排序C、插入排序D、二路歸并排序15. 對(duì)下列四個(gè)序列用快速排序方法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)進(jìn)行劃分。在第1趟劃分過(guò)程中,兀素移動(dòng)次數(shù)最多的是序列()A、 70, 75, 82, 90, 23, 16, 10, 68C、 82, 75, 70, 16, 10, 90, 68, 23 二、填空題1 .下列程序段的

5、時(shí)間復(fù)雜性的量級(jí)為0 (m*n )for (i=0; i<m; i+)for (j=0; j< n; j+)t=t+1;2. 索引文件由索引表 和主文件兩部分組成。3. 在一個(gè)不帶有頭結(jié)點(diǎn)的非空單鏈表中，其結(jié)點(diǎn)形式為 結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句序列：B、 70, 75, 68, 23, 10, 16, 90, 82D、 23, 10, 16, 70, 82, 75, 68, 90data | next ,若要在指針q所指結(jié)點(diǎn)之后插入一個(gè)p=malloc(size); p->data=x;p->n ext=q->n ext ;q->n ext=p;4. 設(shè)鏈棧的棧

6、頂指針為Is,棧不空的條件為Is! =NULL或等價(jià)敘述5. 遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索。其中，深度優(yōu)先搜索 是一個(gè)遞歸過(guò)程。棧的基本運(yùn)算表示應(yīng)為pop(S),pop(S),pop(S)。push (S,1), push (S,2) , push ( S,3) , push (S,4), pop(S),pop(S), push(S,5),輸出端輸入端棧S123456. 如圖所示，設(shè)輸入元素的順序?yàn)?, 2, 3, 4, 5，要在棧S的輸出端得到序列 43521，則應(yīng)進(jìn)行的操作用7. 下圖為某樹的靜態(tài)雙親鏈表表示:0A-11B02C03D14E2則結(jié)點(diǎn)D、E的雙親結(jié)點(diǎn)分別為B、

7、C&在下列樹中，結(jié)點(diǎn) H的祖先為 A、D、G9靜態(tài)查找表的順序查找算法中，通常采用設(shè)置崗哨的方式以確保查找不成功時(shí)循環(huán)也能終止執(zhí)行，若給 定值為K，表的長(zhǎng)度為n,查找表的數(shù)據(jù)單元用R.item表示，鍵值用key表示，則在表尾設(shè)置崗哨的相應(yīng)方法描述為R.item n+1.key=K10對(duì)于二叉樹的查找，若根結(jié)點(diǎn)元素的鍵值大于被查找元素的鍵值，則應(yīng)該在該二叉樹的左子樹 上繼續(xù)查找。11 采用二次探測(cè)法解決沖突問(wèn)題，對(duì)于鍵值為K，容量為m的閉散列表，若散列地址為do,則發(fā)生沖突后，其第三個(gè)后繼散列地址d3為（do+22） mod m12 .對(duì)一組記錄（54, 38, 96, 23, 15,

8、72, 60, 45, 83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到已排序的有序表時(shí)，為尋找其插入位置需比較3次。13. 對(duì)n個(gè)元素進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)是n-1三應(yīng)用題1. 已知序列(17, 18, 60, 40, 7, 32, 73, 65, 趟的過(guò)程。解：依題意：初始(17, 18, 60, 40, 7, 32, 73, 65, 85)85），請(qǐng)給出采用冒泡排序法對(duì)該序列作升序排序時(shí)每1 趟(17, 18, 40,乙32,60,65,73,85)2 趟(17, 18, 7,32,40,60,65,73,85)3 趟(17, 7, 18,32,40,60,65,73,85)4

9、 趟(7, 17, 18,32,40,60,65,73,85)5 趟(7, 17, 18,32,40,60,65,73,85)第5趟兀素未交換，則排序結(jié)束。2. 如圖所示，在棧的輸入端有6個(gè)元素，順序?yàn)锳、B、C、D、E、F。能否在棧的輸出端得到序列DCFEBA及EDBFCA ?若能，給出棧操作的過(guò)程，若不能，簡(jiǎn)述其理由。ABCDEF輸出端輸入端棧r解：（1）能得到序列 DCFEBA操作過(guò)程如下：push, push, push, push, pop, pop, push, push, pop, pop, pop, pop(2)不能得到EDBFCA因?yàn)橐玫紼需將A, B, C, D順序入棧，

10、根據(jù) LIFO原則，不可能B在C之前出棧。3 分別寫出下列二叉樹的先根、中根、后根遍歷序列。 解：先根遍歷序列：ABCDFGHE中根遍歷序列：BADGFHCE后根遍歷序列：BGHFDECA4已知無(wú)向圖G的鄰接表如下，請(qǐng)寫出其從頂點(diǎn)V2開始的深度優(yōu)先搜索序列。解：V2V4V0V1V3設(shè)散列iifiSJ為H(K) = K. mod 11 f做列我tt瞳為IN散列地址空何0 . , 10),蛉定喪(SUN, MON； TUE, WED.THU, FRJ, SAT)中，取肌訶的第-冷字母在英諂字母衷中的序號(hào)為琥值Q 構(gòu)虛一幵般列舉*井用拴輕法解決有關(guān)地址沖突.(7分)評(píng)分細(xì)則：本小嚏共7分.菩錯(cuò)?？鄯?/p>

11、.四、iftttH (共14分)I、設(shè)以:叉進(jìn)表為一丈棧的存儲(chǔ)幼構(gòu).結(jié)點(diǎn)的結(jié)梅如下:Ichild 帕怡 rchild11中dau罐為駅數(shù)”試設(shè)計(jì)-個(gè)算世void change (bilrcpir r )；若詹點(diǎn)莊摟子的data域的 伉九于右踐子的dataS的值.則立換其左.右子神.(6S; oidchartgc(bitrcptrr)I bitrepir i iffr! = NULL)< if(r->khiM&&r->rchild&& (r->IchiJd>data>(r - >rchild )>dala) x =

12、r - > Ichildjr - > khid & r * > rchild：r * > ichild = x；(1分(1分<1 乂、change r > khjld)；changc( r - > rchild)；J注；算法中斗也取其它變最名；左右子祐的交換也可改為： X r - > rchild：r > rchild 世 a child；r->lchild=x;2 .已知奇偶轉(zhuǎn)換排序如下所述：第一趟對(duì)所有奇數(shù)i，將ai和ai+1進(jìn)行比較，第二趟對(duì)所有偶數(shù)i，將ai和ai+1進(jìn)行比較，每次比較時(shí)若ai>ai+1，則將兩者

13、交換，以后重復(fù)上述二趟過(guò)程交替進(jìn)行，直至整個(gè)數(shù)組有序。（1）試問(wèn)：排序結(jié)束的條件是什么？（2） 編寫一個(gè)實(shí)現(xiàn)上述排序過(guò)程的算法：void oesort （int a , int n）。解：(1)在一趟奇排序和一趟偶排序時(shí)均不發(fā)生數(shù)據(jù)交換。(2)void oesort ( int a , int n )int i, flag, t; doflag=0;for (i=1; i<n; i+)if (ai > ai+1)flag=1;t= ai+1; ai+1= ai; ai=t; i+;while (flag!=0);Whe n you are old and grey and full

14、 of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows

15、of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I p