數(shù)據(jù)結(jié)構(gòu)習(xí)題集(答案)

1、緒論22n) _一個(gè)后緒論22n) _一個(gè)后第一章1.1 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 _ 以及它們之間的 _ 和運(yùn)算等的學(xué)科。A.數(shù)據(jù)元素 B. 計(jì)算方法 C. 邏輯存儲(chǔ) D. 數(shù)據(jù)映像A.結(jié)構(gòu) B.關(guān)系 C. 運(yùn)算 D. 算法1.2 算法分析的目的是 _ ，算法分析的兩個(gè)主要方面是 _ 。 A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系C.分析算法的效率 以求該進(jìn) D. 分析算法的易懂性和文檔性 A. 空間復(fù)雜度和時(shí)間復(fù)雜度 B. 正確性和簡(jiǎn)明性C.可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性1.3 計(jì)算機(jī)算法指的是 _ ，它必須具備輸入、輸出和 _

2、 等 5個(gè)重要特性。 A. 計(jì)算方法 B. 排序方法C.解決問題的有限運(yùn)算序列 D. 調(diào)度方法 A. 可讀性、可移植性和可擴(kuò)展性 B. 可讀性、可移植性和有窮性C.確定性、有窮性和可行性 D. 易讀性、穩(wěn)定性 和安全性1.4 數(shù)據(jù)元素是數(shù)據(jù)處理的 基本單位 ；數(shù)據(jù)項(xiàng)是數(shù)據(jù)處理的 _最小單位 。1.5 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 邏輯結(jié)構(gòu) _和_物理結(jié)構(gòu) _，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，分析算法的效率。算法的效率包括時(shí)間和空間兩個(gè)方面，分別稱為 _空間復(fù)雜度 和時(shí)間復(fù)雜度 。數(shù)據(jù)的邏輯結(jié)構(gòu)是指 _數(shù)據(jù)元素之間的關(guān)系 _；包括 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖形結(jié)構(gòu) 三種類型 ,其中樹

3、形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱為 _非線性結(jié)構(gòu) _。1.6 線性結(jié)構(gòu)中元素之間存在 _一對(duì)一 _ 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 _一對(duì)多 _ 關(guān)系，圖狀結(jié)構(gòu)中元素之間存在 _多對(duì)多_ 關(guān)系。1.7 數(shù)據(jù)結(jié)構(gòu) 在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理（或存儲(chǔ)）結(jié)構(gòu)，數(shù)據(jù)的物理結(jié)構(gòu)可以采用 _順序存儲(chǔ)和_鏈?zhǔn)酱鎯?chǔ) _兩種存儲(chǔ)方法。1.8 順序存儲(chǔ)方法是把邏輯上 相鄰的元素 存儲(chǔ)在物理位置 相鄰的存單元中 ；鏈?zhǔn)酱鎯?chǔ)方法中元素間的關(guān)系是由 _指針來表示 _的。第二章 線性表2.1 鏈表不具備的特點(diǎn)是 _ 。A.可隨機(jī)訪問任一結(jié)點(diǎn) B. 插入刪除不需移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間 D. 所需空間與其長(zhǎng)度成正比2.2 不

4、帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 _。A. head=null B. head-next=null C. head-next=head D. head !=null 2.3 帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 _。A. head=null B. head-next=null C. head-next=head D. head!=null 2.4 非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p所指向）滿足 _。A. p-next=null B. p=null C. p-next=head D. p=head 2.5 在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持

5、有序的時(shí)間復(fù)雜度是 _。A. O(1) B. O(n) C. O(n ) D. O(nlog2.6 線性鏈表中各個(gè)結(jié)點(diǎn)之間的地址 不一定 連續(xù)。2.7 線性表中數(shù)據(jù)元素之間具有 _一對(duì)一_，除第一個(gè)和最后一個(gè)元素外， 其他數(shù)據(jù)元素有且只有存儲(chǔ)結(jié)構(gòu)比較合適。s-next=_ p-next _和 p-next= _s_k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為每個(gè)數(shù)據(jù)元素占用100 。存儲(chǔ)結(jié)構(gòu)比較合適。s-next=_ p-next _和 p-next= _s_k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為每個(gè)數(shù)據(jù)元素占用100 。1000，每個(gè)數(shù)據(jù)元素占 3個(gè)存儲(chǔ)單元，則要分配2000，則第 11個(gè)元素的存儲(chǔ)地址是he

6、ad-llink= 。q和p指的結(jié)點(diǎn)之間插入一個(gè)由 B. q-next=s;s-next=p 2n）3個(gè)存儲(chǔ)單元，第 11個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為heads指的130，head-rlink= head 。2.8 若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用 鏈?zhǔn)?.9 在一個(gè)單鏈表中 p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行的操作。2.10 已知具有 n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占LOC(a1)，那么， LOC(ai)=_ LOC(a1)+（i-1 ）*k_。2.12 若線性表采用順序存儲(chǔ)結(jié)構(gòu)，則第 1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是2.12 若線性表采用順序存儲(chǔ)結(jié)構(gòu)，線性表的

7、最大長(zhǎng)度為給該線性表 _3000_存儲(chǔ)單元，若第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是_2030_。2.13 以head為頭結(jié)點(diǎn)循環(huán)雙鏈表為空時(shí)，應(yīng)滿足2.14 在單鏈表中，指針 p指向元素為 x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除 x的后繼”的語句是A.p=p-next; B.p-next=p-next-next; C.p-next=p; D.p=p-next-next; 2.15 在單鏈表中，已知 q指的結(jié)點(diǎn)是 p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在結(jié)點(diǎn)，則需執(zhí)行 _。A. s-next=p-next;p-next=s C. p-next=s-next;s-next=p D.p-next=s;s-next=q 2.16 用鏈表表

8、示線性表的優(yōu)點(diǎn)是（）A便于隨機(jī)存儲(chǔ) B.便于進(jìn)行插入和刪除操作C. 占用的存儲(chǔ)空間較順序表少 D. 元素的物理順序與邏輯順序相同2.17 下面關(guān)于線性表的敘述中，錯(cuò)誤的是（）A. 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)單元B. 線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)單元D. 線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行插入和刪除操作2.18 線性表是具有 n個(gè)（）的有限序列A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)元素 C. 表元素 D. 字符2.19 長(zhǎng)度為 n的線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，訪問其第 i 個(gè)元素的算法時(shí)間復(fù)雜度為（） A. O （1） B.O（n） C. O （n2

9、） D.O （log2.20 在長(zhǎng)度為 n的順序表刪除第 i（1i n）個(gè)元素，則需要向前移動(dòng)元素的次數(shù)為（） A. i B. n-i C. n-i+1 D.n-i-1 2.21 在長(zhǎng)度為 n的順序表中第 i（1i n）個(gè)位置上插入一個(gè)元素時(shí)，為留出插入位置所需要移動(dòng)元素的次數(shù)為（） A. n-i B. i C. n-i-1 D. n-i+12.22 以下對(duì)單鏈表的敘述錯(cuò)誤的是（）A. 單鏈表中的每一個(gè)結(jié)點(diǎn)都由存放結(jié)點(diǎn)值的數(shù)據(jù)域和存放直接后繼結(jié)點(diǎn)地址信息的指針域兩部分組成B.從單鏈表的第 i 個(gè)結(jié)點(diǎn)出發(fā)，可以訪問到鏈表中的任何一個(gè)結(jié)點(diǎn)C.在單鏈表結(jié)構(gòu)中加入頭結(jié)點(diǎn)可以簡(jiǎn)化結(jié)點(diǎn)的插入和刪除操作D.

10、單鏈表尾結(jié)點(diǎn)的指針域應(yīng)置為空指針2.23 以下記敘中正確的是 （）A. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)先于順序存儲(chǔ)結(jié)構(gòu)B. 線性表的存儲(chǔ)結(jié)構(gòu)不影響其各種運(yùn)算的實(shí)現(xiàn)C. 選擇線性表的存儲(chǔ)結(jié)構(gòu)就是要保證存儲(chǔ)其各個(gè)元素的值D.順序存儲(chǔ)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)屬于動(dòng)態(tài)結(jié)構(gòu)第三章 棧與隊(duì)列一、選擇題3.1 棧的特點(diǎn)是 _B_ ，隊(duì)列的特點(diǎn)是 _A_ 。A.先進(jìn)先出 B. 先進(jìn)后出3.2 棧和隊(duì)列的共同點(diǎn)時(shí) _。A.都是先進(jìn)后出 B. 都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)3.3 一個(gè)棧的進(jìn)棧序列是 a,b,c,d,e, 則棧的不可能的輸出序列是 _ 。A. edcba B. decba C.

11、 dceab D. abcde 3.4 判定一個(gè)棧 ST（最多元素 MaxSize）為空的條件是 _ 。A.ST-top!=-1 B. ST-top=-1C.ST-top!= MaxSize D. ST-top=MaxSize-1 3.5 判定一個(gè)棧 ST（最多元素 MaxSize）為棧滿的條件是 _ 。A.ST-top!=-1 B. ST-top=-1 C.ST-top!= MaxSize D. ST-top=MaxSize-1 3.6 循環(huán)隊(duì)列用數(shù)組 A0，m-1存放其元素值，已知其頭尾指針分別是 front 和 rear, 則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 _。A.（rear-front+m ）

12、%m B. rear-front+1 C. rear-front-1 D. rear-front 3.7 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別是隊(duì)頭和隊(duì)尾指針，則插入一個(gè) s 結(jié)點(diǎn)的運(yùn)算時(shí) _。 A. f-next=s; f=s; B. r-next=s; r=s; C. s-next=r; r=s; D. s-next=f; f=s; 3.8 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別是隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí) _。 A. r=f-next; B. r=r-next; C. f=f-next; D. f=r-next; 03.9 若進(jìn)棧序列為 a，b，c，進(jìn)棧過程中允許出棧，則以下

13、_是不可能得到的出棧序列。0A. a,b,c B. b,a,c C. c,a,b D. c,b,a 3.10 一個(gè)最多能容納 m個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列 Q，其頭尾指針分別為 front 和 rear ，則判定該隊(duì)列為滿的條件是 _ A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rear C. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear 3.11 一個(gè)最多能容納 m個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列 Q，其頭尾指針分別為 front 和 rear ，則判定該隊(duì)列為空的條件是 _ A. (Q.rear+1)%m= =Q.

14、front B. Q.front = = Q.rear C. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear 3.12 若進(jìn)棧序列為 1，2，3，4，進(jìn)棧過程中可以出棧，則以下不可能的出棧序列是（）A. 1 ，4，3，2 B.2 ，3，4，1 C. 3 ，1，4，2 D.3 ，4，2，1 3.13 一個(gè)隊(duì)列的入隊(duì)序列是 1，2，3，4，則隊(duì)列的輸出序列是 _。A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 3.14 若用一個(gè)可容納 6個(gè)元素的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別是 0和

15、4，當(dāng)執(zhí)行2次出隊(duì)和 1次入隊(duì)操作后 ，rear 和 front 的值分別為（）A.1 和0 B.0 和 2 C.2 和 D.1 和 5 第四章 串和數(shù)組4.1 串是一種特殊的線形表，其特殊性體現(xiàn)在 _ A. 可以順序存儲(chǔ) B. 數(shù)據(jù)元素是一個(gè)字符C. 可以存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符4.2 串的兩種最基本的存儲(chǔ)方式是 _順序和鏈?zhǔn)?_。4.3 兩個(gè)串相等的充分必要條件是 : 長(zhǎng)度相等 _且_對(duì)應(yīng)位置上的字符相等 _。4.4 如下述中正確的是 _。A串是一種特殊的線性表 B串的長(zhǎng)度必須大于零 C 串中元素只能是字母 D 空串就是空白串4.5 不含任何字符的串稱為 _空串_,其長(zhǎng)度為 _長(zhǎng)

16、度等于零 _。4.6 設(shè)有字符串 S=“ABC123XYZ”，問該串的長(zhǎng)度為（）A.9 B.10 C.11 D.12 4.7 已知二維數(shù)組 Amn 采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占 k 個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是 LOC（A00 ），則 Aij 的地址是 _loc(a00)+(n*i+j)*k 。4.8 二維數(shù)組有兩種存儲(chǔ)方式，第一種是以 _行 為主序的存儲(chǔ)方式，第二種是以 _列_為主序的存儲(chǔ)方式。設(shè)有二維數(shù)組 A1020 ，其中每個(gè)元素占 2個(gè)字節(jié)，數(shù)組按行優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素 A812 的存儲(chǔ)地址為 _100+（20*8+12）*2 4.9 對(duì)于

17、稀疏矩陣的壓縮存儲(chǔ)，通常用一個(gè)三元組表示非零元素的信息，其中包括非零元素的 值、 行、列 。這些信息可用一個(gè) 三元組 數(shù)組表示，也稱此為 三元組順序表 。4.10 設(shè)有一個(gè) 10 階的對(duì)稱矩陣 A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)， a0, 為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占 1個(gè)字節(jié)，則 a8,5的地址為 _。A. 13 B. 33 C. 18 D. 42 第五章 樹與二叉樹5.1 采用二叉鏈表存儲(chǔ)結(jié)構(gòu) ,具有 n 個(gè)結(jié)點(diǎn)的二叉樹中 ,一共有_2n_個(gè)指針域 ,其中有 _n-1_個(gè)指針域指向孩子結(jié)點(diǎn)，有 _n+1_個(gè)指針域?yàn)榭?. h h h-1 h+15.2 一棵非空二叉樹 ,其

18、第 i 層上最多h h h-1 h+15.3 滿二叉樹是一棵深度為 k 且恰有_2k-1_結(jié)點(diǎn)的二叉樹 . 5.4 一棵哈夫曼樹有個(gè) m葉子結(jié)點(diǎn) ,則其結(jié)點(diǎn)總數(shù)為 _2m-1_. 5.5 三個(gè)結(jié)點(diǎn)的二叉樹，最多有 _5_種形狀。5.6 將一棵完全二叉樹按層次編號(hào) ,對(duì)任一編號(hào)為 i 的結(jié)點(diǎn)有 :如有左孩子 ,則其編號(hào)為 _2i_; 如有右孩子 ,則其編號(hào)為 _2i+1 . 5.7 深度為 k 的非空二叉樹最多有 2k-1 個(gè)結(jié)點(diǎn)，最少有 k 個(gè)結(jié)點(diǎn)，其第 i 層最多有_2i-1 個(gè)結(jié)點(diǎn)。5.8 樹最適合用來表示 _。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素C. 數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù) D

19、. 元素之間無聯(lián)系的數(shù)據(jù)5.9 在下列存儲(chǔ)形式中，不是樹的存儲(chǔ)形式的是 _。A雙親表示法 B. 孩子表示法 C.孩子雙親表示法 D. 孩子兄弟表示法5.10 一棵高度為 h的滿二叉樹中結(jié)點(diǎn)的個(gè)數(shù)為 _。 A. 2 B. 2 -1 C. 2 D.25.11 已知一棵二叉樹的先序遍歷序列為 ABCDEFG,中序遍歷序列為 :CBDAFEG,則該二叉樹的后序遍歷序列是( )ACDBFGEA BCDFGBEA C CDBAFGE D CDBFEGA 5.12 具有 100個(gè)結(jié)點(diǎn)的完全二叉樹，其中含有 _個(gè)度為 1的結(jié)點(diǎn)。A.1 B. 0 C. 2 D. 不確定5.13 已知一棵二叉樹的先序遍歷序列為

20、EFHIGJK,中序遍歷序列為 :HFIEJGK,則該二叉樹的右子樹的根是( )A B C D5.14 如下左圖所示二叉樹的中序遍歷序列是 _ A. abcdgef B. dfebagc C. dbaefcg D. defbagc 5.15 一棵二叉樹如上右圖所示，其中序遍歷的序列為 _ Aabdgcefh Bdgbaechf C gdbehfca D abcdefgh 5.16 在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該 ( ) A. 只有左子樹上的所有結(jié)點(diǎn) B. 只有左子樹上的部分結(jié)點(diǎn) C. 只有右子樹上的所有結(jié)點(diǎn) D. 只有右子樹上的部分結(jié)點(diǎn)5.17 在一非空二叉樹的中序遍歷

21、序列中，根結(jié)點(diǎn)的右邊應(yīng)該 _。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)5.18 有一棵樹如下左圖所示，回答下列問題：這棵樹的葉子結(jié)點(diǎn)是 _k2,k4,k5,k7這棵樹的度為 _3_ 這棵樹的葉子結(jié)點(diǎn)是 _k2,k4,k5,k7這棵樹的度為 _3_ 結(jié)點(diǎn) k3的孩子結(jié)點(diǎn)是 _ k5,k6 _ _ 結(jié)點(diǎn) k3的度為 _2_; 這棵樹的深度為 _4_; 結(jié)點(diǎn) k3的雙親結(jié)點(diǎn)是 _ k1 _ 5.19 由上右圖所示的二叉樹，回答以下問題。 其中序遍歷序列為 _ 其先序遍歷序列為 _ 其后序遍歷序列為 _ (4) 該二叉樹對(duì)應(yīng)得

22、森林是 _ 5.20 某二叉樹的先序遍歷序列為 abdgcefh, 中序遍歷序列是 dgbaechf, 請(qǐng)畫出該二叉樹并給出其后序遍歷序列。 gdbehfca5.21 如下左圖所示 , 以數(shù)據(jù)集 4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值所構(gòu)成的二叉樹為 _哈夫曼樹 _，其帶權(quán)路徑長(zhǎng)度為 _165_。5.22 對(duì)如上右圖所示的樹， 該樹的高度為 _，該樹的度為 _，結(jié)點(diǎn) E的層次為 _，結(jié)點(diǎn) H的雙親為 _，結(jié)點(diǎn) H的兄弟為 _，結(jié)點(diǎn) B的度為 _。5.23 若二叉樹中度為 2的結(jié)點(diǎn)有 15 個(gè)，該二叉樹則有 16 個(gè)葉結(jié)點(diǎn)。5.24 若深度為 6的完全二叉樹的第 6層有 3個(gè)葉結(jié)點(diǎn)，則該二叉

23、樹一共有 34 個(gè)結(jié)點(diǎn)。5.25二叉樹的前序遍歷序列為 A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為 A，E，C，F(xiàn)，B，G，D，H，其后序遍歷序列為 。5.26 一個(gè)深度為 k的二叉樹，當(dāng)具有 2k-1 個(gè)結(jié)點(diǎn)時(shí)稱之為 _滿二叉樹 。5.27 下面關(guān)于哈夫曼樹的說法， 不正確 的是 ( ) A. 對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的 B. 哈夫曼樹具有最小帶權(quán)路徑長(zhǎng)度 C. 哈夫曼樹中沒有度為 1的結(jié)點(diǎn) D. 哈夫曼樹中除了度為 1的結(jié)點(diǎn)外，還有度為 2的結(jié)點(diǎn)和葉結(jié)點(diǎn)5.28 在如圖所示的表達(dá)式二叉樹中，按中序遍歷得到的序列為 _。圖第六章圖6.1 一個(gè)具有 n 個(gè)頂點(diǎn)的無向連通圖

24、至少有 _n-1_條邊， 所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 2_倍。6.2 在有向圖的鄰接矩陣中，第 i 行中 1的個(gè)數(shù)為第 i 個(gè)頂點(diǎn)的 _出度_。第 i 列中 1的個(gè)數(shù)為第 i 個(gè)頂點(diǎn)的_入度_。6.3 一個(gè)無向圖有 n 個(gè)頂點(diǎn)和 e條邊，則所有頂點(diǎn)的度的和為 _2e。具有 n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為_n(n-1)/2 _。具有 n個(gè)頂點(diǎn)的有向完全圖的弧個(gè)數(shù)為 _ n(n-1) _。6.4 設(shè)連通圖 G的頂點(diǎn)數(shù)為 n，則 G的生成樹的邊數(shù)為 _ n-1 。6.5 若無向圖中有 e條邊，則表示該無向圖的鄰接表中就有 _2e 個(gè)結(jié)點(diǎn)。6.6 Dijkstra 算法是按 _路徑長(zhǎng)序依次遞增 _

25、的次序產(chǎn)生一點(diǎn)到其余各頂點(diǎn)最短路徑的算法。6.7 可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是 _無環(huán)的 _。在拓?fù)渑判蛐蛄兄械谝粋€(gè)頂點(diǎn)一定是 _入度為零 _的頂點(diǎn)。6.8 設(shè)一個(gè)無向圖為如下左圖所示，畫出該圖的鄰接表和鄰接矩陣；寫出從 頂點(diǎn) A出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。1 2 31 2 32 2 12 2 33 2 31 3 36.9 設(shè)一個(gè)無向圖為 G=(V,E), 其中 V=v1,v2,v3,v4 ，v5,v6,v7 ，E=(v1,v2),(v1,v3),(v2,v4),(v2,v5), (v3,v6),(v3,v7),(v6,v7), 畫出該無向圖，畫出其鄰 接表和鄰接矩陣，寫出

26、從頂點(diǎn) v1 出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。6.10 設(shè)一個(gè)無向圖為 G=(V,E), 其中 V=v1,v2,v3,v4 ，v5,v6 ，其鄰接矩陣如上右圖所示：(1) 畫出該無向圖; (2) 畫出其鄰 接表和鄰接矩陣; (3) 寫出從頂點(diǎn) v1 出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列; (4) 分別用 Prim 和 Kruskal 算法, 從頂點(diǎn) v1 頂點(diǎn)出發(fā)，寫出求該網(wǎng)的最小生成樹的產(chǎn)生過程。6.11 設(shè)一個(gè)圖為 G=(V,E), 其中 V=a,b,c,d,e,f ，E=, ， ， ， ，, (1) 畫出該圖; 216對(duì)下圖，寫出拓?fù)溆行蛐蛄?？E5D4C6算法求出從

27、源點(diǎn) A到其余各頂點(diǎn)的最短路徑及E212 4 8 查找）。41010216對(duì)下圖，寫出拓?fù)溆行蛐蛄?？E5D4C6算法求出從源點(diǎn) A到其余各頂點(diǎn)的最短路徑及E212 4 8 查找）。41010F16 3 2 C2197 DF38510 (3) 寫出從頂點(diǎn) a 出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列; 6.15 對(duì)如下無向圖，分 別用 Prim 和 Kruskal 算法, 分別從頂點(diǎn) 1 和頂點(diǎn) a 出發(fā)，寫 出求該網(wǎng)的最小生成樹的產(chǎn)生過程。11676.16 B2A1a36.17 對(duì)下圖所示的1帶權(quán)有向圖，利用 Dijstra其長(zhǎng)度。125 B10 A1413第七章8.1 用順序查找法在具有

28、各結(jié)點(diǎn)的線性表中查找一個(gè)結(jié)點(diǎn)所需的平均查找時(shí)間為（22n) C. O(n) 2n)排序(n) B.O(nlog2n) C.O(n) 22n) C. O(n) 2n)排序8.2 使用折半查找，線性表必須（ ）。、一順序方式存儲(chǔ) 、以鏈?zhǔn)椒绞酱鎯?chǔ)，且元素已按值排好序、以鏈?zhǔn)椒绞酱鎯?chǔ) 、以順序方式存儲(chǔ)，且元素已按值排好序8.3 采用順序查找法查找長(zhǎng)度為 n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 _。 A. n B. n/2 C. （n+1）/2 D. (n-1)/2 8.4 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 _ 的線性表。A散列存儲(chǔ) B. 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)8.5 采用折半查找

29、法查找長(zhǎng)度為 n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 _。 A. O(n ) B. O(nlog D. O(log8.6 采用順序查找法檢索長(zhǎng)度為 n的線性表，則檢索每個(gè)元素的平均比較次數(shù)為 _n-i+1 _。8.7 有一個(gè)有序表為： (1,3,9,12,32,41,45,62,75,77,82,95,100), 當(dāng)折半查找值 82 的結(jié)點(diǎn)時(shí)，經(jīng)過_次比較后查找成功。A. 1 B. 2 C. 4 D. 8 8.8 折半查找有序表 6,15,30,37,65,70,72,89,99, 若要查找元素 37，需要依次與表中元素 _進(jìn)行比較。A. 65 ，15，37 B. 68 ，30，37 C. 6

30、5 ，15，30 D. 65 ，15，30，378.9 已有序表為（ 20，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找 90時(shí)，需要進(jìn)行_2_ 次查找可確定成功。查找 47時(shí)需進(jìn)行 _4_ 次查找可確定成功，查找 100時(shí)，需進(jìn)行 _4_ 次查找才能確定不成功。8.10 按序列60,17 ，38，40，7，32，73，65，85的輸入順序建立一顆二叉排序樹. （1）畫出該二叉排序樹；（2）在（1）的基礎(chǔ)上插入結(jié)點(diǎn) 80 后，畫出對(duì)應(yīng)的二叉排序樹; (3) 在（2）的基礎(chǔ)上刪除結(jié)點(diǎn) 38 后，畫出對(duì)應(yīng)的二叉排序樹。8.11 按序列（53，49，26，78，6

31、3，35，19，99）的輸入順序建立一顆二叉排序樹. （1）畫出該二叉排序樹；（2）在（1）的基礎(chǔ)上插入結(jié)點(diǎn) 50 后，畫出對(duì)應(yīng)的二叉排序樹; (3) 在（2）的基礎(chǔ)上刪除結(jié)點(diǎn) 26 后，畫出對(duì)應(yīng)的二叉排序樹。8.12 已知一組關(guān)鍵字序列為（ 75，33，52，41，12，88，66，27），請(qǐng)按哈希函數(shù) H(key)=key MOD 7 ，分別用線性探測(cè)和二次探測(cè)處理沖突方法構(gòu)造一個(gè)表長(zhǎng)為 10的哈希表。8.13 已知一組關(guān)鍵字為（ 17，12，21，01，66，35，82，37），請(qǐng)按哈希函數(shù) H(key)=key MOD 13，分別用線性探測(cè)和二次探測(cè)處理沖突方法構(gòu)造一個(gè)表長(zhǎng)為 14的哈希表。8.14 已知：哈希表長(zhǎng)為 10，哈希函數(shù) H(