數(shù)據(jù)結(jié)構(gòu)c語言版期末題庫-資料下載頁

　　

【正文】 字有序排列C 以鏈?zhǔn)椒绞酱鎯?D 以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(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é)點時， C 次比較后查找成功。A． 11 B 5 C 4 D 894．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法 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é)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C．負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D．散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97．查找效率最高的二叉排序樹是 C 。A．所有結(jié)點的左子樹都為空的二叉排序樹。B．所有結(jié)點的右子樹都為空的二叉排序樹。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,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．直接選擇排序的時間復(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é)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有 1 個后續(xù)結(jié)點。4．線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。5．在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以 任意多個 。6．?dāng)?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é)點，必須找到該結(jié)點的 前驅(qū) 結(jié)點。12．在雙鏈表中，每個結(jié)點有兩個指針域，一個指向 前驅(qū) 結(jié)點，另一個指向 后繼結(jié)點 。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é)點包含的指針個數(shù)，將線性鏈表分成 單鏈表 和 雙鏈表 。16．順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。17．帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是 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é)點的個數(shù)為n0，度為2 的結(jié)點的個數(shù)為n2，則有n0＝ n2+1 。27．在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為__n+1__。28．一棵有n個葉子結(jié)點的哈夫曼樹共有__2n1_個結(jié)點。29．深度為5的二叉樹至多有 31 個結(jié)點。30．若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為 69 。31．某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為 gdbehfca 。32．線索二叉樹的左線索指向其 遍歷序列中的前驅(qū) ，右線索指向其遍歷序列中的后繼 。33．在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找法 。34．在分塊索引查找方法中，首先查找 索引表 ，然后查找相應(yīng)的 塊表 。35．一個無序序列可以通過構(gòu)造一棵 二叉排序 樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。36．具有10個頂點的無向圖，邊的總數(shù)最多為__45__。37．已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6__。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é)點外，每個結(jié)點最多有 m 棵子樹，最少有 m/2 棵子樹。三、判斷題。1．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（√）2．抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實現(xiàn)。(√ )3．抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實現(xiàn)無關(guān)。（√ ）4．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。? ）5．線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點和結(jié)點內(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é)點。（ ）15．在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點s插入結(jié)點p的后面 ：pnext = s。 snext = pnext。 ( )16．隊列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ ）17. 串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。（ ）18．長度為1的串等價于一個字符型常量。( )19．空串和空白串是相同的。（）20．?dāng)?shù)組元素的下標(biāo)值越大，存取時間越長。( )21．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。(√ )22．一個廣義表的表頭總是一個廣義表。（ ）23．一個廣義表的表尾總是一個廣義表。（ √ ）24．廣義表((( a ), b), c ) 的表頭是(( a ), b)，表尾是( c )。（ √ ）25．二叉樹的后序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的后面。（ √ ）26．度為2的有序樹是二叉樹。（ ）27．二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（ √ ）28．用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。（）29．若已知一棵二叉樹的前序遍歷序列和后序遍歷序列，則可以恢復(fù)該二叉樹。（ ）30．在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。( )31．強(qiáng)連通圖的各頂點間均可達(dá)。（ √ ）32．對于任意一個圖，從它的某個結(jié)點進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（ ）33．在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序為穩(wěn)定排序。(√ )34．在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。(√ )35．拓?fù)渑判蚴前碅OE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進(jìn)行排序。( )36．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（ ）37．對線性表進(jìn)行折半查找時，要求線性表必須以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點按關(guān)鍵字有序排列。（ ）38．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址。（√ ）39．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。（ ）40．具有n個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。（ √）