《数据结构——C语言描述》习题及标准答案-耿国华

第1章绪论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一、问答题1.什么是数据结构2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anx n的值Pn(x)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入ai (i=0,1,…,n), x和n，输出为Pn(x).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。

首元素结点：线性表中的第一个结点成为首元素结点。

4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p);return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。

第1章绪论之邯郸勺丸创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义.3. 算法的定义与特性.4. 算法的时间庞杂度.5. 数据类型的概念.6. 线性结构与非线性结构的不同.7. 面向对象程序设计语言的特点.8. 在面向对象程序设计中,类的作用是什么？9. 参数传递的主要方法及特点.10. 抽象数据类型的概念.二、判断题1. 线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放.2. 算法就是程序.3. 在初级语言（如C、或 PASCAL）中,指针类型是原子类型.三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法庞杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0),并确定算法中的每一语句的执行次数和整个算法的时间庞杂度,要求时间庞杂度尽可能的小,规定算法中不克不及使用求幂函数.注意：本题中的输入ai(i=0,1,…,n), x和n,输出为Pn(x0).通常算法的输入和输出可采取下列两种方法之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递.试讨论这两种办法的优缺点,并在本题算法中以你认为较好的一种方法实现输入和输出.[提示]：float PolyValue(float a[ ], float x, int n) {……}核心语句：p=1; (x的零次幂)s=0;i从0到n循环s=s+a[i]*p;p=p*x;或：p=x; (x的一次幂)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;实习题设计实现抽象数据类型“有理数”.基本操纵包含有理数的加法、减法、乘法、除法,以及求有理数的份子、分母.第一章答案1.3计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法,求p n(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间庞杂度,要求时间庞杂度尽可能小,规定算法中不克不及使用求幂函数.注意：本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(x0).算法的输入和输出采取下列办法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递.讨论两种办法的优缺点,并在算法中以你认为较好的一种实现输入输出.【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强.缺点：形参须与实参对应,且前往值数量有限.（2）通过全局变量隐式传递优点：减少实介入形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低,移植性差算法如下：通过全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f”,&a[i]); /*执行次数：n次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*执行次数：n次*/ x=x*x;}printf(“%f”,p);}算法的时间庞杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*执行次数:n次*/p=p*x;}return(p);}算法的时间庞杂度：T(n)=O(n)第2章线性表习题2.1 描述以下三个概念的区别：头指针,头结点,首元素结点. 2.2 填空：（1）在顺序表中拔出或删除一个元素,需要平均移动＿＿一半＿＿元素,具体移动的元素个数与＿＿拔出或删除的位置＿＿有关.（2）在顺序表中,逻辑上相邻的元素,其物理位置＿＿＿＿＿＿相邻.在单链表中,逻辑上相邻的元素,其物理位置＿＿＿＿＿＿相邻.（3）在带头结点的非空单链表中,头结点的存储位置由＿＿＿＿＿＿指示,首元素结点的存储位置由＿＿＿＿＿＿指示,除首元素结点外,其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示.2.3 已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点.按要求从下列语句中选择合适的语句序列.a. 在P结点后拔出S结点的语句序列是：＿（4）、（1）＿.b. 在P结点前拔出S结点的语句序列是：（7）、（11）、（8）、（4）、（1）.c. 在表首拔出S结点的语句序列是：（5）、（12）.d. 在表尾拔出S结点的语句序列是：（11）、（9）、（1）、（6）.供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递增有序.试写一算法,将X拔出到L的适当位置上,以坚持线性表L的有序性.[提示]：void insert(SeqList *L; ElemType x)< 办法1 >（1）找出应拔出位置i,（2）移位,（3）……< 办法2 > 参P. 2292.5 写一算法,从顺序表中删除自第i个元素开始的k个元素.[提示]：注意检查i和k的合法性.（集体搬家,“新房”、“旧房”）< 办法1 > 以待移动元素下标m（“旧房号”）为中心,计算应移入位置（“新房号”）：for ( m= i－1+k; m<= L－>last; m++)L－>elem[ m－k ] = L－>elem[ m ];< 办法2 > 同时以待移动元素下标m和应移入位置j为中心：< 办法3 > 以应移入位置j为中心,计算待移动元素下标：2.6已知线性表中的元素（整数）以值递增有序排列,并以单链表作存储结构.试写一高效算法,删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素）,阐发你的算法的时间庞杂度（注意：mink和maxk是给定的两个参变量,它们的值为任意的整数）.[提示]：注意检查mink和maxk的合法性：mink < maxk不要一个一个的删除（多次修改next域）.（1）找到第一个应删结点的前驱prepre=L; p=L－>next;while (p!=NULL && p－>data <= mink){ pre=p; p=p－>next; }（2）找到最后一个应删结点的后继s,边找边释放应删结点s=p;while (s!=NULL && s－>data < maxk){ t =s; s=s－>next; free(t); }（3）pre－>next = s;2.7试辨别以不合的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）.（1）以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum个份量中.（2）以单链表作存储结构.[办法1]：在原头结点后重新头插一遍[办法2]：可设三个同步移动的指针p, q, r,将q的后继r改成p2.8 假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表（即A表和B表的）结点空间存放表C.[提示]：参P.28 例2-1< 办法1 >void merge(LinkList A; LinkList B; LinkList *C){ ……pa=A－>next; pb=B－>next;*C=A; (*C)－>next=NULL;while ( pa!=NULL && pb!=NULL ){if ( pa－>data <= pb－>data ){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next; /* 头插法 */(*C)－>next = smaller;}else{smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}}while ( pa!=NULL){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}while ( pb!=NULL){smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}< 办法2 >LinkList merge(LinkList A; LinkList B){ ……LinkList C；pa=A－>next; pb=B－>next;C=A; C－>next=NULL;…………return C;2.9 假设有一个循环链表的长度大于1,且表中既无头结点也无头指针.已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前趋结点.[提示]：设指针p指向s结点的前趋的前趋,则p与s有何关系？2.10 已知有单链表暗示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符）,试编写算法来机关三个以循环链表暗示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间.2.11 设线性表A=(a1, a2,…,am),B=(b1, b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得：C= (a1, b1,…,am, bm, bm+1, …,bn)当m≤n时；或者C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时.线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间组成.注意：单链表的长度值m和n均未显式存储.[提示]：void merge(LinkList A; LinkList B; LinkList *C)或：LinkList merge(LinkList A; LinkList B)2.12 将一个用循环链表暗示的稀疏多项式分化成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来组成这两个链表.[提示]：注明用头指针还是尾指针.2.13 建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位.并在此链表上实现对二进制数加1的运算.[提示]：可将低位放在前面.2.14 设多项式P(x)采取课本中所述链接办法存储.写一算法,对给定的x值,求P(x)的值.[提示]：float PolyValue(Polylist p; float x) {……}实习题1．将若干城市的信息存入一个带头结点的单链表,结点中的城市信息包含城市名、城市的位置坐标.要求：（1）给定一个城市名,前往其位置坐标；（2）给定一个位置坐标P和一个距离D,前往所有与P的距离小于等于D的城市.2．约瑟夫环问题.约瑟夫问题的一种描述是：编号为1,2,…,n的n团体按顺时针标的目的围坐一圈,每人持有一个密码（正整数）.一开始任选一个整数作为报数上限值m,从第一团体开始顺时针自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针标的目的上的下一团体开始重新从1报数,如此下去,直至所有的人全部出列为止.试设计一个程序,求出出列顺序.利用单向循环链表作为存储结构模拟此过程,依照出列顺序打印出大家的编号.例如m的初值为20；n=7,7团体的密码依次是：3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5.第二章答案实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,…,n的n团体按顺时针标的目的围坐一圈,每团体持有一个密码（正整数）.一开始任选一个报数上限值m,从第一团体开始顺时针自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针标的目的上的下一团体开始重新从1报数,如此下去,直至所有的人全部出列为止.试设计一个程序,求出出列顺序.利用单向循环链表作为存储结构模拟此过程,依照出列顺序打印出大家的编号.例如,m的初值为20；n=7,7团体的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5.【解答】算法如下：typedef struct Node{int password;int num;struct Node *next;} Node,*Linklist;void Josephus(){Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/if(L==NULL) { printf("\n链表申请不到空间!");return;} L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d团体的密码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n"); printf("出列的顺序为:\n");q=L;p=L->next;while(n!=1)/*计算出列的顺序*/{j=1;while(j<m)/*计算当前出列的人选p*/{q=p;/*q为当前结点p的前驱结点*/p=p->next;j++;}printf("%d->",p->num);m=p->password; /*获得新密码*/ n--;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}2.7试辨别以不合的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表（a1,a2,…,an）逆置为(an,an-1,…,a1).【解答】（1）用一维数组作为存储结构void invert(SeqList *L, int *num) {int j;ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表作为存储结构void invert(LinkList L){Node *p, *q, *r;if(L->next ==NULL) return; /*链表为空*/p=L->next;q=p->next;p->next=NULL; /* 摘下第一个结点,生成初始逆置表 */while(q!=NULL) /* 从第二个结点起依次头拔出当前逆置表 */{r=q->next;q->next=L->next;L->next=q;q=r;}}2.11将线性表A=(a1,a2,……am), B=(b1,b2,……bn)合并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时,或C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构,且C表利用A表和B表中的结点空间组成.注意：单链表的长度值m和n均未显式存储.【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C){Node *pa, *qa, *pb, *qb, *p;pa=A->next; /*pa 暗示A的当前结点*/pb=B->next;p=A; / *利用p来指向新连接的表的表尾,初始值指向表A 的头结点*/while(pa!=NULL && pb!=NULL) /*利用尾插法建立连接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa; /*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL) p->next=pa; /*A的长度大于B 的长度*/if(pb!=NULL) p->next=pb; /*B的长度大于A 的长度*/C=A;return(C);}第3章限定性线性表—栈和队列习题1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度,回答：⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么？123、213、132、231、321（312）⑵如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因.（即写出以“S”暗示进栈、以“X”暗示出栈的栈操纵序列）.SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 设队列中有A、B、C、D、E这5个元素,其中队首元素为A.如果对这个队列重复执行下列4步操纵：（1）输出队首元素；（2）把队首元素值拔出到队尾；（3）删除队首元素；（4）再次删除队首元素.直到队列成为空队列为止,则是否可能得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C[提示]：A、B、C、D、E （输出队首元素A）A、B、C、D、E、A （把队首元素A拔出到队尾）B、C、D、E、A （删除队首元素A）C、D、E、A （再次删除队首元素B）C、D、E、A （输出队首元素C）C、D、E、A、C （把队首元素C拔出到队尾）D、E、A、C （删除队首元素C）E、A、C （再次删除队首元素D）3. 给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满？4. 依照四则运算加、减、乘、除和幂运算（↑）优先关系的常规,画出对下列算术表达式求值时操纵数栈和运算符栈的变更过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5. 试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1& 序列2’模式的字符序列.其中序列1和序列2中都不含字符’&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.[提示]：（1）边读边入栈,直到&（2）边读边出栈边比较,直到……6. 假设表达式由单字母变量和双目四则运算算符组成.试写一个算法,将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）.[提示]：例：中缀表达式：a+b后缀表达式: ab+中缀表达式：a+b×c后缀表达式: abc×+中缀表达式：a+b×c-d后缀表达式: abc×+d-中缀表达式：a+b×c-d/e后缀表达式: abc×+de/-中缀表达式：a+b×(c-d)-e/f后缀表达式: abcd-×+ef/-•后缀表达式的计算过程：（简便）顺序扫描表达式,（1）如果是操纵数,直接入栈；（2）如果是操纵符op,则连续退栈两次,得操纵数X, Y,计算X op Y,并将结果入栈.•如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式,（1）如果是操纵数,直接输出；（2）如果是操纵符op2,则与栈顶操纵符op1比较：如果op2 > op1,则op2入栈；如果op2 = op1,则脱括号；如果op2 < op1,则输出op1；7. 假设以带头结点的循环链表暗示队列,并且只设一个指针指向队尾元素结点（注意不设头指针）,试编写相应的队列初始化、入队列和出队列的算法.[提示]：参P.56 P.70 先画图.typedef LinkListCLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标记域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法.[提示]：初始状态：front==0, rear==0, tag==0队空条件：front==rear, tag==0队满条件：front==rear, tag==1其它状态：front !=rear, tag==0（或1、2）入队操纵：……（入队）if (front==rear) tag=1；（或直接tag=1）出队操纵：……（出队）tag=0；[问题]：如何明确区分队空、队满、非空非满三种情况？9. 简述以下算法的功效（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ iint i, n, A[255];n=0;{n++;Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}将栈S逆序.（2）void proc_2(Stack S, int e) {Stack T; int d;InitStack(&T);while(!EmptyStack(S)){Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){Pop(&T, &d);Push( &S, d);}}删除栈S中所有等于e的元素.（3）void proc_3(Queue *Q){Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}{Pop(&S, &d);EnterQueue(Q,d)}}将队列Q逆序.实习题1．回文判断.称正读与反读都相同的字符序列为“回文”序列.试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1&序列2’模式的字符序列.其中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.2．停车场办理.设停车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出.在停车场内,汽车按到达的先后次序,由北向南依次排列（假设大门在最南端）.若车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入.当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序前往车场.每辆车离开停车场时,应按其停留时间的长短交费（在便道上停留的时间不收费）.试编写程序,模拟上述办理过程.要求以顺序栈模拟停车场,以链队列模拟便道.从终端读入汽车到达或离去的数据,每组数据包含三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻.与每组输入信息相应的输出信息为：如果是到达的车辆,则输出其在停车场中或便道上的位置；如果是离去的车辆,则输出其在停车场中停留的时间和应交的用度.（提示：需另设一个栈,临时停放为让路而从车场退出的车.）3．商品货架办理.,栈底商品的生产日期最近.上货时,需要倒货架,以包管生产日期较近的商品在较下的位置.用队列和栈作为周转,实现上述办理过程.第三章答案3.1按3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度,回答：（1）如进站的车厢序列为123,则可能得到的出站车厢序列是什么？（2）如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因（即写出以“S”暗示进栈、“X”暗示出栈的栈序列操纵）.【解答】（1）可能得到的出站车厢序列是：123、132、213、231、321.（2）不克不及得到435612的出站序列.因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时依照“后进先出”的原则,出栈的顺序必须为X(2)X(1).能得到135426的出站序列.因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1).3.3给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top用来存放栈顶元素的下标）判断栈S空：如果S->top==-1暗示栈空.判断栈S满：如果S->top==Stack_Size-1暗示栈满.（2）链栈（top为栈顶指针,指向当前栈顶元素前面的头结点）判断栈空：如果top->next==NULL暗示栈空.判断栈满：当系统没有可用空间时,申请不到空间存放要进栈的元素,此时栈满.3.4 照四则运算加、减、乘、除和幂运算的优先常规,画出对下列表达式求值时操纵数栈和运算符栈的变更过程：A-B*C/D+E↑F 【解答】3.5写一个算法,判断依次读入的一个以@为结束符的字母序列,是否形如‘序列1&序列2’的字符序列.序列1和序列2中都不含‘&’,且序列2是序列1 的逆序列.例如,’a+b&b+a’是属于该模式的字符序列,而’1+3&3-1’则不是.【解答】算法如下：int IsHuiWen(){Stack *S;Char ch,temp;InitStack(&S);Printf(“\n请输入字符序列：”);Ch=getchar();While( ch!=&) /*序列1入栈*/{Push(&S,ch);ch=getchar();}do /*判断序列2是否是序列1的逆序列*/{ch=getchar();Pop(&S,&temp);if(ch!= temp) /*序列2不是序列1的逆序列*/{return(FALSE); printf(“\nNO”);}} while(ch!=@ && !IsEmpty(&S))if(ch = = @ && IsEmpty(&S)){ return(TRUE); printf(“\nYES”);} /*序列2是序列1的逆序列*/else{return(FALSE); printf(“\nNO”);} }/*IsHuiWen()*/3.8 要求循环队列不损失一个空间全部都能得到利用,设置一个标记tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法.【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x){ /*将元素x入队*/if(Q->front==Q->front && tag==1) /*队满*/return(FALSE);if(Q->front==Q->front && tag==0) /*x入队前队空,x入队后重新设置标记*/tag=1;Q->elememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE);}出队算法：int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*删除队头元素,用x前往其值*/if(Q->front==Q->rear && tag==0) /*队空*/return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ if(Q->front==Q->rear) tag=0; /*队头元素出队后队列为空,重新设置标记域*/Return(TUUE);}编写求解Hanoi问题的算法,并给出三个盘子挪动转移时的递归调用过程.【解答】算法：void hanoi (int n ,char x, char y, char z){ /*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上,Y可用做帮助塔座*/if(n = =1)move(x,1,z);else{ Hanoi(n-1,x,z,y);move(x, n, z);Hanoi(n-1, y,x,z);}}Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C) move(A->C) 1号搬到CMove(A->B) 2号搬到BHanoi(1,C,A,B) move(C->B) 1号搬到BMove(A->C) 3号搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A) move(B->A) 1号搬到AMove(B->C) 2号搬到CHanoi(1,A,B,C) move(A->C) 1号搬到C第4章串习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’.给出下列操纵的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrWordStr(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));[参考答案]StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6;StrWordStr(s,’STUDENT’,q)= ’I AM A WORKER’;StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’;2. 编写算法,实现串的基本操纵StrWordStr(S,T,V).3. 假设以块链结构暗示串,块的大小为1,且附设头结点.试编写算法,实现串的下列基本操纵：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len). [说明]：用单链表实现.4. 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值.5. 已知：S=”(xyz)*”,T=”(x+z)*y”.试利用联接、求子串和置换等操纵,将S转换为T.6. S和T是用结点大小为1的单链表存储的两个串,设计一个算法将串S中首次与T匹配的子串逆置.7. S是用结点大小为4的单链表存储的串,辨别编写算法在第k 个字符后拔出串T,及从第k个字符删除len个字符.以下算法用定长顺序串：8. 写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符.（2）将顺序串r中所有字符依照相反的次序仍存放在r中.（3）从顺序串r中删除其值等于ch的所有字符.（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置.（5）从顺序串r中删除所有与串r1相同的子串.9. 写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换.[提示]：（1）用静态顺序串（2）先移位,后复制10. 写算法,实现顺序串的基本操纵StrCompare(s,t).11. 写算法,实现顺序串的基本操纵StrWordStr(&s,t,v).[提示]：（1）被替换子串定位（相当于第9题中i）（2）被替换子串后面的字符左移或右移（为替换子串准备房间）（3）替换子串入住（复制）（4）重复上述,直到……第四章答案4.1 设s=’I AM A STUDENT’,t=’GOOD’, q=’WORKER’.给出下列操纵的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1=’IAM A ’;SubString(sub2,s,7,1) sub2=’ ’;StrIndex(s,4,’A’)=6;S trWordStr(s,’STUDENT’,q); s=’I AMA WORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’I AM A GOOD WORKER’.4.2编写算法,实现串的基本操纵StrWordStr(S,T,V).【解答】算法如下：int strWordStr(SString S,SString T, SString V){/*用串V替换S中的所有子串T */int pos,i;pos=strIndex(S,1,T); /*求S中子串T第一次出现的位置*/if(pos = = 0) return(0);while(pos!=0) /*用串V替换S中的所有子串T */{switch(T.len-V.len){case 0: /*串T的长度等于串V的长度*/for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];case >0: /*串T的长度大于串V的长度*/for(i=pos+t.ien;i<S->len;i--)/*将S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len个位置*/for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case <0: /*串T的长度小于串V的长度*/if(S->len-T.len+V.len)<= MAXLEN /*拔出后串长小于MAXLEN*/{ /*将S中子串T后的所有字符后移V.len-T.len个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len; }else{ /*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN){ for(i=MAXLEN-1;i>=pos+T.len; i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else /*串V的部分字符要舍弃*/{ for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/}/*while()*/return(1);}/*StrWordStr()*/附加题：用链式结构实现定位函数.【解答】typedef struct Node{ char data;struct Node *next;}Node,*Lstring;int strIndex(Lstring S, int pos, Lstring T)/*从串S的pos序号起,串T第一次出现的位置 */{Node *p, *q, *Ppos;int i=0,,j=0;if(T->next= =NULL || S->next = =NULL) return(0);p=S->next;q=T->next;while(p!=NULL && j<pos) /*p指向串S中第pos个字符*/{p=p->next; j++;}if(j!=pos) return(0);while(p!=NULL && q!=NULL){Ppos=p; /*Ppos指向当前匹配的起始字符*/if(p->data = = q->data){p=p->next; q=q->next;}else /*从Ppos指向字符的下一个字符起从新匹配*/{p=Ppos->next;q=T->head->next;i++;}}if(q= =NULL) return(pos+i); /*匹配成功*/else return(0); /*失败*/}第五章数组和广义表习题1. 假设有6行8列的二维数组A,每个元素占用6个字节,存储器按字节编址.已知A的基地址为1000,计算：（1）数组A共占用多少字节；（288）（2）数组A的最后一个元素的地址；（1282）（3）按行存储时,元素A36的地址；（1126）（4）按列存储时,元素A36的地址；（1192）[注意]：本章自定义数组的下标从1开始.2．设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得B[k]= aij,求：（1）用i,j暗示k的下标变换公式；（2）用k暗示i,j的下标变换公式.i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3或：i = k/3 + 1, j = k - 2×( k/3 )3. 假设稀疏矩阵A和B均以三元组表作为存储结构.试写出矩阵相加的算法,另设三元组表C存放结果矩阵.[提示]：参考P.28例、P.47例.4．在稀疏矩阵的快速转置算法 5.2中,将计算position[col]的办法稍加修改,使算法只占用一个帮助向量空间.[提示]：（1）position[ k ] 中为第k列非零元素个数,k = 1, 2, …, n（2）position[ 0 ] = 1; （第1列中第一个非零元素的正确位置）（3）position[ k ] = position[ k – 1 ] + position[ k ] , k = 1, 2, …, n（4）position[ k ] = position[ k – 1 ] , k = n, n– 1 , … ,15．写一个在十字链表中删除非零元素aij 的算法.[提示]：“删除”两次,释放一次.6．画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))7（（（（（8位,O(n). 9．假设按低下标优先（以最左的下标为主序）存储整数数组A （1:8, 1:2, 1:4, 1:7）时,第一个元素的字节地址是100,每个整数占4个字节,问元素A(4, 2, 3, 5)的存储地址是什么？10. 高低标优先（以最右的下标为主序）存储整数数组A （1:8, 1:2, 1:4, 1:7）时,顺序列出数组A 的所有元素.11．试编写一个以三元组形式输出用十字链表暗示的稀疏矩阵中非零元素及其下标的算法.实习题1． 若矩阵Am×n 中的某个元素aij 是第i 行中的最小值,同时又是第j 列中的最大值,则称此元素为该矩阵中的一个马鞍点.假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点.第五章答案5.2三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中,使得B[k]=aij,求：（1）用i,j 暗示k 的下标变第一种存储结构（自底向上看）。

数据结构耿国华c 语言版答案【篇一：《数据结构——c语言描述》习题及答案耿国华 2】题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如 c、或 pascal ）中，指针类型是原子类型。

三、计算下列程序段中x=x+1 的语句频度for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=j;k++)x=x+1;[提示 ]：⋯f(n) = [ (1+2+3+⋯⋯+n) + (12 + 22 + 32 +⋯⋯+ n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：o(f(n)) = o(n3)四、试编写算法求一元多项式pn(x)=a0+a1x+a2x2+a3x3+ ⋯anxn的值 pn(x0) ，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入 ai(i=0,1, ⋯,n), x和 n，输出为 pn(x0). 通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

[提示 ]： float polyvalue(float{ ⋯⋯}核心语句：p=1; (x的零次幂)s=0;i 从 0 到 n 循环s=s+a[i]*p;p=p*x;或：p=x; (x的一次幂)s=a[0];i 从 1 到 n 循环s=s+a[i]*p;p=p*x;a[ ], float x, int n)实习题设计实现抽象数据类型“有理数”。

第1章绪论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一.问答题1. 什么是数据构造？2. 四类根本数据构造的名称与寄义.3. 算法的界说与特征.4. 算法的时光庞杂度.5. 数据类型的概念.6. 线性构造与非线性构造的不同.7. 面向对象程序设计说话的特色.8. 在面向对象程序设计中,类的感化是什么？9. 参数传递的重要方法及特色.10. 抽象数据类型的概念.二.断定题1. 线性构造只能用次序构造来存放,非线性构造只能用非次序构造来存放.2. 算法就是程序.3. 在高等说话（如C.或 PASCAL）中,指针类型是原子类型.三.盘算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提醒]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法庞杂度：O(f(n)) = O(n3)四.试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0),并肯定算法中的每一语句的履行次数和全部算法的时光庞杂度,请求时光庞杂度尽可能的小,划定算法中不克不及应用求幂函数.留意：本题中的输入a i(i=0,1,…,n), x和n,输出为P n(x0).平日算法的输入和输出可采取下列两种方法之一：（1）经由过程参数表中的参数显式传递;（2）经由过程全局变量隐式传递.试评论辩论这两种办法的优缺陷,并在本题算法中以你以为较好的一种方法实现输入和输出.[提醒]：float PolyValue(float a[ ], float x, int n) {……}焦点语句：p=1; (x的零次幂)s=0;i从0到n轮回s=s+a[i]*p;p=p*x;或：p=x; (x的一次幂)s=a[0];i从1到n轮回s=s+a[i]*p;p=p*x;练习题设计实现抽象数据类型“有理数”.根本操纵包含有理数的加法.减法.乘法.除法,以及求有理数的分子.分母.第一章答案盘算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法,求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并肯定算法中每一语句的履行次数和全部算法的时光庞杂度,请求时光庞杂度尽可能小,划定算法中不克不及应用求幂函数.留意：本题中的输入为a i(i=0,1,…n).x和n,输出为P n(x0).算法的输入和输出采取下列办法（1）经由过程参数表中的参数显式传递（2）经由过程全局变量隐式传递.评论辩论两种办法的优缺陷,并在算法中以你以为较好的一种实现输入输出.【解答】（1）经由过程参数表中的参数显式传递长处：当没有挪用函数时,不占用内存,挪用停滞后形参被释放,实参保持,函数通用性强,移置性强.缺陷：形参须与实参对应,且返回值数目有限.（2）经由过程全局变量隐式传递长处：削减实介入形参的个数,从而削减内存空间以及传递数据时的时光消费缺陷：函数通用性下降,移植性差算法如下：经由过程全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); /*履行次数：n次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*履行次数：n次*/x=x*x;}printf(“%f”,p);}算法的时光庞杂度：T(n)=O(n)经由过程参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*履行次数:n次*/p=p*x;}return(p);}算法的时光庞杂度：T(n)=O(n)第2章线性表习题2.1 描写以下三个概念的差别：头指针,头结点,首元素结点.2.2 填空：（1）在次序表中拔出或删除一个元素,须要平均移动＿＿一半＿＿元素,具体移动的元素个数与＿＿拔出或删除的地位＿＿有关.（2）在次序表中,逻辑上相邻的元素,其物理地位＿＿＿＿＿＿相邻.在单链表中,逻辑上相邻的元素,其物理地位＿＿＿＿＿＿相邻.（3）在带头结点的非空单链表中,头结点的存储地位由＿＿＿＿＿＿指导,首元素结点的存储地位由＿＿＿＿＿＿指导,除首元素结点外,其它任一元素结点的存储地位由＿＿其直接前趋的next域＿＿指导.2.3 已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点.按请求从下列语句中选择适合的语句序列.a. 在P结点后拔出S结点的语句序列是：＿（4）.（1）＿.b. 在P结点前拔出S结点的语句序列是：（7）.（11）.（8）.（4）.（1）.c. 在表首拔出S结点的语句序列是：（5）.（12）.d. 在表尾拔出S结点的语句序列是：（11）.（9）.（1）.（6）.供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递增有序.试写一算法,将X拔出到L的恰当地位上,以保持线性表L的有序性.[提醒]：void insert(SeqList *L; ElemType x)< 办法1 >（1）找出应拔出地位i,（2）移位,（3）……< 办法2 > 参P. 2292.5 写一算法,从次序表中删除自第i个元素开端的k个元素.[提醒]：留意检讨i和k的正当性.（集体搬家,“新房”.“旧房”）< 办法1 > 以待移动元素下标m（“旧房号”）为中间,盘算应移入地位（“新房号”）：for ( m= i－1+k; m<= L－>last; m++)L－>elem[ m－k ] = L－>elem[ m ];< 办法2 > 同时以待移动元素下标m和应移入地位j为中间：< 办法3 > 以应移入地位j为中间,盘算待移动元素下标：已知线性表中的元素（整数）以值递增有序分列,并以单链表作存储构造.试写一高效算法,删除表中所有大于mink且小于maxk的元素（若表中消失如许的元素）,剖析你的算法的时光庞杂度（留意：mink和maxk是给定的两个参变量,它们的值为随意率性的整数）.[提醒]：留意检讨mink和maxk的正当性：mink < maxk不要一个一个的删除（多次修正next域）.（1）找到第一个应删结点的前驱prepre=L; p=L－>next;while (p!=NULL && p－>data <= mink){ pre=p; p=p－>next; }（2）找到最后一个应删结点的后继s,边找边释放应删结点s=p;while (s!=NULL && s－>data < maxk){ t =s; s=s－>next; free(t); }（3）pre－>next = s;试分离以不合的存储构造实现线性表的当场逆置算法,即在原表的存储空间将线性表（a1, a2..., a n）逆置为（a n, a n-1,..., a1）.（1）以一维数组作存储构造,设线性表存于a(1:arrsize)的前elenum个分量中.（2）以单链表作存储构造.[办法1]：在原头结点后从新头插一遍[办法2]：可设三个同步移动的指针p, q, r,将q的后继r改为p2.8 假设两个按元素值递增有序分列的线性表A和B,均以单链表作为存储构造,请编写算法,将A表和B表归并成一个按元素值递减有序的分列的线性表C,并请求应用原表（即A表和B表的）结点空间存放表C.[提醒]：参P.28 例2-1< 办法1 >void merge(LinkList A; LinkList B; LinkList *C){ ……pa=A－>next; pb=B－>next;*C=A; (*C)－>next=NULL;while ( pa!=NULL && pb!=NULL ){if ( pa－>data <= pb－>data ){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next; /* 头插法 */(*C)－>next = smaller;}else{smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}}while ( pa!=NULL){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}while ( pb!=NULL){smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}< 办法2 >LinkList merge(LinkList A; LinkList B){ ……LinkList C;pa=A－>next; pb=B－>next;C=A; C－>next=NULL;…………return C;2.9 假设有一个轮回链表的长度大于1,且表中既无头结点也无头指针.已知s 为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前趋结点.[提醒]：设指针p指向s结点的前趋的前趋,则p与s有何干系？2.10 已知有单链表暗示的线性表中含有三类字符的数据元素（如字母字符.数字字符和其它字符）,试编写算法来构造三个以轮回链表暗示的线性表,使每个表中只含统一类的字符,且应用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间.2.11 设线性表A=(a1, a2,…,a m),B=(b1, b2,…,b n),试写一个按下列规矩归并A.B为线性表C的算法,使得：C= (a1, b1,…,a m, b m, b m+1,…,b n)当m≤n时;或者 C= (a1, b1,…,a n, b n, a n+1,…,a m) 当m>n时.线性表A.B.C均以单链表作为存储构造,且C表应用A表和B表中的结点空间组成.留意：单链表的长度值m和n均未显式存储.[提醒]：void merge(LinkList A; LinkList B; LinkList *C)或：LinkList merge(LinkList A; LinkList B)2.12 将一个用轮回链表暗示的稀少多项式分化成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并请求应用原链表中的结点空间来组成这两个链表.[提醒]：注明用头指针照样尾指针.2.13 树立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位.并在此链表上实现对二进制数加1的运算.[提醒]：可将低位放在前面.2.14 设多项式P(x)采取教材中所述链接办法存储.写一算法,对给定的x值,求P(x)的值.[提醒]：float PolyValue(Polylist p; float x) {……}练习题1．将若干城市的信息存入一个带头结点的单链表,结点中的城市信息包含城市名.城市的地位坐标.请求：（1）给定一个城市名,返回其地位坐标;（2）给定一个地位坐标P和一个距离D,返回所有与P的距离小于等于D 的城市.2．约瑟夫环问题.约瑟夫问题的一种描写是：编号为1,2,…,n的n小我按顺时针偏向围坐一圈,每人持有一个暗码（正整数）.一开端任选一个整数作为报数上限值m,从第一小我开端顺时针自1开端次序报数,报到m时停滞报数.报m的人出列,将他的暗码作为新的m值,从他在顺时针偏向上的下一小我开端从新从1报数,如斯下去,直至所有的人全体出列为止.试设计一个程序,求出出列次序.应用单向轮回链表作为存储构造模仿此进程,按照出列次序打印出大家的编号.例如m的初值为20;n=7,7小我的暗码依次是：3,1,7,2,4,8,4,出列的次序为6,1,4,7,2,3,5.第二章答案练习题二：约瑟夫环问题约瑟夫问题的一种描写为：编号1,2,…,n的n小我按顺时针偏向围坐一圈,每小我持有一个暗码（正整数）.一开端任选一个报数上限值m,从第一小我开端顺时针自1开端次序报数,报到m时停滞报数.报m的人出列,将他的暗码作为新的m值,从他在顺时针偏向上的下一小我开端从新从1报数,如斯下去,直至所有的人全体出列为止.试设计一个程序,求出出列次序.应用单向轮回链表作为存储构造模仿此进程,按照出列次序打印出大家的编号.例如,m的初值为20;n=7,7小我的暗码依次是：3,1,7,2,4,8,4,出列次序为6,1,4,7,2,3,5.【解答】算法如下：typedef struct Node{int password;int num;struct Node *next;} Node,*Linklist;void Josephus(){Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初始化单向轮回链表*/if(L==NULL) { printf("\n链表申请不到空间!");return;}L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*树立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d小我的暗码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n");printf("出列的次序为:\n");q=L;p=L->next;while(n!=1) /*盘算出列的次序*/{j=1;while(j<m) /*盘算当前出列的人选p*/{q=p; /*q为当前结点p的前驱结点*/p=p->next;j++;}printf("%d->",p->num);m=p->password; /*获得新暗码*/n--;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}试分离以不合的存储构造实现单线表的当场逆置算法,即在原表的存储空间将线性表（a1,a2,…,a n）逆置为(a n,a n-1,…,a1).【解答】（1）用一维数组作为存储构造void invert(SeqList *L, int *num){int j;ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表作为存储构造void invert(LinkList L){Node *p, *q, *r;if(L->next ==NULL) return; /*链表为空*/p=L->next;q=p->next;p->next=NULL; /* 摘下第一个结点,生成初始逆置表 */while(q!=NULL) /* 从第二个结点起依次头拔出当前逆置表 */{r=q->next;q->next=L->next;L->next=q;q=r;}}将线性表A=(a1,a2,……am), B=(b1,b2,……bn)归并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时,或C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A.B.C以单链表作为存储构造,且C表应用A表和B表中的结点空间组成.留意：单链表的长度值m和n均未显式存储.【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C){Node *pa, *qa, *pb, *qb, *p;pa=A->next; /*pa暗示A的当前结点*/pb=B->next;p=A; / *应用p来指向新衔接的表的表尾,初始值指向表A的头结点*/ while(pa!=NULL && pb!=NULL) /*应用尾插法树立衔接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa; /*瓜代选择表A和表B中的结点衔接到新链表中;*/ p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL) p->next=pa; /*A的长度大于B的长度*/ if(pb!=NULL) p->next=pb; /*B的长度大于A的长度*/ C=A;return(C);}第3章限制性线性表—栈和队列习题1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调剂,答复：⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么？123.213.132.231.321（312）⑵如进站的车厢序列为123456,可否得到435612和135426的出站序列,并解释原因.（即写出以“S”暗示进栈.以“X”暗示出栈的栈操纵序列）.SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 设队列中有A.B.C.D.E这5个元素,个中队首元素为A.假如对这个队列反复履行下列4步操纵：（1）输出队首元素;（2）把队首元素值拔出到队尾;（3）删除队首元素;（4）再次删除队首元素.直到队列成为空队列为止,则是否可能得到输出序列：（1） A.C.E.C.C （2） A.C.E（3） A.C.E.C.C.C （4） A.C.E.C[提醒]：A.B.C.D.E （输出队首元素A）A.B.C.D.E.A （把队首元素A拔出到队尾）B.C.D.E.A （删除队首元素A）C.D.E.A （再次删除队首元素B）C.D.E.A （输出队首元素C）C.D.E.A.C （把队首元素C拔出到队尾）D.E.A.C （删除队首元素C）E.A.C （再次删除队首元素D）3. 给出栈的两种存储构造情势名称,在这两种栈的存储构造中若何判别栈空与栈满？4. 按照四则运算加.减.乘.除和幂运算（↑）优先关系的通例,画出对下列算术表达式求值时操纵数栈和运算符栈的变更进程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5. 试写一个算法,断定依次读入的一个以@为停滞符的字母序列,是否为形如‘序列1& 序列2’模式的字符序列.个中序列1和序列2中都不含字符’&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.[提醒]：（1）边读边入栈,直到&（2）边读边出栈边比较,直到……6. 假设表达式由单字母变量和双目四则运算算符组成.试写一个算法,将一个平日书写情势（中缀）且书写准确的表达式转换为逆波兰式（后缀）.[提醒]：例：中缀表达式：a+b后缀表达式: ab+中缀表达式：a+b×c后缀表达式: abc×+中缀表达式：a+b×c-d后缀表达式: abc×+d-中缀表达式：a+b×c-d/e后缀表达式: abc×+de/-中缀表达式：a+b×(c-d)-e/f后缀表达式: abcd-×+ef/-•后缀表达式的盘算进程：（轻便）次序扫描表达式,（1）假如是操纵数,直接入栈;（2）假如是操纵符op,则持续退栈两次,得操纵数X, Y,盘算X op Y,并将成果入栈.•若何将中缀表达式转换为后缀表达式？次序扫描中缀表达式,（1）假如是操纵数,直接输出;（2）假如是操纵符op2,则与栈顶操纵符op1比较：假如op2 > op1,则op2入栈;假如op2 = op1,则脱括号;假如op2 < op1,则输出op1;7. 假设以带头结点的轮回链表暗示队列,并且只设一个指针指向队尾元素结点（留意不设头指针）,试编写响应的队列初始化.入队列和出队列的算法.[提醒]：参P.56 P.70 先绘图.typedef LinkListCLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 请求轮回队列不损掉一个空间全体都能得到应用, 设置一个标记域tag ,以tag为0或1来区分头尾指针雷同时的队列状况的空与满,请编写与此构造响应的入队与出队算法.[提醒]：初始状况：front==0, rear==0, tag==0队空前提：front==rear, tag==0队满前提：front==rear, tag==1其它状况：front !=rear, tag==0（或1.2）入队操纵：……（入队）if (front==rear) tag=1;（或直接tag=1）出队操纵：……（出队）tag=0;[问题]：若何明白区分队空.队满.非空非满三种情形？9. 简述以下算法的功效（个中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ iint i, n, A[255];n=0;while(!EmptyStack(S)){n++;Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}将栈S逆序.（2）void proc_2(Stack S, int e){Stack T; int d;InitStack(&T);while(!EmptyStack(S)){Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){Pop(&T, &d);Push( &S, d);}}删除栈S中所有等于e的元素.（3）void proc_3(Queue *Q){Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){Pop(&S, &d);EnterQueue(Q,d)}}将队列Q逆序.练习题1．回文断定.称正读与反读都雷同的字符序列为“回文”序列.试写一个算法,断定依次读入的一个以@为停滞符的字母序列,是否为形如‘序列1&序列2’模式的字符序列.个中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.2．泊车场治理.设泊车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出.在泊车场内,汽车按到达的先后次序,由北向南依次分列（假设大门在最南端）.若车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入.当泊车场内某辆车要分开时,在它之落后入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序返回车场.每辆车分开泊车场时,应按其逗留时光的长短交费（在便道上逗留的时光不收费）.试编写程序,模仿上述治理进程.请求以次序栈模仿泊车场,以链队列模仿便道.从终端读入汽车到达或离去的数据,每组数据包含三项：①是“到达”照样“离去”;②汽车派司号码;③“到达”或“离去”的时刻.与每组输入信息响应的输出信息为：假如是到达的车辆,则输出其在泊车场中或便道上的地位;假如是离去的车辆,则输出其在泊车场中逗留的时光和应交的费用.（提醒：需另设一个栈,临时停放为让路而从车场退出的车.）3．商品货架治理.,栈底商品的临盆日期比来.上货时,.用队列和栈作为周转,按,答复：（1）如进站的车厢序列为123,则可能得到的出站车厢序列是什么？（2）如进站的车厢序列为123456,可否得到435612和135426的出站序列,并解释原因（即写出以“S”暗示进栈.“X”暗示出栈的栈序列操纵）.【解答】（1）可能得到的出站车厢序列是：123.132.213.231.321.（2）不克不及得到435612的出站序列.因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“落后先出”的原则,出栈的次序必须为X(2)X(1).能得到135426的出站序列.因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1).给出栈的两种存储构造情势名称,在这两种栈的存储构造中若何判别栈空与栈满？【解答】（1）次序栈（top用来存放栈顶元素的下标）断定栈S空：假如S->top==-1暗示栈空.断定栈S满：假如S->top==Stack_Size-1暗示栈满.（2）链栈（top为栈顶指针,指向当前栈顶元素前面的头结点）断定栈空：假如top->next==NULL暗示栈空.断定栈满：当体系没有可用空间时,申请不到空间存放要进栈的元素,此时栈满.3.4 照四则运算加.减.乘.除和幂运算的优先通例,画出对下列表达式求值时操纵数栈和运算符栈的变更进程：A-B*C/D+E↑F【解答】3.5写一个算法,断定依次读入的一个以@为停滞符的字母序列,是否形如‘序列1&序列2’的字符序列.序列1和序列2中都不含‘&’,且序列2是序列1 的逆序列.例如,’a+b&b+a’是属于该模式的字符序列,而’1+3&3-1’则不是.【解答】算法如下：int IsHuiWen(){Stack *S;Char ch,temp;InitStack(&S);Printf(“\n请输入字符序列：”);Ch=getchar();While( ch!=&) /*序列1入栈*/{Push(&S,ch);ch=getchar();}do /*断定序列2是否是序列1的逆序列*/{ch=getchar();。

第1章绪论之勘阻及广创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义.3. 算法的界说与特性.4. 算法的时间复杂度.5. 数据类型的概念.6. 线性结构与非线性结构的分歧.7. 面向对象法式设计语言的特点.8. 在面向对象法式设计中,类的作用是什么？9. 参数传递的主要方式及特点.10. 笼统数据类型的概念.二、判断题1. 线性结构只能用顺序结构来寄存,非线性结构只能用非顺序结构来寄存.2. 算法就是法式.3. 在高级语言（如C、或 PASCAL）中,指针类型是原子类型.三、计算下列法式段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0),并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数.注意：本题中的输入ai(i=0,1,…,n), x和n,输出为Pn(x0).通常算法的输入和输出可采纳下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递.试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出.[提示]：float PolyValue(float a[ ], float x, int n) {……}核心语句：p=1; (x的零次幂)s=0;i从0到n循环s=s+a[i]*p;p=p*x;或：p=x; (x的一次幂)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;实习题设计实现笼统数据类型“有理数”.基本把持包括有理数的加法、减法、乘法、除法,以及求有理数的分子、分母.第一章谜底1.3计算下列法式中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法,求pn(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数.注意：本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(x0).算法的输入和输出采纳下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递.讨论两种方法的优缺点,并在算法中以你认为较好的一种实现输入输出.【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强.缺点：形参须与实参对应,且返回值数量有限.（2）通过全局变量隐式传递优点：减少实介入形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低,移植性差算法如下：通过全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); /*执行次数：n次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*执行次数：n次*/ x=x*x;}printf(“%f”,p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n)第2章线性表习题2.1 描述以下三个概念的区别：头指针,头结点,首元素结点. 2.2 填空：（1）在顺序表中拔出或删除一个元素,需要平均移动＿＿一半＿＿元素,具体移动的元素个数与＿＿拔出或删除的位置＿＿有关.（2）在顺序表中,逻辑上相邻的元素,其物理位置＿＿＿＿＿＿相邻.在单链表中,逻辑上相邻的元素,其物理位置＿＿＿＿＿＿相邻.（3）在带头结点的非空单链表中,头结点的存储位置由＿＿＿＿＿＿指示,首元素结点的存储位置由＿＿＿＿＿＿指示,除首元素结点外,其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示.2.3 已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点.按要求从下列语句中选择合适的语句序列.a. 在P结点后拔出S结点的语句序列是：＿（4）、（1）＿.b. 在P结点前拔出S结点的语句序列是：（7）、（11）、（8）、（4）、（1）.c. 在表首拔出S结点的语句序列是：（5）、（12）.d. 在表尾拔出S结点的语句序列是：（11）、（9）、（1）、（6）.供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递增有序.试写一算法,将X拔出到L的适当位置上,以坚持线性表L的有序性.[提示]：void insert(SeqList *L; ElemType x)< 方法1 >（1）找出应拔出位置i,（2）移位,（3）……< 方法2 > 参P. 2292.5 写一算法,从顺序表中删除自第i个元素开始的k个元素.[提示]：注意检查i和k的合法性.（集体搬场,“新房”、“旧房”）< 方法1 > 以待移动元素下标m（“旧房号”）为中心,计算应移入位置（“新房号”）：for ( m= i－1+k; m<= L－>last; m++)L－>elem[ m－k ] = L－>elem[ m ];< 方法2 > 同时以待移动元素下标m和应移入位置j为中心：< 方法3 > 以应移入位置j为中心,计算待移动元素下标：2.6已知线性表中的元素（整数）以值递增有序排列,并以单链表作存储结构.试写一高效算法,删除表中所有年夜于mink且小于maxk的元素（若表中存在这样的元素）,分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量,它们的值为任意的整数）.[提示]：注意检查mink和maxk的合法性：mink < maxk不要一个一个的删除（屡次修改next域）.（1）找到第一个应删结点的前驱prepre=L; p=L－>next;while (p!=NULL && p－>data <= mink){ pre=p; p=p－>next; }（2）找到最后一个应删结点的后继s,边找边释放应删结点s=p;while (s!=NULL && s－>data < maxk){ t =s; s=s－>next; free(t); }（3）pre－>next = s;2.7试分别以分歧的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）.（1）以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum个分量中.（2）以单链表作存储结构.[方法1]：在原头结点后重新头插一遍[方法2]：可设三个同步移动的指针p, q, r,将q的后继r改为p2.8 假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递加有序的排列的线性表C,并要求利用原表（即A表和B表的）结点空间寄存表C.[提示]：参P.28 例2-1< 方法1 >void merge(LinkList A; LinkList B; LinkList *C){ ……pa=A－>next; pb=B－>next;*C=A; (*C)－>next=NULL;while ( pa!=NULL && pb!=NULL ){if ( pa－>data <= pb－>data ){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next; /* 头插法 */(*C)－>next = smaller;}else{smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}}while ( pa!=NULL){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}while ( pb!=NULL){smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}< 方法2 >LinkList merge(LinkList A; LinkList B){ ……LinkList C；pa=A－>next; pb=B－>next;C=A; C－>next=NULL;…………return C;2.9 假设有一个循环链表的长度年夜于1,且表中既无头结点也无头指针.已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前趋结点.[提示]：设指针p指向s结点的前趋的前趋,则p与s有何关系？2.10 已知有单链表暗示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符）,试编写算法来构造三个以循环链表暗示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间.2.11 设线性表A=(a1, a2,…,am),B=(b1, b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得：C= (a1, b1,…,am, bm, bm+1, …,bn)当m≤n时；或者C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时.线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成.注意：单链表的长度值m和n均未显式存储.[提示]：void merge(LinkList A; LinkList B; LinkList *C)或：LinkList merge(LinkList A; LinkList B)2.12 将一个用循环链表暗示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表.[提示]：注明用头指针还是尾指针.2.13 建立一个带头结点的线性链表,用以寄存输入的二进制数,链表中每个结点的data域寄存一个二进制位.并在此链表上实现对二进制数加1的运算.[提示]：可将低位放在前面.2.14 设多项式P(x)采纳课本中所述链接方法存储.写一算法,对给定的x值,求P(x)的值.[提示]：float PolyValue(Polylist p; float x) {……}实习题1．将若干城市的信息存入一个带头结点的单链表,结点中的城市信息包括城市名、城市的位置坐标.要求：（1）给定一个城市名,返回其位置坐标；（2）给定一个位置坐标P和一个距离D,返回所有与P的距离小于即是D的城市.2．约瑟夫环问题.约瑟夫问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码（正整数）.一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.试设计一个法式,求出出列顺序.利用单向循环链表作为存储结构模拟此过程,依照出列顺序打印出各人的编号.例如m的初值为20；n=7,7个人的密码依次是：3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5.第二章谜底实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码（正整数）.一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m 时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.试设计一个法式,求出出列顺序.利用单向循环链表作为存储结构模拟此过程,依照出列顺序打印出各人的编号.例如,m的初值为20；n=7,7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5.【解答】算法如下：typedef struct Node{int password;int num;struct Node *next;} Node,*Linklist;void Josephus(){Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/if(L==NULL) { printf("\n链表申请不到空间!");return;} L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d个人的密码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n"); printf("出列的顺序为:\n");q=L;p=L->next;while(n!=1)/*计算出列的顺序*/{j=1;while(j<m)/*计算以后出列的人选p*/{q=p;/*q为以后结点p的前驱结点*/p=p->next;j++;}printf("%d->",p->num);m=p->password; /*获得新密码*/ n--;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}2.7试分别以分歧的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表（a1,a2,…,an）逆置为(an,an-1,…,a1).【解答】（1）用一维数组作为存储结构void invert(SeqList *L, int *num) {int j;ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表作为存储结构void invert(LinkList L){Node *p, *q, *r;if(L->next ==NULL) return; /*链表为空*/p=L->next;q=p->next;p->next=NULL; /* 摘下第一个结点,生成初始逆置表 */while(q!=NULL) /* 从第二个结点起依次头拔出以后逆置表 */{r=q->next;q->next=L->next;L->next=q;q=r;}}2.11将线性表A=(a1,a2,……am), B=(b1,b2,……bn)合并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时,或C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构,且C表利用A表和B表中的结点空间构成.注意：单链表的长度值m和n均未显式存储.【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C){Node *pa, *qa, *pb, *qb, *p;pa=A->next; /*pa 暗示A的以后结点*/pb=B->next;p=A; / *利用p来指向新连接的表的表尾,初始值指向表A 的头结点*/while(pa!=NULL && pb!=NULL) /*利用尾插法建立连接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa; /*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL) p->next=pa; /*A的长度年夜于B的长度*/if(pb!=NULL) p->next=pb; /*B的长度年夜于A的长度*/C=A;return(C);}第3章限定性线性表—栈和队列习题1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车箱调度,回答：⑴如进站的车箱序列为123,则可能获得的出站车箱序列是什么？123、213、132、231、321（312）⑵如进站的车箱序列为123456,能否获得435612和135426的出站序列,并说明原因.（即写出以“S”暗示进栈、以“X”暗示出栈的栈把持序列）.SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 设队列中有A、B、C、D、E这5个元素,其中队首元素为A.如果对这个队列重复执行下列4步把持：（1）输出队首元素；（2）把队首元素值拔出到队尾；（3）删除队首元素；（4）再次删除队首元素.直到队列成为空队列为止,则是否可能获得输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C[提示]：A、B、C、D、E （输出队首元素A）A、B、C、D、E、A （把队首元素A拔出到队尾）B、C、D、E、A （删除队首元素A）C、D、E、A （再次删除队首元素B）C、D、E、A （输出队首元素C）C、D、E、A、C （把队首元素C拔出到队尾）D、E、A、C （删除队首元素C）E、A、C （再次删除队首元素D）3. 给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满？4. 依照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例,画出对下列算术表达式求值时把持数栈和运算符栈的变动过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5. 试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1& 序列2’模式的字符序列.其中序列1和序列2中都不含字符’&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.[提示]：（1）边读边入栈,直到&（2）边读边出栈边比力,直到……6. 假设表达式由单字母变量和双目四则运算算符构成.试写一个算法,将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）.[提示]：例：中缀表达式：a+b后缀表达式: ab+中缀表达式：a+b×c后缀表达式: abc×+中缀表达式：a+b×c-d后缀表达式: abc×+d-中缀表达式：a+b×c-d/e后缀表达式: abc×+de/-中缀表达式：a+b×(c-d)-e/f后缀表达式: abcd-×+ef/-•后缀表达式的计算过程：（简便）顺序扫描表达式,（1）如果是把持数,直接入栈；（2）如果是把持符op,则连续退栈两次,得把持数X, Y,计算X op Y,并将结果入栈.•如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式,（1）如果是把持数,直接输出；（2）如果是把持符op2,则与栈顶把持符op1比力：如果op2 > op1,则op2入栈；如果op2 = op1,则脱括号；如果op2 < op1,则输出op1；7. 假设以带头结点的循环链表暗示队列,而且只设一个指针指向队尾元素结点（注意不设头指针）,试编写相应的队列初始化、入队列和出队列的算法.[提示]：参P.56 P.70 先画图.typedef LinkListCLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 要求循环队列不损失一个空间全部都能获得利用, 设置一个标识表记标帜域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法. [提示]：初始状态：front==0, rear==0, tag==0队空条件：front==rear, tag==0队满条件：front==rear, tag==1其它状态：front !=rear, tag==0（或1、2）入队把持：……（入队）if (front==rear) tag=1；（或直接tag=1）出队把持：……（出队）tag=0；[问题]：如何明确区分队空、队满、非空非满三种情况？9. 简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ iint i, n, A[255];n=0;while(!EmptyStack(S)){n++;Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}将栈S逆序.（2）void proc_2(Stack S, int e) {Stack T; int d;InitStack(&T);while(!EmptyStack(S)){Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){Pop(&T, &d);Push( &S, d);}}删除栈S中所有即是e的元素.（3）void proc_3(Queue *Q){Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){Pop(&S, &d);EnterQueue(Q,d)}}将队列Q逆序.实习题1．回文判断.称正读与反读都相同的字符序列为“回文”序列.试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1&序列2’模式的字符序列.其中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列.例如,‘a+b&b+a’是属该模式的字符序列,而‘１+３&３－１’则不是.2．停车场管理.设停车场是一个可停放n辆车的狭长通道,且只有一个年夜门可供汽车进出.在停车场内,汽车按达到的先后次第,由北向南依次排列（假设年夜门在最南端）.若车场内已停满n辆车,则后来的汽车需在门外的便道上等待,当有车开走时,便道上的第一辆车即可开入.当停车场内某辆车要离开时,在它之后进入的车辆必需先退出车场为它让路,待该辆车开出年夜门后,其它车辆再按原次第返回车场.每辆车离开停车场时,应按其停留时间的长短交费（在便道上停留的时间不收费）.试编写法式,模拟上述管理过程.要求以顺序栈模拟停车场,以链队列模拟便道.从终端读入汽车达到或离去的数据,每组数据包括三项：①是“达到”还是“离去”；②汽车牌照号码；③“达到”或“离去”的时刻.与每组输入信息相应的输出信息为：如果是达到的车辆,则输出其在停车场中或便道上的位置；如果是离去的车辆,则输出其在停车场中停留的时间和应交的费用.（提示：需另设一个栈,临时停放为让路而从车场退出的车.）3．商品货架管理.,栈底商品的生产日期最近.,以保证生产日期较近的商品在较下的位置.,实现上述管理过程.第三章谜底3.1按3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车箱调度,回答：（1）如进站的车箱序列为123,则可能获得的出站车箱序列是什么？（2）如进站的车箱序列为123456,能否获得435612和135426的出站序列,并说明原因（即写出以“S”暗示进栈、“X”暗示出栈的栈序列把持）.【解答】（1）可能获得的出站车箱序列是：123、132、213、231、321.（2）不能获得435612的出站序列.因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时依照“后进先出”的原则,出栈的顺序必需为X(2)X(1).能获得135426的出站序列.因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1).3.3给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top用来寄存栈顶元素的下标）判断栈S空：如果S->top==-1暗示栈空.判断栈S满：如果S->top==Stack_Size-1暗示栈满.（2）链栈（top为栈顶指针,指向以后栈顶元素前面的头结点）判断栈空：如果top->next==NULL暗示栈空.判断栈满：当系统没有可用空间时,申请不到空间寄存要进栈的元素,此时栈满.3.4 照四则运算加、减、乘、除和幂运算的优先惯例,画出对下列表达式求值时把持数栈和运算符栈的变动过程：A-B*C/D+E↑F 【解答】3.5写一个算法,判断依次读入的一个以@为结束符的字母序列,是否形如‘序列1&序列2’的字符序列.序列1和序列2中都不含‘&’,且序列2是序列1 的逆序列.例如,’a+b&b+a’是属于该模式的字符序列,而’1+3&3-1’则不是.【解答】算法如下：int IsHuiWen(){Stack *S;Char ch,temp;InitStack(&S);Printf(“\n请输入字符序列：”);Ch=getchar();While( ch!=&) /*序列1入栈*/{Push(&S,ch);ch=getchar();}do /*判断序列2是否是序列1的逆序列*/{ch=getchar();Pop(&S,&temp);if(ch!= temp) /*序列2不是序列1的逆序列*/{return(FALSE); printf(“\nNO”);}} while(ch!=@ && !IsEmpty(&S))if(ch = = @ && IsEmpty(&S)){ r eturn(TRUE); printf(“\nYES”);} /*序列2是序列1的逆序列*/else{return(FALSE); printf(“\nNO”);} }/*IsHuiWen()*/3.8 要求循环队列不损失一个空间全部都能获得利用,设置一个标识表记标帜tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法.【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x){ /*将元素x入队*/if(Q->front==Q->front && tag==1) /*队满*/return(FALSE);if(Q->front==Q->front && tag==0) /*x入队前队空,x入队后重新设置标识表记标帜*/tag=1;Q->elememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE);}出队算法：int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*删除队头元素,用x返回其值*/if(Q->front==Q->rear && tag==0) /*队空*/return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ if(Q->front==Q->rear) tag=0; /*队头元素出队后队列为空,重新设置标识表记标帜域*/Return(TUUE);}编写求解Hanoi问题的算法,并给出三个盘子挪动转移时的递归调用过程.【解答】算法：void hanoi (int n ,char x, char y, char z){ /*将塔座X上按直径由小到年夜且至上而下编号为1到n的n 个圆盘按规则搬到塔座Z上,Y可用做辅助塔座*/if(n = =1)move(x,1,z);else{ Hanoi(n-1,x,z,y);move(x, n, z);Hanoi(n-1, y,x,z);}}Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C) move(A->C) 1号搬到CMove(A->B) 2号搬到BHanoi(1,C,A,B) move(C->B) 1号搬到BMove(A->C) 3号搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A) move(B->A) 1号搬到AMove(B->C) 2号搬到CHanoi(1,A,B,C) move(A->C) 1号搬到C第4章串习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’.给出下列把持的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrWordStr(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));[参考谜底]StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6;StrWordStr(s,’STUDENT’,q)= ’I AM A WORKER’;StrCat(St rCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’;2. 编写算法,实现串的基本把持StrWordStr(S,T,V).3. 假设以块链结构暗示串,块的年夜小为1,且附设头结点.试编写算法,实现串的下列基本把持：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len). [说明]：用单链表实现.4. 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值.5. 已知：S=”(xyz)*”,T=”(x+z)*y”.试利用联接、求子串和置换等把持,将S转换为T.6. S和T是用结点年夜小为1的单链表存储的两个串,设计一个算法将串S中首次与T匹配的子串逆置.7. S是用结点年夜小为4的单链表存储的串,分别编写算法在第k 个字符后拔出串T,及从第k个字符删除len个字符.以下算法用定长顺序串：8. 写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符.（2）将顺序串r中所有字符依照相反的次第仍寄存在r中.（3）从顺序串r中删除其值即是ch的所有字符.（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置.（5）从顺序串r中删除所有与串r1相同的子串.9. 写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换.[提示]：（1）用静态顺序串（2）先移位,后复制10. 写算法,实现顺序串的基本把持StrCompare(s,t).11. 写算法,实现顺序串的基本把持StrWordStr(&s,t,v).[提示]：（1）被替换子串定位（相当于第9题中i）（2）被替换子串后面的字符左移或右移（为替换子串准备房间）（3）替换子串入住（复制）（4）重复上述,直到……第四章谜底4.1 设s=’I AM A STUDENT’,t=’GOOD’, q=’WORKER’.给出下列把持的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1=’I AM A ’;SubString(sub2,s,7,1) sub2=’ ’;StrIndex(s,4,’A’)=6;StrWordStr(s,’STUDENT’,q); s=’I AMA WORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’I AM A GOOD WORKER’.4.2编写算法,实现串的基本把持StrWordStr(S,T,V).【解答】算法如下：int strWordStr(SString S,SString T, SString V){/*用串V替换S中的所有子串T */int pos,i;pos=strIndex(S,1,T); /*求S中子串T第一次呈现的位置*/if(pos = = 0) return(0);while(pos!=0) /*用串V替换S中的所有子串T */{switch(T.len-V.len){case 0: /*串T的长度即是串V的长度*/for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];case >0: /*串T的长度年夜于串V的长度*/for(i=pos+t.ien;i<S->len;i--)/*将S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len个位置*/for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case <0: /*串T的长度小于串V的长度*/if(S->len-T.len+V.len)<= MAXLEN /*拔出后串长小于MAXLEN*/{ /*将S中子串T后的所有字符后移V.len-T.len个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len; }else{ /*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN){ for(i=MAXLEN-1;i>=pos+T.len; i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else /*串V的部份字符要舍弃*/{ for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/}/*while()*/return(1);}/*StrWordStr()*/附加题：用链式结构实现定位函数.【解答】typedef struct Node{ char data;struct Node *next;}Node,*Lstring;int strIndex(Lstring S, int pos, Lstring T)/*从串S的pos序号起,串T第一次呈现的位置 */{Node *p, *q, *Ppos;int i=0,,j=0;if(T->next= =NULL || S->next = =NULL) return(0);p=S->next;q=T->next;while(p!=NULL && j<pos) /*p指向串S中第pos个字符*/{p=p->next; j++;}if(j!=pos) return(0);while(p!=NULL && q!=NULL){Ppos=p; /*Ppos指向以后匹配的起始字符*/if(p->data = = q->data){p=p->next; q=q->next;}else /*从Ppos指向字符的下一个字符起重新匹配*/{p=Ppos->next;q=T->head->next;i++;}}if(q= =NULL) return(pos+i); /*匹配胜利*/else return(0); /*失败*/}第五章数组和广义表习题1. 假设有6行8列的二维数组A,每个元素占用6个字节,存储器按字节编址.已知A的基地址为1000,计算：（1）数组A共占用几多字节；（288）（2）数组A的最后一个元素的地址；（1282）（3）按行存储时,元素A36的地址；（1126）（4）按列存储时,元素A36的地址；（1192）[注意]：本章自界说数组的下标从1开始.2．设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得B[k]= aij,求：（1）用i,j暗示k的下标变换公式；（2）用k暗示i,j的下标变换公式.i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3或：i = k/3 + 1, j = k - 2×( k/3 )3. 假设稀疏矩阵A和B均以三元组表作为存储结构.试写出矩阵相加的算法,另设三元组表C寄存结果矩阵.[提示]：参考P.28例、P.47例.4．在稀疏矩阵的快速转置算法 5.2中,将计算position[col]的方法稍加改动,使算法只占用一个辅助向量空间.[提示]：（1）position[ k ] 中为第k列非零元素个数,k = 1, 2, …, n（2）position[ 0 ] = 1; （第1列中第一个非零元素的正确位置）（3）position[ k ] = position[ k – 1 ] + position[ k ] , k = 1, 2, …, n（4）position[ k ] = position[ k – 1 ] , k = n, n – 1 , … ,15．写一个在十字链表中删除非零元素aij的算法.[提示]：“删除”两次,释放一次.6．画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))7（（（（（8位,O(n). 9．假设按低下标优先（以最左的下标为主序）存储整数数组A （1:8, 1:2, 1:4, 1:7）时,第一个元素的字节地址是100,每个整数占4个字节,问元素A(4, 2, 3, 5)的存储地址是什么？10. 高下标优先（以最右的下标为主序）存储整数数组A （1:8, 1:2, 1:4, 1:7）时,顺序列出数组A 的所有元素.11．试编写一个以三元组形式输出用十字链表暗示的稀疏矩阵中非零元素及其下标的算法.实习题1． 若矩阵Am×n 中的某个元素aij 是第i 行中的最小值,同时又是第j 列中的最年夜值,则称此元素为该矩阵中的一个马鞍点.假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点.第五章谜底5.2三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中,使得B[k]=aij,求：（1）用i,j 暗示k 的下标变换公式；第一种存储结构（自底向上看）。

第1章绪论之蔡仲巾千创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的不同。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ]/ 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不克不及使用求幂函数。

注意：本题中的输入ai(i=0,1,…,n), x和n，输出为Pn(x0).通常算法的输入和输出可采取下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。

首元素结点：线性表中的第一个结点成为首元素结点。

4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p);return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。

第1章绪论习题一、问答题1.什么是数据结构2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.~9.在面向对象程序设计中，类的作用是什么10.参数传递的主要方式及特点。

11.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)|for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2:=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n),x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论之马矢奏春创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义.3. 算法的界说与特性.4. 算法的时间复杂度.5. 数据类型的概念.6. 线性结构与非线性结构的分歧.7. 面向对象法式设计语言的特点.8. 在面向对象法式设计中, 类的作用是什么？9. 参数传递的主要方式及特点.10. 笼统数据类型的概念.二、判断题1. 线性结构只能用顺序结构来寄存, 非线性结构只能用非顺序结构来寄存.2. 算法就是法式.3. 在高级语言（如C、或 PASCAL）中, 指针类型是原子类型.三、计算下列法式段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0), 并确定算法中的每一语句的执行次数和整个算法的时间复杂度, 要求时间复杂度尽可能的小, 规定算法中不能使用求幂函数.注意：本题中的输入a i(i=0,1,…,n), x和n, 输出为P n(x0).通常算法的输入和输出可采纳下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递.试讨论这两种方法的优缺点, 并在本题算法中以你认为较好的一种方式实现输入和输出.[提示]：float PolyValue(float a[ ], float x, int n) {……}核心语句：p=1; (x的零次幂)s=0;i从0到n循环s=s+a[i]*p;p=p*x;或：p=x; (x的一次幂)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;实习题设计实现笼统数据类型“有理数”.基本把持包括有理数的加法、减法、乘法、除法, 以及求有理数的分子、分母.第一章谜底计算下列法式中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法, 求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度, 要求时间复杂度尽可能小, 规定算法中不能使用求幂函数.注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0).算法的输入和输出采纳下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递.讨论两种方法的优缺点, 并在算法中以你认为较好的一种实现输入输出.【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时, 不占用内存, 调用结束后形参被释放, 实参维持, 函数通用性强, 移置性强.缺点：形参须与实参对应, 且返回值数量有限.（2）通过全局变量隐式传递优点：减少实介入形参的个数, 从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低, 移植性差算法如下：通过全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); /*执行次数：n次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*执行次数：n次*/ x=x*x;}printf(“%f”,p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n)第2章线性表习题2.1 描述以下三个概念的区别：头指针, 头结点, 首元素结点.2.2 填空：（1）在顺序表中拔出或删除一个元素, 需要平均移动＿＿一半＿＿元素, 具体移动的元素个数与＿＿拔出或删除的位置＿＿有关.（2）在顺序表中, 逻辑上相邻的元素, 其物理位置＿＿＿＿＿＿相邻.在单链表中, 逻辑上相邻的元素, 其物理位置＿＿＿＿＿＿相邻.（3）在带头结点的非空单链表中, 头结点的存储位置由＿＿＿＿＿＿指示, 首元素结点的存储位置由＿＿＿＿＿＿指示, 除首元素结点外, 其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示.2.3 已知L是无表头结点的单链表, 且P结点既不是首元素结点, 也不是尾元素结点.按要求从下列语句中选择合适的语句序列.a. 在P结点后拔出S结点的语句序列是：＿（4）、（1）＿.b. 在P结点前拔出S结点的语句序列是：（7）、（11）、（8）、（4）、（1）.c. 在表首拔出S结点的语句序列是：（5）、（12）.d. 在表尾拔出S结点的语句序列是：（11）、（9）、（1）、（6）.供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递增有序.试写一算法, 将X拔出到L的适当位置上, 以坚持线性表L的有序性.[提示]：void insert(SeqList *L; ElemType x)< 方法1 >（1）找出应拔出位置i, （2）移位, （3）……< 方法2 > 参P. 2292.5 写一算法, 从顺序表中删除自第i个元素开始的k个元素. [提示]：注意检查i和k的合法性.（集体搬场, “新房”、“旧房”）< 方法1 > 以待移动元素下标m（“旧房号”）为中心,计算应移入位置（“新房号”）：for ( m= i－1+k; m<= L－>last; m++)L－>elem[ m－k ] = L－>elem[ m ];< 方法2 > 同时以待移动元素下标m和应移入位置j为中心：< 方法3 > 以应移入位置j为中心, 计算待移动元素下标：已知线性表中的元素（整数）以值递增有序排列, 并以单链表作存储结构.试写一高效算法, 删除表中所有年夜于mink且小于maxk的元素（若表中存在这样的元素）, 分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量, 它们的值为任意的整数）.[提示]：注意检查mink和maxk的合法性：mink < maxk不要一个一个的删除（屡次修改next域）.（1）找到第一个应删结点的前驱prepre=L; p=L－>next;while (p!=NULL && p－>data <= mink){ pre=p; p=p－>next; }（2）找到最后一个应删结点的后继s, 边找边释放应删结点s=p;while (s!=NULL && s－>data < maxk){ t =s; s=s－>next; free(t); }（3）pre－>next = s;试分别以分歧的存储结构实现线性表的就地逆置算法, 即在原表的存储空间将线性表（a1, a2..., a n）逆置为（a n, a n-1,..., a1）.（1）以一维数组作存储结构, 设线性表存于a(1:arrsize)的前elenum个分量中.（2）以单链表作存储结构.[方法1]：在原头结点后重新头插一遍[方法2]：可设三个同步移动的指针p, q, r, 将q的后继r改为p2.8 假设两个按元素值递增有序排列的线性表A和B, 均以单链表作为存储结构, 请编写算法, 将A表和B表归并成一个按元素值递加有序的排列的线性表C, 并要求利用原表（即A表和B表的）结点空间寄存表C.[提示]：参P.28 例2-1< 方法1 >void merge(LinkList A; LinkList B; LinkList *C){ ……pa=A－>next; pb=B－>next;*C=A; (*C)－>next=NULL;while ( pa!=NULL && pb!=NULL ){if ( pa－>data <= pb－>data ){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next; /* 头插法 */(*C)－>next = smaller;}else{smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}}while ( pa!=NULL){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}while ( pb!=NULL){smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}< 方法2 >LinkList merge(LinkList A; LinkList B){ ……LinkList C；pa=A－>next; pb=B－>next;C=A; C－>next=NULL;…………return C;2.9 假设有一个循环链表的长度年夜于1, 且表中既无头结点也无头指针.已知s为指向链表某个结点的指针, 试编写算法在链表中删除指针s所指结点的前趋结点.[提示]：设指针p指向s结点的前趋的前趋, 则p与s有何关系？2.10 已知有单链表暗示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符）, 试编写算法来构造三个以循环链表暗示的线性表, 使每个表中只含同一类的字符, 且利用原表中的结点空间作为这三个表的结点空间, 头结点可另辟空间.2.11 设线性表A=(a1, a2,…,a m), B=(b1, b2,…,b n), 试写一个按下列规则合并A、B为线性表C的算法, 使得：C= (a1, b1,…,a m, b m, b m+1,…,b n)当m≤n时；或者 C= (a1, b1,…,a n, b n, a n+1,…,a m) 当m>n时.线性表A、B、C均以单链表作为存储结构, 且C表利用A表和B表中的结点空间构成.注意：单链表的长度值m和n均未显式存储.[提示]：void merge(LinkList A; LinkList B; LinkList *C)或：LinkList merge(LinkList A; LinkList B)2.12 将一个用循环链表暗示的稀疏多项式分解成两个多项式, 使这两个多项式中各自仅含奇次项或偶次项, 并要求利用原链表中的结点空间来构成这两个链表.[提示]：注明用头指针还是尾指针.2.13 建立一个带头结点的线性链表, 用以寄存输入的二进制数,链表中每个结点的data域寄存一个二进制位.并在此链表上实现对二进制数加1的运算.[提示]：可将低位放在前面.2.14 设多项式P(x)采纳课本中所述链接方法存储.写一算法, 对给定的x值, 求P(x)的值.[提示]：float PolyValue(Polylist p; float x) {……}实习题1．将若干城市的信息存入一个带头结点的单链表, 结点中的城市信息包括城市名、城市的位置坐标.要求：（1）给定一个城市名, 返回其位置坐标；（2）给定一个位置坐标P和一个距离D, 返回所有与P的距离小于即是D的城市.2．约瑟夫环问题.约瑟夫问题的一种描述是：编号为1, 2, …, n的n个人按顺时针方向围坐一圈, 每人持有一个密码（正整数）.一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数, 报到m时停止报数.报m的人出列, 将他的密码作为新的m 值, 从他在顺时针方向上的下一个人开始重新从1报数, 如此下去, 直至所有的人全部出列为止.试设计一个法式, 求出出列顺序.利用单向循环链表作为存储结构模拟此过程, 依照出列顺序打印出各人的编号.例如m的初值为20；n=7, 7个人的密码依次是：3, 1, 7, 2, 4, 8, 4, 出列的顺序为6, 1, 4, 7, 2, 3, 5.第二章谜底实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈, 每个人持有一个密码（正整数）.一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数, 报到m 时停止报数.报m的人出列, 将他的密码作为新的m值, 从他在顺时针方向上的下一个人开始重新从1报数, 如此下去, 直至所有的人全部出列为止.试设计一个法式, 求出出列顺序.利用单向循环链表作为存储结构模拟此过程, 依照出列顺序打印出各人的编号.例如, m的初值为20；n=7, 7个人的密码依次是：3,1,7,2,4,8,4, 出列顺序为6,1,4,7,2,3,5.【解答】算法如下：typedef struct Node{int password;int num;struct Node *next;} Node,*Linklist;void Josephus(){Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/if(L==NULL) { printf("\n链表申请不到空间!");return;} L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d个人的密码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n"); printf("出列的顺序为:\n");q=L;p=L->next;while(n!=1)/*计算出列的顺序*/{j=1;while(j<m)/*计算以后出列的人选p*/{q=p;/*q为以后结点p的前驱结点*/p=p->next;j++;}printf("%d->",p->num);m=p->password; /*获得新密码*/ n--;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}试分别以分歧的存储结构实现单线表的就地逆置算法, 即在原表的存储空间将线性表（a1,a2,…,a n）逆置为(a n,a n-1,…,a1).【解答】（1）用一维数组作为存储结构void invert(SeqList *L, int *num) {int j;ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表作为存储结构void invert(LinkList L){Node *p, *q, *r;if(L->next ==NULL) return; /*链表为空*/p=L->next;q=p->next;p->next=NULL; /* 摘下第一个结点, 生成初始逆置表 */while(q!=NULL) /* 从第二个结点起依次头拔出以后逆置表 */{r=q->next;q->next=L->next;L->next=q;q=r;}}将线性表A=(a1,a2,……am), B=(b1,b2,……bn)合并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时, 或C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构, 且C表利用A表和B表中的结点空间构成.注意：单链表的长度值m和n均未显式存储.【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C){Node *pa, *qa, *pb, *qb, *p;pa=A->next; /*pa 暗示A的以后结点*/pb=B->next;p=A; / *利用p来指向新连接的表的表尾, 初始值指向表A 的头结点*/while(pa!=NULL && pb!=NULL) /*利用尾插法建立连接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa; /*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL) p->next=pa; /*A的长度年夜于B的长度*/if(pb!=NULL) p->next=pb; /*B的长度年夜于A的长度*/C=A;return(C);}第3章限定性线性表—栈和队列习题1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车箱调度, 回答：⑴如进站的车箱序列为123, 则可能获得的出站车箱序列是什么？123、213、132、231、321（312）⑵如进站的车箱序列为123456, 能否获得435612和135426的出站序列, 并说明原因.（即写出以“S”暗示进栈、以“X”暗示出栈的栈把持序列）.SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 设队列中有A、B、C、D、E这5个元素, 其中队首元素为A.如果对这个队列重复执行下列4步把持：（1）输出队首元素；（2）把队首元素值拔出到队尾；（3）删除队首元素；（4）再次删除队首元素.直到队列成为空队列为止, 则是否可能获得输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C[提示]：A、B、C、D、E （输出队首元素A）A、B、C、D、E、A （把队首元素A拔出到队尾）B、C、D、E、A （删除队首元素A）C、D、E、A （再次删除队首元素B）C、D、E、A （输出队首元素C）C、D、E、A、C （把队首元素C拔出到队尾）D、E、A、C （删除队首元素C）E、A、C （再次删除队首元素D）3. 给出栈的两种存储结构形式名称, 在这两种栈的存储结构中如何判别栈空与栈满？4. 依照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例,画出对下列算术表达式求值时把持数栈和运算符栈的变动过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5. 试写一个算法, 判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1& 序列2’模式的字符序列.其中序列1和序列2中都不含字符’&’, 且序列2是序列1的逆序列.例如, ‘a+b&b+a’是属该模式的字符序列, 而‘１+３&３－１’则不是.[提示]：（1）边读边入栈, 直到&（2）边读边出栈边比力, 直到……6. 假设表达式由单字母变量和双目四则运算算符构成.试写一个算法, 将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）.[提示]：例：中缀表达式：a+b后缀表达式: ab+中缀表达式：a+b×c后缀表达式: abc×+中缀表达式：a+b×c-d后缀表达式: abc×+d-中缀表达式：a+b×c-d/e后缀表达式: abc×+de/-中缀表达式：a+b×(c-d)-e/f后缀表达式: abcd-×+ef/-•后缀表达式的计算过程：（简便）顺序扫描表达式,（1）如果是把持数, 直接入栈；（2）如果是把持符op, 则连续退栈两次, 得把持数X, Y, 计算X op Y, 并将结果入栈.•如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式,（1）如果是把持数, 直接输出；（2）如果是把持符op2, 则与栈顶把持符op1比力：如果op2 > op1, 则op2入栈；如果op2 = op1, 则脱括号；如果op2 < op1, 则输出op1；7. 假设以带头结点的循环链表暗示队列, 而且只设一个指针指向队尾元素结点（注意不设头指针）, 试编写相应的队列初始化、入队列和出队列的算法.[提示]：参P.56 P.70 先画图.typedef LinkListCLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 要求循环队列不损失一个空间全部都能获得利用, 设置一个标识表记标帜域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满, 请编写与此结构相应的入队与出队算法. [提示]：初始状态：front==0, rear==0, tag==0队空条件：front==rear, tag==0队满条件：front==rear, tag==1其它状态：front !=rear, tag==0（或1、2）入队把持：……（入队）if (front==rear) tag=1；（或直接tag=1）出队把持：……（出队）tag=0；[问题]：如何明确区分队空、队满、非空非满三种情况？9. 简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ iint i, n, A[255];n=0;while(!EmptyStack(S)){n++;Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}将栈S逆序.（2）void proc_2(Stack S, int e) {Stack T; int d;InitStack(&T);while(!EmptyStack(S)){Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){Pop(&T, &d);Push( &S, d);}}删除栈S中所有即是e的元素.（3）void proc_3(Queue *Q){Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){Pop(&S, &d);EnterQueue(Q, d)}}将队列Q逆序.实习题1．回文判断.称正读与反读都相同的字符序列为“回文”序列.试写一个算法, 判断依次读入的一个以@为结束符的字母序列, 是否为形如‘序列1&序列2’模式的字符序列.其中序列1和序列2中都不含字符‘&’, 且序列2是序列1的逆序列.例如, ‘a+b&b+a’是属该模式的字符序列, 而‘１+３&３－１’则不是. 2．停车场管理.设停车场是一个可停放n辆车的狭长通道, 且只有一个年夜门可供汽车进出.在停车场内, 汽车按达到的先后次第, 由北向南依次排列（假设年夜门在最南端）.若车场内已停满n辆车, 则后来的汽车需在门外的便道上等待, 当有车开走时, 便道上的第一辆车即可开入.当停车场内某辆车要离开时, 在它之后进入的车辆必需先退出车场为它让路, 待该辆车开出年夜门后, 其它车辆再按原次第返回车场.每辆车离开停车场时, 应按其停留时间的长短交费（在便道上停留的时间不收费）.试编写法式, 模拟上述管理过程.要求以顺序栈模拟停车场, 以链队列模拟便道.从终端读入汽车达到或离去的数据, 每组数据包括三项：①是“达到”还是“离去”；②汽车牌照号码；③“达到”或“离去”的时刻.与每组输入信息相应的输出信息为：如果是达到的车辆, 则输出其在停车场中或便道上的位置；如果是离去的车辆, 则输出其在停车场中停留的时间和应交的费用.（提示：需另设一个栈, 临时停放为让路而从车场退出的车.）3．商品货架管理.栈顶商品的生产日期最早, 栈底商品的生产日期最近.上货时, 需要倒货架, 以保证生产日期较近的商品在较下的位置.用队列和栈作为周转, 实现上述管理过程.第三章谜底按 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车箱调度, 回答：（1）如进站的车箱序列为123, 则可能获得的出站车箱序列是什么？（2）如进站的车箱序列为123456, 能否获得435612和135426的出站序列, 并说明原因（即写出以“S”暗示进栈、“X”暗示出栈的栈序列把持）.【解答】（1）可能获得的出站车箱序列是：123、132、213、231、321.（2）不能获得435612的出站序列.因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6), 此时依照“后进先出”的原则, 出栈的顺序必需为X(2)X(1).能获得135426的出站序列.因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1).给出栈的两种存储结构形式名称, 在这两种栈的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top用来寄存栈顶元素的下标）判断栈S空：如果S->top==-1暗示栈空.判断栈S满：如果S->top==Stack_Size-1暗示栈满.（2）链栈（top为栈顶指针, 指向以后栈顶元素前面的头结点）判断栈空：如果top->next==NULL暗示栈空.判断栈满：当系统没有可用空间时, 申请不到空间寄存要进栈的元素, 此时栈满.3.4 照四则运算加、减、乘、除和幂运算的优先惯例, 画出对下列表达式求值时把持数栈和运算符栈的变动过程：A-B*C/D+E↑F 【解答】3.5写一个算法, 判断依次读入的一个以@为结束符的字母序列, 是否形如‘序列1&序列2’的字符序列.序列1和序列2中都不含‘&’, 且序列2是序列1 的逆序列.例如, ’a+b&b+a’是属于该模式的字符序列, 而’1+3&3-1’则不是.【解答】算法如下：int IsHuiWen(){Stack *S;Char ch,temp;InitStack(&S);Printf(“\n请输入字符序列：”);Ch=getchar();While( ch!=&) /*序列1入栈*/{Push(&S,ch);ch=getchar();}do /*判断序列2是否是序列1的逆序列*/{。