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

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

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

3、n2)D.以上都不對(duì)7. 設(shè)二維數(shù)組A610，每個(gè)數(shù)組元素占用4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放的數(shù)組元素a35的存儲(chǔ)地址為1000，則a00的存儲(chǔ)地址是 。A.872B.860C.868D.8648. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為 。A.11B.10C.111025D.1210249. 一棵二叉樹(shù)的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為 。A.ACBEDB.DECABC.DEABCD.CEDBA10. 對(duì)圖1所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行深度優(yōu)先遍歷；可得到頂點(diǎn)訪問(wè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 一個(gè)無(wú)向圖二、填空題（每題2分，共10分）1. 順序隊(duì)和鏈隊(duì)的區(qū)別僅在于 的不同。2. 在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。3. 對(duì)有18個(gè)元素的有序表R1.18進(jìn)行二分查找，則查找R3的比較序列的下標(biāo)為 。4. 對(duì)含有n元素的關(guān)鍵字序列進(jìn)行直接選擇排序時(shí)，所需進(jìn)行的關(guān)鍵字之間的比較次數(shù)為 。5. 已知關(guān)鍵字序列為2,7,4,3,1,9,10,5,6,8，采用堆排序法對(duì)該序列作升序排序時(shí)，構(gòu)造的初始堆（大根堆）是 。（不用畫(huà)出堆，只需寫(xiě)出初始堆的序列）三、問(wèn)答題（共40分）1. 一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)是多少？（

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

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

7、 A4. A5. B6. B7. B8. C9. D10. A二、填空題（每題2分，共10分）1. 存儲(chǔ)方法或存儲(chǔ)結(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。（序列不全對(duì)不給分）三、問(wèn)答題（共40分）1. 答：二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(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。評(píng)分標(biāo)準(zhǔn)：只給出結(jié)果給3分

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

9、4. 答：不能。因?yàn)樵谶@里，二分查找只減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)不變，時(shí)間的復(fù)雜度仍為O(n2)。評(píng)分標(biāo)準(zhǔn)：答對(duì)“不能”占3分，說(shuō)明理由占5分。5. 答：生成初始?xì)w并段（或順串），采用多路平衡歸并方法進(jìn)行歸并。四、算法設(shè)計(jì)題（共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-next,*minp=p,*minpre=pre;E

10、lemType mindata=p-data;while (p!=NULL & p-datadata;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;評(píng)分標(biāo)準(zhǔn)：根據(jù)算法的正確性評(píng)分，不考慮算法的時(shí)間復(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;評(píng)分標(biāo)準(zhǔn)：根據(jù)算法的正確性評(píng)分，不考慮算法的