【正文】 BCDEFG，后序序列為 BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為： C A． 3 B． 2 C． 4 D． 5 83． 已知一算術(shù)表達(dá)式的中綴形式為 A＋ B *C– D/E，后綴形式為 ABC *+DE/– ，其前綴形式為 D 。 A ． – A+B*C/DE B ． – A+B*CD/E C –+*ABC/DE D． – +A*BC/DE 84． 已知一個圖，如圖所示，若從頂點(diǎn) a 出 發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 ____D___；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂 點(diǎn)序列為___A___； ① A． a， b， e， c， d， f B． a， c， f， e， b， d C． a， e， b， c， f， d， D． a， e， d， f， c， b ② A． a， b， c， e， d， f B． a， b， c， e， f， d C． a， e， b， c， f， d， D． a， c， f， d， e， b 85． 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的 ___A____。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷 86． 采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的 ___D____。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷 87．具有 n 個結(jié)點(diǎn)的連通圖至少有 A 條邊。 A． n1 B． n C． n(n1)/2 D． 2n 88．廣義表（（ a）， a）的表頭是 C ，表尾是 C 。 ab cdefA． a B （） C （ a） D （（ a）） 89．廣義表（（ a））的表頭是 C ，表尾是 B 。 A． a B （） C （ a） D （（ a）） 90．順序查找法適合于存儲結(jié)構(gòu)為 B 的線性表。 A 散列存儲 B 順序存儲或鏈?zhǔn)酱鎯? C 壓縮存儲 D 索引存儲 91．對線性表進(jìn)行折半查找時，要求線性表必須 B 。 A 以順 序方式存儲 B 以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列 C 以鏈?zhǔn)椒绞酱鎯? D 以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點(diǎn)按關(guān)鍵字有序排列 92．采用折半查找法查找長度為 n 的線性表時，每個元素的平均查找長度為 D 。 A O(n2) B O(nlog2n) C O(n) D O(log2n) 93．有一個有序表為｛ 1， 3， 9， 12， 32， 41， 45， 62， 75， 77， 82， 95， 100｝，當(dāng)折半查找值為 82 的結(jié)點(diǎn)時， C 次比較后查找成功。 A． 11 B 5 C 4 D 8 94．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法 B 。 A 正確 B 錯誤 95．下面關(guān)于 B樹和 B+樹的敘述中，不正確的結(jié)論是 A 。 A B樹和 B+樹都能有效的支持順序查找 B B樹和 B+樹都能有效的支持隨機(jī)查找 C B樹和 B+樹都是平衡的 多叉樹 D B樹和 B+樹都可用于文件索引結(jié)構(gòu) 96．以下說法錯誤的是 B 。 A．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址 B．散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。 C．負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。 D．散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。 97．查找效率最高的二叉排序樹是 C 。 A．所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。 B．所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。 C．平衡二叉樹。 D．沒有左子樹的二叉排序樹。 98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為 C 。 A．希爾排序 B。冒泡排序 C插入排序 D。選擇排序 99．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是 D 。 A．希爾排序 B．冒泡排序 C．直接插入排序 D．直接選擇排序 100．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 D 是一個堆。 A． 94,31,53,23,16,72 B． 94,53,31,72,16,23 C． 16,53,23,94,31,72 D． 16,31,23,94,53,72 101． 堆排序是一種 B 排序。 A．插入 B．選擇 C．交換 D．歸并 102． D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。 A．順序查找 B．折半查找 C．分塊查找 D．插入 103．直接選擇排序 的時間復(fù)雜度為 D 。（ n 為元素個數(shù)） A． O（ n) B． O(log2n) C． O(nlog2n) D． O(n2) 二、填空題。 1．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu) 。 2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為 集合 、 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 4 種。 3．在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 1 個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 1 個后續(xù)結(jié)點(diǎn)。 4．線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。 5．在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 1 個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個 。 6． 數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是 順序 、 鏈?zhǔn)? 、 索引 和 散列 存儲 。 7．衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時間復(fù)雜度 與 空間復(fù)雜度 。 8．評估 一個算法的優(yōu)劣，通常從 時間復(fù)雜度 和 空間復(fù)雜度 兩個方面考察。 9．算法的 5個重要特性是 有窮性 、 確定性 、 可行性 、輸入和輸出。 10．在一個長度為 n 的順序表中刪除第 i 個元素時，需向前移動 ni1 個元素。 11．在單鏈表中，要刪除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)。 12．在雙鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向 前驅(qū) 結(jié)點(diǎn) ，另一個指向 后繼結(jié)點(diǎn) 。 13．在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動 n 個數(shù)據(jù)元素，移動數(shù)據(jù) 元素的個數(shù)與 位置 有關(guān)。 14．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲結(jié)構(gòu)。 15．根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)，將線性鏈表分成 單鏈表 和 雙鏈表 。 16．順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。 17．帶頭結(jié)點(diǎn)的循環(huán)鏈表 L中只有一個元素結(jié)點(diǎn)的條件是 Lnextnext=L 。 18． 棧 是限 定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循 后進(jìn)先出 的原則。 19．空串是 零個字符的串 ，其長度等于 零 ?？瞻状?由一個或多個空格字符組成的串 ，其長度等于 其包含的空格個數(shù) 。 20．組成串的數(shù)據(jù)元素只能是 單個字符 。 21．一個字符串中 任意個連續(xù)字符構(gòu)成的部分 稱為該串的子串。 22．子串 ” str” 在主串 ” datastructure” 中的位置是 5 。 23．二維數(shù)組 M 的每個元素是 6 個字符組成的串，行下標(biāo) i 的范圍從 0 到 8，列下標(biāo) j 的范圍從 1 到 10，則存放 M 至少需要 540 個字節(jié)； M 的第 8 列和第 5 行共占 108個字節(jié)。 24． 稀疏矩陣一般的壓縮存儲方法有兩種，即 三元組表 和 十字鏈表 。 25．廣義表（（ a），（（ b）， c），（（（ d））））的長度是 3 ，深度是 4 。 26．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個數(shù)為 n0，度為 2 的結(jié)點(diǎn)的個數(shù)為 n2，則有 n0＝ n2+1 。 27．在有 n 個結(jié)點(diǎn)的二叉鏈表中，空鏈域的個數(shù)為 __n+1__。 28．一棵有 n 個葉子結(jié)點(diǎn)的哈夫曼樹共有 __2n1_個結(jié)點(diǎn)。 29． 深度為 5 的二叉樹至多有 31 個結(jié)點(diǎn)。 30． 若某二叉樹有 20 個葉子結(jié)點(diǎn)，有 30 個結(jié)點(diǎn)僅有一個孩子，則該二叉樹的總結(jié)點(diǎn)個數(shù)為 69 。 31．某二叉樹的前序遍歷序列是 abdgcefh，中序序列是 dgbaechf，其后序序列為 gdbehfca 。 32．線索二叉樹的左線索指向其 遍歷序列中的前驅(qū) ，右線索指向其 遍歷序列中的后繼 。 33．在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù) n無關(guān)的查找方法是 散列查找法 。 34．在分塊索引查找方法中，首先查找 索引表 ，然后查找相應(yīng)的 塊表 。 35．一個無序序列 可以通過構(gòu)造一棵 二叉排序 樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。 36． 具有 10個頂點(diǎn)的無向圖，邊的總數(shù)最多為 __45__。 37． 已知圖 G 的鄰接表如圖所示，其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點(diǎn) v1出發(fā)的廣度優(yōu)先搜索序列為 _v1v2v5v4v3v6__。 v1v2v3v4∧v5v6∧v3v2v6∧v4v5∧v5v6v3∧v4∧ 38． 索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址 。 39． Prim 算法生成一個最小生成樹每一步選擇都要滿足 邊的總數(shù)不超過 n1 ， 當(dāng)前選擇的邊的權(quán)值是候選邊中最小的 ， 選中的邊加入樹中不產(chǎn)生回路 三項原則。 40． 在一棵 m 階 B樹中，除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)最多有 m 棵 子樹，最少有 m/2 棵子樹。 三、判斷題。 1．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點(diǎn)的值如何。（√） 2． 抽象數(shù)據(jù)類型（ ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個 ADT的邏輯特性，不必考慮如何在計算機(jī)中實(shí)現(xiàn)。 (√ ) 3．抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。（√ ） 4．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩＃? ） 5．線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。（ ） 6．對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（ ） 7．順序存儲方式只能用于存儲線性結(jié)構(gòu)。（ ） 8．集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（ ） 9．線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（ ） 10．線性表就是順序存儲的表。（ ） 11．取線性表的第 i 個元素的時間同 i的大小有關(guān)。（ ） 12．循環(huán)鏈表不是線性表。（ ） 13．鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時，在鏈表中比在順序表中效率高。（ √ ） 14．雙向 鏈表可隨機(jī)訪問任一結(jié)點(diǎn)。（ ） 15． 在單鏈表中 ， 給定任一結(jié)點(diǎn)的地址 p， 則可用下述語句將新結(jié)點(diǎn) s 插入結(jié)點(diǎn) p的后面 ： pnext = s。 snext = pnext。 ( ) 16．隊列是一種插入