1、全國(guó)2010年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1.下述文件中適合于磁帶存儲(chǔ)的是（ A ）A.順序文件B.索引文件C.散列文件D.多關(guān)鍵字文件2.某二叉樹(shù)的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為（ D ）A.acbedB.becabC.deabcD.cedba3.含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)用二叉鏈表表示時(shí)，空指針域個(gè)數(shù)為( C )A.n-1B.nC.n+1D.n+2 注：子域?yàn)?n個(gè)，有n

2、-1個(gè)孩子。4.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是( C )A.12B.11C.21D.415.長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則出隊(duì)操作的時(shí)間復(fù)雜度為( A )A.O(1)B.O(1og2n) 二分法 注：若只有尾指針，那么入和出都為O(1)C.O(n) （入隊(duì)）D.O(n2) -冒泡6.下述幾種排序方法中，要求內(nèi)存量最大的是( C )A.插入排序B.快速排序C.歸并排序D.選擇排序7.對(duì)n個(gè)不同值進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為( D )A.n-1B.nC.n+1D.n(n-1)28.對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須( C )A.以順序方式存儲(chǔ)

3、B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列9.在表長(zhǎng)為n的順序表上做刪除運(yùn)算，其平均時(shí)間復(fù)雜度為( B )A.O(1)B.O(n) 注：在雙向循環(huán)鏈表中，刪除最后一個(gè)結(jié)點(diǎn)C.O(nlog2n)D.O(n2) 的時(shí)間復(fù)雜度為O(1)10.當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大容量為( B )A.n-2B.n-1C.nD.n+111.有關(guān)插入排序的敘述，錯(cuò)誤的是( C )A.插入排序在最壞情況下需要O(n2)時(shí)間B.插入排序在最佳情況可在O(n)時(shí)間內(nèi)完成C.插入排序平均需要O(nlog2n)時(shí)間 -快速排序需要o（nlog

4、2n） 樹(shù)：是n各節(jié)點(diǎn)的有限集合。1. 當(dāng)n=0時(shí)，稱(chēng)為空樹(shù)。2. 當(dāng)n>0時(shí)，有且僅有一個(gè)根的結(jié)點(diǎn)。D.插入排序的空間復(fù)雜度為O(1)12.有關(guān)樹(shù)的敘述正確的是( C )A.每一個(gè)內(nèi)部結(jié)點(diǎn)至少有一個(gè)兄弟B.每一個(gè)葉結(jié)點(diǎn)均有父結(jié)點(diǎn)C.有的樹(shù)沒(méi)有子樹(shù)D.每個(gè)樹(shù)至少有一個(gè)根結(jié)點(diǎn)與一個(gè)葉結(jié)點(diǎn)。(有且僅有一個(gè)結(jié)點(diǎn))13.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組元素A0至Am中，則入隊(duì)時(shí)的操作為( D )A.rear=rear+1B.rear=(rear+1)(m-1)C.rear=(rear+1)mD.rear=(rear+1)(m+1)14.關(guān)于串的的敘述，不正確的是( B )A.串是字符的有限序列B.空串是由空格

5、構(gòu)成的串 注：空格串是只包括空格的串，空格串是有長(zhǎng)度的，而空串沒(méi)有長(zhǎng)度。C.替換是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)15.對(duì)稱(chēng)矩陣ANN，A11為首元素，將下三角(包括對(duì)角線(xiàn))元素以行優(yōu)先順序存儲(chǔ)到一維數(shù)組元素T1至TN(N+1)2中，則任一上三角元素Aij存于Tk中，下標(biāo)k為( B )A .i (i-1)2+jB. j(j-1)2+iC .i (j-i)2+1D. j(i-1)2+l 二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.下列程序段的時(shí)間復(fù)雜度為_(kāi)O(n3)_。for(i=1；i<=n；i+

6、)for(j=1；j<=n；j+)for(k=1；k<=n；k+)s=i+j+k；17.在數(shù)據(jù)結(jié)構(gòu)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)可以鄰接的結(jié)構(gòu)稱(chēng)為_(kāi)圖狀結(jié)構(gòu)_。18.在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)_直接后繼_的。注：數(shù)據(jù)域-前接前趨，指針域直接后繼19.在棧結(jié)構(gòu)中，允許插入的一端稱(chēng)為_(kāi)棧頂_。 注：隊(duì)列允許插入的一端叫隊(duì)尾。20.從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng)n-i_個(gè)元素。 注：向后移動(dòng)n-i+1個(gè)元素。21.一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素

7、為_(kāi)n-i+1_。22.循環(huán)隊(duì)列被定義為結(jié)構(gòu)類(lèi)型，含有三個(gè)域：data、front和rear，則循環(huán)隊(duì)列sq為空的條件是_sq.rear=sq.front_。注：1，使用下列公式必要前提是，矩陣式n*n的，也就是方矩陣。上三角情況：當(dāng)iJ時(shí)（前小于等于后）所求地址=首元素所占地址+i(20n-i+1)/2+j-i下三角情況：當(dāng)ij時(shí)所求地址=首元素所占地址+i(i+1)/2+j23.一個(gè)10階對(duì)稱(chēng)矩陣A，采用行優(yōu)先順序壓縮存儲(chǔ)上三角元素，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a45的地址為_(kāi)35_。解；k=0+4（2*10-4+1）/2+5-4=3524.對(duì)于一棵

8、滿(mǎn)二叉樹(shù)，若有m個(gè)葉子，則樹(shù)中結(jié)點(diǎn)數(shù)為_(kāi)2m-1_。(2m-1又稱(chēng)為哈夫曼樹(shù))25.含有n個(gè)頂點(diǎn)和n-1條邊的連通圖G采用_鄰接表_存儲(chǔ)結(jié)構(gòu)較省空間。 n*(n-1)為有向圖，為稀疏矩陣，采用鄰接表。n*（n-1）/2為無(wú)向圖，為對(duì)稱(chēng)矩陣，采用鄰接矩陣。26.在圖中，第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為_(kāi)（簡(jiǎn)單）回路或（簡(jiǎn)單）環(huán)_。27.動(dòng)態(tài)查找中兩個(gè)元素X，Y存入同一個(gè)散列表時(shí)，X、Y鍵值相同，則這種情況稱(chēng)為_(kāi)沖突_。28.堆排序需_一_個(gè)記錄大小的輔助存儲(chǔ)空間。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.有一字符串的次序?yàn)?3*y+ay！2，試?yán)脳⑤敵龃涡蚋淖優(yōu)?y*-a

9、y！2+，試寫(xiě)出進(jìn)棧和退棧的操作步驟。(用push(x)表示x進(jìn)棧，pop(x)表示x退棧)解題技巧剖析：1. 根據(jù)后進(jìn)先出原則。3.把原始字符串與要改變次序的字符串寫(xiě)成如下格式。2.寫(xiě)一點(diǎn)，劃一點(diǎn)原則。2. - 3 * y + a y ！ 2 3 y * - a y ！ 2 + 3. 例如：enter-> -,3 exit ->3, 此時(shí)，剩下 -。 對(duì)應(yīng)著，把里已輸入的 3，刪掉。然后把標(biāo)明已產(chǎn)生排序，然 Push(-)push(3)pop(3) 后以此類(lèi)推。 注：退的時(shí)候，從后往前劃。30.已知一棵二叉樹(shù)的先根遍歷序列為ABCDEGHF，中根遍歷序列為CBEDAGFH，畫(huà)出該

10、二叉樹(shù)。答：由題可知，該二叉樹(shù)為： 解題要點(diǎn)：1.先確定最高分界點(diǎn)左面有幾個(gè)圈，然后確定分界點(diǎn)。如本題，分界點(diǎn)左面有4個(gè)圈，則32 33 34 35 36 37 38 39 4036為分界點(diǎn)2.以根節(jié)點(diǎn)為界，左孩子小于又孩子。3.若出現(xiàn)連續(xù)左孩子，或連續(xù)又孩子，注意左孩子連續(xù)減小原則，又孩子連續(xù)增大原則。4.圈的之間差值最小原則。31.題31圖中二叉排序樹(shù)的各結(jié)點(diǎn)的值為3240，標(biāo)出各結(jié)點(diǎn)的值。40363240353733383439題31圖32.下述矩陣表示一個(gè)無(wú)向網(wǎng)，畫(huà)出該無(wú)向網(wǎng)，并構(gòu)造出其最小生成樹(shù)。答：1連通圖為：0 0 1 2 3 4 50123453651125532644560解

11、題思路：1.畫(huà)連通圖時(shí)的一個(gè)技巧是，數(shù)字基本按順序?qū)懀?為最高端。然后根據(jù)下標(biāo)找出路線(xiàn)即可。 2.最小生成樹(shù)和最優(yōu)路徑選著法一樣，記住兩點(diǎn)之間只有一條線(xiàn)連接。注意：一個(gè)點(diǎn)出去的最短不代表到下一個(gè)點(diǎn)最短，要把兩條路徑加起來(lái)比較一下。2.最小生成樹(shù)為：131253235433.什么是堆?寫(xiě)出對(duì)應(yīng)于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆頂元素取最小值)。答：1堆是一鍵值序列k1,k2,kn,對(duì)所有i=1,2,3 n/2 滿(mǎn)足kik2i解題思路：1. 先將給出的序列以完全二叉樹(shù)依次寫(xiě)出。2. 然后從最右邊的看起，若要求最小根，那么找小的作為根。若要求最大根，那么找最大

12、的作為根。3. 總之，求最大根，從總根開(kāi)始，結(jié)點(diǎn)根依次減小，求最小根，結(jié)點(diǎn)根逐漸減大。4. 調(diào)整位置即可。3 Kik2i+1由題意可以得出如下初始堆972010674133075四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)34.二叉樹(shù)按二叉鏈表形式存儲(chǔ)，編寫(xiě)一個(gè)算法判別給定的二叉樹(shù)是否為完全二叉樹(shù)。Int Judgecomplete(Bitree bt) /判斷是否是二叉樹(shù)，是返回1，否返回0Int tag=0,Bitree p=bt,Q; /Q是隊(duì)列，元素是二叉樹(shù)的結(jié)點(diǎn)指針，容量足夠大If (p=null) return (1); QueueInit(Q),Queuelint(Q,

13、p); /初始化隊(duì)列，根節(jié)點(diǎn)入隊(duì) While (!QueueEmpty(Q) p=QueueOut(Q); /出隊(duì) If（p->lchild&&!tag）QueneIn(Q,p->lchild) /左孩子入隊(duì)Else if (p->lchild) return 0; /前面已有節(jié)點(diǎn)為空，此結(jié)點(diǎn)不為空 Else tag=1; /首次出現(xiàn)結(jié)點(diǎn)為空 If (p->right&&!tag) QueneIn(Q,p->rchild) /又孩子入隊(duì)Elseif (p->rchild) return 0; Else tag=1;/while return 1 ;/JudgeComplete35.試寫(xiě)出直接插入排序算法。Void Straigh