數(shù)據(jù)結構試題(含答案)

1、數(shù)據(jù)結構試題（含答案）1 數(shù)據(jù)邏輯結構包括線性結構、樹形結構和圖狀結構三種類型，樹形結構和圖狀結構合稱非線性結構2 數(shù)據(jù)的邏輯結構分為集合、線性結構、樹形結構和圖狀結構 4 種。3 在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1 個前驅結點；最后一個結點沒有后續(xù)結點，其余每個結點有且只有1 個后續(xù)結點。4 線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。5 在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有1 個前驅結點；葉子結點沒6 數(shù)據(jù)結構的基本存儲方法是順序、鏈式、索引和散列存儲。有后續(xù)結點，其余每個結點的后續(xù)結點

2、可以任意多個。7 衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復雜度與空間復雜度。8 評估一個算法的優(yōu)劣，通常從時間復雜度和空間復雜度兩個方面考察。9 算法的 5 個重要特性是有窮性、確定性、可行性、輸入和輸出。10 在單鏈表中，要刪除某一指定的結點，必須找到該結點的前驅結點。11 在單鏈表中，要刪除某一指定的結點，必須找到該結點的前驅結點。12 在雙鏈表中，每個結點有兩個指針域，一個指向前驅結點，另一個指向后繼結點。13 在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動 n 個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置有關14 當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最

3、快的速度存取線性表的元素是，應采用順序存儲結構15 根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈 表分成單鏈表和雙鏈表。16 順序存儲結構是通過下標表示元素之間的關系的；鏈式存儲結構是通過指針表示元素之間的關系的17 帶頭結點的循環(huán)鏈表L 中只有一個元素結點的條件是L-next-next=L18 棧是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先 出的原則。19 空串是零個字符的串，其長度等于零。空白串是由一個或多個空格字 符組成的串，其長度等于其包含的空格個數(shù)。20組成串的數(shù)據(jù)元素只能是單個字符。21 . 一個子串 st在主串 datastructure中的位置是5

4、。22字符串中任意個連續(xù)字符構成的部分稱為該串的子串。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,貝U有 n0= n2+1。27在有n 個結點的二叉鏈表中，空鏈域的個數(shù)為_n+1_。28. 一棵有n個葉子結點的哈夫曼樹共有_2n-1_個結

5、點29 深度為5 的二叉樹至多有31 個結點。30 若某二叉樹有20 個葉子結點，有30 個結點僅有一個孩子，則該二叉樹的總結點個數(shù)為 69。31 .某二叉樹的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為 gdbehfca 。32線索二叉樹的左線索指向其遍歷序列中的前驅，右線索指向其遍歷序 列中的后繼。33 在各種查找方法中，平均查找長度與結點個數(shù)n 無關的查找方法是散列查找法。34在分塊索引查找方法中，首先查找索引表，然后查找相應的塊表。35一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列，構 造樹的過程即為對無序序列進行排序的過程。36具有10個頂點的無

6、向圖，邊的總數(shù)最多為_45_。37 已知圖G 的鄰接表如圖所示，其從頂點 v1 出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6一38索引是為了加快檢索速度而引進的一種數(shù)據(jù)結構。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結構為關鍵字和關鍵字對應記錄的地址39 Prim 算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1，當前選擇的邊的權值是候選邊中最小的，選中的邊加入樹中不產生回路三項 原則。40 在一棵m 階 B 樹中，除根結點外，每個結點最多有m 棵子樹，最少有 m/2 棵子樹。簡述順序表和鏈表存儲方式的特點。答：順序表的優(yōu)點是可以隨機訪問數(shù)據(jù)元素，缺點是大小固定，不利于增減結點（增減結點操作需要移動元素）。鏈表的優(yōu)點是采用指針方式增減結點，非 常方便（只需改變指針指向，不移動結點）。其缺點是不能進行隨機訪問，只能順序訪問。另外，每個結點上增加指針域，造出額外存儲空間增大。對鏈表設置頭結點的作用是什么？（至少說出兩條好處）答：其好處有：（ 1）對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除表中任何結點，所要做的都是修改前一個結點的指針域，因為任