數(shù)據(jù)結(jié)構(gòu)試題(含答案)

1、數(shù)據(jù)結(jié)構(gòu)試題（含答案）1 數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)2 數(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)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(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)沒6 數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序、鏈?zhǔn)?、索引和散列存?chǔ)。有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)

2、可以任意多個(gè)。7 衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度。8 評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9 算法的 5 個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。10 在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。11 在單鏈表中，要?jiǎng)h除某一指定的結(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ù)元素，需要平均移動(dòng) n 個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置有關(guān)14 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最

3、快的速度存取線性表的元素是，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)15 根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈 表分成單鏈表和雙鏈表。16 順序存儲(chǔ)結(jié)構(gòu)是通過下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針表示元素之間的關(guān)系的17 帶頭結(jié)點(diǎn)的循環(huán)鏈表L 中只有一個(gè)元素結(jié)點(diǎn)的條件是L-next-next=L18 棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先 出的原則。19 空串是零個(gè)字符的串，其長度等于零?？瞻状怯梢粋€(gè)或多個(gè)空格字 符組成的串，其長度等于其包含的空格個(gè)數(shù)。20組成串的數(shù)據(jù)元素只能是單個(gè)字符。21 . 一個(gè)子串 st在主串 datastructure中的位置是5

4、。22字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱為該串的子串。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稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25 廣義表（a），（b），c），（d ）的長度是3，深度是4。26 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0 ，度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為n2,貝U有 n0= n2+1。27在有n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_n+1_。28. 一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有_2n-1_個(gè)結(jié)

5、點(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) 造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。36具有10個(gè)頂點(diǎn)的無

6、向圖，邊的總數(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)鍵字對(duì)應(yīng)記錄的地址39 Prim 算法生成一個(gè)最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1，當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項(xiàng) 原則。40 在一棵m 階 B 樹中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m 棵子樹，最少有 m/2 棵子樹。簡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。答：順序表的優(yōu)點(diǎn)是可以隨機(jī)訪問數(shù)據(jù)元素，缺點(diǎn)是大小固定，不利于增減結(jié)點(diǎn)（增減結(jié)點(diǎn)操作需要移動(dòng)元素）。鏈表的優(yōu)點(diǎn)是采用指針方式增減結(jié)點(diǎn)，非 常方便（只需改變指針指向，不移動(dòng)結(jié)點(diǎn)）。其缺點(diǎn)是不能進(jìn)行隨機(jī)訪問，只能順序訪問。另外，每個(gè)結(jié)點(diǎn)上增加指針域，造出額外存儲(chǔ)空間增大。對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？（至少說出兩條好處）答：其好處有：（ 1）對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都是修改前一個(gè)結(jié)點(diǎn)的指針域，因?yàn)槿?/p>