数据结构总复习设计题

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 分