南京曉莊學(xué)院數(shù)據(jù)結(jié)構(gòu)題庫(kù)參考標(biāo)準(zhǔn)答案

1、習(xí)題冊(cè) 課后部分參考答案） 算法課程組 1 / 27 目錄 課后習(xí)題部分 第一章 緒論 1 第二章 線性表 3 第三章 棧和隊(duì)列 5 第四章 串 8 第五章 數(shù)組和廣義表 10 第六章 樹和二叉樹 13 第七章 圖 16 第九章 查找 20 第十章 排序 23 2 / 27 第一章 緒論 一 . 填空題 1. 從邏輯關(guān)系上講， 數(shù)據(jù)結(jié)構(gòu)的類型主要分為 集合 、線性結(jié)構(gòu) 、樹結(jié)構(gòu) 和 圖結(jié)構(gòu) 。 2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)， 都要存儲(chǔ)兩方面的內(nèi)容： 數(shù)據(jù)元素 和 數(shù)據(jù)元素之間的關(guān)系 。 3. 算法具有五個(gè)特性，分別是 有窮性 、 確定性、可

2、行性 、 輸入 、 輸出 。 4. 算法設(shè)計(jì)要求中的健壯性指的是 算法在發(fā)生非法操作時(shí)可以作出處理的特性 。 二 . 選擇題 1. 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由 C 表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的 數(shù)據(jù)元素之間的邏輯關(guān)系是由 D 表示的。 A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲(chǔ)位置 D 指針 2. 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母 親的遺產(chǎn)；子女間不能相互繼承。 則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是 B A 樹 B 圖 C 線性表 D 集合 3. 算法指的是 A 。 A 對(duì)特定問題求解步驟的一種描述，是指令的有限序列。 B 計(jì)算機(jī)程序 C

3、解決問題的計(jì)算方法 D 數(shù)據(jù)處理 三 . 簡(jiǎn)答題 1. 分析以下各程序段，并用大 O 記號(hào)表示其執(zhí)行時(shí)間。 (1) (2) i=1;k=0;i=1;k=0; While(in-1)do k=k+10*i; k=k+10*i; i+; i+; while(inext =rear-next; rear-next =s; rear =s; ；刪除開始結(jié)點(diǎn)的操作順序?yàn)?q=rear-next-next; rear-next-next=q-next; delete q; 。 二 . 選擇題 1. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)物理地址與邏輯地址相同并且是連續(xù)的，稱之為：C A 存儲(chǔ)結(jié)構(gòu) B 邏輯結(jié)構(gòu) C 順

4、序存儲(chǔ)結(jié)構(gòu) D 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2. 在 n 個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O （1）的操作是： A A 訪問第 i 個(gè)結(jié)點(diǎn)（ 1 i ）n和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)（ 2 i ）n B 在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（ 1 i ）n C 刪除第 i個(gè)結(jié)點(diǎn)（ 1i ）nD 將n 個(gè)結(jié)點(diǎn)從小到大排序 3. 線性表 L 在 B 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 A 需經(jīng)常修改 L 中的結(jié)點(diǎn)值 B 需不斷對(duì) L 進(jìn)行刪除插入 C L 中含有大量的結(jié)點(diǎn) D L 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 4. 單鏈表的存儲(chǔ)密度 C A 大于 1 B 等于 1 C 小于 1 D 不能確定 三 . 判斷題 1. 線性表的邏輯順

5、序和存儲(chǔ)順序總是一致的。F 2. 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。F 3. 設(shè) p，q 是指針，若 p=q ，則*p=*q 。 F 4. 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 F 四 . 簡(jiǎn)答題 1. 分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。 （1） 若線性表的總長(zhǎng)度基本穩(wěn)定， 且很少進(jìn)行插入和刪除操作， 但要求以最快的速度存取 線性表中的元素。 （2）如果 n 個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。 （3）描述一個(gè)城市的設(shè)計(jì)和規(guī)劃。 3 / 27 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所 以應(yīng)選

6、用順序存儲(chǔ)結(jié)構(gòu)。 應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生變化。 應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪 除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。 五 . 算法設(shè)計(jì) 1. 已知數(shù)組 An 中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為 奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為 O(n) 。 2. 線性表存放在整型數(shù)組 Aarrsize 的前 elenum 個(gè)單元中，且遞增有序。編寫算法， 將元素 x 插入到線性表的適當(dāng)位置上， 以保持線性表的有序性， 并且分析算法的時(shí)

7、間復(fù) 雜度。 int insert (datatype A,int *elenum,datatype x) /*設(shè) elenum 為表的最大下標(biāo) */ if (*elenum=arrsize-1) return 0; /* 表已滿，無(wú)法插入 */ else i=*elenum; while (i=0 i-; Ai+1=x; /* 找到的位置是插入位的下一位 */ (*elenum)+; return 1; /* 插入成功 */ O(n) 4 / 27 第三章 棧和隊(duì)列 一 . 填空題 1. 設(shè)有一個(gè)空棧，棧頂指針為 1000H ，現(xiàn)有輸入序列為 1. 2. 3. 4. 5 ，經(jīng)過 push ，

8、push ， pop ， push ， pop ，push ，push 后，輸出序列是 23 ，棧頂指針為 1003H 。 2. 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是 順序棧 、 鏈棧 ；其判定?？盏臈l件分別是 TOP=-1 、 TOP=NULL ，判定棧滿的條件分別是 TOP= 數(shù)組長(zhǎng)度 、存儲(chǔ)空間滿 3. 棧 可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 4. 表達(dá)式 a*(b+c)-d 的后綴表達(dá)式是 abc+*d- 。 . 選擇題 1. 若一個(gè)棧的輸入序列是 1，2 ，3，n，輸出序列的第一個(gè)元素是 n，則第 i 個(gè)輸 出元素是 D 。 A 不確定 B n-i C n-i-1 D n-i+1 2. 設(shè)

9、棧 S 和隊(duì)列 Q 的初始狀態(tài)為空，元素 e1. e2. e3. e4. e5. e6 依次通過棧 S，一個(gè) 元素出棧后即進(jìn)入隊(duì)列 Q，若 6 個(gè)元素出隊(duì)的順序是 e2. e4. e3. e6. e5. e1 ，則棧 S 的 容量至少應(yīng)該是 C 。 A 6 B 4 C 3 D 2 3. 一個(gè)棧的入棧序列是 1，2， 3，4，5，則棧的不可能的輸出序列是C 。 A 54321 B 45321 C 43512 D 12345 三 . 判斷題 1. 有 n 個(gè)元素依次進(jìn)棧，則出棧序列有 (n-1)/2 種。 F 2. ?？梢宰鳛閷?shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 T 3. 在棧滿的情況下不能做進(jìn)棧操作，否

10、則將產(chǎn)生 “上溢 ”。 T 4. 在循環(huán)隊(duì)列中， front 指向隊(duì)頭元素的前一個(gè)位置， rear 指向隊(duì)尾元素的位置，則隊(duì) 滿的條件是 front=rear 。 F 四 . 簡(jiǎn)答題 1. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)?A，B， C， D， E，能否得到如下出棧序列，若能， 請(qǐng)寫出操作序列，若不能，請(qǐng)說明原因。 C， E，A，B，D C， B，A，D，E 不能，因?yàn)樵?C、 E出棧后， A 一定在棧中，而且在 B的下面，不可能先于 B 出棧 可以，設(shè)為進(jìn)棧操作，為入棧操作，則其操作序列為 IIIOOOIOIO 。 2. 在操作序列 push(1). push(2). pop. push(5).

11、 push(7). pop. push(6)之后，棧頂元素和 5 / 27棧底元素分別是什么？( push(k) 表示 k 入棧， pop 表示棧頂元素出棧。 ) 棧頂元素為 6 ，棧底元素為 1 。 3. 在操作序列 EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9) 之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？( EnQueue(k) 表示整 數(shù) k 入隊(duì)， DeQueue 表示隊(duì)頭元素出隊(duì)) 。 隊(duì)頭元素為 5 ，隊(duì)尾元素為 9 。 4. 簡(jiǎn)述以下算法的功能(棧的元素類型 SElemType 為

12、 int )。 (1) status algo1(Stack S,int e) Stack T; int d; InitStack(T); while(!StackEmpty(S) Pop(S,d); if(d!=e) Push(T,d); while(!StackEmpty(T) Pop(T,d); Push(S,d); /S 中如果存在 e，則刪除它。 (2) void algo2(Queue int d; InitStack(S); while(!QueueEmpty(Q) DeQueue(Q, d); Push(S, d); while(!StackEmpty(S) Pop(S, d)

13、; EnQueue(Q, d); /隊(duì)列逆置 五 . 算法設(shè)計(jì) 1. 試寫一個(gè)判別表達(dá)式中開、閉括號(hào)是否配對(duì)出現(xiàn)的算法 ElemType x; while(ai) switch(ai) case (: Push(s,ai); BOOL BracketCorrespondency(char a) int i=0; Stack s; InitStack(s); 6 / 27 break; case : Push(s,ai); break; case ): GetTop(s,x); if(x=() Pop(s,x); else return FALSE; break; case : GetTop(s

14、,x); 2. 假設(shè)稱正讀和反讀都相同的字符序列為 if(x=) Pop(s,x); else return FALSE; break; default: break; i+; if(s.size!=0) return FALSE; return TRUE; 回文 ”，例如， abba和 abcba是回文， abcde 和ababab則不是回文。 試寫一個(gè)算法判別讀入的一個(gè)以 為結(jié)束符的字符序列是否是 “回文”。 Status SymmetryString(char* p) Queue q; if(!InitQueue(q) return 0; Stack s; InitStack(s); E

15、lemType e1,e2; while(*p) Push(s,*p); EnQueue(q,*p); p+; while(!StackEmpty(s) Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; return OK; 7 / 27 第四章串 一. 填空題 1. 不包含任何字符(長(zhǎng)度為 0)的串稱為空串；由一個(gè)或多個(gè)空格(僅由空格符) 組成的串 稱為空白串。 2. 設(shè) S=“ A;/document/Mary.doc ，”則 strlen(s)= 20 , “的/字”符定位的位置為 3 。 3. 若 n 為主串長(zhǎng)， m 為子串長(zhǎng)，則串的

16、經(jīng)典模式匹配算法最壞的情況下需要比較字符 的總次數(shù)為 (n-m+1)*m 。 二. 選擇題 1. 串是一種特殊的線性表，其特殊性體現(xiàn)在： ( B ) A 可以順序存儲(chǔ)B 數(shù)據(jù)元素是一個(gè)字符 C 可以鏈?zhǔn)酱鎯?chǔ)D 數(shù)據(jù)元素可以是多個(gè)字符 2. 設(shè)有兩個(gè)串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱作： ( B ) A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng) 3. 設(shè)串 s1=ABCDEFG，s2=PQRST，函數(shù) con(x,y) 返回 x 和 y 串的連接串， subs(s, i, j) 返回串 s 的從序號(hào) i 開始的 j 個(gè)字符組成的子串， len(s)返回串 s 的長(zhǎng)度，則

17、con(subs(s1, 2, len(s2), subs(s1, len(s2), 2) 的結(jié)果串是： ( D ) A BCDEF B BCDEFG C BCPQRST D BCDEFEF 4. 若串 S=” software ，”其子串的數(shù)目是( B )。 A 8 B 37 C 36 D 9 三. 計(jì)算題 1. 設(shè)s=I AM A STUDENT, t= GOOD , q= WORK求ER：, 1)Replace(s, STUDENT ,q) 2)Concat(t,SubString(s,7,8) 1、 Replace(s, STUDENT ,q) I AM A WORKER2、因?yàn)?Su

18、bString(s,7,8) STUDENT Concat(t,SubString(s,7,8) GOODSTUDENT 四. 算法設(shè)計(jì) 1. 利用 C 的庫(kù)函數(shù) strlen, strcpy(或strncpy )寫一個(gè)算法 void StrDelete(char *S,int t,int m) ，刪除串 S 中從位置 i 開始的連續(xù)的 m 個(gè)字符。若 i strlen(S，) 則沒有字符被刪除； 若 i+mstrlen(S) ，則將 S 中從位置 i 開始直至末尾的字符均被刪去。 提示： strlen 是求串長(zhǎng) (length) 函數(shù)： int strlen(char s); /求串的長(zhǎng)度

19、strcpy 是串復(fù)制 (copy) 函數(shù)： char *strcpy(char to,char from); / 該函數(shù)將串 from 復(fù)制到 串 to 中，并且返回一個(gè)指向串 to 的開始處的指針。 8 / 27 void StrDelete(char *S, int i ,int m) / 串刪除 char TempMaxsize;/ 定義一個(gè)臨時(shí)串 if(i+m=strlen(S)/ 把位置 i 的元素置為 0 ，表示串結(jié)束 9 / 27 第五章 數(shù)組和廣義表 一 . 填空 1. 假設(shè)有二維數(shù)組 A68，每個(gè)元素用相鄰的 6 個(gè)字節(jié)存儲(chǔ)， 存儲(chǔ)器按字節(jié)編址。 已知 A 的起始存儲(chǔ)位置(

20、基地址)為 1000 ，則數(shù)組 A 的體積(存儲(chǔ)量)為 288 ；末尾元素 A57 的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素 A14 的第一個(gè)字節(jié)地址為 1072； 若按列存儲(chǔ)時(shí)，元素 A47 的第一個(gè)字節(jié)地址為 1276 。 2. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)， 分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。 3. 廣義表(a), (b),c),(d) 的長(zhǎng)度是 3 ，深度是 4 ，表頭是 (a) ，表尾是 (b),c),(d) 4. 已知廣義表 LS=(a ，(b，c，d)，e) ，用 Head 和 Tail 函數(shù)取出 LS 中原子

21、 b 的運(yùn)算是 Head(Head(Tail(LS) ) 。 . 選擇題 1. 假設(shè)有 60 行 70 列的二維數(shù)組 a1 60, 1 70以 列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為 10000 ，每個(gè)元素占 2 個(gè)存儲(chǔ)單元，那么第 32 行第 58 列的元素 a32,58 的存儲(chǔ)地址為 ( A ) 。(無(wú)第 0 行第 0 列元素) A 16902 B 16904 C 14454 D 答案 A, B, C 均不對(duì) 2. 設(shè)矩陣 A 是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組 B 1, n(n-1)/2 中，下三角部分中任一元素 ai,j(i j)在, 一維數(shù)組 B 中下標(biāo) k 的

22、值是：( B ) A i(i-1)/2+j-1B i(i-1)/2+jC i(i+1)/2+j-1 Di(i+1)/2+j 3. 一個(gè) n*n 的對(duì)稱矩陣， 用壓縮存儲(chǔ)方法處理其對(duì)稱性質(zhì)后存儲(chǔ)， 則其容量為： ( C )。 A n*n B n*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2 三 . 計(jì)算題 1. 設(shè)有一個(gè)二維數(shù)組 Amn ，假設(shè) A00存放位置在 644 ， A22 存放位置在 676， 每個(gè)元素占一個(gè)空間，問 A33 存放在什么位置？寫出計(jì)算過程。 (676-644)/1=32 A22 的地址相對(duì) A00 偏移量為 32，則A33 相較于 A00 的偏移量為

23、32*3/2=48 A33 地址為 48+644=692 2. 設(shè) A99 是一個(gè) 10*10 對(duì)稱矩陣，采用壓縮存儲(chǔ)方式存儲(chǔ)其下三角部分，已知每個(gè) 元素占用兩個(gè)存儲(chǔ)單元，其第一個(gè)元素 A00 的存儲(chǔ)位置在 1000 ，求下面問題的計(jì)算 過程及結(jié)果： 給出 A45 的存儲(chǔ)位置。 A45 是上三角部分，所以存在 A 5 4 10 / 27若以行序?yàn)橹餍颍瑒t地址為 1000+2 (5(1+5)/ 2+4 )=1036 若以列序?yàn)橹餍?，則地址為 1000+2 (4(10+7 )/ 2+5 )=1062 給出存儲(chǔ)位置為 1080 的元素下標(biāo)。 i(i+1)/2+j 或 j(10+10-j+1)/2+i

24、=40 得 i=9，j=4 或 i=8 j=5 ，A 8 5 或 A 9 4 3. 一個(gè)稀疏矩陣如圖所示，則對(duì)應(yīng)的三元組線性表是什么？其對(duì)應(yīng)的十字鏈表是什 么？ 0 0 2 0 3 0 0 0 0 0 -1 5 0 0 0 0 4. 下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣 6 4 6 1 2 2 2 1 12 (1) 3 1 3 4 4 4 5 3 6 6 1 16 0 2 0 0 12 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 四 . 算法設(shè)計(jì) 1. 設(shè)計(jì)一個(gè)算法，計(jì)算一個(gè)三元組表表示的稀疏矩陣的對(duì)角線元素之和 11 / 27 2. 若在

25、矩陣 A 中存在一個(gè)元素 ai,j( 0 i -1n， 0 j -m1)，該元素是第 i 行元素中最小 值且又是第 j 列元素中最大值，則稱此元素為該矩陣的一個(gè)鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ) 矩陣 A，試設(shè)計(jì)一個(gè)求該矩陣所有鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度 void Saddle( int Amn) /A int for 是 m*n 的矩陣 , 本算法求矩陣 A 中的馬鞍點(diǎn) . maxn=0, /max minm=0, /min i, j; (i=0;im;i+) / 數(shù)組存放各列最大值元素的行號(hào) 數(shù)組存放各行最小值元素的列號(hào) 選各行最小值元素和各列最大值元素 for (j=0;jn;j+)

26、 if (AmaxjjAij) mini=j; / for (i=0;i0 ）個(gè) 互不相交 的集合，每個(gè)集 合都是根結(jié)點(diǎn)的子樹。 2. 一棵二叉樹的第 i（i ）1層最多有 2i-1 個(gè)結(jié)點(diǎn)；一棵有 n（n0 ）個(gè)結(jié)點(diǎn)的滿二叉樹 共有 （n+1）/2 個(gè)葉子結(jié)點(diǎn)和 （n-1）/2 個(gè)非終端結(jié)點(diǎn)。 3. 設(shè)深度為 k 的二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的 最大值是 2k-1 ，最小值是 2k-1 。 4. 深度為 k 的二叉樹中，所含葉子的個(gè)數(shù)最多為 2k-1 。 5. 在順序存儲(chǔ)的二叉樹中編號(hào)為 i和 j的兩個(gè)結(jié)點(diǎn)處在同一層的條件為： 二 . 選擇題 1. 前

27、序遍歷和中序遍歷結(jié)果相同的二叉樹是（ D ）。 A 根結(jié)點(diǎn)無(wú)左孩子的二叉樹B 根結(jié)點(diǎn)無(wú)右孩子的二叉樹 C 所有結(jié)點(diǎn)只有左子樹的二叉樹D 所有結(jié)點(diǎn)只有右子樹的二叉樹 2. 序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組 A1 An 中，結(jié)點(diǎn) Ai 若有左子樹，則左子樹的根結(jié)點(diǎn)是（ D ）。 A A2i-1 B A2i+1 C Ai/2 D A2i 3. 完全二叉樹中的任一結(jié)點(diǎn)， 若其右分支下的子孫的最大層次為 h ，則其左分支下的子 孫的最大層次為（ C ）。 A h B h+1 C h 或 h+1 D 任意 4. 在線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)的充要條件為（ C ）。 A 左線索標(biāo)志為

28、 0，右線索標(biāo)志為 1 B 左線索標(biāo)志為 1 ，右線索標(biāo)志為 0 C 左 . 右線索標(biāo)志均為 0 D 左 . 右線索標(biāo)志均為 1 5. 由權(quán)值為 3, 8, 6, 2, 5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，其帶權(quán)路徑長(zhǎng)度為（ C ）。 A 24 B 48 C 53 D 72 1. 已知二叉樹的中序和后序序列分別為 三 . 簡(jiǎn)答題 CBEDAFIGH 和 CEDBIFHGA ，請(qǐng)構(gòu)造出此二 叉樹，并寫出此樹的后序遍歷序列 13 / 27 3. 圖 5-17 所示的二叉樹轉(zhuǎn)換為樹或森林 4. 已知某字符串 S 中共有 符A,B,C,D,E,F,G,H ，分別 次. 4 次和 9 次。 出現(xiàn) 2 次.

29、1 次. 4 次. 5 1）試構(gòu)造出哈夫曼編碼樹， 2）問該字符串的編碼至少 并對(duì)每個(gè)字符進(jìn)行編碼 有多少位 E 2. 將下圖所示的樹轉(zhuǎn)換為二叉樹， A:00000 B:00001 C:100 D:001 E:11 F:0001 G:101 H:01 其帶權(quán)路徑長(zhǎng)度 =2 5+1 5+3 4+5 3+9 2+4 3+4 3+7 2=98 ，所以，該字符串的編 碼長(zhǎng)度至少為 98 位。 四 . 算法設(shè)計(jì) 1. 設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù) 14 / 27 2. 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點(diǎn) x 的雙親 3. 編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹。 15 / 27 第七章 圖 一

30、. 填空題 1. 設(shè)無(wú)向圖 G 中頂點(diǎn)數(shù)為 n，則圖 G 至少有 0 條邊，至多有 n(n-1)/2 條邊；若 G 為有向圖，則至少有 0 條邊，至多有 n(n-1) 條邊。 2. 任何連通圖的連通分量只有一個(gè)，即是 它自身 3. 若一個(gè)有向圖由鄰接矩陣表示，則計(jì)算第 j 個(gè)頂點(diǎn)入度的方法是 求矩陣第 j列元素 之和 4. 圖的深度優(yōu)先遍歷類似于樹的 先根 遍歷，廣度優(yōu)先遍歷類似于樹的 層序 遍歷。 5. 對(duì)于含有 n 個(gè)頂點(diǎn) e 條邊的連通圖， 利用 Prim 算法求最小生成樹的時(shí)間復(fù)雜度為 (n2)，利用 Kruskal 算法求最小生成樹的時(shí)間復(fù)雜度為 (elog2e) 。 二 . 選擇題

31、 1. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的( C )倍。 A 1/2 B 1 C 2 D 4 2. n 個(gè)頂點(diǎn)的強(qiáng)連通圖至少有( A )條邊。 A n B n+1 C n-1 D n (n-1) 3. 含 n 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過( C )。 A 1B n/2 C n-1 D n 4. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖用鄰接矩陣存儲(chǔ)，則該矩陣的大小是( D )。 A nB (n-1) 2C n-1D n 2 5. 設(shè)無(wú)向圖 G=(V, E)和G =(V, E ) ，如果G 是G的生成樹，則下面的說法中錯(cuò)誤的 是( B )。 A G 為 G 的子圖B

32、 G 為 G 的連通分量 C G 為 G 的極小連通子圖且 V= VD G 是 G 的一個(gè)無(wú)環(huán)子圖 6. 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用( D )。 A 求關(guān)鍵路徑的方法B 求最短路徑的方法 C 廣度優(yōu)先遍歷算法D 深度優(yōu)先遍歷算法 7. 下面關(guān)于工程計(jì)劃的 AOE 網(wǎng)的敘述中，不正確的是( B ) A 關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間 B 任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成 C 所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成 D 某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完 三 . 計(jì)算題 1. 已知一個(gè)連通圖如圖所示，試給出

33、圖的鄰接矩陣和鄰接表 16 / 27 存儲(chǔ)示意圖，若從頂點(diǎn) 優(yōu)先遍歷的頂點(diǎn)序列。 v1 出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度 鄰接矩陣表示如下： v5 v4 v6 v6 v3 v5 鄰接表表示如右： 深度優(yōu)先遍歷序列為： 廣度優(yōu)先遍歷序列為： 的鄰接表如下圖所示，分別寫出從頂點(diǎn) 1 出發(fā)的深度遍歷和廣度遍歷 2. 已知無(wú)向圖 G 序列，并畫出相應(yīng)的生成樹。 深度優(yōu)先遍歷序列為： 5，6 對(duì)應(yīng)的生成樹為： 廣度優(yōu)先遍歷序列為： 5，6 對(duì)應(yīng)的生成樹為： Prim 算法和 Kruskal 1，2，3，4， 1，2，4，3， 算法求最小生成樹。 圖所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別按 3.

34、 為： v0 v1 v5 v2 v3 v6 v4 拓?fù)?v0 v1 v5 v2 v6 v3 v4 v0 v1 v5 v6 v2 v3 v4 其他各頂點(diǎn)的最短路徑。 從源點(diǎn) v1 到其他各頂點(diǎn)的最短路徑如下表所示。 源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 5. 已知一個(gè) AOV 網(wǎng)如下圖所示，寫出所有拓?fù)湫蛄?四 . 算法設(shè)計(jì) 1. 設(shè)計(jì)算法，將一個(gè)無(wú)向圖的鄰接表轉(zhuǎn)換成鄰接矩陣。 2. 設(shè)計(jì)算法， 計(jì)算圖中出 度為零的頂

35、點(diǎn)個(gè)數(shù)。 3. 已知一個(gè)有向圖的鄰 接表，編寫算法建立其逆 鄰接表 18 / 27 19 / 27 第九章 查找 一 . 填空題 1. 順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為 順序和鏈?zhǔn)酱鎯?chǔ) 的線性表，而折半查找技術(shù)適用 于存儲(chǔ)結(jié)構(gòu)為 順序存儲(chǔ) 的線性表，并且表中的元素必須是 按關(guān)鍵碼有序 。 2. 折半查找有序表（ 4，6，12，20，28，38，50，70，88 ，100 ），若查找表中元素 20，它將依次與表中元素 28，6，12 ，20 比較大小。 3. 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無(wú)關(guān)的查找方法是 散列（哈希） 查找 。 4. 為了能有效地應(yīng)用哈希查找技術(shù)，必須解決的兩個(gè)問題

36、是 構(gòu)造散列函數(shù) 和 解決 沖突。 5. 有一個(gè)表長(zhǎng)為 m 的散列表，初始狀態(tài)為空，現(xiàn)將 n（nlchild if(T-datadata; if(T-rchild return flag; /Is_BSTree 22 / 27 第十章 排序 一 . 填空題 1. 排序的方法有很多種， 插入排序 法從未排序序列中依次取出元素，與已排序序列 中的元素作比較，將其放入已排序序列的正確位置上。 選擇排序 法從未排序序列 中挑選元素， 并將其依次放入已排序序列的一端。 交換排序是對(duì)序列中元素進(jìn)行一系列 比較，當(dāng)被比較的兩元素為逆序時(shí)，進(jìn)行交換； 冒泡排序 和 快速排序 是基于這 類方法的兩種排序方法，

37、而 快速排序是比冒泡排序效率更高的方法； 堆排序 法是 基于選擇排序的一種方法，是完全二叉樹結(jié)構(gòu)的一個(gè)重要應(yīng)用。 2. 一組記錄（ 54, 38, 96, 23, 15, 72, 60, 45, 83 ）進(jìn)行直接插入排序，當(dāng)把第 7 個(gè)記錄 60 插入到有序表時(shí)，為尋找插入位置需比較 3 次。 3. 對(duì) n 個(gè)待排序記錄序列進(jìn)行快速排序，所需要的最好時(shí)間是 O（nlog2n） ，最壞時(shí)間是 2 O（n 2） . 選擇題 1. 下列序列中，（ A）是執(zhí)行第一趟快速排序的結(jié)果。 A da ， ax ， eb，de，bb ff ha ，gc C gc ， ax ， eb，cd，bb ff da ，ha B c