数据结构(c语言版)第三版习题解答.doc

1 数据结构 （C语言版）（第3版） 最好的沉淀 最好的沉淀 江西师范大学计算机信息工程学院 联系方式：最好的沉淀2012年12月 2 第1章 绪论 1.1什么是数据结构？ 【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。 1.2 数据结构涉及哪几个方面？ 【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。 1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？ 【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。 1.4 线性结构的特点是什么？非线性结构的特点是什么？ 【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。 1.5 数据结构的存储方式有哪几种？ 【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。 1.6 算法有哪些特点？它和程序的主要区别是什么？ 【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。 1.7 抽象数据类型的是什么？它有什么特点？ 【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。 1.8 算法的时间复杂度指的是什么？如何表示？ 【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法的时间复杂度，大写O符号给出了函数f的一个上限。其它义如下： 定义：f (n)=O (g (n) 当且仅当存在正的常数c和n0，使得对于所有的nn0，有f (n) c g(n)。 3 上述定义表明，函数f顶多是函数g的c倍，除非n 小于n0。因此对于足够大的n (如nn0)，g是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些常用的g函数及其名称。对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大于1的常数a和b都有logan =logbn/logba,所以logan和logbn都有一个相对的乘法系数1/logba，其中a是一个常量。 表1-1常用的渐进函数 函数 名称 1 常数 logn 对数 n 线性 nlogn n个logn n2 平方 n3 立方 2n 指数 n! 阶乘 1.9 算法的空间复杂度指的是什么？如何表示？ 【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。 1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。 （1） i+; （2） for(i=0;i<n;i+) if (ai<x) x=ai; （3）for(i=0;i<n;i+) for(j=0;j<n;j+) printf(“%d”,i+j); （4）for (i=1;i<=n-1;i+) k=i; for(j=i+1;j<=n;j+) if(aj>aj+1) k=j; t=ak; ak=ai; ai=t; （5）for(i=0;i<n;i+) for(j=0;j<n;j+) +x;s=s+x; 【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2） 4 第2章 线性表及其顺序存储 2.1 选择题 （1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数为（ A ）。 A（n1）/2 Bn Cn+1 Dn1 En/2 F(n+1)/2 G(n2)/2 （2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（ C ）。 A6 B4 C3 D2 （3）设栈的输入序列为1、2、3 n，若输出序列的第一个元素为n，则第i个输出的元素为（ B ）。 A不确定 Bni+1 Ci Dni （4）在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（ A ）个元素。 Ani Bni+1 Cni1 Di （5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（ A ）。 AO(n) BO(1) CO(n2) DO(n3) （6）表达式a*(b+c)d的后缀表达式是（ B ）。 Aabcd*+ Babc+*d Cabc*+d D+*abcd （7）队列是一种特殊的线性表，其特殊性在于（ C ）。 A插入和删除在表的不同位置执行 B插入和删除在表的两端位置执行 C插入和删除分别在表的两端执行 D插入和删除都在表的某一端执行 （8）栈是一种特殊的线性表，具有（ B ）性质。 A先进先出 B先进后出 C后进后出 D顺序进出 （9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n - 1个元素，即循环队列满的条件为（ B ）。 A(rear+1)%n=front1 B(rear+1)%n=front C(rear)%n=front Drear+1=front （10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（ D ）。 A5和1 B2和4 C1和5 D4和2 2.2什么是顺序表？什么是栈？什么是队列？ 5 【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。 2.3设计一个算法，求顺序表中值为x的结点的个数。 【答】：顺序表的存储结构定义如下： #include <stdio.h> #define N 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct datatype aN; /*此处假设数据元素只包含一个整型的关键字域*/ int size; /*线性表长度*/ sequence_list; /*预定义的顺序表类型*/ 算法count()用于求顺序表H中值为x的结点的个数。 int count (sequence_list *H,datatype x) int j=0; int i; for (i=0;i<H->size;i+) if (H->ai=x) j+; return j; 2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a0等于原来的最后一个元素，a1 等于原来的倒数第2个元素，a的最后一个元素等于原来的第一个元素。 【答】：实现顺序表倒置的算法程序如下： void verge(seqlist *L) int t,i,j; i=0; j=L->length-1; while (i<j) t=L->datai; L->datai+=L->dataj; L->dataj-=t; 2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。 【答】：实现本题要求的算法程序如下： 6 void insertx(seqlist *L,datatype x) int j; if (L->length<N) j=L->length-1; while (j>=0 && L->dataj>x) L->dataj+1=L->dataj; j-; L->dataj+1=x; L->length+; 2.6 将下列中缀表达式转换为等价的后缀表达式。 (1) 5+6*7 (2) (5-6)/7 (3) 5-6*7*8 (4) 5*7-8 (5) 5*(7-6)+8/9 (6) 7*(5-6*8)-9 【答】： (7) 5+6*7 后缀表达式：5 6 7*+ (8) (5-6)/7 后缀表达式：5 6-7/ (9) 5-6*7*8 后缀表达式：5 6 7*8*- (10) 5*7-8 后缀表达式：5 7* 8- (11) 5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+ (12) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9- 2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。 【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n 2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。 【答】： 方法一： 算法思想：逐次输出所有可能，用回溯法。即： 总体：对原始序列中的每一个元素，总是先入栈，后出栈 1入栈后的操作：a.该元素出栈；b.下一个元素入栈； 2出栈后的操作：a.（栈中其他元素）继续出栈；b. （原始序列中）下一个数入栈； 注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”， 7 实际上就是恢复。 程序代码：(2_8_1.c) #include <stdio.h> #define MAX 26 typedef struct s char aMAX; int top; Stack; /*定义一些全局变量*/ Stack S; /*定义全局性的栈*/ char dMAX,seqMAX; /*dMAX用于存储原始入栈序列，seqMAX用于存储输出序列*/ int len; /*定义将通过栈的元素个数*/ int count=0; /* 用于统计输出序列的个数 */ void initStack(Stack *S) /*初始化空栈*/ S->top=-1; void push(Stack *S, char x) /*进栈*/ if (S->top>=MAX) return; S->top+; S->aS->top=x; char pop(Stack *S)/*出栈*/ if (S->top=-1) printf("ERROR, POP Empty Stack"); return -1; S->top-; return S->aS->top+1; int isEmpty(Stack *S)/*判断栈是否为空*/ if (S->top=-1) return 1; return 0; void outSeq(char *seq, int len)/*输出顶点序列*/ int i; for(i=0; i<len; i+) printf("%2c",seqi); printf("n"); void scheduler(int pos, int seq_pos) 8 /* pos: 处理到原始数据中的第pos个元素， seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置 */ int i=0;char t; /*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素”用递归*/ if(pos<len)/*一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈*/ push(&S,dpos); scheduler(pos+1,seq_pos); pop(&S); if (!isEmpty(&S)/*一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈*/ t=pop(&S); seqseq_pos+=t; scheduler(pos,seq_pos); push(&S,t); if (pos>=len && isEmpty(&S) outSeq(seq,len); count+; int main() int i; printf("nplease input the num be scheduled: "); scanf("%d", &len); /*用len存储待调度的火车数量*/ for(i=0; i<len; i+) di=a+i; /*创建火车编号，如a、b、c、.等*/ printf("the original seq is:"); outSeq(d,len); initStack(&S); scheduler(0,0); printf("n count=%5d", count); return 0; 方法二： 解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321是一个有效的出栈序 9 列，1423不是一个有效的出栈结果（4后面比它小的两个数2，3不是倒序）。据此，本题可以通过算法产生n个数的全排列，然后将满足出栈规则的序列输出。 产生n个数的全排列有递归与非递归两种实现算法。 产生全排列的递归算法： 设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中惟一的元素； 当n>1时，perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。 依此递归定义，可设计产生perm(R)的递归算法如下： 递归解法：(2_8_2.c) #include<stdio.h> int cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/ void print(int str,int n); /*求整数序列str从k到n的全排列*/ void perm(int str,int k,int n) int i,temp; if (k=n-1) print(str,n); else for (i=k;i<n;i+) temp=strk; strk=stri; stri=temp; perm(str,k+1,n); /*递归调用*/ temp=stri; stri=strk; strk=temp; /*本函数判断整数序列str是否满足进出栈规则,若满足则输出*/ void print(int str,int n) int i,j,k,l,m,flag=1,b2; for(i=0;i<n;i+) /*对每个stri判断其后比它小的数是否为降序序列*/ m=0; for(j=i+1;j<n&&flag;j+) if (stri>strj) if (m=0) bm+=strj; else if (strj>b0) flag=0; else b0=strj; if(flag) /*满足出栈规则则输出str中的序列*/ 10 printf(" %2d:",cont+); for(i=0;i<n;i+) printf("%d",stri); printf("n"); int main() int str100,n,i; printf("input a int:"); /*输出排列的元素个数*/ scanf("%d",&n); for(i=0;i<n;i+) /*初始化排列集合*/ stri=i+1; printf("input the result:n"); perm(str,0,n); printf("n"); return 0; 当参与进出栈的元素个数为4时，输出的结果如下图所示。 该算法执行的时间复杂度为O（n!）。随着n的增大，算法的执行效率非常的低。 非递归解法：（2_8_3.c） 对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为126453就不是排列124653的下一个排列。为得到排列124653的下一个排列，应从已考察过的那部分数 11 字中选出比数字4大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。在前面数字1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排列颠倒，如将数字6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6，5，3的下一个排列。按照以上想法可以编写非递归程序实现n个数的全排列，对满足进出栈规则的排列则计数并输出。 /*本程序输出1 2 . n个序列进栈出栈的序列*/ #include <stdio.h> int pl(int n) int a100; /*最大处理范围为99个数*/ int flag=1,flag1=0; FILE *rf ; int i,j,k,x,count=0; rf = fopen("stack.txt", "w") ; /*pl.txt用于存放进出栈序列结果*/ for (i=1;i<=n;i+) /*初始序列*/ ai=i; while (flag) /* 还剩余未输出的排列*/ flag1=1; /* 判断本次排列是否符合进栈出栈序列 */ for (i=1;i<=n;i+) j=i+1; while (j<=n && aj>ai) j+; /* 找ai后第一个比ai小的元素aj*/ k=j+1; while (k<=n) /* 如果aj后还有比ai小且比aj大的元素,则此排列无效*/ if ( ak <ai && ak>aj) flag1=0; k+; if (flag1) for (i=1;i<=n;i+) /*输出当前排列*/ printf("%4d",ai); fprintf(rf,"%4d",ai); printf("n"); fprintf(rf,"n"); count+; /*计数器加1*/ i=n; /*从后向前找相邻位置后大前小的元素值*/ while (i>1 && ai<ai-1) i-; if (i=1) flag=0; /*未找到则结束*/ else j=i-1;i=n;/* 若找到,则在该位置的后面从右向左找第一个比该元素大的值*/ while (i>j && ai<aj) i-; 12 k=aj; /*交换两元素的值*/ aj=ai; ai=k; k=j+1; /*对交换后后面的数据由小到大排序*/ for ( i=k+1;i<=n;i+) /*插入排序*/ j=i-1; x=ai; while (j>=k && x<aj) aj+1=aj; j-; aj+1=x; fclose(rf); return count; /*返回排列总个数*/ void main() int n,m=0; printf("please input n:"); /*输入排列规模*/ scanf("%d",&n); m=pl(n); printf("nm=%d",m); /*输出满足进出栈的排列总个数*/ 程序运行时如果输入4，则输出的结果如下图所示。 该算法的时间复杂度也是O(n!)。 结论：如果n个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序列的总数为：!)1()!2(nnnn+ 13 第3章 线性表的链式存储 3.1 选择题 （1）两个有序线性表分别具有n个元素与m个元素且nm，现将其归并成一个有序表，其最少的比较次数是（ A ）。 An Bm Cn1 Dm+n （2）非空的循环单链表head的尾结点（由p所指向）满足（ C ）。 Ap->next=NULL Bp=NULL Cp->next=head Dp=head （3）在带头结点的单链表中查找x应选择的程序体是（ C ）。 Anode *p=head->next; while (p && p->info!=x) p=p->next; if (p->info=x) return p else return NULL; Bnode *p=head; while (p&& p->info!=x) p=p->next; return p; Cnode *p=head->next; while (p&&p->info!=x) p=p->next; return p; Dnode *p=head; while (p->info!=x) p=p->next ; return p; （4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以 （5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。 AO(1) BO(n) CO(n2) DO(nlog2n) （6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ D ）。 A仅修改队头指针 B仅修改队尾指针 C队头、队尾指针都要修改 D队头,队尾指针都可能要修改 （7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。 AO(n) BO(n2) CO(n3) DO(nlog2n) （8）下面哪个术语与数据的存储结构无关（ D ）。 A顺序表 B链表 C散列表 D队列 （9）在一个单链表中，若删除p所指结点的后续结点，则执行（ A ）。 Ap->next=p->next->next; Bp=p->next; p->next=p->next->next; Cp->next=p->next; Dp =p->next->next; （10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。 As->next=p;p->next=s; Bs->next=p->next;p->next=s; Cs->next=p->next;p=s; Dp->next=s;s->next=p; 3.2 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：linklist.h） #include <stdlib.h> 14 #include <stdio.h> typedef struct node int data; struct node *next; linknode; typedef linknode *linklist; /*尾插法创建带头结点的单链表*/ linklist creatlinklist() linklist head,r,s; int x; head=r=(linklist)malloc(sizeof(linknode); printf("n请输入一组以0结束的整数序列：n"); scanf("%d",&x); while (x) s=(linklist)malloc(sizeof(linknode); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; return head; /*输出带头结点的单链表*/ void print(linklist head) linklist p; p=head->next; printf("List is:n"); while(p) printf("%5d",p->data); p=p->next; printf("n"); 基于上述结构定义，求单链表中的结点个数的算法程序如下： int count(linklist head) int c=0; linklist p=head; while (p) 15 c+; p=p->next; return c; 3.3设计一个算法，求一个带头结点单链表中的结点个数。 【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c） #include "linklist.h" int count(linklist head) int c=0; linklist p=head->next; while (p) c+; p=p->next; return c; main() /*测试函数*/ linklist head; head=creatlinklist(); print(head); printf("nLength of head is:%d",count(head); getch(); 当输入5个数据时，产生的输出结果如下图所示： 3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成为值为y的结点的前驱结点。 【答】： #include "linklist.h" void insert(linklist head,int y,int x) /*在值为y的结点前插入一个值为x的结点*/ linklist pre,p,s; pre=head; 16 p=head->next; while (p && p->data!=y) pre=p; p=p->next; if (p)/*找到了值为y的结点*/ s=(linklist)malloc(sizeof(linknode); s->data=x; s->next=p; pre->next=s; void main() /*测试程序*/ linklist head; int y,x; head=creatlinklist(); /*创建单链表*/ print(head); /*输出单链表*/ printf("n请输入y与x的值:n"); scanf("%d %d",&y,&x); inser