《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(答案)》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(答案)（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)習(xí)題 第一章 緒論 1.1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(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.可讀性和文

2、檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 1.3 計(jì)算機(jī)算法指的是__①__ ，它必須具備輸入、輸出和__②_ 等5個(gè)重要特性。 ① A.計(jì)算方法 B.排序方法 C.解決問(wèn)題的有限運(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)的算法，分析算法的效

3、率。算法的效率包括時(shí)間和空間兩個(gè)方面，分別稱為_(kāi)空間復(fù)雜度和時(shí)間復(fù)雜度。數(shù)據(jù)的邏輯結(jié)構(gòu)是指_數(shù)據(jù)元素之間的關(guān)系__；包括線性結(jié)構(gòu)、 樹(shù)形結(jié)構(gòu)和 圖形結(jié)構(gòu) 三種類型,其中樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱為_(kāi)_非線性結(jié)構(gòu)__。 1.6 線性結(jié)構(gòu)中元素之間存在_一對(duì)一___ 關(guān)系，樹(shù)形結(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ǔ)在物理位置 相鄰的內(nèi)存單元中 ；鏈?zhǔn)酱鎯?chǔ)方法中元素間的關(guān)

4、系是由__指針來(lái)表示_的。 第二章 線性表 2.1 鏈表不具備的特點(diǎn)是 ____ 。 A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B.插入刪除不需移動(dòng)元素 C.不必事先估計(jì)存儲(chǔ)空間 D.所需空間與其長(zhǎng)度成正比 2.2 不帶頭結(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. h

5、ead->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)并仍然保持有序的時(shí)間復(fù)雜度是____。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 2.6線性鏈表中各個(gè)結(jié)點(diǎn)之間的地址 不一定 連續(xù)。 2.7線性表中數(shù)據(jù)元素之間具有__一對(duì)一__，除第一個(gè)和最后一個(gè)元素外，其他

6、數(shù)據(jù)元素有且只有_一個(gè) 請(qǐng)預(yù)覽后下載！ 后繼和前趨。 2.8若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用 鏈?zhǔn)? 存儲(chǔ)結(jié)構(gòu)比較合適。 2.9 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=_p->next_和p->next=_s_的操作。 2.10 已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為L(zhǎng)OC(a1)，那么，LOC(ai)=__ LOC(a1)+（i-1）*k_。 2.12 若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用3個(gè)存儲(chǔ)單元，第11個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為130，則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是 1

7、00 。 2.12 若線性表采用順序存儲(chǔ)結(jié)構(gòu)，線性表的最大長(zhǎng)度為1000，每個(gè)數(shù)據(jù)元素占3個(gè)存儲(chǔ)單元，則要分配給該線性表_3000__存儲(chǔ)單元，若第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是2000，則第11個(gè)元素的存儲(chǔ)地址是__2030__。 2.13 以head為頭結(jié)點(diǎn)循環(huán)雙鏈表為空時(shí)，應(yīng)滿足head->llink= head ，head->rlink= head 。 2.14 在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語(yǔ)句是 。 A.p=p->next; B.p->next=p->next->next; C.p->next=

8、p; D.p=p->next->next; 2.15 在單鏈表中，已知q指的結(jié)點(diǎn)是p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入一個(gè)由s指的結(jié)點(diǎn)，則需執(zhí)行________。 A. s->next=p->next;p->next=s B. q->next=s;s->next=p C. p->next=s->next;s->next=p D.p->next=s;s->next=q 2.16 用鏈表表示線性表的優(yōu)點(diǎn)是（） A．便于隨機(jī)存儲(chǔ) B.便于進(jìn)行插入和刪除操作 C. 占用的存儲(chǔ)空間較順序表少

9、 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)，訪問(wèn)其第i個(gè)元素的算法時(shí)間復(fù)雜度為（） A. O（1） B.O（n） C. O（n2）

10、 D.O（log2n） 2.20 在長(zhǎng)度為n的順序表刪除第i（1≤i≤n）個(gè)元素，則需要向前移動(dòng)元素的次數(shù)為（） A. i B. n-i C. n-i+1 D.n-i-1 2.21 在長(zhǎng)度為n的順序表中第i（1≤i≤n）個(gè)位置上插入一個(gè)元素時(shí)，為留出插入位置所需要移動(dòng)元素的次數(shù)為（） A. n-i B. i C. n-i-1 D. n-i+1 2.22 以下對(duì)單鏈表的敘述錯(cuò)誤的是（） A. 單鏈表中的每一個(gè)結(jié)點(diǎn)都由存放結(jié)點(diǎn)值的數(shù)據(jù)域和存放直接

11、后繼結(jié)點(diǎn)地址信息的指針域兩部分組成 B.從單鏈表的第i 個(gè)結(jié)點(diǎn)出發(fā)，可以訪問(wèn)到鏈表中的任何一個(gè)結(jié)點(diǎn) C.在單鏈表結(jié)構(gòu)中加入頭結(jié)點(diǎn)可以簡(jiǎn)化結(jié)點(diǎn)的插入和刪除操作 請(qǐng)預(yù)覽后下載！ D.單鏈表尾結(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)先出

12、 B.先進(jìn)后出 3.2 棧和隊(duì)列的共同點(diǎn)時(shí)____。 A.都是先進(jìn)后出 B.都是先進(jìn)先出 C.只允許在端點(diǎn)處插入和刪除元素 D.沒(méi)有共同點(diǎn) 3.3 一個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是____ 。 A. edcba B. decba C. dceab D. abcde 3.4 判定一個(gè)棧ST（最多元素MaxSize）為空的條件是____ 。 A.ST->top!=-1 B. ST->top==-1 C.ST->top!= MaxSize D. ST->t

13、op==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ù)組A[0，m-1]存放其元素值，已知其頭尾指針?lè)謩e是front和 rear,則 當(dāng)前隊(duì)列中的元素個(gè)數(shù)是____。 A.（rear-front+m）%m B. rear-front+1 C. rear-front-1 D. rear-front 3.

14、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; 請(qǐng)預(yù)覽后下載！ 3.9若進(jìn)棧序列為a，b，c，進(jìn)棧過(guò)程中允許出棧，則以下_____是不可能得到

15、的出棧序列。 A. 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，其頭尾指針?lè)謩e為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，其頭尾指針?lè)謩e為front和rear，則判定該隊(duì)列為空的條件是__________

16、 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.12若進(jìn)棧序列為 1，2，3，4，，進(jìn)棧過(guò)程中可以出棧，則以下不可能的出棧序列是（） 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

17、. 3,2,4,1 3.14 若用一個(gè)可容納6個(gè)元素的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別是0和4，當(dāng)執(zhí)行2次出隊(duì)和1次入隊(duì)操作后 ，rear和front 的值分別為（） A.1和0 B.0和2 C.2和5 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)位置上的字符相等

18、__。 4.4 如下陳述中正確的是______。 A．串是一種特殊的線性表 B．串的長(zhǎng)度必須大于零 C．串中元素只能是字母 D．空串就是空白串 4.5 不含任何字符的串稱為_(kāi)_空串_,其長(zhǎng)度為_(kāi)長(zhǎng)度等于零__。 4.6 設(shè)有字符串S=“ABC123XYZ”，問(wèn)該串的長(zhǎng)度為（） A.9 B.10 C.11 D.12 4.7已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC（A[0][0]），則A[i][j]的地址是__loc(a[0][0])+(n*i+j)*k。 4.8二維數(shù)組有

19、兩種存儲(chǔ)方式，第一種是以_行 為主序的存儲(chǔ)方式，第二種是以_列_為主序的存儲(chǔ)方式。設(shè)有二維數(shù)組A[10][20]，其中每個(gè)元素占2個(gè)字節(jié)，數(shù)組按行優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素A[8][12]的存儲(chǔ)地址為_(kāi)_100+（20*8+12）*2 4.9對(duì)于稀疏矩陣的壓縮存儲(chǔ)，通常用一個(gè)三元組表示非零元素的信息，其中包括非零元素的值、 行、 列 。這些信息可用一個(gè)三元組 數(shù)組表示，也稱此為 三元組順序表 。 4.10設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，a0,0為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)字節(jié)，則a8,5的地址為_(kāi)_____

20、____。 A. 13 B. 33 C. 18 D. 42 第五章 樹(shù)與二叉樹(shù) 5.1 采用二叉鏈表存儲(chǔ)結(jié)構(gòu),具有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)中,一共有_2n_個(gè)指針域,其中有__n-1_個(gè)指針域指向孩子結(jié)點(diǎn)，有_n+1_個(gè)指針域?yàn)榭? 請(qǐng)預(yù)覽后下載！ 5.2 一棵非空二叉樹(shù),其第i層上最多有_2i-1__結(jié)點(diǎn)。 5.3 滿二叉樹(shù)是一棵深度為k且恰有_2k-1___結(jié)點(diǎn)的二叉樹(shù). 5.4 一棵哈夫曼樹(shù)有個(gè)m葉子結(jié)點(diǎn),則其結(jié)點(diǎn)總數(shù)為_(kāi)2m-1__. 5.5 三個(gè)結(jié)點(diǎn)的二叉樹(shù)，最多有_5__種形狀。 5.6 將一棵完全二叉樹(shù)按層次編號(hào),對(duì)任

21、一編號(hào)為i的結(jié)點(diǎn)有:如有左孩子,則其編號(hào)為_(kāi)_2i_; 如有右孩子,則其編號(hào)為_(kāi)2i+1. 5.7深度為k的非空二叉樹(shù)最多有 2k-1個(gè)結(jié)點(diǎn)，最少有 k 個(gè)結(jié)點(diǎn)，其第i層最多有_2i-1 個(gè)結(jié)點(diǎn)。 5.8 樹(shù)最適合用來(lái)表示____。 A. 有序數(shù)據(jù)元素 B.無(wú)序數(shù)據(jù)元素 C. 數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無(wú)聯(lián)系的數(shù)據(jù) 5.9 在下列存儲(chǔ)形式中，不是樹(shù)的存儲(chǔ)形式的是____。 A．雙親表示法 B.孩子表示法 C.孩子雙親表示法 D.孩子兄弟表示法 5.10 一棵高度為h的滿二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)___。

22、A. 2h B. 2h-1 C. 2h-1 D.2h+1 5.11 已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG,中序遍歷序列為:CBDAFEG,則該二叉樹(shù)的后序遍歷序列是(　)． A．CDBFGEA　　　 B．CDFGBEA　　　 C．CDBAFGE　　　 D．CDBFEGA 5.12　具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其中含有__________個(gè)度為1的結(jié)點(diǎn)。 A.1 B. 0 C. 2 D. 不確定 5.13 已知一棵二叉樹(shù)的先序遍歷序列為EFHIGJK,中序遍歷序列為:HFIEJGK,則該二叉樹(shù)的右子樹(shù)的根是(

23、　)． A．Ｅ　　　 B．Ｆ　　　 C．Ｇ　　　 D．Ｊ 5.14 如下左圖所示二叉樹(shù)的中序遍歷序列是____ A. abcdgef B. dfebagc C. dbaefcg D. defbagc 5.15 一棵二叉樹(shù)如上右圖所示，其中序遍歷的序列為_(kāi)___ A．a(chǎn)bdgcefh B．dgbaechf C．gdbehfca D．a(chǎn)bcdefgh 5.16在非空二叉樹(shù)的中序遍歷序列中，二叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該 ( ) A.只有左子樹(shù)上的所有結(jié)點(diǎn) B.只有左子樹(shù)上的部分結(jié)點(diǎn) C.只有右子樹(shù)上的所

24、有結(jié)點(diǎn) D.只有右子樹(shù)上的部分結(jié)點(diǎn) 5.17 在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊應(yīng)該____。 A. 只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的部分結(jié)點(diǎn) C. 只有左子樹(shù)上的部分結(jié)點(diǎn) D. 只有左子樹(shù)上的所有結(jié)點(diǎn) 5.18 有一棵樹(shù)如下左圖所示，回答下列問(wèn)題： 請(qǐng)預(yù)覽后下載！ ⑴這棵樹(shù)的根結(jié)點(diǎn)是_k1___; ⑵這棵樹(shù)的葉子結(jié)點(diǎn)是_k2,k4,k5,k7___ ⑶結(jié)點(diǎn)k3的度為_(kāi)2___; ⑷這棵樹(shù)的度為_(kāi)3___ ⑸這棵樹(shù)的深度為_(kāi)4__; ⑺結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是_

25、k5,k6_ ⑻結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是__ k1__ 5.19 由上右圖所示的二叉樹(shù)，回答以下問(wèn)題。 ⑴ 其中序遍歷序列為_(kāi)___ ⑵ 其先序遍歷序列為_(kāi)___ ⑶ 其后序遍歷序列為_(kāi)___ (4) 該二叉樹(shù)對(duì)應(yīng)得森林是____ 5.20某二叉樹(shù)的先序遍歷序列為abdgcefh,中序遍歷序列是dgbaechf, 請(qǐng)畫(huà)出該二叉樹(shù)并給出其后序遍歷序列。gdbehfca 5.21 如下左圖所示 ,以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)成的二叉樹(shù)為_(kāi)哈夫曼樹(shù)___，其帶權(quán)路徑長(zhǎng)度為_(kāi)165___。 5.22對(duì)如上右

26、圖所示的樹(shù)，該樹(shù)的高度為_(kāi)_________，該樹(shù)的度為_(kāi)_________，結(jié)點(diǎn)E的層次為_(kāi)_________，結(jié)點(diǎn)H的雙親為_(kāi)_________，結(jié)點(diǎn)H的兄弟為_(kāi)_________，結(jié)點(diǎn)B的度為_(kāi)_________。 5.23若二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，該二叉樹(shù)則有 16 個(gè)葉結(jié)點(diǎn)。 5.24若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)一共有 34 個(gè)結(jié)點(diǎn)。 5.25二叉樹(shù)的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G，D，H，其后序遍歷序列為 。 5.26一個(gè)深度為k的二叉樹(shù)，當(dāng)具有2k-

27、1個(gè)結(jié)點(diǎn)時(shí)稱之為_(kāi)滿二叉樹(shù)。 5.27下面關(guān)于哈夫曼樹(shù)的說(shuō)法，不正確的是 ( ) A.對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹(shù)一般不是唯一的 B.哈夫曼樹(shù)具有最小帶權(quán)路徑長(zhǎng)度 C.哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn) D.哈夫曼樹(shù)中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn) 5.28在如圖所示的表達(dá)式二叉樹(shù)中，按中序遍歷得到的序列為_(kāi)_________。 請(qǐng)預(yù)覽后下載！ 第六章 圖 6.1 一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有_n-1___條邊，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2_倍。 6.2 在有向圖的鄰接矩陣中，第i行中1的個(gè)數(shù)為第i個(gè)頂點(diǎn)

28、的_出度__。第i列中1的個(gè)數(shù)為第i個(gè)頂點(diǎn)的_入度__。 6.3 一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)和e條邊，則所有頂點(diǎn)的度的和為_(kāi)2e。具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為_(kāi)_n(n-1)/2__。具有n個(gè)頂點(diǎn)的有向完全圖的弧個(gè)數(shù)為_(kāi)_ n(n-1)_。 6.4 設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹(shù)的邊數(shù)為_(kāi)_ n-1 。 6.5 若無(wú)向圖中有e條邊，則表示該無(wú)向圖的鄰接表中就有_2e 個(gè)結(jié)點(diǎn)。 6.6 Dijkstra算法是按_路徑長(zhǎng)序依次遞增__的次序產(chǎn)生一點(diǎn)到其余各頂點(diǎn)最短路徑的算法。 6.7 可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_無(wú)環(huán)的_。在拓?fù)渑判蛐蛄兄械谝粋€(gè)頂點(diǎn)一定是__入度為零_的

29、頂點(diǎn)。 6.8 設(shè)一個(gè)無(wú)向圖為如下左圖所示，畫(huà)出該圖的鄰接表和鄰接矩陣；寫出從頂點(diǎn)A出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。 6.9 設(shè)一個(gè)無(wú)向圖為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)},畫(huà)出該無(wú)向圖，畫(huà)出其鄰接表和鄰接矩陣，寫出從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。 6.10 設(shè)一個(gè)無(wú)向圖為G=(V,E)

30、,其中V={v1,v2,v3,v4，v5,v6 }，其鄰接矩陣如上右圖所示： (1)畫(huà)出該無(wú)向圖; (2)畫(huà)出其鄰接表和鄰接矩陣; (3)寫出從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列; 請(qǐng)預(yù)覽后下載！ (4)分別用Prim和Kruskal算法,從頂點(diǎn)v1頂點(diǎn)出發(fā)，寫出求該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程。 6.11 設(shè)一個(gè)圖為G=(V,E),其中V={a,b,c,d,e,f}， E={,,,，，，，,} (1)畫(huà)出該圖; (2)畫(huà)出其鄰接矩陣和鄰接表; (3)寫出從頂點(diǎn)a出發(fā)

31、進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列; 6.15對(duì)如下無(wú)向圖，分別用Prim和Kruskal算法,分別從頂點(diǎn)1和頂點(diǎn)a出發(fā)，寫出求該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程。 ① ② ③ ⑤ ④ ⑥ ⑦ 6 21 7 4 11 2 19 10 10 8 3 6 6.16 對(duì)下圖，寫出拓?fù)溆行蛐蛄校? A1a11 B2 D4 C3 E5 F6 6.17 對(duì)下圖所示的帶權(quán)有向圖，利用Dijstra算法求出從源點(diǎn)A到其余各頂點(diǎn)的最短路徑及其長(zhǎng)度。 A11 B2 D4 C3 E5 F 25 10 8

32、3 16 7 2 10 12 4 請(qǐng)預(yù)覽后下載！ 第七章 查找 8.1用順序查找法在具有ｎ各結(jié)點(diǎn)的線性表中查找一個(gè)結(jié)點(diǎn)所需的平均查找時(shí)間為（　?。? ＡＯ(n) B.O(nlog2n) C.O(n) D.O(log2n) 8.2 使用折半查找，線性表必須（　?。?。 Ａ、一順序方式存儲(chǔ)　　　　?。隆⒁枣?zhǔn)椒绞酱鎯?chǔ)，且元素已按值排好序 Ｃ、以鏈?zhǔn)椒绞酱鎯?chǔ)　　　　?。摹⒁皂樞蚍绞酱鎯?chǔ)，且元素已按值排好序 8.3 采用順序查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)___。

33、 A. n B. n/2 C. （n+1）/2 D. (n-1)/2 8.4 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為_(kāi)___ 的線性表。 A．散列存儲(chǔ) B. 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C. 壓縮存儲(chǔ) D. 索引存儲(chǔ) 8.5采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)___。 A. O(n2) B. O(nlog2n) C. O(n) D. O(log2n) 8.6采用順序查找法檢索長(zhǎng)度為n的線性表，則檢索每個(gè)元素的平均比較次數(shù)為_(kāi)n-i+1_。 8.7有一個(gè)有序表為：(1,3,9,12,32,41,45,

34、62,75,77,82,95,100),當(dāng)折半查找值82的結(jié)點(diǎn)時(shí)，經(jīng)過(guò)__________次比較后查找成功。 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. 65，15，30 D. 65，15，30，37 8.9 已有序表為（20，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找90時(shí)，需要進(jìn)行_2_ 次查找可確定成功。查

35、找47時(shí)需進(jìn)行_4_ 次查找可確定成功，查找100時(shí)，需進(jìn)行_4__ 次查找才能確定不成功。 8.10 按序列{60,17，38，40，7，32，73，65，85}的輸入順序建立一顆二叉排序樹(shù). （1）畫(huà)出該二叉排序樹(shù)； （2）在（1）的基礎(chǔ)上插入結(jié)點(diǎn)80后，畫(huà)出對(duì)應(yīng)的二叉排序樹(shù); (3) 在（2）的基礎(chǔ)上刪除結(jié)點(diǎn)38后，畫(huà)出對(duì)應(yīng)的二叉排序樹(shù)。 8.11按序列（53，49，26，78，63，35，19，99）的輸入順序建立一顆二叉排序樹(shù). （1）畫(huà)出該二叉排序樹(shù)； （2）在（1）的基礎(chǔ)上插入結(jié)點(diǎn)50后，畫(huà)出對(duì)應(yīng)的二叉排序樹(shù); (3) 在（2）的基礎(chǔ)上刪除結(jié)點(diǎn)26后，畫(huà)出對(duì)應(yīng)的二

36、叉排序樹(shù)。 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(key)=key MOD 9，給出關(guān)鍵字序列為（23，45，14，17，9，29,37，18，25,41,33），采用鏈地址法解決沖突，請(qǐng)畫(huà)出哈希表。

37、 第八章 排序 9.1 對(duì)于給定的12個(gè)整數(shù)：23，37，7，79，29，43，73，19，31，61，23，47，分別寫出用直接插入序、冒泡和直接選擇 請(qǐng)預(yù)覽后下載！ 、快速、歸并排序的各趟結(jié)果。 9.2排序可分為_(kāi)_________和_____________兩類；衡量排序算法的兩個(gè)主要性能指標(biāo)分別是:______________、______________。 9.3假設(shè)待排序數(shù)據(jù)元素序列為[ ４，６，３，２，５]，應(yīng)用快速排序方法按遞增序排序，得到第一次劃分后的結(jié)果為_(kāi)［2_3_4_6_5_］ 。 9.4 排序算法的穩(wěn)定性是指____相同的紀(jì)錄經(jīng)過(guò)

38、排序后的__是否發(fā)生變化，不發(fā)生變化的排序算法，就是___;否則就是___。 9.5 排序算法的基本操作是____和____。 9.6 排序算法的____取決于關(guān)鍵字的比較和記錄的移動(dòng)等基本操作的次數(shù)。 9.7排序算法的空間效率取決于算法所占用的_____的大小。 9.8 下面排序算法的平均時(shí)間復(fù)雜度最小的是_______。 A．直接插入排序 B．簡(jiǎn)單選擇排序 C．冒泡排序 D．快速排序 9.9以下排序方法中，穩(wěn)定的排序方法是__________。 A. 直接插入排序和冒泡排序 B. 簡(jiǎn)單選擇排序和歸并排序 C. 堆排序和快速排序

39、 D. 冒泡排序和快速排序 9.11 一組紀(jì)錄的關(guān)鍵碼為（46，79，56，38，40，84）則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到一次劃分結(jié)果為_(kāi)___。 A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，56，79，84 D. 40，38，46，84，56，79 9.12快速排序方法在____ 情況下最不利于發(fā)揮其長(zhǎng)處。 A.要排序得數(shù)據(jù)量太大 B. 要排序得數(shù)據(jù)種含有多個(gè)相同值 C.要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 9

40、.13 已知序列{53，87，12，61，98，17，87，27，63，46}，畫(huà)出與該序列對(duì)應(yīng)的完全二叉樹(shù)；判斷該序列是否為堆，如果不是，請(qǐng)調(diào)整為大根（頂）堆。 9．14已知序列{27，10，14，55，39，19，84，68，11，23，85}，畫(huà)出與該序列對(duì)應(yīng)的完全二叉樹(shù)；判斷該序列是否為堆，如果不是，請(qǐng)調(diào)整為大根（頂）堆。 9．15已知序列{20，15，4，18，9，6，25，12，3，22}，畫(huà)出與該序列對(duì)應(yīng)的完全二叉樹(shù)；判斷該序列是否為堆，如果不是，請(qǐng)調(diào)整為小根（頂）堆。 （注：可編輯下載，若有不當(dāng)之處，請(qǐng)指正，謝謝!） 請(qǐng)預(yù)覽后下載！