1、緒論5. 選擇題：CCBDCA6. 試分析下面各程序段的時間復雜度。(1) O(1)(2) O( m*n)(3) O( n2)(4) O (logj)(5) 因為x+共執行了 n-1+ n-2+, +1= n(n-1)/2，所以執行時間為 0 ( n2)(6) O( ,n)線性表1選擇題babadbcabdcddac2算法設計題(6) 設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。ElemType Max (Li nkList L )if(L->n ext=NULL) return NULL;pmax=L-> next; /假定第一個結點中數據具有最大值p=L->n

2、ext->n ext;while(p != NULL )/如果下一個結點存在if(p->data > pmax->data) pmax=p; p=p->n ext; return pmax->data;(7) 設計一個算法，通過遍歷一趟，將鏈表中所有結點的鏈接方向逆轉，仍利用原表 的存儲空間。void in verse(L in kList &L) /逆置帶頭結點的單鏈表Lp=L->n ext; L->n ext=NULL;while ( p) q=p->next; / q指向*p的后繼p->n ext=L->n ext

3、;L-> next=p; / *p插入在頭結點之后p = q;（ 10）已知長度為 n 的線性表 A 采用順序存儲結構，請寫一時間復雜度為 O（n） 、空間 復雜度為 O（1） 的算法，該算法刪除線性表中所有值為 item 的數據元素。 題目分析 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i 個元素，第 i+1 至第 n 個元素要依次前移） 。本題要求刪除線性表中所有值為 item 的數據 元素，并未要求元素間的相對位置不變。因此可以考慮設頭尾兩個指針（i=1 ， j=n ），從兩端向中間移動， 凡遇到值 item 的數據元素時， 直接將右端元素左移至值為 item

4、 的數據元素void Delete （ ElemType A ， int n ）/ A是有n個元素的一維數組，本算法刪除A中所有值為item的元素。i=1 ; j=n ;/設置數組低、高端指針（下標） 。while （ i<j ） while （ i<j && Ai!=item ） i+ ;/若值不為 item ，左移指針。if （ i<j ） while （ i<j && Aj=item ） j- ;/若右端元素值為 item ，指針左移 if （ i<j ） Ai+=Aj-;算法討論因元素只掃描一趟，算法時間復雜度為O （n）。

5、刪除元素未使用其它輔助空間，最后線性表中的元素個數是 j。第 3 章 棧和隊列1 選擇題CCDAADABCDDDBCB2.算法設計題（2）回文是指正讀反讀均相同的字符序列，如“ abba"和“ abdba"均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。（提示：將一半字符入棧 ）根據提示，算法可設計為：/ 以下為順序棧的存儲結構定義#define StackSize 100 /假定預分配的?？臻g最多為 100 個元素typedef char DataType;/假定棧元素的數據類型為字符typedef structDataType dataSta

6、ckSize;int top;SeqStack;int IsHuiwen( char *t)/ 判斷 t 字符向量是否為回文，若是，返回1，否則返回 0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量長度for ( i=0; i<len/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個字符與相應字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回 0else

7、 i+;return 1 ; / 比較完畢均相等則返回 1(7)假設以數組 Qm存放循環隊列中的元素，同時設置一個標志tag,以tag = 0和 tag = 1來區別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態為 空”還是 滿”試編 寫與此結構相應的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h隊列類定義#include <assert.h>template <class Type> classQueue /循環隊列的類定義public:Queue ( int=10 );Queue ( ) delete Q; void EnQueue

8、 ( Type& item );Type DeQueue ( );Type GetFront ( );void MakeEmpty ( ) front = rear = tag = 0;/ 置空隊列int IsEmpty ( ) const return front = rear && tag = 0; /判隊列空否int IsFull ( ) const return front = rear && tag = 1; / 判隊列滿否private:int rear, front, tag; Type *Q;/隊尾指針、隊頭指針和隊滿標志 /存放隊列元素

9、的數組int m;/隊列最大可容納元素個數構造函數template <class Type>Queue<Type>: Queue ( intsz ) : rear (0), front (0), tag(0), m (sz) /建立一個最大具有 m 個元素的空隊列。Q = new Type m ;/ 創建隊列空間assert ( Q != 0 );/斷言: 動態存儲分配成功與否插入函數template<class Type>void Queue<Type> : EnQueue ( Type &item ) assert ( ! IsFul

10、l ( ) );rear = ( rear + 1 ) % m;Qrear = item;tag = 1;/判隊列是否不滿，滿則出錯處理/隊尾位置進 1, 隊尾指針指示實際隊尾位置 /進隊列/標志改 1，表示隊列不空/判斷隊列是否不空，空則出錯處理/ 隊頭位置進 1, 隊頭指針指示實際隊頭的前一位置 /標志改 0, 表示棧不滿 /返回原隊頭元素的值/判斷隊列是否不空，空則出錯處理/返回隊頭元素的值刪除函數template<class Type>Type Queue<Type> : DeQueue ( ) assert ( ! IsEmpty ( ) ); front =

11、 ( front + 1 ) % m; tag = 0;return Qfront;讀取隊頭元素函數template<class Type>Type Queue<Type> : GetFront ( ) assert ( ! IsEmpty ( ) ); return Q(front + 1) % m;第 4 章 串、數組和廣義表1選擇題BBCABBBCBBABDCBC2.綜合應用題（ 1）已知模式串 t= abcaabbabcab '寫出用 KMP 法求得的每個字符對應的 next 和 nextval 函數值。模式串 t 的 next 和 nextval 值如

12、下：j12345678910 11 12t串abcaabbab cabn extj011122312345n extvalj011021301105(3) 數組A中，每個元素Ai,j的長度均為32個二進位，行下標從-1到9，列下標從1到11,從首地址S開始連續存放主存儲器中，主存儲器字長為16位。求： 存放該數組所需多少單元？ 存放數組第4列所有元素至少需多少單元？ 數組按行存放時，元素A7,4的起始地址是多少？ 數組按列存放時，元素A4,7的起始地址是多少？每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。(1) 242(2) 22(3) S+182(4)

13、 s+142 請將香蕉banana用工具H( ) Head( )，T( ) Tail() 從L中取出。L=(apple,(ora nge,(strawberry,(ba nan a),peach),pear)H ( H( T( H( T( H( T( L)(5)寫一個算法統計在輸入字符串中各個不同字符出現的頻度并將結果存入文件(字 符串中的合法字符為A-Z這26個字母和0-9這10個數字)。void Count ()/統計輸入字符串中數字字符和字母字符的個數。int i , num36;char ch ;for (i = 0; i<36 ; i+ ) numi =0; / 初始化whil

14、e (ch = getchar () != #')/ #'表示輸入字符串結束。if (' 0' <=ch<= '9') i=ch 48;numi+ ；/ 數字字符else if (' A <=ch<= ' Z) i=ch-65+10;numi+ ； / 字母字符for (i=0 ; i<10 ; i+ ) /輸出數字字符的個數printf("數字 d 的個數=% dn ”，i , numi);for (i = 10; i<36 ; i+ ) / 求出字母字符的個數printf(&quo

15、t;字母字符 c 的個數=% dn ”，i + 55, n umi); /算法結束。第5章樹和二叉樹1 選擇題ADDCACCBDCCCACC2應用題(2)設一棵二叉樹的先序序列：A B D F C E G H ，中序序列：B F D A G E H C 畫出這棵二叉樹。 畫出這棵二叉樹的后序線索樹。 將這棵二叉樹轉換成對應的樹(或森林)。 (2)0.07，(3)假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設計赫夫曼編碼。 試設計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案

16、的優缺點。解：方案1哈夫曼編碼 先將概率放大100倍，以方便構造哈夫曼樹。w=7,19,2,6,32,3,21,10，按哈夫曼規則:【(2,3), 6, (7,10)】，”19, 21, 32字母對應出現1編號編碼頻率111000.072000.193111100.02411100.065100.32方案比較:字母編號對應編碼出現頻率10000.0720010.1930100.0240110.0651000.32610003的WPL方案12(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案 2 的 WPL

17、= 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結論：哈夫曼編碼優于等長二進制編碼3算法設計題以二叉鏈表作為二叉樹的存儲結構，編寫以下算法：(1) 統計二叉樹的葉結點個數。int LeafNodeCou nt(BiTree T)if(T=NULL)return 0;/如果是空樹，則葉子結點個數為0else if(T->lchild=NULL&& T->rchild=NULL)return 1; /判斷該結點是否是葉子結點(左孩子右孩子都為空)，若是則返回1elsereturn LeafNodeCou nt(T->lc

18、hild)+LeafNodeCou nt(T->rchild);(3)交換二叉樹每個結點的左孩子和右孩子。void Cha ngeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&& T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp;Cha ngeLR(T->lchild);Cha ngeLR(T->rchild);1 選擇題CBBBCBABAADCCDDB2應用題(1

19、)已知如圖6.27所示的有向圖，請給出: 每個頂點的入度和出度； 鄰接矩陣； 鄰接表；逆鄰接表。1235113f0223)J00000'10 0 10 0 01000C01011100000J10010.逆命接表邨接表圖6.28 無(2) 已知如圖6.28所示的無向網，請給出: 鄰接矩陣； 鄰接表； 最小生成樹5 456 :7 5:55 53d5d5e7f3g2h6g6c3c5b5c5d7e3f2d4b4a4a3b5b9d6d5c5abcdefgh先生成樹和廣度優先生成樹。深度優先生成樹)01IJo000001000100D(4) 有向網如圖6.29所示，試用迪杰斯特拉算法求出從頂點a

20、到其他各頂點間的最短路徑，完成表6.9。圖6.29鄰接矩陣(3) 已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點1出發進行遍歷所得的深度優廣度優先生成樹V終點i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,f)gcoco16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e

21、,d,g,b第7章查找i選擇題CDCABCCCDCBCADA2應用題(1)假定對有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)進行折半查找, 試回答下列問題： 畫出描述折半查找過程的判定樹； 若查找元素54,需依次與哪些元素比較？ 若查找元素90,需依次與哪些元素比較？ 假定每個元素的查找概率相等，求查找成功時的平均查找長度。 先畫出判定樹如下(注： mid=_(1+12)/2=6)： 查找元素 54,需依次與 30, 63, 42, 54元素比較； 查找元素 90,需依次與 30, 63,87, 95元素比較； 求ASL之前，需要統計每個元素

22、的查找次數。判定樹的前3層共查找1 + 2X 2+ 4X 3=17次；但最后一層未滿，不能用8X 4，只能用5X 4=20次，所以 ASL = 1/12 (17 + 20)= 37/12 3.08(2)在一棵空的二叉排序樹中依次插入關鍵字序列為12, 7, 17, 11, 16, 2, 13, 9, 21,4,請畫出所得到的二叉排序樹。12 X/172 丿1 214913驗算方法：用中序遍歷應得到排序結果：2,4,7,9,11,12,13,16,17 , 21(5) 設哈希表的地址范圍為 017,哈希函數為：H ( key) =key%16。用線性探測法 處理沖突，輸入關鍵字序列：(10, 2

23、4, 32, 17, 31, 30, 46, 47, 40, 63, 49),構造哈希表，試回答下列問題： 畫出哈希表的示意圖； 若查找關鍵字63，需要依次與哪些關鍵字進行比較？ 若查找關鍵字60,需要依次與哪些關鍵字比較？ 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次! 查找60,首先要與H(60)=60%16=12號單元內容

24、比較， 但因為12號單元為空(應當有空標 記)，所以應當只比較這一次即可。 對于黑色數據元素，各比較1次；共6次；對紅色元素則各不相同，要統計移位的位數?！?3”需要6次，“49”需要3次，“40”需要2次，“ 46”需要3次，“ 47”需要3次，所以 ASL=1/11 (6+ 2+ 3 X 3+6 )= 23/11(6)設有一組關鍵字 (9, 01 , 23, 14, 55, 20, 84, 27),采用哈希函數：H( key) =key %7 , 表長為10,用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構造哈希表，并 計算查找成功的平均查找長度。散列地址0123456789關鍵字

25、140192384275520比較次數11123412平均查找長度： AS%c= (1 + 1+1+2+3+4+1+2) /8=15/8以關鍵字 27 為例：H(27) =27%7=6(沖突)H 1=(6+1) %10=7(沖突)H2= (6+22) %10=0(沖突) H 3= (6+33) %10=5 所以比較了 4 次。第8章排序1 選擇題CDBDCBCDBCBCCCA2應用題(1)設待排序的關鍵字序列為 12 , 2, 16, 30, 28, 10, 16* , 20, 6, 18，試分別寫 出使用以下排序方法，每趟排序結束后關鍵字序列的狀態。 直接插入排序 折半插入排序 希爾排序(增

26、量選取 5, 3, 1) 冒泡排序 快速排序 簡單選擇排序 堆排序 二路歸并排序直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折半插入排序排序過程同布爾排序（增量選取5,3, 1)102166181216*203028 （增量選取5)621210181616*203028 （增量選取3)2610121616*182C)2830（增量選取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序1262 1012283016* 20 16 1862 61012283016* 20 16 18