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

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

3、B.以鏈式方式存儲C.以順序方式存儲，且結點按關鍵字有序排列D.以鏈接方式存儲，且結點按關鍵字有序排列9.在表長為n的順序表上做刪除運算，其平均時間復雜度為( B )A.O(1)B.O(n) 注：在雙向循環鏈表中，刪除最后一個結點C.O(nlog2n)D.O(n2) 的時間復雜度為O(1)10.當利用大小為n的數組順序存儲一個隊列時，該隊列的最大容量為( B )A.n-2B.n-1C.nD.n+111.有關插入排序的敘述，錯誤的是( C )A.插入排序在最壞情況下需要O(n2)時間B.插入排序在最佳情況可在O(n)時間內完成C.插入排序平均需要O(nlog2n)時間 -快速排序需要o（nlog

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

5、構成的串 注：空格串是只包括空格的串，空格串是有長度的，而空串沒有長度。C.替換是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲15.對稱矩陣ANN，A11為首元素，將下三角(包括對角線)元素以行優先順序存儲到一維數組元素T1至TN(N+1)2中，則任一上三角元素Aij存于Tk中，下標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分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.下列程序段的時間復雜度為_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.在數據結構中，各個結點按邏輯關系互相纏繞，任意兩個結點可以鄰接的結構稱為_圖狀結構_。18.在單鏈表中，存儲每個結點有兩個域，一個是數據域，另一個是指針域，指針域指向該結點_直接后繼_的。注：數據域-前接前趨，指針域直接后繼19.在棧結構中，允許插入的一端稱為_棧頂_。 注：隊列允許插入的一端叫隊尾。20.從一個長度為n的順序表中刪除第i個元素(1in)時，需向前移動n-i_個元素。 注：向后移動n-i+1個元素。21.一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素

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

8、滿二叉樹，若有m個葉子，則樹中結點數為_2m-1_。(2m-1又稱為哈夫曼樹)25.含有n個頂點和n-1條邊的連通圖G采用_鄰接表_存儲結構較省空間。 n*(n-1)為有向圖，為稀疏矩陣，采用鄰接表。n*（n-1）/2為無向圖，為對稱矩陣，采用鄰接矩陣。26.在圖中，第一個頂點和最后一個頂點相同的路徑稱為_（簡單）回路或（簡單）環_。27.動態查找中兩個元素X，Y存入同一個散列表時，X、Y鍵值相同，則這種情況稱為_沖突_。28.堆排序需_一_個記錄大小的輔助存儲空間。三、應用題(本大題共5小題，每小題6分，共30分)29.有一字符串的次序為-3*y+ay！2，試利用棧將輸出次序改變為3y*-a

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

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

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

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

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