數(shù)據(jù)結(jié)構(gòu)試卷(八)及答案

1、數(shù)據(jù)結(jié)構(gòu)試卷（八）數(shù)據(jù)結(jié)構(gòu)試卷（八）一、選擇題一、選擇題(30(30分)1.字符串的長(zhǎng)度是指（）。(A)串中不同字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù)2.建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（）(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.兩個(gè)字符串相等的充要條件是（）。(A)兩個(gè)字符串的長(zhǎng)度相等(B)兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等(C)同時(shí)具備(A)和(B)兩

2、個(gè)條件(D)以上答案都不對(duì)4.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。(A)99(B)97(C)91(D)935.在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)6.設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?)。(A)A[1]，A[2]，A[3]，A[4](B

3、)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4]7.設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（）。(A)8(B)7(C)6(D)58.設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。(A)5(B)6(C)7(D)89.設(shè)無向圖G中的邊的集合E=(a，b)，(a，e)，(a，c)

4、，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc10.隊(duì)列是一種（）的線性表。(A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除二、判斷題二、判斷題(20(20分)1.如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（）2.設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(

5、nlog2n)。（）3.分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（）4.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（）5.向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（）6.如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（）7.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）8.不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪

6、除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（）9.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。（）數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案一、選擇題一、選擇題1C2C3C4B5B6C7B8C9A10A二、判斷題二、判斷題1對(duì)2錯(cuò)3對(duì)4錯(cuò)5錯(cuò)6對(duì)7對(duì)8對(duì)9對(duì)10對(duì)三、填空題三、填空題1.(49，13，27，50，76，38，65，97)2.t=(bitree)malloc(sizeof(bit

7、ree))，bst(trchildk)3.pnext=s4.headrlink，pllink5.CABD6.1，167.08.(13，27，38，50，76，49，65，97)9.n110.50四、算法設(shè)計(jì)題四、算法設(shè)計(jì)題1.設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitreebtintcountnode(btlchildcount)countnode(btrchildcount)2.設(shè)計(jì)一個(gè)算法

8、將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedefstructintvertex[m]intedge[m][m]gadjmatrixtypedefstructnode1intinfointadjvertexstructnode1nextarcglinklistnodetypedefstructnode2intvertexinfoglinklistnodefirstarcglinkheadnodevoidadjmatrixtoadjl