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

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

2、操作中， 高。 _ 在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更A. 輸出第 i ( K i w n) 個(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.可能是 2C.不可能是1B.一定是D. 一定是215. 以下各種存儲(chǔ)結(jié)構(gòu)中，最適合用作鏈隊(duì)的鏈表是_ 。A.帶隊(duì)首指針和隊(duì)尾指針的循環(huán)單鏈表B.帶隊(duì)首指針和隊(duì)尾指針的非循環(huán)單鏈表C.只帶隊(duì)首指針的非循環(huán)單鏈表D.只帶隊(duì)首指針的循

3、環(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( n 2 )D.以上都不對(duì)7. 設(shè)二維數(shù)組 A610組元素 a35 的，每個(gè)數(shù)組元素占用4 個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存儲(chǔ)地址為存放的數(shù)A.8721000 ，貝 y a00 的存儲(chǔ)地址是C.868B.8608. 一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹的高D.864A.11h 為 。C.11? 1025B.10D.12 ? 10249. 一棵二叉樹的后序遍歷序列為DABEC ，中序遍歷序列為DEBAC ，則先序遍歷序列A.ACBEDB.DECABC.

4、DEABCD.CEDBA10. 對(duì)圖 1 所示的無向圖，從頂點(diǎn) 1 開始進(jìn)行深度優(yōu)先遍歷；可得到頂點(diǎn)訪問序列歡迎下載2A.1243576B.1243567C.1245637二、 填空題（每題 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í)

5、，構(gòu)造的初始堆（大根堆）是 _ 。（不用畫出堆，只需寫出初始堆的序列）三、 問答題（共 40 分）1. 一棵完全二叉樹上有 1001 個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)是多少？（需寫出推導(dǎo)過程，8 分）2. 給出如下各種情況下求任意一個(gè)頂點(diǎn)的度的過程（只需文字描述）：（ 8 分）（ 1 ）含 n 個(gè)頂點(diǎn)的無向圖采用鄰接矩陣存儲(chǔ)；（ 2） 含 n 個(gè)頂點(diǎn)的無向圖采用鄰接表存儲(chǔ)；（ 3） 含 n 個(gè)頂點(diǎn)的有向圖采用鄰接矩陣存儲(chǔ)；（ 4） 含 n 個(gè)頂點(diǎn)的有向圖采用鄰接表存儲(chǔ)。3.將整數(shù)序列 4,5,7,2,136 中的數(shù)依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應(yīng)的平衡二叉樹。（要求畫出每個(gè)元素插入過程，若需

6、調(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ū)中的可能插入位置，這樣做能否改善直接插入排序算法的時(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è)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法copy

7、 （ BTNode*b,BTNode*&t ），由二叉樹b 復(fù)制成另一棵二叉樹to歡迎下載33. 假設(shè)一個(gè)無向圖是非連通的，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。歡迎下載4參考答案一、單項(xiàng)選擇題（每小題2 分，共 20 分）1.C2. D3. 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ì)不給分）三、問答題（共 40 分）1. 答：二叉樹中度為 1

8、 的結(jié)點(diǎn)個(gè)數(shù)只能是1 或 0。設(shè) n1=1 ，n=n +n+n=n0+ n+1=1001 ，°122由性質(zhì) 1可知 n =n+1，由兩式可求 n=500.5 ，不成立；設(shè)n1=0 ， n=n +n 什 n=n +n=1001 ，° 20°2°2由性質(zhì) 1可知 n0=n 2+1 ，由兩式可求 n0=501 。本題答案為： 501。評(píng)分標(biāo)準(zhǔn)：只給出結(jié)果給3 分，推導(dǎo)過程占 5 分。2. 答：對(duì)于鄰接矩陣表示的無向圖，頂點(diǎn)i 的度等于第 i 行中元素等于1的個(gè)；對(duì)于鄰接矩陣表示的有向圖，頂點(diǎn)i 的出度等于第i 行中元素等于1 的個(gè)數(shù)；入度等于第i 列中 元素等

9、于1 的個(gè)數(shù)；度數(shù)等于它們之和。對(duì)于鄰接矩陣表示的無向圖，頂點(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)：有向圖、無向圖兩種存儲(chǔ)方式各占4 分。3. 建立平衡二叉樹過程如圖2 所示（圖中加陰影的結(jié)點(diǎn)表示要調(diào)整的結(jié)點(diǎn)）。歡迎下載51-20045插入 4插入 5插入 7RR 調(diào)整115插入 25 0470002155插入 1LL 調(diào)整0 7插入 34710202-1感(7丿07 '7 0201410000-

10、114 )'4 J0bLR調(diào)整? -16. &龜-2 |丄 TV插-入( 21030、37131000010004RL 調(diào)整 c 彳廣6 -013570000圖 2 構(gòu)造平衡二叉樹過程評(píng)分標(biāo)準(zhǔn)：每次調(diào)整占1 分。4. 答：不能。因?yàn)樵谶@里，二分查找只減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)不變，時(shí)間的復(fù)雜度仍為0( n 2)。評(píng)分標(biāo)準(zhǔn)：答對(duì)“不能”占3 分，說明理由占5 分。5. 答：生成初始?xì)w并段 ( 或順串 ) ，采用多路平衡歸并方法進(jìn)行歸并。四、算法設(shè)計(jì)題 ( 共 30 分)1.解：用 p 從頭至尾掃描單鏈表，pre 指向 *p 結(jié)點(diǎn)的前驅(qū)，用minp 保存值最小的結(jié)點(diǎn)

11、指針，minpre 指向 *minp 結(jié)點(diǎn)的前驅(qū)。一面掃描，一面比較，將最小值的結(jié)點(diǎn)放到*minp中。算法如下：void delminnode(LinkList *&L)歡迎下載6Lin kList *pre=L,*p=pre _>n ext,*mi np=p,*mi npre=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->

12、;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)：