數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題-資料下載頁
2025-04-17 01:46本頁面
【正文】 表 。 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．隊列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ ） 17. 串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。（ ） 18．長度為 1 的串等價于一個字符型常量。( ) 19．空串和空白串是相同的。（） 20．?dāng)?shù)組元素的下標(biāo)值越大，存取時間越長。( ) 21．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。(√ ) 22．一個廣義表的表頭總是一個廣義表。（ ） 23．一個廣義表的表尾總是一個廣義表。（ √ ） 24．廣義表((( a ), b), c ) 的表頭是(( a ), b)，表尾是( c )。（ √ ） 25．二叉樹的后序遍歷序列中，任意一個結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的后面。（ √ ） 26．度為 2 的有序樹是二叉樹。（ ） 27．二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。（ √ ） 28．用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。（） 29．若已知一棵二叉樹的前序遍歷序列和后序遍歷序列，則可以恢復(fù)該二叉樹。（ ） 30．在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。( ) 31．強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（ √ ） 32．對于任意一個圖，從它的某個結(jié)點(diǎn)進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點(diǎn)。（ ） 33．在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序?yàn)榉€(wěn)定排序。(√ ) 34．在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差（絕對值）不超過 1。(√ ) 35．拓?fù)渑判蚴前?AOE 網(wǎng)中每個結(jié)點(diǎn)事件的最早發(fā)生時間對結(jié)點(diǎn)進(jìn)行排序。( ) 36．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（ ） 37．對線性表進(jìn)行折半查找時，要求線性表必須以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點(diǎn)按關(guān)鍵字有序排列。（ ） 38．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址。（√ ） 39．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（ ） 40．具有 n 個結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。（ √） 41．直接選擇排序算法在最好情況下的時間復(fù)雜度為 O(n)。（ ） 18
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1