數(shù)據(jù)結(jié)構(gòu)自考題-4

1、數(shù)據(jù)結(jié)構(gòu)自考題 -4( 總分： 103.00 ，做題時(shí)間： 90 分鐘 )一、單項(xiàng)選擇題 ( 總題數(shù)： 14，分?jǐn)?shù)： 28.00)1. 棧一般情況下常采用以下兩種存儲(chǔ)方式( )A. 順序結(jié)構(gòu)和散列結(jié)構(gòu) B 散列結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：2. 考慮下列四種排序方法，在排序過(guò)程中，關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無(wú)關(guān)的是( )A. 直接插入排序和快速排序B 快速排序和歸并排序C.直接選擇排序和歸并排序D 直接插入排序和歸并排序(分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：3. 在桶排序中，其平均時(shí)間復(fù)雜度

2、是 ( )A. 0(1) B . 0(n) C . 0(n2) D . 0(1gn)(分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：4. 鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)即 ( )A. 插入操作更加方便B .通常不會(huì)出現(xiàn)棧滿(mǎn)的情況C.不會(huì)出現(xiàn)?？盏那闆r D .刪除操作更加方便分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：5. 二維數(shù)組 A106 采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占 4 個(gè)存儲(chǔ)單元，已知元素 A34 的存儲(chǔ)地址 為 1000 ，則元素 A43 的存儲(chǔ)地址為 （ ）A 1020 B 1024C 1036 D 1240（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：解析由題意可

3、知，自A34的存儲(chǔ)地址1000起共存放了 5個(gè)元素（即A34 、A35 、A40、 A41和A42） 后，才開(kāi)始存放 A43，所以A43的存儲(chǔ)地址為1000+5X4=102Q6. 鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類(lèi)似于于叉樹(shù)的 （ ）A. 先序遍歷B 中序遍歷C 后序遍歷D 按層遍歷（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：7. 對(duì)采用二分查找法進(jìn)行查找運(yùn)算的查找表，要求按 （ ） 方式進(jìn)行存儲(chǔ)。A.順序存儲(chǔ)B 鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序D 鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析：8. 將上萬(wàn)個(gè)一組無(wú)序并且互不相等的正整數(shù)序列，存放于

4、順序存儲(chǔ)結(jié)構(gòu)中，采用（ ）方法能夠最快地找出其中最大的正整數(shù)。A.快速排序B 插入排序C 選擇排序D 歸并排序（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析：9. 已知二叉樹(shù)的中序序列和后序序列均為ABCDEF則該二叉樹(shù)的先序序列為 （）A. FEDCBA B ABCDEFCFDECBA DFBDCEA(分?jǐn)?shù):2.00 )A. VB.C.D.解析：解析對(duì)于前序遍歷、中序遍歷和后序遍歷，將結(jié)點(diǎn)按其訪問(wèn)的先后次序排列起來(lái)，所得到的結(jié)點(diǎn) 序列分別稱(chēng)為前序序列、中序序列和后序序列。用線10. 設(shè)散列函數(shù)為H（k）=k mod7，組關(guān)鍵碼為23,14,9,6,30,12 和18,散列表T的地址空間為0.

5、6， 性探測(cè)法解決沖突，依次將這組關(guān)鍵碼插入T中，得到的散列表為（）（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：11. 對(duì)含有（）個(gè)結(jié)點(diǎn)的非空二叉樹(shù)，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問(wèn)序列均相同A. O B. 1 C . 2 D .不存在這樣的二叉樹(shù)（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：12. 若用冒泡排序法對(duì)序列18,14,6,27,8,12,16,52,10,26,47,29,41,24從小到大進(jìn)行排序，共要進(jìn)行次比較。A. 33 B. 45 C . 70 D. 91（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：13. 下列排序算法中，其時(shí)間復(fù)雜度和記錄的初始排列無(wú)關(guān)的是 （） A

6、.插入排序B 堆排序C 快速排序D 冒泡排序（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析：14. 在圖的鄰接表存儲(chǔ)結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類(lèi)似于二叉樹(shù)上的 （ ）A.先序遍歷B 中序遍歷C 后序遍歷D 按層次遍歷（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：二、填空題 （總題數(shù)： 10，分?jǐn)?shù)： 20.00）15. 判斷一個(gè)沒(méi)有頭結(jié)點(diǎn)的單鏈表 head 為空的條件是 1（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:（正確答案： hcad=NULL）解析：16.設(shè)二維數(shù)組 A10 20,5 10按行優(yōu)先存儲(chǔ)，每個(gè)元素占4 個(gè)存儲(chǔ)單元， A10,5 的存儲(chǔ)地址是1000，則 A15,10 的存儲(chǔ)地址是1

7、。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 1700）解析：17. 對(duì)于一個(gè)具有 n 條邊和 e 個(gè)頂點(diǎn)的圖來(lái)說(shuō)，如果采用鄰接表表示， 則其空間復(fù)雜度為 ，若采用鄰接矩陣表示，則其空間復(fù)雜度為 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： O（n+c） O（n 2） ）解析：18. 在5階B-樹(shù)中，每個(gè)結(jié)點(diǎn)至多含 4個(gè)關(guān)鍵字，除根結(jié)點(diǎn)之外，其他結(jié)點(diǎn)至少含1個(gè)關(guān)鍵字（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 2）解析：19. 設(shè)對(duì)稱(chēng)矩陣A壓縮存儲(chǔ)在一維數(shù)組B中，其中矩陣的第一個(gè)元素aii存儲(chǔ)在B0，元素日52存儲(chǔ)在B11，則矩陣元素日36存儲(chǔ)在B 1中。分?jǐn)?shù)： 2.00 ）填

8、空項(xiàng)1:解析：（正確答案：17）20.設(shè)樹(shù)T的度為4,其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別是 4、2、1和1 ,則T中葉子結(jié)點(diǎn)的個(gè)數(shù)是：1（分?jǐn)?shù)：2.00 ）填空項(xiàng)1:解析：（正確答案：8個(gè)）21. 一個(gè)字符串相等的充要條件是和。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1:解析：（正確答案：兩個(gè)字符串的長(zhǎng)度相等對(duì)應(yīng)位置的字符相等）22.在串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，有一個(gè)串S1="ejidc"，我們假設(shè)存儲(chǔ)時(shí)結(jié)點(diǎn)的大小為1,并設(shè)指針占有4個(gè)字節(jié)，則鏈串的存儲(chǔ)密度為 個(gè)字節(jié)，則此鏈串的存儲(chǔ)密度為，又假設(shè)串S2="abcdefg"在存儲(chǔ)時(shí)我們?cè)O(shè)定結(jié)點(diǎn)的大小為4，指針占有4。（分?jǐn)?shù)

9、：2.00 ）填空項(xiàng)1:解析：（正確答案：20% 50%23.若對(duì)關(guān)鍵字序列（43,02,80,48,26,57,15,73,21,24,66）進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為1。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1:解析：（正確答案：15,02,21,24,26,57,43,66,80,48,73）24.在線性結(jié)構(gòu)中，1決定了它的遍歷路線只有一條。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1:解析：（正確答案：線性結(jié)構(gòu)中后繼的惟一性）三、解答題（總題數(shù)：3,分?jǐn)?shù)：25.00）已知有向圖G的定義如下：G=（V,E）V=a,b,c,d,eE= a,b ， a,c ， b,c ， b,d ， c,d ， e,c

10、 ， e,d ）（1）畫(huà)出G的圖形；（2）寫(xiě)岀G的全部拓?fù)湫蛄?。（分?jǐn)?shù)：10.00）正確答案：（解析：正確答案：(a,b,e,c,da,e,b,c,de,a,b,c,d)解析：25. 畫(huà)出與如圖所示森林對(duì)應(yīng)的二叉樹(shù)正確答案：dI)解析：(分?jǐn)?shù)：5.00)正確答案：(I )解析：(1)畫(huà)岀對(duì)表長(zhǎng)為13的有序順序表進(jìn)行二分查找的判定樹(shù)；已知關(guān)鍵字序列為(12,14,16,21,24,28,35,43,52,67,71,84,99)，寫(xiě)出在該序列中二分查找37時(shí)所需進(jìn)行的比較次數(shù)。(分?jǐn)?shù)：10.00 )正確答案：(3)解析：四、算法閱讀題(總題數(shù)：3,分?jǐn)?shù)：20.00)26. 求下面算法中變量 co

11、unt的值：(假設(shè)n為2的乘冪，并且n > 2)int Timeint ncount=0;x=2;while(x < n/2)x*=2;count+;return(count)(分?jǐn)?shù)：5.00 ) 正確答案：(count=log 2n)解析：假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類(lèi)型定義如下:typedef struct Nodeint id; /* 學(xué)號(hào) */int score; /*成績(jī) */srruct Node*next;LNode,*LinkList;閱讀算法f31，并回答問(wèn)題:(1)設(shè)結(jié)點(diǎn)結(jié)構(gòu)為成績(jī)鏈表A和B如圖所示，畫(huà)岀執(zhí)行算法f31(A,B)后A所指的鏈表

12、;(2)簡(jiǎn)述算法f31的功能void f31(LinkList A,LinkList B) LinkList p,q;p=A> next; q=B> next;while(p&&q)if(p > id<Q > id) p=p> next;else if(p > id >q> id) q=q> next; else if(p > score < 60)if(q > score < 60) p> score=q > score; else p > score=60;p=p>

13、next;q=q> next;(分?jǐn)?shù)：10.00) 正確答案：()解析：正確答案：(對(duì)于表A中成績(jī)低于60的學(xué)生，如果在表B中也有成績(jī)記錄，則將表A中的成績(jī)修改為其在表B中的成績(jī)；但若其在表B中的成績(jī)高于60分，則只改為60分。)解析：27. 簡(jiǎn)述一下算法的功能：status A (1inkedlist L)/L是無(wú)表頭結(jié)點(diǎn)的單鏈表if (L&&L > next)Q=L;L=L> next;P=L;while(P > next)P=P > next;P> next=Q;Q > next=NULL;return ok;)/A(分?jǐn)?shù)：5.0

14、0 )正確答案：(本程序?qū)崿F(xiàn)的功能就是：如果 L的長(zhǎng)度不小于2,則將首元結(jié)點(diǎn)刪去并插入到表尾。)解析：五、算法設(shè)計(jì)題 （ 總題數(shù)： 1，分?jǐn)?shù)： 10.00）28. 假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示有序表，單鏈表的類(lèi)型定義如下： typedef struct nodeDataType data;struct node*nextLinkNode,*LinkList;編寫(xiě)算法，從有序表 A 中刪除所有和有序表 B 中元素相同的結(jié)點(diǎn)（分?jǐn)?shù)： 10.00 ） 正確答案： ( 參考答案一：void f34(LinkList ha,LinkList hb) hb和hb分剮為存放A和B有序鏈表的頭指針LinkList p,q,r;p=ha;q=hb> next;while(p > next&&q)if(p > next > data <q- >data)p=p> next;elseif(p > next > data=q > data)r=p > next;p> next=r > next;free(r); / 從 A 表刪除相同的元素結(jié)點(diǎn)q=q> next;參考答案二：void f34(LinkList ha,LinkList hb) /hb 和hb分別為存放A和B有