1、/課程名稱：數據結構/設計題在數據結構中特指算法設計題試題分類: 第二章線性表/第二節線性表的結構/第一條順序結構命題人：君所屬：工程系題型：設計題1、設計線性表的順序：線性表的順序結構及算法，并分析算法的時間復雜度。結構：#define ListInitSize 100;#define ListIncrement 10; typedefstructElemType*elem; length; listSize;SqList;S us ListInsert(SqList &L,i, ElemType e)if (i1 | iL.length) return ERROR; if (L.lengt

2、h =L.listSize) newbase = (ElemType*)realloc(L.elem, (L.listSize + ListIncrement)*sizeof(ElemType); if(!newbase) exit(OVERFLOW);L.elem = newbase; L.listSize += ListIncrement;q = &for (p=&(L.elemi-1);( L.elemL.length-1);p=q; p-)*(p+1) = *p;*q = e; L.length+; return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層

3、次：簡單應用結構 順序結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。2、設計線性表的順序：線性表的順序結構及刪除算法，并分析算法的時間復雜度。結構：#define ListInitSize 100;#define ListIncrement 10; typedefstructElemType*elem; length; listSize;SqList;S us ListDelete(SqList &L,i, ElemType &e)if (i1 | iL.length) return ERROR;p = &e = *p; q = &(L.elemi-1

4、);(L.elemL.length -1);for (p+; p=q;p+)*(p-1) = *p;L.length-; return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 順序結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。3、L 是線性表的順序的遞增有序。：線性表的順序結構，且遞增有序，設計算法將 x到向量 L 中，并保持向量結構：#define ListInitSize 100;#define ListIncrement 10; typedefstructElemType*elem; length;

5、 listSize;SqList;Sus ListInsert(SqList L, ElemType x)if (L.length =L.listSize) newbase = (ElemType*)realloc(L.elem, (L.listSize + ListIncrement)*sizeof(ElemType);if(!newbase) exit(OVERFLOW); L.elem = newbase;L.listSize += ListIncrement; i=0;while (L.elemix) i+;q = &for (p=&(L.elemi-1);( L.elemL.leng

6、th-1);p=q; p-)*(p+1) = *p;*q = x; L.length+; return OK;難度:4所屬知識點：線性表 線性表的認知層次：綜合應用結構 順序結構算法基本思路正確 14 分，其他方面的相關細節描述正確 6 分。4、A 是線性表的順序空間。：參考1：void rightro結構，設計算法將向量中的元素循環右移 k 位，且只用一個輔助e(SqList &A,k)/ 以向量作num=0; start=0;結構，本算法將向量中的n 個元素循環右移k 位，且只用一個輔助空間。/ 計數，最終應等于n/開始位置（下標）while (numA.length)temp=A.ele

7、mstart;/暫存起點元素值，temp 與向量中元素類型相同empty=start;/保存空位置下標next=(start-K+ A.length) % A.length; / 計算下一右移元素的下標while (next !=start) A.elemempty=A.elemnext;/ 右移num+; empty=next;/ 右移元素數加 1next=(next-K+ A.length) % A.length; / 計算新右移元素的下標A.elemempty=temp; num+;start+;/ 把一輪右移中最后一個元素放到合適位置/ 起點增 1，若numn 則開始下一輪右移。參考2

8、：void EMove(SqList A,k)t=0;r=1; /t 是需要到位的元素的靜態指針；s 指向下一個K 步到達的位置；/r 初值為 1，在每一循環圈中置初值一次for(i = 0 ; i A.length;)s = ( t + r * k ) % A.length ;temp = A.elemt;/用 At為緩沖空間 , 使此鏈上一個到位，/到位位置的緩存到緩沖區中A.elemt = A.elems;A.elems = temp;r+ ;i+;s = ( t +r *k) % A.length;if(s = t)t+; r=1; i+;/end if/end for /使兩個到位，

9、一圈結束/選擇新的起始點難度:5所屬知識點：線性表 線性表的認知層次：綜合應用結構 順序結構算法基本思路正確 14 分，其他方面的相關細節描述正確 6 分。5、設計：結點的單鏈表線性表結構及算法，并分析算法的時間復雜度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListInsert(linkList &L,i,ElemType e)p=L; j=0;while (p &ji-1) p=pnext;試題分類: 第二章線性表/第二節線性表的結構/第二條鏈式結構j+;if (

10、!p | j=i-1) return ERROR;s = (linkList) malloc(sizeof(LNode);if (!s) sdata snextpnextreturn ERROR;=e;= pnext;= s;return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。6、設計：線性表的單鏈表結點的單鏈表線性表結構及刪除算法，并分析算法的時間復雜度。結構：typedefstruct LNode ElemTypedata; Struct LNode

11、 *next;LNode, *linkList;Sus ListDeleinkList &p=L; j=0;L,i,ElemType &e)while (p &ji-1)p=pnext;j+;if (!p | j=i-1) return q = pnext;pnext = qnext; e = qdata; free(q);return OK;ERROR;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。7、設計：結點的雙鏈表線性表結構及算法，并分析算法的時間復雜度。線性

12、表的雙鏈表結構：typedefstructDuLNode ElemTypedata;Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListInsert(dulinkList &L,i, ElemTypee)p=L; j=0;while (p &ji-1) p=pnext;j+;if (!p | j=i-1) return ERROR;s = (linkList) malloc(sizeof(DuLNode);if (!s) sdatasnextreturn ERROR;=e;= pnext; sprio

13、r=p;pnextprior = s; pnext = p;return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。8、設計：線性表的雙鏈表結點的雙鏈表線性表結構及刪除算法，并分析算法的時間復雜度。結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListDelete(dulinkList &L,

14、i,ElemType&e)p=L; j=0;while (p &ji-1) p=pnext;j+;if (!p | j=i-1) return ERROR; q = pnext;pnextprior = p; pnext = qnext; e = qdata; free(q);return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。9、設計：線性表的單鏈表結點的單循環鏈表線性表結構及算法，并分析算法的時間復雜度。結構：typedefstruct LNode

15、ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListInsert(linkList &p=L; j=0;L,i,ElemType e)while (pnext!=L & p=pnext;j+;&ji-1) if (pnext=L s = (linkList) if (!s) returnsdata =e;| j=i-1)return ERROR;malloc(sizeof(LNode);ERROR;snext = pnext; pnext = s;return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層

16、次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。10、設計：結點的單循環鏈表線性表結構及刪除算法，并分析算法的時間復雜度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListDeleinkList &L,p=L; j=0;i,ElemType&e)while (p &ji-1) p=pnext;j+;if (p | j=i-1) return ERROR; q = pnext;pnext = qnext; e

17、= qdata; free(q);return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。11、設計：線性表的雙鏈表結點的雙循環鏈表線性表結構及算法，并分析算法的時間復雜度。結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListInsert(dulinkList &L,i, ElemTypee

18、)p=L; j=0;while (pnext!=L & p=pnext;j+;&ji-1) if (pnext=Ls = (linkList)| j=i-1)return ERROR;malloc(sizeof(DuLNode);ERROR;if (!s)sdata snextreturn=e;= pnext; sprior=p;pnextprior = s; pnext = p;return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。12、設計：結點的雙循

19、環鏈表線性表結構及刪除算法，并分析算法的時間復雜度。線性表的雙鏈表結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListDelete(dulinkList &p=L; j=0;L,i,ElemType &e)while (pnext!=L &ji-1) p=pnext;j+;if (p=L | j=i-1) return ERROR; q = pnext;pnextprior = p; pnext = qnext; e = qd

20、ata; free(q);return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。13、設計不：結點的單鏈表線性表結構及算法，并分析算法的時間復雜度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListInsert(linkList &L,i,ElemType e)s = (linkList) malloc(sizeof(LNode)

21、; if (!s) return ERROR;sdata =e; if （i=1） snext = L; L = s;else p=L; j=1;while (pnext!=L &ji-1) p=pnext;j+;if (!p | snext =pnext =j=i-1) free(s); return ERROR; pnext;s;return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。14、設計不：結點的單鏈表線性表結構及刪除算法，并分析算法的時間復雜

22、度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListDeleinkList &L,i,ElemType&e)if (i=1) q = L;L = Lnext;else p=L; j=1;while (p &ji-1)p=pnext;j+;if (!p | j=i-1) return q = pnext;pnext = qnext;ERROR;e = qdata; free(q); return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次

23、：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。15、設計不：結點的雙鏈表線性表結構及算法，并分析算法的時間復雜度。線性表的雙鏈表結構：typedefstructDuLNode ElemTypedata;Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListInsert(dulinkList &L,i, ElemType e)s = (linkList) malloc(sizeof(DuLNode); if (!s) return ERROR;

24、sdata =e; if(i=1) snext = L; Lprior = s; L = s;else p=L; j=1;while (p &ji-1) p=pnext;j+;if (!p | j=i-1) free(s);return snext = pnext; sprior=p; pnextprior = s; pnext = p;ERROR; return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。16、設計不：結點的雙鏈表線性表結構及刪除算法，并分

25、析算法的時間復雜度。線性表的雙鏈表結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListDelete(dulinkList &L,i,ElemType&e)if (i=1) q = L;L = Lnext;else p=L; j=0;while (p &ji-1) p=pnext;j+;if (!p | j=i-1) return ERROR; q = pnext;pnextprior = p;pnext = qnext;e =

26、 qdata; free(q); return OK;時間復雜度為O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。17、設計不：結點的單循環鏈表線性表結構及算法，并分析算法的時間復雜度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListInsert(linkList &L,i,ElemType e)s = (linkList) malloc(sizeof(L

27、Node); if (!s) return ERROR;sdata =e; if （i=1） snext = L; tp=L;while (tpnext!=L) tp = tpnext; tpnext = s;L = s;else p=L; j=1;while (pnext！=L & p=pnext;j+;ji-1) if (p=L | j=i-1) free(s); return ERROR; snext = pnext;pnext = s;return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分

28、（基本占 8 分），時間復雜度正確 2 分。18、設計不：結點的單循環鏈表線性表結構及刪除算法，并分析算法的時間復雜度。線性表的單鏈表結構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Sus ListDeleinkList &p=L; j=0;L,i,ElemType &e)while (p!=L & p=pnext; j+;&ji-1)if (p=L | j=i-1) return ERROR; q = pnext;pnext = qnext; e = qdata; free(q);return

29、OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。19、設計不：線性表的雙鏈表結點的雙循環鏈表線性表結構及算法，并分析算法的時間復雜度。結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListInsert(dulinkList &L,i, ElemType e)s = (linkList) mallo

30、c(sizeof(DuLNode); if (!s) return ERROR;sdata =e;if(i=1) snext = L; sprior = Lprior; Lprior = s; spriornext = s; L = s;else p=L; j=1;while (pnext！=L & p=pnext;j+;&ji-1) if (p =L | j=i-1) free(s);return ERROR; snext = pnext; sprior=p;pnextprior = s; pnext = p;return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認

31、知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。20、設計不：結點的雙循環鏈表線性表結構及刪除算法，并分析算法的時間復雜度。線性表的雙鏈表結構：typedefstructDuLNode ElemTypedata; Struct DuLNode *prior; Struct DuLNode *next;DuLNode, *duLinkList;Sus ListDelete(dulinkList &L,i,ElemType &e)if (i=1) q = L;Lnextprior = Lprior; Lpriornext = Lne

32、xt; L = Lnext;else p=L; j=0;while (pnext!=L & p=pnext;j+;&ji-1) if (p=L | j=i-1) return ERROR; q = pnext;pnextprior = p;pnext = qnext;e = qdata; free(q); return OK;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。21、設計度。：單循環鏈表線性結構及計算其線性表長度的算法，并分析算法的時間復雜線性表的單鏈表結

33、構：typedefstruct LNode ElemTypedata; Struct LNode *next;LNode, *linkList;Count(linkList &L)p=L; j=0;while (pnext!=L) p=pnext;j+;return j;時間復雜度為 O（n）。難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構結構描述正確 6 分，算法正確 12 分（基本占 8 分），時間復雜度正確 2 分。22、結點的單鏈表L 遞增有序，設計算法將x：到鏈表中，并保持鏈表的遞增有序。Sus ListInsert(linkList &p=L; j=0;L,

34、ElemTypex)while (!p &p=pnext; j+;&pnextdatax) if (p) return ERROR;s = (linkList) malloc(sizeof(LNode);if (!s) sdata snextpnextreturn ERROR;=x; pnext;s;return OK;難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構算法基本正確 14 分，其它細節設計正確 6 分。23、設計算法，將：void invert(linklist *L)結點的單鏈表L 逆置。/ 本算法將結點的單鏈表L 逆置。/算法是先將頭結點從表上摘下，然后從

35、第一個元素結點開始，依次前點的鏈表中。以L 為頭結linklist *p=Lnext,*s;/ p 為工作指針，指向當前元素，s 為p 的后繼指針Lnext=null;/頭結點摘下，指針域置空。算法中頭指針 L 始終不變while (p) s=pnext; pnext=Lnext; Lnext=p;p=s;/ 保留后繼結點的指針/ 逆置/ 將p 指向下個待逆置結點/ 算法結束難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構算法基本正確 14 分，其它細節設計正確 6 分。24、長度大于 1 的單循環鏈表，既無頭結點，也無頭指針，設計算法刪除指針 s 的前驅結點。：void

36、deleteprior(linklist *L，linklist *s)/ 長度大于 1 的單循環鏈表，既無頭結點，也無頭指針，本算法刪除*s 的前驅結點 linklist *p=snext,*pre=s; / p 為工作指針，指向當前元素，/ pre 為前驅指針，指向當前元素*p 的前驅while (pnext!=s) pre=p; p=pnext; / 查找*s 的前驅prenext=snext; free(p); / 刪除元素 / 算法結束難度:3所屬知識點：線性表 線性表的認知層次：簡單應用結構 鏈式結構算法基本正確 14 分，其它細節設計正確 6 分。25、分別設計棧的兩種順序結構及

37、出棧算法。：結構 1：#define StackInitSize100#define StackIncreament 10 typedef struct ElemTypeElemType*baze;*top; stackSize;SqStack;Sus Pop(SqStack &S, ElemType &e)if (S.top=S.base) return ERROR; e = *S.top-;return OK;結構 2：#define StackInitSize100#define StackIncreament 10 typedef struct ElemType*base; stack

38、Lenght;stackSize;SqStack;Sus Pop(SqStack &S, ElemType &e)if (S.stackLenght=0) return ERROR; e =*S.base;for (i=0; iS.stackLenght-1; i+) *(S.base+i) = *(S.base+i+1);試題分類: 第三章棧和隊列/第一節棧/第二條棧的結構S.stackLength-;return OK;難度:4所屬知識點：棧和隊列 棧 棧的認知層次：簡單應用結構結構正確各 3 分，算法正確各 7 分（其中算法基本正確 5 分）。26、用一個順序結構設計二個棧，并給出如下接

39、口的入棧和出棧操作：push(twostack *s,i, ElemType x)ElemType pop(twostack *s,i)其中，取 0 和 1 分別表示第一個棧和第二個棧。：typedef struct ElemType vm; top2twostack;/ 兩棧共向量空間/ 棧可用空間 0m-1/ 棧頂指針push(twostack*s,i, ElemType x)/ 兩棧共享向量空間,i 是 0 或 1，表示兩個棧，x 是進棧元素，/ 本算法是入棧操作if (abs(stop0 - stop1)=1) return(0);/ 棧滿else switch (i) case 0:

40、 sv+(stop)=x; break; case 1: sv-(stop)=x; break;default: prf(“棧輸入錯誤”); return(0);return(1);/ 入棧成功 / 算法結束ElemType pop(twostack *s,i)/ 兩棧共享向量空間,i 是 0 或 1，表示兩個棧，本算法是退棧操作ElemType x;if (i!=0 &i!=1) return(0);/ 棧else switch (i)錯誤case 0: if(stop0=-1) return(0);/棧空 else x=svstop-;break;case 1: if(stop1=m) r

41、eturn(0);/棧空 else x=svstop+; break;default: prf(“棧輸入錯誤”);return(0);return(x);/ 退棧成功 / 算法結束難度:5所屬知識點：棧和隊列 棧 棧的認知層次：簡單應用結構結構正確 6 分，算法正確各 7 分（其中算法基本正確 5 分）。27、設計棧的單鏈：結構及入棧和出棧的算法，并分析算法的時間復雜度。#define StackInitSize100#define StackIncreament 10 typedef struct ElemTypeElemType*baze;*top; stackSize;SqStack;S

42、us Push(SqStack &S, ElemType e)if (S.top-S.base=S.stackSize) return ERROR;*S.top+ = e; return OK;Sus Pop(SqStack &S, ElemType &e)if (S.top=S.base) return ERROR; e = *S.top-;return OK;難度:3所屬知識點：棧和隊列 棧 棧的認知層次：簡單應用結構結構描述正確 6 分，入棧和出棧算法正確各 6 分，時間復雜度正確 2 分。試題分類: 第三章棧和隊列/第一節棧/第三條棧的應用28、設計一個算法，對正文中“”和“”、“ ”

43、和“ ”、“（”和“）”、“”和“”等的配對情況進行檢查。：check(FILE *fp)initStack(q); ch = getch(fp);while (ch!=EOF) if (ch=(| ch = | ch = | ch=) ch2=Pop(q);if (ch2=(&ch=)| ch2=&ch = |ch2=&ch = | ch2=)continue;難度:5所屬知識點：棧和隊列 棧 棧的應用認知層次：綜合應用結構正確各 3 分，算法正確各 7 分（其中算法基本正確 5 分）。29、設計隊列的：typedef struct Qnode 單鏈式結構及入隊列和出隊列的算法。ElemTy

44、pe structQnode; typedef struct Qnode QnodeLinkQueue;data;*next;*front;*rear;sus EnQueue(LinkQueue &Q, ElemType e)p=(Qnode*)malloc(sizeof(Qnode); if (!p) return ERROR;pdata = e; pnext = NULL;Q.rearnext = p; Q.rear = p;return OK;試題分類: 第三章棧和隊列/第二節隊列/第二條隊列的結構sus DeQueue(LinkQueue &Q, ElemType &e)if(Q.fr

45、ont=Q.rear) return ERROR; p = Q.frontnext;e = pdata;Q frontnext = pnext;if (Q rear = p) Q rear = Q front; free(p);return OK;/為空的條件是頭和尾都指向頭節點。難度:3所屬知識點：棧和隊列 隊列 隊列的認知層次：簡單應用結構結構描述正確 6 分，入棧和出棧算法正確各 7 分（其中算法基本正確 5 分）。30、設計隊列的不：單鏈式結構及入隊列和出隊列的算法。typedef struct Qnode ElemType structQnode; typedef struct Qn

46、ode QnodeLinkQueue;data;*next;*front;*rear;sus EnQueue(LinkQueue &Q, ElemType e)p=(Qnode*)malloc(sizeof(Qnode); if (!p) return ERROR;pdata = e; pnext = NULL;if （Q.front=Q rear & Q.front=Q.rear=p;else Q.rearnext = p; Q.rear = p;return OK;&Q.front=NULL） sus DeQueue(LinkQueue &Q, ElemType &e)if(Q.front

47、=Q.rear &等，并且都為 NULL。If(Q.front=Q.rear & p=Q.front;&Q front=NULL) return ERROR; /為空的條件是頭和尾相&Q.front!=NULL) Q.front = Q.rear = NULL;else p = Q.front; Q.frontnext = pnext;e = pdata; free(p); return OK;難度:3所屬知識點：棧和隊列 隊列 隊列的認知層次：簡單應用結構結構描述正確 6 分，入棧和出棧算法正確各 7 分（其中算法基本正確 5 分）。31、設計隊列的循環順序結構及入隊列和出隊列的算法。：#d

48、efine MaxQSize typedef struct ElemType100*base; front;rear;Sueue;sus EnQueue(Sueue &Q, ElemType e)if (Q.rear+1)% MaxQSize = Q front) return ERROR; /隊列滿的條件 Q.baseQ.rear = e;Q.rear = (Q.rear + 1) % MaxQSize；return OK;sus DeQueue(Sueue &Q, ElemType &e)if(Q front=Q.rear) return ERROR; e = Q.baseQ.front;

49、Q. front = (Q. front + 1) % MaxQSize；return OK;/隊列空的條件難度:3所屬知識點：棧和隊列 隊列 隊列的認知層次：簡單應用結構結構描述正確 6 分，入棧和出棧算法正確各 7 分（其中算法基本正確 5 分）。32、設計循環隊列的順序：typedef struct 結構，并設計一個計算其大小的算法。ElemType datam;/ 循環隊列占m 個front,rear;S ueue;單元queuelength(S ueue *cq)return (cqrear - cqfront + m) % m; / 算法結束難度:2所屬知識點：棧和隊列 隊列 隊列

50、的認知層次：簡單應用結構結構描述正確 8 分，算法正確 12 分。33、設計串的定長順序：結構及串連接算法，并分析算法的時間復雜度。#define MAX_STR_LEN 40typedef char SStringMAX_STR_LEN+1;S us Concat(SString T,SString S1,SString S2)/最大串長/ 0 號單元存放串的長度 / 用T 返回 S1 和 S2 連接而成的新串。若未截斷，則返回 TRUE；否則返回 FALSEif(S10+S20 =MAX_STR_LEN)for(i=1;i =S10;i+) Ti=S1i;for(j=1;j=S20;j+)

51、 TS10+j=S2j;T0=S10+S20;return TRUE;/ 未截斷試題分類: 第四章串/第二節串的結構 else for(i=1;i =S10;i+) Ti=S1i;/ 截斷 S2for(j=1;j =MAX_STR_LEN-S10;j+) / 到串長為止TS10+j=S2j; T0=MAX_STR_LEN;return FALSE;算法時間復雜度：O(n)難度:3所屬知識點：串 串的認知層次：簡單應用結構結構描述正確 6 分，算法正確 12 分（其中基本正確 10 分），時間復雜度正確 2分。34、設計串的堆分配順序：typedef struct結構及串連接算法，并分析算法的時

52、間復雜度。char *ch;length;HString;/ 若是非空串，則按串實用長度分配/ 串長度區，否則 ch為 NULLS us Concat(HString &T, HString S1, HString S2) / 用T 返回由 S1 和 S2 聯接而成的新串if (T.ch) free(T.ch);/舊空間if (!(T.ch =(char *)malloc(S1.length+S2.length)*sizeof(char) exit (OVERFLOW);T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length +

53、 S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1;return OK;算法時間復雜度：O(n)難度:3所屬知識點：串 串的認知層次：簡單應用結構結構描述正確 6 分，算法正確 12 分（其中基本正確 10 分），時間復雜度正確 2分。試題分類: 第四章串/第三節串的應用35、假設模式串的 next 函數已經給定，請給出 KMP 模式匹配算法。：index(string s , stirng t)m=length(s); n=length(t);i=0;j=1;while(i=m &j=n) if( j=0 | si=tj) i+

54、; j+; else j= nextj;if(j=n) return(i); else return(0);/模式匹配成功/s 串中無子串t難度:3所屬知識點：串 串的應用認知層次：簡單應用算法正確 20 分（其中基本正確 15 分）。36、設s、t 是字符串，設計算法求子串t 在主串s 中的第一次出現，若s 串中包含t 串，返回其第一個字符在s 中的位置，否則返回 0。：index(string s, string t) m=length(s);n=length(t); i=1;while(i=m-n+1) if(strcmp(substr(s,i,n),t)=0) break; else

55、i+;if(i=m-n+1)return(i);/模式匹配成功 elsereturn(0);/s 串中無子串t/算法 index 結束難度:3所屬知識點：串 串的應用認知層次：簡單應用算法正確 20 分（其中基本正確 15 分）。37、設 S 和T 是指向兩個順序串的指針，設計算法比較兩個串的大小，若 S 串大于T 串，返回 1；若S 串等于T 串，返回 0；否則返回-1。：strcmp(seqstring *S, seqstring *T)i=0;while (schi!= 0 &tchi!= 0)if (schitchi) return(1);else if (schi tchi) ret

56、urn(-1);else i+;/ 比較下一字符if (schi!= 0& else if (schi= else return(0);/ 算法結束& 0&tchi=0) return(1);&tchi!=0) return(-1);難度:3所屬知識點：串 串的應用認知層次：簡單應用算法正確 20 分（其中基本正確 15 分）。試題分類: 第六章樹和二叉樹/第二節二叉樹/第三條二叉樹的遍歷和線索化38、設計二叉樹的鏈式：二叉樹的鏈式結構及先序遍歷算法。結構：typedef struct BiTNode ElemTypedata;struct BiTNode *Lchild, *Rchild;B

57、iTNode, *BiTree;先序遍歷算法：sus PreOrderTravser(BiTree T)if (T) visit(T); PreOrderTravser(TLchild); PreOrderTravser(TRchild);/ PreOrderTravser難度:3所屬知識點：樹和二叉樹 二叉樹 二叉樹的遍歷和線索化認知層次：簡單應用結構描述正確 6 分，算法正確 14 分（其中算法基本正確 10 分）。39、設計二叉樹的鏈式：二叉樹的鏈式結構及中序遍歷算法。結構：typedef struct BiTNode ElemTypedata;struct BiTNode *Lchil

58、d, *Rchild;BiTNode, *BiTree;中序遍歷算法：sus MidOrderTravser(BiTree T)if (T) MidOrderTravser(TLchild); visit(T); MidOrderTravser(TRchild);/ MidOrderTravser難度:3所屬知識點：樹和二叉樹 二叉樹 二叉樹的遍歷和線索化認知層次：簡單應用結構描述正確 6 分，算法正確 14 分（其中算法基本正確 10 分）。40、設計二叉樹的鏈式：二叉樹的鏈式結構及后序遍歷算法。結構：typedef struct BiTNode ElemTypedata;struct Bi

59、TNode *Lchild, *Rchild;BiTNode, *BiTree;后序遍歷算法：sustOrderTravser(BiTree T)if (T) tOrderTravser(TLchild); tOrderTravser(TRchild);visit(T);/tOrderTravser難度:3所屬知識點：樹和二叉樹 二叉樹 二叉樹的遍歷和線索化認知層次：簡單應用結構描述正確 6 分，算法正確 14 分（其中算法基本正確 10 分）。41、設計二叉樹的鏈式：二叉樹的鏈式結構及非遞歸先序遍歷算法。結構：typedef struct BiTNode ElemTypedata;struc

60、t BiTNode *lchild, *rchild;BiTNode, *BiTree;先序遍歷非遞歸算法：void preorder (Bitree *t)(先序非遞歸遍歷)Bitree *sn+1; / s 是指針數組，數組中元素為二叉樹節點的指針top=0;while (t!=null | top!=0) while (t!=null) visit(*t); s+top=t; t=tlchild if (top!=0) t=stop-; t=trchild; / 算法結束難度:4所屬知識點：樹和二叉樹 二叉樹 二叉樹的遍歷和線索化認知層次：簡單應用結構描述正確 6 分，算法正確 14 分