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