南郵通達(dá)數(shù)據(jù)結(jié)構(gòu)B期末試卷及答案

1、 數(shù)據(jù)結(jié)構(gòu)B 期末試卷（A）本試卷共 4 頁； 考試時(shí)間 110 分鐘；裝 訂 線 內(nèi) 不 要 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊 專業(yè) 班級(jí) 學(xué)號(hào) 姓名 一、填空題（20分，共10題）1. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的_結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及在數(shù)據(jù)上執(zhí)行的運(yùn)算。2. 設(shè)順序表長(zhǎng)度為100，若下標(biāo)從0開始計(jì)，則刪除元素a10需要移動(dòng)_個(gè)元素。3. 一棵二叉樹中，若葉結(jié)點(diǎn)的個(gè)數(shù)為2011，則度為2的結(jié)點(diǎn)個(gè)數(shù)為_。4. 有向圖進(jìn)行拓?fù)渑判驎r(shí)，沒有輸出圖中所有頂點(diǎn)，說明圖中存在_。5. 線性表采用二分搜索必須滿足兩個(gè)條件：線性表關(guān)鍵字必須是_；存儲(chǔ)結(jié)構(gòu)必須采用順序存儲(chǔ)結(jié)

2、構(gòu)。6. 二叉搜索樹的_序遍歷序列是一個(gè)按關(guān)鍵字遞增排列的有序序列。7. 設(shè)有一組記錄的關(guān)鍵字為19, 14, 1, 69, 20, 27, 55, 79，散列函數(shù)為h(key) = key%11，散列函數(shù)值為3的有_個(gè)。8. 快速排序算法平均情況下的漸近時(shí)間復(fù)雜度為O(_)。9. 采用二次探查法解決沖突可能產(chǎn)生_聚集。10. 圖常見的兩種存儲(chǔ)結(jié)構(gòu)有鄰接矩陣和_。二、選擇題（20分，共10題）1. 一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。這是算法的_。A. 有窮性B. 正確性C. 確定性D. 可行性2. 在指針p所指示的結(jié)點(diǎn)之后插入新結(jié)點(diǎn)s的操作是_。A. s->link=p;p->li

3、nk=s;B. s->link=p->link;p->link=s;C. s->link=p->link;p=s;D. p->link=s;s->link=p;3. 棧和隊(duì)列的共同點(diǎn)是_。A. 都是先進(jìn)后出B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素D. 沒有共同點(diǎn)4. 后綴表達(dá)式：5 3 2 * 3 + 3 / +的值為_。A. 18B. 7C. 9D. 85. 高度為5的二叉樹至多有_個(gè)結(jié)點(diǎn)。A. 5B. 10C. 31D. 326. 采用對(duì)半查找方法查找長(zhǎng)度為n的線性表時(shí)，時(shí)間復(fù)雜度為_。A. O(n2)B. O(nlog2n)C. O(

4、n)D. O(log2n) 7. n個(gè)頂點(diǎn)的無向圖采用鄰接矩陣表示，則該矩陣的大小是_。A. n B. (n - 1)2 C. n2D. n 1 8. 一個(gè)無向連通圖的生成樹是一個(gè)_連通子圖。A. 極大B. 極小C. 有時(shí)極大D. 有時(shí)候極小9. 下列排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是_。A. 簡(jiǎn)單選擇排序法B. 直接插入排序法C. 快速排序法D. 冒泡排序法10. 散列表的長(zhǎng)度為11，下標(biāo)范圍是0，10，散列函數(shù)為h(key) = key % 11。采用線性探查法解決沖突，依次將關(guān)鍵字7，38，5，16插入空的散列表中。則關(guān)鍵字16在散列表中存放的下標(biāo)是_。A. 5B. 6C

5、. 7D. 8三、簡(jiǎn)答題（30分，共5題）1 有二叉樹如圖1所示，寫出該二叉樹的前序遍歷序列和中序遍歷序列。圖1圖22 寫出圖2所有可能的拓?fù)渑判颉? 設(shè)有向圖的鄰接表表示如圖3所示，請(qǐng)給出每個(gè)頂點(diǎn)的入度。圖34 空二叉搜索樹中依次插入33，44，99，22，11，55，畫出最終所構(gòu)建二叉搜索樹。5 設(shè)W=5, 6, 7, 8, 9，（1）畫出由權(quán)值集合W構(gòu)造的哈夫曼樹。（2）計(jì)算加權(quán)路徑長(zhǎng)度。四、判斷題（10分，共5題）1 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。2 簡(jiǎn)單選擇排序是穩(wěn)定的排序算法。3 散列函數(shù)越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突概率小。4 完全二叉樹一定

6、存在度為1的結(jié)點(diǎn)。5 在一非空二叉樹的中序遍歷中，根結(jié)點(diǎn)的右邊是其右子樹上的所有結(jié)點(diǎn)。五、程序填空題（10分，共1題）1. 以下程序是對(duì)半搜索的迭代實(shí)現(xiàn)，請(qǐng)?zhí)顚懲暾OOL BSearch2(List lst, KeyType k, T *x) int mid, low=(1)_, high = lst.Size1; while ( (2)_)mid=(low+high)/2; if (k<lst.Elementsmid.Key) high = (3) _; else if (4)_) low = mid+1; else *x=lst.Elementsmid; return TRUE;

7、 (5)_ 六、編程題（10分，共1題）1. 用二叉鏈表方式存儲(chǔ)二叉樹。試編寫函數(shù)Count1，求一棵二叉樹的結(jié)點(diǎn)總數(shù)。并編寫Count接口函數(shù)，讓其調(diào)用Count1函數(shù)。typedef int K;typedef struct btnodeK Element;struct btnode* LChild, *RChild;裝 訂 線 內(nèi) 不 要 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊BTNode;typedef struct btreestruct btnode* Root;BTree; 數(shù)據(jù)結(jié)構(gòu)B 期末試卷（A）答案一、 填空題（20分，共10題）1234567

8、8910邏輯892010有向回路有序中2nlog2n二次鄰接表二、選擇題（20分，共10題）12345678910ABCDCDCBAD三、簡(jiǎn)答題（30分，共5題）1前序遍歷序列：BADCE （3分）中序遍歷序列：ABCDE （3分）2每個(gè)1分，全對(duì)再加2分BACDE BACED BCADE BCAED3每個(gè)1分頂點(diǎn)入度03122131425145（4分）WPL = (5+6) * 3 + (7+8+9)*2 = 33 + 48 = 81 （2分） 四、判斷題（10分，每題2分）12345××××五、程序填空題（10分，每空2分）(1) 0(2) low <= high(3) mid1 (4) k>lst.Elementsmid.Key (5) return FALSE;六、編程題（10分，共1題）1int Count(B