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