杭電數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題(含詳解)

1、一是非題（共 分，每題 分）1. 數(shù)據(jù)結(jié)構(gòu)可用三元式表示（D，S，P）。其中：D是數(shù)據(jù)對象，S是D上的關(guān)系，P是對 D的基本操作集。(f)2 簡單地說,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3 判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表（頭指針為L）中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn) 的條件是：p->next=L。(t)4 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。(f) 5 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。(f)6. 在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是： P->next= S ; S-> next = P->next;。(f)7 對于插入、刪除而言，

2、線性表的鏈?zhǔn)酱鎯?yōu)于順序存儲。(t)8. 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。(f)9. 棧和隊(duì)列是操作上受限制的線性表。(t)10. 隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)11. 隊(duì)列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進(jìn)行。(f)12. 棧和隊(duì)列也是線性表。如果需要，可對它們中的任一元素進(jìn)行操作。(f)13. 棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14. 二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對一般的樹，則無此限制，所 以，二叉樹是樹的 特殊情形。(f)15 二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹。(f) 16 赫夫曼樹中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。

3、(t)17 在二叉樹的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)18 假設(shè)B是一棵樹，B是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B的后序遍歷 。(f)19. 通常，二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。(f)20. 中序線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21 二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22 由樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹。 (t)23 鄰接多重表可以用以表示無向圖，也可用以表示有向圖。(f)24 可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡颉?f)25 有向圖的十字鏈表是將鄰接表和逆鄰接表合二為

4、一的鏈表表示形式。(t)26 關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。(f)27 連通圖G的生成樹是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條邊的子圖。(f)28 一個(gè)無向圖的連通分量是其極大的連通子圖。(t)29 十字鏈表可以表示無向圖，也可用以表示有向圖。(f)30 鄰接表可以表示有向圖，也可以表示無向圖。（ t ）31. 二叉排序樹的平均查找長度為O(log)。(t)32. 二叉排序樹的最大查找長度與（LOG2N）同階。(f)33 選用好的HASH函數(shù)可避免沖突。(f)34 折半查找不適用于有序鏈表的查找。(t)35. 對于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 對于任何待

5、排序序列來說，快速排序均快于冒泡排序。(f)37 在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)38 快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是O（n log n）。(f)39. 字符串是數(shù)據(jù)對象特定的線性表。(t)40. 空串與空格串是相同的。(f)41. 對于一棵m階的B-樹.樹中每個(gè)結(jié)點(diǎn)至多有m 個(gè)關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至 少有m/2個(gè)關(guān)鍵字。(f)42. 當(dāng)二叉排序樹是一棵平衡二叉樹時(shí)，其平均查找長度為O(log2n)。(t)43. 廣義表的表頭和表尾都是廣義表。(f)44 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。1 從邏輯

6、上可以把數(shù)據(jù)結(jié)構(gòu)分成( c )。 A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 順序組織和鏈接組織 C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 基本類型和組合類型2 線性表L在( b )情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。 A. 不需修改L的結(jié)構(gòu) B. 需不斷對L進(jìn)行刪除、插入 C. 需經(jīng)常修改L中結(jié)點(diǎn)值 D. L中含有大量結(jié)點(diǎn)3 帶頭結(jié)點(diǎn)的單鏈表L為空的判斷條件是 b 。 帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判斷條件是 。 A. L=null B. L->next=null C. L->next=L D. L!=null4 若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定 的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其

7、后繼（若存在）結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至 表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。 順序表的存儲結(jié)構(gòu)為：typedef struct ElemType *elem; /數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨 int length; /表長度 SSTable;int search_seq(SSTable ST,KeyType key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key)

8、f ;if( G ) ST.elemiST.elemi+1； e ； return i;A. i>0 B. i>=0 C. i<ST.length D. i<=ST.lengthE. i+ F. i- G. A和C同時(shí)滿足 H. B和D同時(shí)滿足5 若入棧順序?yàn)锳、B、C、D、E，則下列( d )出棧序列是不可能的。 AA、B、C、D、E BB、C、D、A、E CC、D、B、E、A DD、E、C、A、B6 遞歸程序可借助于( c )轉(zhuǎn)化為非遞歸程序。 a.線性表 b.隊(duì)列 c: 棧 d.數(shù)組 7 在下列數(shù)據(jù)結(jié)構(gòu)中( c )具有先進(jìn)先出（FIFO）特性， ( b )具有先進(jìn)

9、后出(FILO）特性。 a線性表 b棧 c隊(duì)列 d廣義表8 若對編號為1，2，3的列車車廂依次通過扳道棧進(jìn)行調(diào)度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,19 在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過程，應(yīng)借助于( b ) 這種數(shù)據(jù)結(jié)構(gòu)。 A. 線性表 B. 棧 C. 隊(duì)列 D. 雙向隊(duì)列10 若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選擇中（ c ）最適用于隊(duì)列。 A）單鏈表 B）雙向鏈表 C循環(huán)單鏈表 D）雙向循環(huán)鏈表11 棧和隊(duì)列的一個(gè)共同點(diǎn)是( c )。 A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入

10、和刪除元素 D. 沒有共同點(diǎn)12 循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，設(shè)頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中 的元素個(gè)數(shù)是( c )。 A. rear-front-1 B. Rear-front+1 C. (rear-front+m)%m D. Rear-front13 如下關(guān)于串的陳述中，正確的是( a, c )。 A. 串是數(shù)據(jù)元素類型特殊的線性表 B. 串中的元素是字母 C. 串中若干個(gè)元素構(gòu)成的子序列稱為子串 D. 空串即為空格串14 對字符串s=data-structure 執(zhí)行操作replace(s,substring(s,6,8),bas) 的結(jié)果是 ( b )

11、。 a: database b: data-base c: bas d: data-basucture 15 設(shè)有二維數(shù)組A 5 x 7 ,每一元素用相鄰的4個(gè)字節(jié)存儲，存儲器按字節(jié)編址. 已知A的起始地址為100。則按行存儲時(shí)，元素A06的第一個(gè)字節(jié)的地址是（d ） 按列存儲時(shí)，元素A06的第一個(gè)字節(jié)的地址是（ a ） a: 220 b: 200 c: 140 d: 12416對廣義表 A=（a,(b)）,(c,(),d）執(zhí)行操作gettail(gethead(gettail(A) 的結(jié)果是：（ b ） 。 a:（） b: （） c: d d: (d)17 假設(shè)用于通訊的電文僅由6個(gè)字符組成

12、，字母在電文中出現(xiàn)的頻率分別為7, 19, 22, 6, 32, 14。 若為這6個(gè)字母設(shè)計(jì)哈夫曼編碼（設(shè)生成新的二叉樹的規(guī)則是按給出的次序從左至 右的結(jié)合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（ g ），頻率 為32的字符編碼是（ c ）。 a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:111118 對二叉排序樹（ c ）可得到有序序列。 a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷19 設(shè)一棵二叉樹BT的存儲結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B

13、 C D E F G H rchild 0 5 4 0 8 7 0 0 其中l(wèi)child，rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。則 該二叉樹的高度為( d )； 第3層有( a )個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)為第1層）。 A2 B. 3 C. 4 D. 520 先序遍歷圖示二叉樹可得到（ a ）的序列。 (A) (B) (C) (H) (D) (G) (E) (F) (I) a)A B H D E F I C G b)H B E D F I A C G c) H E I F D B G C A 21 在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù) （ b ）。 a.不定 b.n+

14、1 c.n d.n-122 若某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)是 ( c )。 A40 B. 55 C. 59 D. 6123 已知某二叉樹的先序遍歷次序?yàn)閍bcdefg中序遍歷次序?yàn)閎adcgfe， 則該二叉樹的后序遍歷次序?yàn)椋?c ）。層次遍歷次序?yàn)椋?a ）。 a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba.24 圖示的三棵二叉樹中( c)為最優(yōu)二叉樹。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 425 已知某二叉樹的后序遍歷和中序遍歷次序分

15、別為DBFGECA和BDACFEG。則其先序遍歷次序?yàn)椋?b ），層次遍歷次序?yàn)椋?a ）。 a: abcdefg b: abdcefg c: abcdfeg d: abcdegf26 已知某樹的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。 若將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序?yàn)椋?d ）。a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba27 設(shè)x和y是二叉樹中的任意兩個(gè)結(jié)點(diǎn)，若在先根序列中x在y之前，而在后根序列中x 在y之后，則x和y的關(guān)系是( c )。 A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的子孫2

16、8 用三叉鏈表作二叉樹的存儲結(jié)構(gòu)，當(dāng)二叉樹中有n個(gè)結(jié)點(diǎn)時(shí)，有( d )個(gè)空指針。 A. n-1 B. n C. n+1 D. n+229 對一棵完全二叉樹進(jìn)行層序編號。則編號為n的結(jié)點(diǎn)若存在右孩子,其位序是( d )。 編號為n的結(jié)點(diǎn)若存在雙親,其位置是( a )。 a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)30 設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3，則與 森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是( d )。 A. m1 B. m1+m2 C. m3 D. m2+m331 下列二叉樹中，( a )可用于實(shí)現(xiàn)符號不等

17、長高效編碼。 a:最優(yōu)二叉樹 b:次優(yōu)查找樹 c:二叉平衡樹 d:二叉排序樹32 鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類似于二叉樹的(a )遍歷。 A. 先根 B. 中根 C. 后根 D. 層次33 設(shè)無向圖G = (V,E)和G= (V,E)，若G是G的生成樹，則下面不正確的說法是( b )。 A. G是G的子圖         B. G是G的連通分量 C. G是G的無環(huán)子圖      D. G是G的極小連通子圖且V= V34 任何一個(gè)連通圖的最小生成樹( b )。 A只有

18、一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 e f e f35 深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（b ），而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（ c ）。A）數(shù)組 B）棧 C）隊(duì)列 D）線性表36 已知某有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。 0 E 2 1 1 D 0 3 4 2 C 43 B 1 2 0 4 A 2 根據(jù)存儲結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)椋?d ）。 廣度優(yōu)先遍歷此序?yàn)椋?c ）。各強(qiáng)連通分量的頂點(diǎn)集為（ h ）。 a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc及ed f: bc及aed g: ab及ced h: ac

19、及bed37 下列查找方法中（ a ）適用于查找單鏈表。 A）順序查找 B）折半查找 C）分塊查找 D）hash查找38 下列算法中（c ）適用于求圖的最小代價(jià)生成樹。（ b ）能對圖作廣度優(yōu)先遍歷。 A）DFS算法 B）BFS算法 C）Prim算法 D）Dijkstra算法39 關(guān)鍵路徑是指在只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)（ c ）的路徑。 a:弧的數(shù)目最多 b:弧的數(shù)目最少 c:權(quán)值之和最大 d:權(quán)值之和最小40 希表的查找效率取決于（ d ）。 a: 哈希函數(shù) b:處理沖突的方法。 c:哈希表的裝填因子。 d:以上都是41 在Hash函數(shù)H(k)=k MOD m中，一般來

20、說，m應(yīng)取( c )。 A. 奇數(shù) B. 偶數(shù) C. 素?cái)?shù) D. 充分大的數(shù)42 在順序表查找中，為避免查找過程中每一步都檢測整個(gè)表是否查找完畢， 可采用 a 方法。 A.設(shè)置監(jiān)視哨 B.鏈表存貯 C.二分查找 D.快速查找43 靜態(tài)查找表和動態(tài)查找表的區(qū)別在于( b )。 A. 前者是順序存儲，而后者是鏈?zhǔn)酱鎯?B. 前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作 C. 前者只能順序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序44 在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查找，找到一個(gè)元素最多要進(jìn)行( b )次元素 比較。 Aëlog2(n)û B.

21、 ëlog2(n)û+1 C. ëlog2(n+1)û D. ëlog2(n+1)û+145 設(shè)輸入序列為20, 45, 30, 89, 70, 38, 62，19依次插入到一棵2-3樹中(初始狀態(tài)為空)， 該B-樹為（ b ）。再刪除38，該B-樹為（ f ）。 （ 30 62 ） （ 45 ） （19，20）（ 38 45 ） （ 70，89 ） （ 30 ） （ 70 ） （19 20） （38 ）（ 62 ） （ 89 ） a: b: （ 45 70 ） （ 45 ） （20） （ 62 ） （ 89 ） （ 20 ） （ 7

22、0 ）（19）（ 30 ） （ 19 ） ( 30,38 ）（ 62 ） （ 89 ） c: d: （ 30 70 ） （ 45 ） （19，20） （ 45 62） （ 89 ） （ 20 ） （ 70 ） （19 ） （30 ）（ 62 ） （ 89 ） e: f:46根據(jù)插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。 圖（ a ）是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。圖（ c ）是最 終變化的結(jié)果。 80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d:47 若有序表中關(guān)鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。對其進(jìn)行 折半查找，則在等概率情況下，查找成功時(shí)的平均查找長度是( c )。查找32時(shí)需進(jìn) 行( c )次比較。A. 1 B. 2 C. 3 D. 4 48 已知哈希表地址空間為A