中南大学：《数据结构》课程教学资源（试卷习题）习题

第一章绪论 例:计算f=1!+2!+3!+…+n!,用C语言描述 void factorsum (n) int f, w or(i=1:i《=n:i++) for (=l:j(=i; j++) W-W 第二章线性表 Pl6【算法21顺序表的插入】 int Insert(Elemtype ListI, int*num, int i, Elemtype x) {*在顺序表Lis中,·num为表尾元素下标位置,在第i个元素前插入数据元素x,若成功,返回 TRUE,否则返回 FALSE。 f(<O‖>*num+1) i printf("Error!) 插入位置出错* eturn FALSE, if(num>=MAXNUM-1) return FALSe; j 表已满* for(F*num; j >=i;j--) List[+1FList] 数据元素后移* ListOn /插入x 长度加1· return TRUE; P18【算法22顺序表的删除】 int Delete( Elemtype List, int*num, int i) 在线性表List中,*mum为表尾元素下标位置,删除第i个长度,线性表的长度减1,若成功 则返回TRUE:否则返回 FALSE。* if(i<op*num printi"ror!"), return False,}*删除位置出错!*/ fo(产=计1Jj<=*numj++) List[j-1=List 数据元素前移 (num)- 长度减1。 eturn TRUE, i P19例:将有序线性表La=(2,4,6,79},Lb={1,5,7,8},合并为Lc={1,2,4,5,6,7,78,9}。 void merge( Elemtype La[, Elemtype Lbl, Elemtype **Lc) i int ij, k, int La length, Lb length La length= Length(La) Lb length= Leng th(Lb),/*取表LaLb的长度* 初始化表Lc While(i<=La length&&j<=Lb length i aFget(La, i), b=get(Lb,j; a<b)insert(Lc, ++k, a); ++1; else (insert(Lc, ++k, b): ++; 将La和Lb的元素插入到Lc中考 (<=La length)i aFget(La, i) insert(Lc, ++k, a): i while ( <=lb length)i b=get (La.j), insert(Lc, ++k, b);3j P2I例如:下面定义的结点类型中,数据域包含三个数据项:学号、姓名、成绩 Struct studer i char num[8] 数据域 数据域 数据域 struct student*next/指针域*/

第一章 绪论 例： 计算 f=1！+2！+3！+…+n！，用 C 语言描述。 void factorsum（n） int n； {int i，j； int f，w； f=0； for （i=1；i〈=n；i++） {w=1； for （j=1；j〈=i；j++） w=w*j； f=f+w；} return； } 第二章 线性表 P16【算法 2.1 顺序表的插入】 int Insert(Elemtype List[],int *num,int i,Elemtype x) {/*在顺序表 List[]中，*num 为表尾元素下标位置，在第 i 个元素前插入数据元素 x，若成功，返回 TRUE，否则返回 FALSE。*/ int j; if (i<0||i>*num+1) {printf(“Error!”); /*插入位置出错*/ return FALSE;} if (*num>=MAXNUM-1) {printf(“overflow!”); return FALSE;} /*表已满*/ for (j=*num;j>=i;j--) List[j+1]=List[j]; /*数据元素后移*/ List[i]=x; /*插入 x*/ (*num)++; /*长度加 1*/ return TRUE;} P18【算法 2.2 顺序表的删除】 int Delete(Elemtype List[],int *num,int i) {/*在线性表 List[]中，*num 为表尾元素下标位置，删除第 i 个长度，线性表的长度减 1，若成功， 则返回 TRUE；否则返回 FALSE。*/ int j; if(i<0||i>*num) {printf(“Error!”); return FALSE; } /*删除位置出错！*/ for(j=i+1;j<=*num;j++) List[j-1]=List[j]; /*数据元素前移*/ (*num)--; /*长度减 1*/ return TRUE; } P19 例：将有序线性表 La={2,4,6,7,9}，Lb={1,5,7,8}，合并为 Lc={1,2,4,5,6,7,7,8,9}。 void merge(Elemtype La[],Elemtype Lb[],Elemtype **Lc) { int i,j,k; int La_length,Lb_length; i=j=0;k=0; La_length=Length(La);Lb_length=Length(Lb); /*取表 La,Lb 的长度*/ Initiate(Lc); /*初始化表 Lc*/ While (i<=La_length&&j<=Lb_length) { a=get(La,i);b=get(Lb,j); if(a<b) {insert(Lc,++k,a);++i;} else {insert(Lc,++k,b);++j;} } /*将 La 和 Lb 的元素插入到 Lc 中*/ while (i<=La_length) { a=get(La,i);insert(Lc,++k,a);} while (j<=lb_length) { b=get(La,j);insert(Lc,++k,b); } } P21 例如：下面定义的结点类型中，数据域包含三个数据项：学号、姓名、成绩。 Struct student { char num[8]; /*数据域*/ har name[8]; /*数据域*/ int score; /*数据域*/ struct student *next; /*指针域*/}

P21单链表结点结构定义为: Typedef struct sInode struct sInode 'next Inodetype retype P21【算法2.3单链表的初始化】 nt Initiate(sInodetype **h) i if((h=(sInodetype")malloc(sizeof(sInodetype)NULL) return FALSE return TRUE. P22【算法24单链表的后插入】 i s=(slnodetype")malloc(sizeof(sInodety pe) ->datax - >nexts P22【算法2.5单链表的结点插入】 while(q->next!=p)q=q->next retype S->nextp; P23【算法26单链表的前插入】 int insert(sInodetype "h, int 1, Elemtype x) /在链表h中,在第i个数据元素前插入一个数据元素x制 while(p!=NULL&&j<i-l){p=q>next++;/*寻找第i1个结点*} /*插入位置错误 if(s=(sInodety pe* )malloc(sizeof(slnodetype)=NULL) return FALSE S->dataS; s->nextp-next, -next=s return TRUI P23 面C程序中的功能是,首先建立一个线性链表head={3,5,7,9},其元素值依 次为从键盘输入正整数(以输入一个非正整数为结束);在线性表中值为x的元素前插入 个值为y的数据元素。若值为x的结点不存在,则将y插在表尾 # include“ stdlib. h struct sInode fint data, struct slnode*next /定义结点类型* head=NULL; /置链表空 scanf(“%d”,&d),/输入链表数据元素* ip(struct sInode*)malloc(sizeof(struct sInode); /*F 个新结点 p->data=d if(head=NULL)head=p,/若链表为空,则将头指针指向当前结点p* else q->next=p,链表不为空时,则将新结点链接在最后* qFp,/*将指针q指向链表的最后一个结点 scanf%d”,d)} scanf("%d, %d, &x, &y ) hile(pl=NULL&&(p-> datal=x){q=pp=p->next;}/*查找元素为x的指针*

P21 单链表结点结构定义为： Typedef struct slnode { Elemtype data; struct slnode *next; }slnodetype; slnodetype *p,*q,*s; P21 【算法 2.3 单链表的初始化】 int Initiate(slnodetype * *h) { if((*h=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; (*h)->next=NULL; return TRUE; } P22 【算法 2.4 单链表的后插入】 { s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p->next;p->next=s;} P22 【算法 2.5 单链表的结点插入】 {q=head; while(q->next!=p) q=q->next; s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p; q->next=s;} P23【算法 2.6 单链表的前插入】 int insert(slnodetype *h,int i,Elemtype x) {/*在链表 h 中，在第 i 个数据元素前插入一个数据元素 x */ slnodetype *p,*q,*s; int j=0; p=h; while(p!=NULL&&j<i-1) { p=q->next;j++; /*寻找第 i-1 个结点*/ } if ( j!=i-1) {printf(“Error!”);return FALSE; /*插入位置错误*/} if ((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; s->data=x; s->next=p->next; q->next=s; return TRUE;} P23 例：下面 C 程序中的功能是，首先建立一个线性链表 head={3，5，7，9}，其元素值依 次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为 x 的元素前插入一 个值为 y 的数据元素。若值为 x 的结点不存在，则将 y 插在表尾。 #include “stdlib.h” #include “stdio.h” struct slnode {int data; struct slnode *next;} /*定义结点类型*/ main() {int x,y,d; struct slnode *head,*p,*q,*s; head=NULL; /*置链表空*/ q=NULL; scanf(“%d”,&d); /*输入链表数据元素*/ while(d>0) {p=(struct slnode*)malloc(sizeof(struct slnode)); /*申请一个新结点*/ p->data=d; p->next=NULL; if(head==NULL) head=p; /*若链表为空，则将头指针指向当前结点 p*/ else q->next=p; /*链表不为空时，则将新结点链接在最后*/ q=p; /*将指针 q 指向链表的最后一个结点*/ scanf(“%d”,&d);} scanf(“%d,%d”,&x,&y); s=(struct slnode*)malloc(sizeof(struct slnode)); s->data=y; q=head;p=q->next; while((p!=NULL)&&(p->data!=x)) {q=p;p=p->next;} /*查找元素为 x 的指针*/ s->next=p;q->next=s; /*插入元素 y*/

P24【算法2.7单链表的删除】 /*在链表h中删除第i个结点* Int, while(p->nextI=NULL&&j<i-1) p=p> nextF=j+1;/寻找第-1个结点p指向其前驱啼 printi"ror!”),*删除位置错误! return FALSE; j nextp>next>next,/删除第i个结点制 es);/*释放被删除结点空间 P25例:假设已有线性链表La,编制算法将该链表逆置 void converse(sInodetype *head) { slnodetype孝p,*q while(p=NULL) head->next=p P27例:将两个循环链表首尾相接。La为第一个循环链表表尾指针,Lb为第二个循环链表 表尾指针。合并后Lb为新链表的尾指针 Void merge(sInodetype *La, slnodetype "Lb) i slnodetype"p; Lb->next La->next, free(p) P29【算法28双向链表的插入】 int insert dul( dInodetype *head, int i, Elemtype x) {/在带头结点的双向链表中第i个位置之前插入元素x* p=head; while(pl=NULL& p=p->ney ++, ifgI=iK<1) printf("eror!”); return FALSe; if(s=(dInodetype ")malloc(sizeof(dInodetype)=NULL) return FALSE; s→> prior=p-> pror,/图中步骤①* p> prior->next=s,/图中步骤② s→>next=p,/图中步骤③*/ /*图中步骤 return TRUE; P30【算法29双向链表的删除】 int Delete dl(dInodetype*head, int i) dInodetype’p,*s p=head

} P24【算法 2.7 单链表的删除】 int Delet(slnodetype *h,int i) { /*在链表 h 中删除第 i 个结点*/ slnodetype *p,*s; int j; p=h;j=0; while(p->next!=NULL&&j<i-1) { p=p->next;j=j+1; /*寻找第 i-1 个结点,p 指向其前驱*/} if(j!=i-1) {printf(“Error!”); /*删除位置错误!*/ return FALSE; } s=p->next; p->next=p->next->next; /*删除第 i 个结点*/ free(s); /*释放被删除结点空间*/ return TRUE; } P25 例：假设已有线性链表 La，编制算法将该链表逆置。 void converse(slnodetype *head) {slnodetype *p,*q; p=head->next; head->next=NULL; while(p!=NULL) { q=p->next; p->next=head->next; head->next=p; p=q; } } P27 例：将两个循环链表首尾相接。La 为第一个循环链表表尾指针，Lb 为第二个循环链表 表尾指针。合并后 Lb 为新链表的尾指针。 Void merge(slnodetype *La,slnodetype *Lb) { slnodetype *p; p=La->next; Lb->next= La->next; La->next=p->next; free(p); } P29【算法 2.8 双向链表的插入】 int insert_dul(dlnodetype *head,int i,Elemtype x) {/*在带头结点的双向链表中第 i 个位置之前插入元素 x*/ dlnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&&j<i) { p=p->next; j++; } if(j!=i||i<1) { printf(“Error!”); return FALSE;} if((s=(dlnodetype *)malloc(sizeof(dlnodetype)))==NULL) return FALSE; s->data=x; s->prior=p->prior; /*图中步骤①*/ p->prior->next=s; /*图中步骤②*/ s->next=p; /*图中步骤③*/ p->prior=s; /*图中步骤④*/ return TRUE;} P30【算法 2.9 双向链表的删除】 int Delete_dl(dlnodetype *head,int i) { dlnodetype *p,*s; int j; p=head; j=0;

while (pl=nULL&&j<i i p=p->next; +;} iful=i<D) i printf("Error!) return FALSE; p>pror>nex=p>next/图中步骤①*/ p>next> prior=p-> prior,/*图中步骤②*/ return TRUE, P32【算法210多项式相加】 struct poly *add poly(struct poly "Ah, struct poly "Bh) istruct poly *qa, *qb, * s, r, Ch qa=Ah> next: qb=Bh->next/qa和qb分别指向两个链表的第一结点 rqa Ch=Ah 件将链表Ah作为相加后的和链表* while(qal=nULL&&qbl=NULL /两链表均非空* i if (qa->exp==qb->exp) 两者指数值相等* fx=qa->coef+qb->coef; i qa->coef=x r->next=qa rqa 相加后系数不为零时 else{s=qa++fes,s=qb++,fees)}陣*相加后系数为零时制 else if(qa->exp<qb->exp){r->next=qar=qaqa++;}/多项式Ah的指数值小* else (r->next=qb rqb qb++ 3 多项式Bh的指数值小 if(qa=NULL)r->next=qb e r->nextga 链接多项式Ah或Bh中的剩余结点 return(Ch); 第三章栈和队列 P35相应的C语言函数是: oat fact(int n) if(n==|==1)s=1; else s=n’facn-1) P38用C语言定义的顺序存储结构的栈如下 # define maXnum<最大元素数> typedef struct i Elemtype stack MAXNUMI P39【算法3.1栈的初始化】 int initStack(sqstack *s) {/*创建一个空栈由指针S指出* if(s=(sqstack*malloc(sizeof(sqstack)F=NULL)return FALSE; return TR P39【算法3.2入栈操作】 int push(sqstack *s, Elemtype x) {将元素x插入到栈s中,作为s的新栈项* fs→>top>= MAXNUM1) return FALSE,/栈满 s->top++; return TRUE. P39【算法3.3出栈操作】 Elemtype pop(sqstack* s) {/*若栈s不为空,则删除栈顶元素

while (p!=NULL&&j<i) { p=p->next; j++; } if(j!=i||i<1) { printf(“Error!”); return FALSE;} s=p; p->prior->next=p->next; /*图中步骤①*/ p->next->prior=p->prior; /*图中步骤②*/ free(s); return TRUE;} P32【算法 2.10 多项式相加】 struct poly *add_poly(struct poly *Ah,struct poly *Bh) {struct poly *qa,*qb,*s,*r,*Ch; qa=Ah->next;qb=Bh->next; /*qa 和 qb 分别指向两个链表的第一结点*/ r=qa;Ch=Ah; /*将链表 Ah 作为相加后的和链表*/ while(qa!=NULL&&qb!=NULL) /*两链表均非空*/ { if (qa->exp==qb->exp) /*两者指数值相等*/ {x=qa->coef+qb->coef; if(x!=0) { qa->coef=x;r->next=qa;r=qa; s=qb++;free(s);qa++; } /*相加后系数不为零时*/ else {s=qa++;free(s);s=qb++;free(s);} /*相加后系数为零时*/ } else if(qa->exp<qb->exp){ r->next=qa;r=qa;qa++;} /*多项式 Ah 的指数值小*/ else {r->next=qb;r=qb;qb++;} /*多项式 Bh 的指数值小*/ } if(qa==NULL) r->next=qb; else r->next=qa; /*链接多项式 Ah 或 Bh 中的剩余结点*/ return (Ch); } 第三章 栈和队列 P35 相应的 C 语言函数是： float fact(int n) {float s; if (n= =0||n= =1) s=1; else s=n*fact(n-1); return (s); } P38 用 C 语言定义的顺序存储结构的栈如下： # define MAXNUM <最大元素数> typedef struct { Elemtype stack[MAXNUM]; int top; } sqstack; P39【算法 3.1 栈的初始化】 int initStack(sqstack *s) {/*创建一个空栈由指针 S 指出*/ if ((s=(sqstack*)malloc(sizeof(sqstack)))= =NULL) return FALSE; s->top= -1; return TRUE; } P39【算法 3.2 入栈操作】 int push(sqstack *s, Elemtype x) {/*将元素 x 插入到栈 s 中，作为 s 的新栈顶*/ if(s->top>=MAXNUM-1) return FALSE; /*栈满*/ s->top++; s->stack[s->top]=x; return TRUE; } P39【算法 3.3 出栈操作】 Elemtype pop(sqstack *s) {/*若栈 s 不为空，则删除栈顶元素*/

if(s->top<0)return NULL; 栈空 P39【算法34取栈顶元素】 pe get Top(sq {/若栈s不为空,则返回栈顶元素柳 if(s->top<O)return NULL, /栈空 return(s->stack[s->top)); P40【算法3.5判栈空操作】 int Empty(sqstack "s) {/栈s为空时,返回为TRUE:非空时,返回为 FALSE if(s->top<o)return TRUE, P40【算法36栈置空操作】 {*将栈s的栈顶指针top,置为-1*/ P40C语言定义的这种两栈共享邻接空间的结构如下 Elemtype stack[ IMAXNUMJ 左栈栈顶位置指示器 ghttop 右栈栈顶位置指示器* P41【算法3.7共享栈的初始化】 int init DupStack( dupsqstack *s) {/*创建两个共享邻接空间的空栈由指针S指出* if(s=(dupsqstack")malloc(sizeof(dupsqstack)))==NULL)return FALSE, s->righto=MAXNUM P41【算法38共享栈的入栈操作】 x) *把数据元素x压入左栈( status=L)或右栈( status=R')* if(s->leftop+1==s->righttop) return FALSE; 栈满* if(status=L) S->stack[++s->lefttoplx; 左栈进栈制 else if(status=R)s->stack(--s->righttopF=x;右栈进栈*/ else return FALSE; 参数错误 return TRUE. P42【算法3.9共享栈的出栈操作】 Elemtype pop Dup Stack( dupsqstack*s, char status) {/*从左栈( status=L’)或右栈( status=R')退出栈顶元素* if(status==L) i if (s->lefttop<o) return NULL. 左栈为空 else return(s->stack[s->lefttop--D; 左栈出栈 else if(status==R) i if(s->righttop>MAXNUM-1) return NULL. /右栈为空 else return(s-> stack[s-> righto+]),右栈出栈* else return NULL- /参数错误* P42链栈的C语言定义为

Elemtype x; if(s->top<0) return NULL; /*栈空*/ x=s->stack[s->top]; s->top--; return x; } P39【算法 3.4 取栈顶元素】 Elemtype getTop(sqstack *s) {/*若栈 s 不为空，则返回栈顶元素*/ if(s->top<0) return NULL; /*栈空*/ return (s->stack[s->top]); } P40【算法 3.5 判栈空操作】 int Empty(sqstack *s) {/*栈 s 为空时，返回为 TRUE；非空时，返回为 FALSE*/ if(s->top<0) return TRUE; return FALSE; } P40【算法 3.6 栈置空操作】 void setEmpty(sqstack *s) {/*将栈 s 的栈顶指针 top，置为-1*/ s->top= -1; } P40 C 语言定义的这种两栈共享邻接空间的结构如下： Typedef struct { Elemtype stack[MAXNUM]; int lefttop; /*左栈栈顶位置指示器*/ int righttop; /*右栈栈顶位置指示器*/ } dupsqstack; P41【算法 3.7 共享栈的初始化】 int initDupStack(dupsqstack *s) {/*创建两个共享邻接空间的空栈由指针 S 指出*/ if (s=(dupsqstack*)malloc(sizeof(dupsqstack)))= =NULL) return FALSE; s->lefttop= -1; s->righttop=MAXNUM; return TRUE; } P41【算法 3.8 共享栈的入栈操作】 int pushDupStack(dupsqstack *s,char status,Elemtype x) {*把数据元素 x 压入左栈（status=’L’）或右栈（status=’R’）*/ if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/ if(status=’L’) s->stack[++s->lefttop]=x; /*左栈进栈*/ else if(status=’R’) s->stack[--s->righttop]=x; /*右栈进栈*/ else return FALSE; /*参数错误*/ return TRUE; } P42【算法 3.9 共享栈的出栈操作】 Elemtype popDupStack(dupsqstack *s,char status) {/*从左栈（status=’L’）或右栈（status=’R’）退出栈顶元素*/ if(status= =’L’) { if (s->lefttop<0) return NULL; /*左栈为空*/ else return (s->stack[s->lefttop--]); /*左栈出栈*/ } else if(status= =’R’) { if (s->righttop>MAXNUM-1) return NULL; /*右栈为空*/ else return (s->stack[s->righttop++]); /*右栈出栈*/ } else return NULL; /*参数错误*/ } P42 链栈的 C 语言定义为：