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

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

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

4、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）。刪除元素未使用其它輔助空間，最后線性表中的元素個數是j。第3章 棧和隊列1選擇題CCDAADABCDDDBCB2.算法設計題（2）回文是指正讀反讀均相同的字符序列，如“abba

5、”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 根據提示，算法可設計為：/以下為順序棧的存儲結構定義#define StackSize 100 /假定預分配的棧空間最多為100個元素typedef char DataType;/假定棧元素的數據類型為字符typedef structDataType dataStackSize;int top;SeqStack; int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;c

6、har 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 i+; return 1 ; / 比較完畢均相等則返回 1（7）假設以數組Qm存放循環隊列中的元素, 同時設置一個標志tag，以tag = 0和tag = 1來區別在隊頭指針(fr

7、ont)和隊尾指針(rear)相等時，隊列狀態為“空”還是“滿”。試編寫與此結構相應的插入(enqueue)和刪除(dlqueue)算法。【解答】循環隊列類定義#include <assert.h>template <class Type> class Queue /循環隊列的類定義public: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = re

8、ar = 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;/存放隊列元素的數組 int m;/隊列最大可容納元素個數構造函數template <class Type>Queue<Type>: Queue ( int

9、 sz ) : rear (0), front (0), tag(0), m (sz) /建立一個最大具有m個元素的空隊列。 Q = new Typem;/創建隊列空間 assert ( Q != 0 );/斷言: 動態存儲分配成功與否插入函數template<class Type> void Queue<Type> : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判隊列是否不滿，滿則出錯處理rear = ( rear + 1 ) % m;/隊尾位置進1, 隊尾指針指示實際隊尾位置Qrear = item;/進

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

11、sert ( ! IsEmpty ( ) );/判斷隊列是否不空，空則出錯處理return Q(front + 1) % m;/返回隊頭元素的值第4章 串、數組和廣義表1選擇題BBCAB BBCBB ABDCB C2.綜合應用題（1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個字符對應的next和nextval函數值。模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0

12、 5（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）s+142(4)請將香蕉banana用工具 H( )Head( )，T( )Tail( )從L中取出。L=(apple,(orange,(stra

13、wberry,(banana),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（i0；i<36；i+）numi；/ 初始化while（chgetchar（）!=#） /#表示輸入字符串結束。if（0<=ch<=9）i=ch48;numi+； / 數字字符 elseif（A<=ch<=Z）i=ch-65+10;

14、numi+；/ 字母字符for（i=0；i<10；i+） / 輸出數字字符的個數printf（“數字d的個數dn”，i，numi）；for（i10；i<36；i+）/ 求出字母字符的個數printf（“字母字符c的個數dn”，i55，numi）；/ 算法結束。第5章 樹和二叉樹1選擇題ADDCA CCBDC CCACC2應用題（2）設一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。ABMFD(3)CEMHG將這棵二叉樹轉換成對應的樹（或森林）。    

15、60;     (1) (2)（3） 假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設計赫夫曼編碼。 試設計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案的優缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12

16、 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應編碼出現頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應編碼出現頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(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的WPL3(0

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

18、ld)+LeafNodeCount(T->rchild);（3）交換二叉樹每個結點的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp;ChangeLR(T->lchild);ChangeLR(T->rchild);第6章 圖1選擇題CBBBCBABAADCCDDB2應用題（1）已知

19、如圖6.27所示的有向圖，請給出： 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 （2）已知如圖6.28所示的無向網，請給出： 鄰接矩陣； 鄰接表； 最小生成樹圖6.28 無向網 ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6（3）已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點1出發進行遍歷所得的深度優先生成樹和廣度優先生成樹。（4）有向網如圖6.29所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成表6.9。 圖6.29 鄰接矩陣D終點i=1i=2i=3i=4i=5i=6b15(a

20、,b)15(a,b)15(a,b)15(a,b)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)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(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,d,g,b 第7章 查找1選擇題CDCABCCCDCBCADA2應用題（1）假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題： 畫出描述折半查找過程的判定

21、樹； 若查找元素54，需依次與哪些元素比較？ 若查找元素90，需依次與哪些元素比較？ 假定每個元素的查找概率相等，求查找成功時的平均查找長度。先畫出判定樹如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95查找元素54，需依次與30, 63, 42, 54 元素比較；查找元素90，需依次與30, 63,87, 95元素比較；求ASL之前，需要統計每個元素的查找次數。判定樹的前3層共查找12×24×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL1/12（17

22、20）37/123.08（2）在一棵空的二叉排序樹中依次插入關鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。 127 17 2 11 16 21 4 9 13驗算方法： 用中序遍歷應得到排序結果： 2,4,7,9,11,12,13,16,17，21（5）設哈希表的地址范圍為017，哈希函數為：H（key）=key%16。用線性探測法處理沖突，輸入關鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構造哈希表，試回答下列問題： 畫出哈希表的示意圖； 若查找關鍵字63，需要依次與哪些關鍵字進行比較？ 若查找關鍵字60，需要依次

23、與哪些關鍵字比較？ 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內容比較，但因為12號單元為空（應當有空標記），所以應當只比較這一次即可。對于黑色數據元素，各比較1次；共6次；對紅色元素則各不相同，要統計移位的位數。“63”需要6次，“49”需要3次，“40”需要2次，“46

24、”需要3次，“47”需要3次，所以ASL=1/11（623×3+6）23/11（6）設有一組關鍵字（9，01，23，14，55，20，84，27），采用哈希函數：H（key）=key %7 ，表長為10，用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。散列地址0123456789關鍵字140192384275520  比較次數1112 3 412  平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%1

25、0=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4次。第8章 排序1選擇題CDBDCBCDBCBCCCA2應用題（1）設待排序的關鍵字序列為12，2，16，30，28，10，16*，20，6，18，試分別寫出使用以下排序方法，每趟排序結束后關鍵字序列的狀態。 直接插入排序 折半插入排序 希爾排序（增量選取5，3，1） 冒泡排序 快速排序 簡單選擇排序 堆排序 二路歸并排序直接插入排序2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6

26、18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30 折半插入排序 排序過程同 希爾排序（增量選取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量選取5）6 2 12 10 18 16 16* 20 30 28 （增量選取3）2 6 10 12 16 16* 18 20

27、28 30 （增量選取1） 冒泡排序2 12 16 28 10 16* 20 6 18 30 2 12 16 10 16* 20 6 18 28 30 2 12 10 16 16* 6 18 20 28 30 2 10 12 16 6 16* 18 20 28 30 2 10 12 6 16 16* 18 20 28 30 2 10 6 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 302 6 10 12 16 16* 18 20 28 30 快速排序12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28

28、30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 6 10 12 16* 16 18 20 28 30 16* 2 6 10 12 16* 16 18 20 28 30左子序列遞歸深度為1，右子序列遞歸深度為3 簡單選擇排序2 12 16 30 28 10 16* 20 6 18 2 6 16 30 28 10 16* 20 12 18 2 6 10 30 28 16 16* 20 12 18 2 6 10 12 28 16 16* 20 30 18 2 6 10 12 16 28 16* 20 30 18 2 6 10 12 16 16* 28 20 30 18 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 二路歸并排序2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10