1、【精品文檔】如有侵權，請聯系網站刪除，僅供學習與交流數據結構考試題6.精品文檔.要求：所有的題目的解答均寫在答題紙上（每張答題紙上要寫清楚姓名、班號和學號），需寫清楚題目的序號。每張答題紙都要寫上姓名和序號。一、單項選擇題（每小題2分，共20分）1. 在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲 。A. 數據的處理方法 B. 數據元素的類型C. 數據元素之間的關系 D. 數據的存儲方法2. 下述函數中對應的漸進時間復雜度（n為問題規模）最小是 。A.T1(n)=nlog2n+5000n B.T2(n)=n2-8000nC.T3(n)= n-6000n D.T4(n)=7000log

2、2n3. 設線性表有n個元素，以下操作中， 在順序表上實現比在鏈表上實現效率更高。A.輸出第i（1in）個元素值B.交換第1個元素與第2個元素的值C.順序輸出這n個元素的值D.輸出與給定值x相等的元素在線性表中的序號4. 設n個元素進棧序列是p1，p2，p3，pn，其輸出序列是1，2，3，n，若p3=3，則p1的值 。A.可能是2B.一定是2C.不可能是1D.一定是15. 以下各種存儲結構中，最適合用作鏈隊的鏈表是 。A.帶隊首指針和隊尾指針的循環單鏈表B.帶隊首指針和隊尾指針的非循環單鏈表C.只帶隊首指針的非循環單鏈表D.只帶隊首指針的循環單鏈表6. 對于鏈串s（長度為n，每個結點存儲一個字

3、符），查找元素值為ch的算法的時間復雜度為 。A.O(1)B.O(n)C.O(n2)D.以上都不對7. 設二維數組A610，每個數組元素占用4個存儲單元，若按行優先順序存放的數組元素a35的存儲地址為1000，則a00的存儲地址是 。A.872B.860C.868D.8648. 一個具有1025個結點的二叉樹的高h為 。A.11B.10C.111025D.1210249. 一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為 。A.ACBEDB.DECABC.DEABCD.CEDBA10. 對圖1所示的無向圖，從頂點1開始進行深度優先遍歷；可得到頂點訪問序列 。A.

4、1 2 4 3 5 7 6B.1 2 4 3 5 6 7C.1 2 4 5 6 3 7D.1 2 3 4 5 7 6圖1 一個無向圖二、填空題（每題2分，共10分）1. 順序隊和鏈隊的區別僅在于 的不同。2. 在有n個頂點的有向圖中，每個頂點的度最大可達 。3. 對有18個元素的有序表R1.18進行二分查找，則查找R3的比較序列的下標為 。4. 對含有n元素的關鍵字序列進行直接選擇排序時，所需進行的關鍵字之間的比較次數為 。5. 已知關鍵字序列為2,7,4,3,1,9,10,5,6,8，采用堆排序法對該序列作升序排序時，構造的初始堆（大根堆）是 。（不用畫出堆，只需寫出初始堆的序列）三、問答題

5、（共40分）1. 一棵完全二叉樹上有1001個結點，其中葉結點的個數是多少？（需寫出推導過程，8分）2. 給出如下各種情況下求任意一個頂點的度的過程（只需文字描述）：（8分）（1）含n個頂點的無向圖采用鄰接矩陣存儲；（2）含n個頂點的無向圖采用鄰接表存儲；（3）含n個頂點的有向圖采用鄰接矩陣存儲；（4）含n個頂點的有向圖采用鄰接表存儲。3. 將整數序列4,5,7,2,1,3,6中的數依次插入到一棵空的平衡二叉樹中，試構造相應的平衡二叉樹。（要求畫出每個元素插入過程，若需調整，還需給出調整后的結果，并指出是什么類型的調整，12分）4. 當實現插入直接排序過程中，假設R0.i-1為有序區，Ri.n

6、-1為無序區，現要將Ri插入到有序區中，可以用二分查找來確定Ri在有序區中的可能插入位置，這樣做能否改善直接插入排序算法的時間復雜度?為什么?（8分）5. 簡述外排序的兩個階段。（4分）四、算法設計題（每小題10分，共30分）1. 設計一個算法delminnode(LinkList *&L)，在帶頭結點的單鏈表L中刪除所有結點值最小的結點（可能有多個結點值最小的結點）。2. 假設二叉樹采用二叉鏈存儲結構存儲，設計一個算法copy(BTNode *b,BTNode *&t)，由二叉樹b復制成另一棵二叉樹t。3. 假設一個無向圖是非連通的，采用鄰接表作為存儲結構，試設計一個算法，輸

7、出圖中各連通分量的節點序列。參考答案一、單項選擇題（每小題2分，共20分）1. C2. D3. A4. A5. B6. B7. B8. C9. D10. A二、填空題（每題2分，共10分）1. 存儲方法或存儲結構。2. 2(n-1)。3. 9、4、2、34. n(n-1)/2。5. 10,8,9,6,7,2,4,5,3,1。（序列不全對不給分）三、問答題（共40分）1. 答：二叉樹中度為1的結點個數只能是1或0。設n1=1，n=n0+n1+n2=n0+n2+1=1001，由性質1可知n0=n2+1，由兩式可求n0=500.5，不成立；設n1=0，n=n0+n1+n2=n0+n2=1001，由性

8、質1可知n0=n2+1，由兩式可求n0=501。本題答案為：501。評分標準：只給出結果給3分，推導過程占5分。2. 答：對于鄰接矩陣表示的無向圖，頂點i的度等于第i行中元素等于1的個；對于鄰接矩陣表示的有向圖，頂點i的出度等于第i行中元素等于1的個數；入度等于第i列中元素等于1的個數；度數等于它們之和。對于鄰接矩陣表示的無向圖，頂點i的出度等于g->adjlisti為頭結點的單鏈表中結點的個數；入度需要遍歷各頂點的邊表，若g->adjlistk為頭結點的單鏈表中存在頂點編號為i的結點，則頂點i的入度增1；度數等于它們之和。評分標準：有向圖、無向圖兩種存儲方式各占4分。3. 建立平

9、衡二叉樹過程如圖2所示(圖中加陰影的結點表示要調整的結點)。圖2 構造平衡二叉樹過程評分標準：每次調整占1分。4. 答：不能。因為在這里，二分查找只減少了關鍵字間的比較次數，而記錄的移動次數不變，時間的復雜度仍為O(n2)。評分標準：答對“不能”占3分，說明理由占5分。5. 答：生成初始歸并段（或順串），采用多路平衡歸并方法進行歸并。四、算法設計題（共30分）1. 解：用p從頭至尾掃描單鏈表，pre指向*p結點的前驅，用minp保存值最小的結點指針，minpre指向*minp結點的前驅。一面掃描，一面比較，將最小值的結點放到*minp中。算法如下：void delminnode(LinkLis

10、t *&L)LinkList *pre=L,*p=pre->next,*minp=p,*minpre=pre;ElemType mindata=p->data;while (p!=NULL && p->data<mindata)mindata=p->data;p=p->next;p=pre->next;while (p!=NULL)if (p->data=mindata)pre->next=p->next;free(p);pre=pre->next;p=pre->next;評分標準：根據算法的正確性評分，不考慮算法的時間復雜度。2解：遞歸算法如下：void copy(BTNode *b,BTNode *&t)BTNode *l,*r;if (b=NULL) t=NULL;elset=(BTNode *)malloc(sizeof(BTNode);copy(b->lchild,l);copy(b->rchild,r);t->lchild=l;t->rchild=r;評分標準：根據算法的正確性評分，不考慮算法的時間復雜度。3. 解：采