數(shù)據(jù)結(jié)構(gòu)與算法模擬卷2

1、、寫出以下各詞語的對應(yīng)中文 binary queue LIFO tree subtree edge 二、選擇題 1. 下列兩個圖各表現(xiàn)一批數(shù)據(jù)的結(jié)構(gòu)，其中 A. 左邊表現(xiàn)的是邏輯結(jié)構(gòu)，右邊表現(xiàn)的是物理結(jié)構(gòu) B. 右邊表現(xiàn)的是邏輯結(jié)構(gòu)，左邊表現(xiàn)的是物理結(jié)構(gòu) C. 兩者表現(xiàn)的都是邏輯結(jié)構(gòu) A B C A 2. 用一維數(shù)組存放線性表，這個線性表的存儲結(jié)構(gòu) A. 一定是順序結(jié)構(gòu) B. 一定是鏈?zhǔn)浇Y(jié)構(gòu) C. 可以是順序結(jié)構(gòu)，也可以是鏈?zhǔn)浇Y(jié)構(gòu) D. 既不是順序結(jié)構(gòu)，也不是鏈?zhǔn)浇Y(jié)構(gòu) 3. 關(guān)于算法的正確性，教材上說“在任何條件下，算法只有惟一的一條執(zhí)行路徑，即對于 相同的輸入只能得出相同的輸出”，你認為對此

2、的正確理解應(yīng)當(dāng)是 A. 包含條件判斷分支的算法不是正確性的算法 B. 對各種輸入數(shù)據(jù)，算法的執(zhí)行路徑都是一樣的 C. 對不同的輸入數(shù)據(jù)，算法的執(zhí)行路徑可能不同，但對同一個輸入數(shù)據(jù)，算法執(zhí)行的路徑 是惟一的 D. 對不同的輸入數(shù)據(jù)，算法的執(zhí)行路徑可能不同；對同一個輸入數(shù)據(jù)，算法執(zhí)行的路徑雖 然可以不同，但輸出是惟一的 4. 算法的正確性是針對 而言的，否則，算法正確與否的衡量準(zhǔn)則不存在 A. 所使用的程序設(shè)計語言 B. 特定閱讀對象 C. 所要解決的問題的需求 D. 所使用的數(shù)據(jù)結(jié)構(gòu) 5. 一個棧的入棧序列是 A,B,C,D,E則棧的可能的輸出序列是 A. E B A D C B. A E D

3、C B C. B A E C D D. D C E B A 6. 按照定義，具有3個結(jié)點的二叉樹有 種 A. 3 B. 4 C. 5 D. 6 *”表示空位，該數(shù)組中下 7. 假定用一維數(shù)組順序存放下圖的二叉樹，并且用特殊符號 標(biāo)為3和9的元素的值分別是 A. D 和J B. C和I C. C 和G D. D 和* 8. q_prior=p_prior; p-prior- n ext=q; q_n ext=p; p-prior=q; q所指的結(jié)點之前 q所指的結(jié)點之后 p所指的結(jié)點之前 p所指的結(jié)點之后 上面的操作序列完成的工作是 A. 把p所指的結(jié)點插入雙向鏈表中 B. 把p所指的結(jié)點插入雙

4、向鏈表中 C. 把q所指的結(jié)點插入雙向鏈表中 D. 把q所指的結(jié)點插入雙向鏈表中 9. 遞歸函數(shù)運行時使用的重要數(shù)據(jù)結(jié)構(gòu)是 A. 棧 B. 隊列 C. 二叉樹 D. 有向圖 10. 以下關(guān)于串的說法中， 是正確的 A. ABCD 與abed 相等 B. ABCD的長度是6 C. 空串也是空格串 D. ABCD 是ABCD 的子串 11.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍 A. 1/2 B. 1 C. 2 D. 4 12.關(guān)于AOE網(wǎng)，以下說法中錯誤的是 A. 從開始點到完成點，長度最大的路徑叫關(guān)鍵路徑 B. 找到關(guān)鍵路徑后，只要把這條路徑上的某個活動所需時間縮短d,整個工程的完成

5、時間 就提前d C. 關(guān)鍵路徑一定存在，但不一定惟一 D. AOE網(wǎng)中一定沒有定點數(shù)超過 1的強連通分量 13. int Search_Seq(SSTable ST, KeyType key) ST.elemO.key=key; For(i=ST.Ie ngth;!EQ(ST.elemi.key, key); -i); Retur n i; 在上面的順序查找算法中，使用語句ST.elem0.key=key的目的是 A. 減少查找失敗的可能 B. 配合其他措施提高查找速度 C. 補充表中缺少的兀素 D. 把參數(shù)復(fù)制下來，以便與表中的其他兀素比較 14. 哈希函數(shù)是 A. 計算平均查找長度的函數(shù)

6、B. 計算最大查找次數(shù)的函數(shù) C. 從關(guān)鍵字計算記錄位置的函數(shù) D. 從記錄位置計算關(guān)鍵字的函數(shù) 15. 關(guān)于排序算法性能的以下說法中，是錯誤的 A. 算法的時間復(fù)雜度是根據(jù)關(guān)鍵字間的比較次數(shù)和記錄的移動次數(shù)求得的 B. 沒有哪一種算法是絕對最優(yōu)的 C. 快速排序算法與堆排序算法的平均時間復(fù)雜度相同 D. 快速排序算法是所有排序中最優(yōu)的 KEFJIHGDCAB中序序列為 JFHIGEDKABC請畫出這棵二 三. 已知一顆二叉樹的先序序列為 叉樹，寫出它的后序序列 四. 假設(shè)用于通信的電文由字符集A, B, C, D, E, F中的字母構(gòu)成，這些字母在電文中出現(xiàn)的 概率分另為0.10, 0.19

7、, 0.20, 0.35, 0.12, 0.04，要求： 1構(gòu)造一顆Hufman樹，填寫下表，要求左結(jié)點的權(quán)不大于右結(jié)點的權(quán) weight pare nt Ichild rchile 1 2 3 4 5 6 7 8 9 10 11 2在下表中填入各字符的 Huffman編碼（左分支為“ 0”，右分支為“ 1 ”） 字符 A B C D E F Huffman 編碼 3.求帶權(quán)路徑長度 五根據(jù)左下圖給出的帶權(quán)有向圖，要求: 1 在圖的右邊填寫改圖的帶權(quán)鄰接矩陣 2使用迪杰斯特拉算法，求出從源點1到其余各頂點的最短路徑，在下面的表中填寫反映算 法執(zhí)行過程和最終結(jié)果的數(shù)據(jù) 第1步 第2步 第3步 第

8、4步 第5步 v2 v3 v4 v5 v6 vj S 六. 散列表表長為13,散列函數(shù)好h (x) =x% 13,把10個關(guān)鍵字25, 17, 6, 36, 33, 76, 43, 41, 31, 38依次存入散列表，用線性探查法解決沖突。要求： 1填寫對應(yīng)的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 2求出平均查找長度 七. 已知一組關(guān)鍵字為 27, 8, 32, 40, 34, 22, 25, 33, 7, 13,要求: 1建立一顆二叉樹排序樹 2畫出插入結(jié)點10后的二叉排序樹 3畫出再刪除結(jié)點8后的二叉排序樹 八. 已知序列24, 8, 30, 50, 42, 19

9、, 21, 40, 11 , 15，要求: 1用希爾排序法排序，增量序列為：5、3、1,寫出每趟的結(jié)果 2用快速排序法排序，寫出每趟結(jié)果 3用冒泡法排序，寫出每趟結(jié)果 4用堆排序法排序，畫出初始堆(大頂堆) 九下面函數(shù)的功能是從二叉樹BT中查找值為x的結(jié)點，若查找成功則返回結(jié)點地址，否 則返回空。請在劃有橫線的地方填寫合適內(nèi)容 Bi nTreeNode *BTF(Bi nTreeNode *BT, ElemType x) if(BT=NULL) ; else Bi nTreeNode *t; t=BTF(BT-left, x); if(t); If Else return NULL; 十寫一算

10、法，在帶頭結(jié)點的單鏈表中查找數(shù)據(jù)值為x的結(jié)點，如果找到，返回這個結(jié)點的 地址，否則在表尾插入一個數(shù)據(jù)值為x的新結(jié)點，然后返回新結(jié)點的地址 難得的是有份清閑時光, 難得的是有種知途迷返， 知之為知之，不知 為不知，知你冷暖，懂你悲歡，把你放在了心頭上的人。難得的是面對片 深山廣林、教你為人，怎樣處事，面對人生 ；淡泊世事，踐行伯樂，明鏡心 扉。 心似無物化有物，道似無情渡有情，佛似無邊勝有邊，儒似學(xué)而不 思厭也，山高不止于流水，流水不止于小橋，除非去哪里在看看，除非 去哪里在歷歷，除非去哪里在觀光 ！ 一路走馬觀花，沐浴星星的樂園，想 哪，念那。 白若溪在月牙泉唱著： 每當(dāng)太陽落下西邊的陽，也有美麗的月牙泉， 它是天的鏡子，也是沙漠的眼。就在那片天的很遠很遠，從那年我月牙 泉邊走過，從此以后魂牽夢