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

1、要求：所有的題目的解答均寫在答題紙上（每張答題紙上要寫清楚姓名、班號和學(xué)號），需寫清楚題目的序號。每張答題紙都要寫上姓名和序號。一、單項選擇題（每小題2分，共20分）1. 在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 。A. 數(shù)據(jù)的處理方法 B. 數(shù)據(jù)元素的類型C. 數(shù)據(jù)元素之間的關(guān)系 D. 數(shù)據(jù)的存儲方法2. 下述函數(shù)中對應(yīng)的漸進(jìn)時間復(fù)雜度（n為問題規(guī)模）最小是 。A.T1(n)=nlog2n+5000n B.T2(n)=n2-8000nC.T3(n)= n-6000n D.T4(n)=7000log2n3. 設(shè)線性表有n個元素，以下操作中， 在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高

2、。A.輸出第i（1in）個元素值B.交換第1個元素與第2個元素的值C.順序輸出這n個元素的值D.輸出與給定值x相等的元素在線性表中的序號4. 設(shè)n個元素進(jìn)棧序列是p1，p2，p3，pn，其輸出序列是1，2，3，n，若p3=3，則p1的值 。A.可能是2B.一定是2C.不可能是1D.一定是15. 以下各種存儲結(jié)構(gòu)中，最適合用作鏈隊的鏈表是 。A.帶隊首指針和隊尾指針的循環(huán)單鏈表B.帶隊首指針和隊尾指針的非循環(huán)單鏈表C.只帶隊首指針的非循環(huán)單鏈表D.只帶隊首指針的循環(huán)單鏈表6. 對于鏈串s（長度為n，每個結(jié)點(diǎn)存儲一個字符），查找元素值為ch的算法的時間復(fù)雜度為 。A.O(1)B.O(n)C.O(n

3、2)D.以上都不對7. 設(shè)二維數(shù)組A610，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素a35的存儲地址為1000，則a00的存儲地址是 。A.872B.860C.868D.8648. 一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為 。A.11B.10C.111025D.1210249. 一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為 。A.ACBEDB.DECABC.DEABCD.CEDBA10. 對圖1所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷；可得到頂點(diǎn)訪問序列 。A.1 2 4 3 5 7 6B.1 2 4 3 5 6 7C.1 2 4 5 6

4、3 7D.1 2 3 4 5 7 6圖1 一個無向圖二、填空題（每題2分，共10分）1. 順序隊和鏈隊的區(qū)別僅在于 的不同。2. 在有n個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá) 。3. 對有18個元素的有序表R1.18進(jìn)行二分查找，則查找R3的比較序列的下標(biāo)為 。4. 對含有n元素的關(guān)鍵字序列進(jìn)行直接選擇排序時，所需進(jìn)行的關(guān)鍵字之間的比較次數(shù)為 。5. 已知關(guān)鍵字序列為2,7,4,3,1,9,10,5,6,8，采用堆排序法對該序列作升序排序時，構(gòu)造的初始堆（大根堆）是 。（不用畫出堆，只需寫出初始堆的序列）三、問答題（共40分）1. 一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個數(shù)是多少？（需

5、寫出推導(dǎo)過程，8分）2. 給出如下各種情況下求任意一個頂點(diǎn)的度的過程（只需文字描述）：（8分）（1）含n個頂點(diǎn)的無向圖采用鄰接矩陣存儲；（2）含n個頂點(diǎn)的無向圖采用鄰接表存儲；（3）含n個頂點(diǎn)的有向圖采用鄰接矩陣存儲；（4）含n個頂點(diǎn)的有向圖采用鄰接表存儲。3. 將整數(shù)序列4,5,7,2,1,3,6中的數(shù)依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應(yīng)的平衡二叉樹。（要求畫出每個元素插入過程，若需調(diào)整，還需給出調(diào)整后的結(jié)果，并指出是什么類型的調(diào)整，12分）4. 當(dāng)實(shí)現(xiàn)插入直接排序過程中，假設(shè)R0.i-1為有序區(qū)，Ri.n-1為無序區(qū)，現(xiàn)要將Ri插入到有序區(qū)中，可以用二分查找來確定Ri在有序區(qū)中的可能

6、插入位置，這樣做能否改善直接插入排序算法的時間復(fù)雜度?為什么?（8分）5. 簡述外排序的兩個階段。（4分）四、算法設(shè)計題（每小題10分，共30分）1. 設(shè)計一個算法delminnode(LinkList *&L)，在帶頭結(jié)點(diǎn)的單鏈表L中刪除所有結(jié)點(diǎn)值最小的結(jié)點(diǎn)（可能有多個結(jié)點(diǎn)值最小的結(jié)點(diǎn)）。2. 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，設(shè)計一個算法copy(BTNode *b,BTNode *&t)，由二叉樹b復(fù)制成另一棵二叉樹t。3. 假設(shè)一個無向圖是非連通的，采用鄰接表作為存儲結(jié)構(gòu)，試設(shè)計一個算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。參考答案一、單項選擇題（每小題2分，共20分）1.

7、C2. D3. A4. A5. B6. B7. B8. C9. D10. A二、填空題（每題2分，共10分）1. 存儲方法或存儲結(jié)構(gòu)。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的結(jié)點(diǎn)個數(shù)只能是1或0。設(shè)n1=1，n=n0+n1+n2=n0+n2+1=1001，由性質(zhì)1可知n0=n2+1，由兩式可求n0=500.5，不成立；設(shè)n1=0，n=n0+n1+n2=n0+n2=1001，由性質(zhì)1可知n0=n2+1，由兩式可求n0=501。本題答案為：501。評分標(biāo)準(zhǔn)：只

8、給出結(jié)果給3分，推導(dǎo)過程占5分。2. 答：對于鄰接矩陣表示的無向圖，頂點(diǎn)i的度等于第i行中元素等于1的個；對于鄰接矩陣表示的有向圖，頂點(diǎn)i的出度等于第i行中元素等于1的個數(shù)；入度等于第i列中元素等于1的個數(shù)；度數(shù)等于它們之和。對于鄰接矩陣表示的無向圖，頂點(diǎn)i的出度等于g->adjlisti為頭結(jié)點(diǎn)的單鏈表中結(jié)點(diǎn)的個數(shù)；入度需要遍歷各頂點(diǎn)的邊表，若g->adjlistk為頭結(jié)點(diǎn)的單鏈表中存在頂點(diǎn)編號為i的結(jié)點(diǎn)，則頂點(diǎn)i的入度增1；度數(shù)等于它們之和。評分標(biāo)準(zhǔn)：有向圖、無向圖兩種存儲方式各占4分。3. 建立平衡二叉樹過程如圖2所示(圖中加陰影的結(jié)點(diǎn)表示要調(diào)整的結(jié)點(diǎn))。圖2 構(gòu)造平衡二叉樹

9、過程評分標(biāo)準(zhǔn)：每次調(diào)整占1分。4. 答：不能。因為在這里，二分查找只減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變，時間的復(fù)雜度仍為O(n2)。評分標(biāo)準(zhǔn)：答對“不能”占3分，說明理由占5分。5. 答：生成初始?xì)w并段（或順串），采用多路平衡歸并方法進(jìn)行歸并。四、算法設(shè)計題（共30分）1. 解：用p從頭至尾掃描單鏈表，pre指向*p結(jié)點(diǎn)的前驅(qū)，用minp保存值最小的結(jié)點(diǎn)指針，minpre指向*minp結(jié)點(diǎn)的前驅(qū)。一面掃描，一面比較，將最小值的結(jié)點(diǎn)放到*minp中。算法如下：void delminnode(LinkList *&L)LinkList *pre=L,*p=pre->nex

10、t,*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;評分標(biāo)準(zhǔn)：根據(jù)算法的正確性評分，不考慮算法的時間復(fù)雜度。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;評分標(biāo)準(zhǔn)：根據(jù)算法的正確性評分，不考慮算法的時間復(fù)雜度。3. 解：采用深