数据结构课习题参考答案

1、数据结构目录一、1.1比较2个线性链表的c函数 31.2写一个倒置顺序存贮的线性表的c函数31.3 写一个在线性表中，使线性表中没有值相同的结点的函数。41.4 编写一个求解给定多项式的值的c函数。51.5 实现多项式乘法61.7 车厢出站问题91.8编写对任一栈作进栈和出栈运算的c函数101.10 写出表达式等价的后缀表达式。121.11编写一个统计给定的线性链表的结点个数的c函数。151.12编写一个将给定的线性链表逆转的c函数。161.13编写一个插入值的c函数。181.14编写一个删除链表中结点的前趋结点的c函数。191.15试编写一个将两个链表归并成一个线性链表的c函数。201.17

2、 用环形链表解1。6题23118 将给定的线性链表改成环形链表241 19将给定的线性链表改成一个带表头的环形链表25120 编写用hash函数h（xi）xi，对x1，x2x800进行hash存储的程序261 21求广义表的深度。2721试编写一个在两个顺序字符串中寻找最大公共子串的c函数。292 2试编写一个实现strins（s1，i，s2）的c函数。3123 按照2.2题的要求，编一个实现strdel（s，i，j）的c函数。3231编写一个二分插入排序的c程序3332编写一个对给定链表进行插入排序的c程序。3435采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。363 6采

3、用顺序存储的结构即数组实现。3837编写一个实现快速排序的非递归的c函数。3938对于分别写出用下列排序方法对线性表进行排序的结果。4043将n阶三对角阵（即半带宽为1的带状矩阵）a按行序列序存放在一维数组b3*n-2中。若aij(|i-j|<=1)存放在bk中，请求出求解k的计算公式。4244如果把广义的anab按行序列序存放在一维数组b(a+b-1)*n-(a+b-2)中，元素aij存放在bk中，那么请写出计算k的计算公式。4245试编写一个求解两个三元数组相加的c函数。4246试编写一个将十字链表转置的c函数.4451请分别给出对树进行前序、后序、层次序遍历后的结点序列。4552试

4、叙述将m棵有序树组成的有序树林转换成相应的二叉树的逆变换。4653试编写一个把树中每个结点的左右子结点进行对换的c函数。4754编写一个利用栈来实现后序遍历一棵给定的二叉树的c函数。4955题目：51试为下面各小题分别编写一个c函数：（1） 按前序输出t的结点值。（2） 按后序输出t的结点值。（3） 输出树t的叶子结点值。（4） 求出树t的次数。56试编写一个把树t按标准形式进行存贮的c函数。5357 已知树t中结点的中序和后序，编写一个把t按标准形式存储的c函数5458 判断给定的二叉树是否为完全二叉树5559 判断两棵给定的二叉树是否相似55510 把树t转换成由标准形式进行存储的树t55

5、511试编写一个寻找结点a的父结点的c函数。56512试编写一个按前序遍历穿线树的c函数。5861画出由集合中结点所构成的查找树，画出删除后的查找树。6062试编写一个用平分法构造出由集合中结点所构成的丰满查找树的c函数。6065编写一个判断给定二叉树t是否为平衡树的c函数。6266试画出adelson插入方法的右改组的转换图。6569试画出用hu-tucker算法构造出的最佳叶子查找树。66610 画出每次插入后的b树67612 修改皇后问题70613 马的周游路线7671对于图题7.1（p235）的无向图，给出：79（1） 表示该图的邻接矩阵。（2） 表示该图的邻接表。（3） 图中每个顶点

6、的度。72对于图题7.1的无向图，给出：79（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。73对于图题7.3的有向图，给出：84（1） 表示该图的邻接矩阵。（2） 表示该图的邻接表。（3） 图中每个顶点的入度和出度。74对于图题7.3的有向图，给出：85（1） 从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。（2） 从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。75对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？8576对于图题 7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图

7、吗？8677图题7-7是有向图，试问其中哪个图是86（1） 弱连通的？（2） 强连通的？78具有n个顶点的连通无向图至少有几条边？8679具有n个顶点的强连通有向图至少有几条边？86710分别写出用深度和广度优先搜索法遍历完全无向图的顶点序列。 87711改写以深度优先搜索法遍历给定的连通图的dfs程序。87 712在图题7.1中，从顶点1出发，分别画出其dfs生成树和bfs生成树。881.1：比较2个线性链表的c函数1 存储法：用两个数组存放线性表。2 存储结构：一般的顺序存储方式。3 源程序：int comp(int a,int as,int b,int bs) int tmp=as>

8、;bs?as:bs; int i; for(i=0;i<tmp;i+) if(ai>bi) return 1; if(ai<bi) return -1; if(as>bs) return 1; if(bs>as) return -1; return 0;4.测试用例：1 a3=1,2,3 b3=1,2,3 output : 0;2 a3=1.2.3 b3=1,1,3 output: 1;3 a3=1,2,3 b3=1,2,4 output: -14 a3=1,2,3 b4=1,2,3,0 output: -1;5 a4=1,2,3,0 b3=1,2,3 outpu

9、t: 1;6 a4=1,2,3,0 b3=1,3,2 output:-1;1.2 写一个倒置顺序存贮的线性表的c函数。要求用最少的附加存贮空间来完成。· 分析：假设用数组a存贮一组int类型的数据，每次将a0取出，其余数依次前移，然后将a0放到 尚未倒置的数据元素的最后，直至整个数组完成倒置。· 算法：（1）取t=a0，余下的a1，a2，.an-1依次前移一个位置； （2）an-1=t； （3）对由a0，a1.an-2组成的数组重复上述步骤。· 程序： # include<stdio.h> # define n 10 void reverse(a,n)

10、 int a; int n; int t,i,j=0; while(j<n-1) t=a0; for(i=0;i<n-j-1;i+) ai=ai+1; ai=t; j+; void main( ) int an; int i; printf("input the array:n"); for(i=0;i<n;i+) scanf("%d", &ai); reverse(a,n); printf("the reversed array:n"); for(i=0;i<n;i+); printf("%

11、d ",ai); printf("n"); · sample: input the array: 0 1 2 3 4 5 6 7 8 9 the reversed array:9 8 7 6 5 4 3 2 1 01.3 在具有n个结点的顺序存贮的线性表中，对值相同的结点只保留一个，把多余的结点删除掉，使线性表中没有值相同的结点。试编写一个实现上述操作的c函数，并分析该程序的执行时间。解答：首先应对线性表中每一个结点进行搜索，找到和他值相同的结点就把其删除，同时改变原结点的个数。主要运用两层循环：最外层对线性表中的第0到第n-2个元素进行扫描，第二层是对

12、于第一层的每一个元素从其后面一个元素开始扫描，检查是否有和该元素值相同的元素若有则删除该元素，若无则循环关键值+1进行下一个元素比较，直到线性表最后一个元素，然后在回到上层循环。如此继续，直到跳出所有循环时，所得线性表即为题目要求的线性表。 下面给出实现的函数。sq_delete()为删除一个结点的函数，i表示所要删除的结点的下标，del()为删除线性表中所有相同结点的函数。其中list为进行操作的线性表，*p_m和*p_n在两个函数中都表示线性表中结点个数。 #include<stdio.h>#define m 100int sq_delete(int list,int *p_m

13、,int i) int j; if(i<0|i>=*p_m) return(1); for(j=i+1;j<*p_m;j+) listj-1=listj; (*p_m)-; return (0);void del(int list,int *p_n) int i,j; for(i=0;i<(*p_n)-1);i+) for(j=i+1;j<(*p_n);j+) if(listi=listj)sq_delete(list,p_n,j);j-;main() int listm,i,n; printf("input the number of the data

14、:n"); scanf("%d",&n); for(i=0;i<n;i+) printf("input data %d:n",i+1); scanf("%d",&listi); del(list,&n); for(i=0;i<n;i+) printf("%d ",listi);对于以上程序提供一组测试数据：input the number of the data:5输入一组数据为：13 23 33 13 23执行完毕后得到的输出结果为：13 23 33对于该程序的时间复

15、杂性分析：主要是del 和sq_delete两个函数中的循环语句的执行时间。一种极端情况是线性表中的数据没有一个重复，则只执行del中的循环体，(n-1)+(n-2)+1=o(n*n);另一种极端情况是线性表中只有一个元素，其他都与它重复，此时del的内和外循环都只执行一次，主要的执行时间用在了sq_delete上，可以知道他的复杂性也是o(n*n).故总的来说该程序的时间复杂性是o(n*n)。 1.4 编写一个求解给定多项式在x=xo(xo为指定的某个值)时的值的c函数。存储法：定义结构数组 struct node int exp; float coef; ; typedef struct

16、node term #define max 100 node amax;算法步骤：1 令sum=0, i=02 算出第i项的值，并与sum相加。3 若i<n, 则转2，否则return(sum)程序： float cal ( float x, term a , int n ) float sum; int i, j, k; for ( i=0; i<n; i+ ) for ( k=1, j=1; j<= ai . exp; j+) k=k*x; sum+= ai .coef*k; return(sum); 测试用例： 令x=2; 多项式为 3x6+8x4+5x2+9 结果为

17、349。 1.5实现多项式乘法一：存储结构：多项式以线性链表存储，以增加其插入删除的效率。结果多项式与所给多项式采取相同的存储结构，以方便实现多项式的连乘。二：分析 多项式的加法书上有源程序，而乘法与加法相似，只是由于乘法的规则与加法不同，因此我用了一个双重循环来实现（详见源程序），得到一个结果项之后，查找结果链表，若已有，则看是否相加之后为0，若为0，则将该项删去，否则，就直接改系数，若没有，则直接链上。 原本想用数组加链表的索引法来实现，但据分析后，认为并不能显著提高效率，显得得不偿失，因此，我就使用了最原始的方法，请老师同学多多指教。三：输入/输出输入：先输入a、b多项式（根据提示）输出

18、：a、b、c（a×b）四：源程序#include<stdio.h>struct node int exp; int data; struct node *next; ;typedef struct node node;int search(int exp,node *c,node *pc,node *qc)*pc=null;*qc=c;if(c=null) return(0);while(*qc)->exp>exp) *pc=*qc;*qc=(*qc)->next;if(*qc)->exp=exp) return(1);return(0);node

19、 *multi(node *a,node *b) node *pa,*pb,*pc,*qc,*p,*c=null; int exp,data,flag; for(pa=a;pa!=null;pa=pa->next) for(pb=b;pb!=null;pb=pb->next) exp=pa->exp+pb->exp;data=pa->data*pb->data; if(data) flag=search(exp,c,&pc,&qc); if(flag) if(!(data+qc->data) pc->next=qc->nex

20、t;free(qc); else (qc->data)+=data; else p=(node *)malloc(sizeof(node); p->data=data;p->exp=exp; if(!pc) c=p; else pc->next=p; p->next=qc; return(c);node* creat()node *root,*p,*q; char ch;int i;printf("do you want to creat a null one(y/n)?n");scanf("%c",&ch);get

21、char();if(ch='y'|ch='y') return(null);p=null;ch='y'for(i=0;ch='y'|ch='y'i+)q=(node*)malloc(sizeof(node);if(p=null) root=q; else p->next=q;printf("nplease input the data of node %d:n",i);scanf("%d",&(q->data);getchar();printf("

22、;please input the exp of node %d:n",i);scanf("%d",&(q->exp);getchar();printf("do you want to continue(y/n)?n");scanf("%c",&ch);getchar();p=q;p->next=null;return(root);void print(node *root)int i=0;if(!root) printf("n0");while(i+,root!=null)p

23、rintf("nnode %d:tdata:%dtexp:%d",i,root->data,root->exp);root=root->next;main()char ch;node *a,*b,*c;clrscr();printf("now please input a:n");a=creat();printf("now please input b:n");b=creat();printf("na:n");print(a);printf("nb:n");print(b);c

24、=multi(a,b);printf("nnnc:n");print(c);五：测试数据：输入：a：5x6+3x4+2xb：7x3+3x2+5输出：c：35x9+15x8+21x7+34x6+29x4+6x3+10x输入：a：0b：5x3+2x2输出：0输入：a：3x2+5x1b：3x15c：01.7假设右边轨道排列有编号为1，2，3,n的n节车厢，它们依次被拖进站，从左边轨道依次出站的号的排列顺序有a n 种情况 。那么a n是用下列方法所形成的所有可能排列顺序的总数：某时刻站中只剩下编号为k+1的车厢，而此时左边轨道是已出站的编号为1，2，3，,k的车厢，则排列顺序有a

25、k种；右边轨道是尚未进站的编号为k+1，k+2,k+n的n-k-1节车厢，则可能有的排列顺序有an-k-1种。因此 给出了前k节车厢已出站的情况下所有的排列顺序，我们应该取遍k（0kn）的所有可能值，获得akan-k-1这样形式的所有项，然后把它们相加起来，可得到如下的关系式： a0=1； a1=1； an=a0an-1+a1an-2+.+an-1a0 ( n>1) an=akan-k-1 (0kn-1) 为了求解排列顺序的数目，先求解这个递推关系：令 g（x）=a0+a1x+anx? n>1即g（x）=akxk (k0)让g（x）自乘得 g2(x)=g(x)g(x) =(a0+a

26、1x+a2x2+.)(a0+a1x+a2x2+.) =a0a0+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+. =(akan-k)x? (0n,0kn)由上式可知，g2(x)的xn项的系数正好是an1。因此有g2(x)=an+1x? (n0)如果我们用x乘g2(x)，则有 xg2(x)=a1x+a2x2.两边都加上a0，又因为a0=1，故有 1+x g2(x)=akxk (k0) 1+xg2(x)=g(x)求解得g（x）=1±(1-4x)/2x因为a0=1，所以g（x）=1-(1-4x)/2x再根据二项式定理，将(1-4x)1/2展开，得 g(x)=1/2x1-(

27、1n/2)(-4x)n (n0)令n=m+1,则有 g(x)= ( 1/2m+1)(-1)m 22m+1xm (m0) 比较可知an是上式中x?项的系数。所以 an=(1n+1/2)(-1)n22n+1化简得an=1/(n+1)(2nn)n节车厢出站有1/(n+1)(2nn)种排列顺序。所以，当 n=3时，有5种排列顺序，分别为，；当n=4时，有14种排列顺序。存储结构可采用栈实现。1_8.假设2个栈共享一个数组stackn，编写对任一栈作进栈和出栈运算的c函数，push(x,i) 和pop(i),i=1,2。这里i=1表示左边的栈，2则表示右边的栈。要求整个数组元素都被占用时才产生溢出。存储

28、结构：用一个数组存放2个栈。如图：(m为数组元素个数)32 tail1=0 head1 head2 tail2=m-1head1,head2分别为栈1，栈2中下个元素入栈的位置，tail1，tail2为两个栈底。分析与算法步骤：因为tail10,tail2m1，一般情况下不会变动，所以省去这2个量。初始值：head10，head2m-1；1执行入栈时：（1） 若head1-1+1head2+1，即head1head2+1时，整个数组满，溢出。（2） 若对栈1入栈，把元素存入stackhead1，head1+；（3） 若对栈2入栈，把元素存入stackhead2，head2；2执行出栈时：（1）

29、对栈1：若head10，栈空，出栈失败；否则head1； （2）对栈2：若head2m1，栈2空，出栈失败；否则head2+；tc程序：include<stdio.h>#define m 10int head1=0,head2=m-1;int stackm;void push(int x,int i)if(head1=head2+1) printf("the stack is full.fail to push.n"); return; if(i=1) stackhead1+=x; else stackhead2-=x;void pop(int i)if(i=1

30、) if(head1=0) printf("the stack is empty.fail to pop.n"); return; *p=stack-head1; else if(head2=m1) printf("the stack is empty.fail to pop."); return; *p=stack+head2; main()int x,i,no=1; for(i=0;i<m;i+) stacki=0; while(no!=0)printf("seclect the operation:npush:1;npop:2;np

31、rint:3nexit:0;n"); scanf("%d",&no); switch(no) case 1: printf("input the number you want push and the team no,n"); scanf("%d %d",&x,&i); if(i=1|i=2) push(x,i); else printf("wrong number.select again.n"); break; case 2: printf("input the t

32、eam you want to pop:n"); scanf("%d",&i); if(i=1|i=2) pop(i); else printf("wrong number,select again.n"); break; case 3: for(i=head1-1;i>=0;i-) printf("%d",stacki); printf("n"); for(i=head2+1;i<m;i+) printf("%d",stacki); printf("n&

33、quot;); break; 测试用例：在main函数中，提供了操作的选择。1为入栈，2为出栈，3为输出2个栈中的元素，0为退出操作。第一次进栈1：1，2，3，4，5； 输出：12345第二次进栈2：6，7，8，9，10； 输出：678910栈1连续出栈5次后，继续执行出栈，输出为the stack is empty.fail to pop.栈2连续出栈3次后，输出栈2中元素为910110 写出与下列表达式等价的后缀表达式：(1) a+b*c/d+efg+h(2) (a+b)*(c/d)+(ef)(g+h)存储结构： 对于两个表达式采用字符数组存储形式，并以0作为结尾。 另外，使用一个栈来存放

34、运算符，当遇到运算符,就把运算符入栈，直到某个适当的时机，再让运算符出栈。算法分析：当前扫描到的字符按以下几种情况分别处理：a) 若当前的字符是变量，则立即将它输出。b) 若当前的字符是(，则让(入栈。c) 若当前的字符是运算符(+,-,*,/,),则将它的（进栈前)优先级别与栈顶字符的（栈中）优先级别相比较。如果当前的运算符的优先级别小于等于栈顶字符的优先级别，那么退出栈顶字符并输出。这样的过程一直进行到当前的运算符的优先级别大于栈顶字符的为止，然后让当前的运算符入栈。d) 若当前的字符是)，则从栈中依次退出运算符并输出，直到(为止，然后退出(，但不输出(.e) 若当前的字符是0,则从栈中依

35、次退出所有的运算符并输出，直到$为止，$”不退栈，也不输出。下面给出程序：#define maxn 100int icp(char c) switch(c) case '':return(4); /进栈前的运算符的优先级 case '*': case '/':return(2); case '+': case '-':return(1); int isp(char c) switch(c) case '':return(3); /栈中的运算符的优先级 case '*': case &

36、#39;/':return(2); case '+': case '-':return(1); case '(':return(0); case '$':return(-1);/置于栈底，保证后面的运算符能进栈 int ischar(char c) if(c>='a'&&c<='z')|(c>='a'&&c<='z') return(1); else return(0);int mid_to_pos(ch

37、ar midexpress,char posexpress)char stackmaxn,c; int top,i,j; stack0='$' top=0; j=0; i=0; c=midexpress0; while(c!='0') if(ischar(c)posexpressj+=c; elseswitch(c) case '+': case '-': case '*': case '/': case '': while(icp(c)<=isp(stacktop) pose

38、xpressj+=stacktop-; stack+top=c; break; case '(': stack+top=c; break; case ')': while(stacktop!='(') posexpressj+=stacktop-; top-; break; default: return(1); c=midexpress+i; while(top>0) posexpressj+=stacktop-; posexpressj='0' return(0);测试报告： void main()char midexp

39、ressmaxn,posexpressmaxn,c; int i,result; i=0; printf("ninput the mid_expresstion:(end with '!')n"); scanf("%c",&c); while(c!='!') midexpressi+=c; scanf("%c",&c); midexpressi='0' result=mid_to_pos(midexpress,posexpress); if(result=1) print

40、f("convertion fails!n"); else printf("the pos_expresstion is:n"); printf("%s",posexpress); 输入：(a+b*c)d(e*f/g)-h*i!(输入以!结尾) 输出：abc*+def*g/hi*-输入：a+b*c/d+efg+h!输出：abc*d/+efg+h+输入：(a+b)*(c/d)+(ef)(g+h)!输出：ab+cd/*efgh+111 编写一个统计给定的线性链表的结点个数的c函数。存储结构：连表的结点采用：struct nodeint d

41、ata;/关键字的类型自定 struct node *link;算发分析：利用链表的性质（结点中的指针指向下一个结点），逐步向表尾移动，以此计算出结点数。下面给出程序：typedef struct nodeint data; struct node *link; node;int count(node *head)node *p;int c=0;p=head;while(p!=null)p=p->link; c+;return(c);测试报告：void main()node a10; int i=0; for(;i<9;i+) ai.data=i; ai.link=&ai+

42、1; ai.data=i; ai.link=null; printf("the total amount of the linked node is:%dn",count(&a0);输入：|0-1-2-3-4-5-6-7-8-9输出：the total amount of the linked node is:10112 编写一个将给定的线性链表逆转的c函数，只允许改变结点的指针值，不允许移动结点值。算法如下：(1) 置p为链表首址，r,q为空；(2) 若p为空返回null；算法结束，转（5），否则转（3）；(3) 若链表只有一个结点，转（5），否则转（4）；(4)

43、 r<=p,p<=p->link,r->link<=q,置q=r,若p->link为空，转（5），否则转（4）；(5) p->link<=r,返回p,算法结束。源程序如下：#include <stdio.h>typedef struct node int data; struct node* link; node; node* tranfer(head) node *head; node *p,*q,*r; p=head; r=q=null; if(head=null) return(null); if(p->link!=nul

44、l) do r=p; p=p->link;r->link=q;q=r;while(p->link!=null); p->link=r; return(p); node* create(n)/*建立初始链表*/ int n; int i; node *head,*p,*q; if(n=0) return(null); head=(node*)malloc(sizeof(node); p=head; for(i=1;i<n;i+) scanf("%d",&(p->data); q=(node*)malloc(sizeof(node);

45、 p->link=q; p=q; scanf("%d",&(p->data); p->link=null; return(head); main() node *head,*r,*p; int n=5; printf("enter the data:n"); head=create(n); p=head; while(p!=null) printf("%d ",p->data); p=p->link; printf("n"); head=tranfer(head); p=hea

46、d; printf("now the list is:n"); while(p!=null) printf("%d ",p->data); p=p->link; printf("n"); 输入：1 2 3 4 5输出：5 4 3 2 11.13对于给定的线性链表,编写一个把值为a的结点插在值为b的结点的前面的c函数。若值为b的结点不在线性链表中，则把a插在表的最后。存储结构 利用线形表的链接存储：typedef struct nodechar data; struct node *link;node; 定义指针node *head,*p,*q,*t; 解题思路 指针*head指向链表的根结点，指针p指向值为b的结点，指针t指向它的前趋结点，指针q指向插入结点a。 (1) 如果头结点*head为空，或*head的结点值为b，修改头指针，结束算法；(2) 查找值为b的结点，若找到，把值为a的结点插到b的前面；(3) 若找不到，把a结点插在链表最后；结束算法。 程序 #include<stdio.h> typedef struct nodechar data; struct node *link;node; void insert(node *head,char a) n