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 != NULL )/如果下一個

2、結點存在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插入在頭結點之后 p = q; （10）已知長度為n的線性表A采用順序存儲結構，請寫一時間復雜度為O(n)、空間復雜度為O(1)的算法，該算法刪除

3、線性表中所有值為item的數據元素。題目分析 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的數據元素，并未要求元素間的相對位置不變。因此可以考慮設頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數據元素時，直接將右端元素左移至值為item的數據元素位置。void Delete（ElemType A ，int n）A是有n個元素的一維數組，本算法刪除A中所有值為item的元素。i=1；j=n；設置數組低、高端指針（下標）。while（ij） while（ij & Ai!=ite

4、m）i+；若值不為item，左移指針。if（ij）while（ij & Aj=item）j-；若右端元素值為item，指針左移if（ij）Ai+=Aj-； 算法討論 因元素只掃描一趟，算法時間復雜度為O（n）。刪除元素未使用其它輔助空間，最后線性表中的元素個數是j。第3章 棧和隊列1選擇題CCDAADABCDDDBCB2.算法設計題（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據提示，算法可設計為：/以下為順序棧的存儲結構定義#define StackSize 100

5、/假定預分配的?？臻g最多為100個元素typedef char DataType;/假定棧元素的數據類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; ilen/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個

6、字符與相應字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1（7）假設以數組Qm存放循環隊列中的元素, 同時設置一個標志tag，以tag= 0和tag = 1來區別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態為“空”還是“滿”。試編寫與此結構相應的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h隊列類定義#include template classQueue /循環隊列的類定義public: Queue (int=10 ); Queue ( )

7、 delete Q;void EnQueue (Type& item );Type DeQueue ();TypeGetFront ( );void MakeEmpty ( ) front = rear = tag = 0;/置空隊列intIsEmpty ( )const return front = rear & tag = 0;/判隊列空否intIsFull ( )const return front = rear & tag = 1;/判隊列滿否private:intrear, front, tag;/隊尾指針、隊頭指針和隊滿標志Type *Q;/存放隊列元素的數組intm;/隊列最大可

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

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

10、素的值第4章 串、數組和廣義表1選擇題BBCABBBCBBABDCBC2.綜合應用題（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 5（3）數組A中，每個元素Ai,j的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首地址S開始連續存放主存儲器中，主存儲器字長為

11、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,(strawberry,(banana),peach),pear)H（H（T（H（T（H（T（L）（5）寫一個算法統計在輸入字符串中各個不同字符出現的頻度并將結果

12、存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數字）。void Count（）/統計輸入字符串中數字字符和字母字符的個數。int i，num36；char ch；for（i0；i36；i+）numi；/ 初始化while（chgetchar（）!=#） /#表示輸入字符串結束。if（0=ch=9）i=ch48;numi+； / 數字字符elseif（A=ch=Z）i=ch-65+10;numi+；/ 字母字符for（i=0；i10；i+） / 輸出數字字符的個數printf（“數字d的個數dn”，i，numi）；for（i10；ilchild=NULL&T-rchild=NU

13、LL)return 1; /判斷該結點是否是葉子結點（左孩子右孩子都為空），若是則返回1elsereturn LeafNodeCount(T-lchild)+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選擇

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

15、i=1i=2i=3i=4i=5i=6b15(a,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）進行折半查找，

16、試回答下列問題：畫出描述折半查找過程的判定樹；若查找元素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層共查找12243=17次；但最后一層未滿，不能用84，只能用54=20次，所以ASL1/12（1720）37/123.08（2）在一

17、棵空的二叉排序樹中依次插入關鍵字序列為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，需要依次與哪些關鍵字比較？ 假定每個關鍵字

18、的查找概率相等，求查找成功時的平均查找長度。畫表如下：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”需要3次，“47”需要3次，所以

19、ASL=1/11（6233+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）%10=7（沖突）H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4

20、次。第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 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30

21、 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 28 30 （增量選取1） 冒泡排序2 12 16 28 10 16*20 6 18 30 2 1

22、2 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 1616* 18 20 28 30 2 10 6 12 1616* 18 20 28 30 2 6 10 12 1616* 18 20 28 302 6 10 12 1616* 18 20 28 30 快速排序126 2 10 12 28 30 16* 20 16 18 62 6 10 12 28 3016* 20 16 18 28 2 6 10 12 18 16 16* 20 2830 182 6 10 12

23、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 1216 30102816 * 206 182 12 16 3010 16* 2028 6 182 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 28 30 堆排序第一步,形成初始大根堆（詳細過程略），第二步做堆排序。1221620103016*286183028161020