数据结构1_2_3_8章答案与学习指南

数据结构（C语言版）李云清杨庆红揭安全编著习题解析与学习指南江西师范大学计算机信息工程学院联系方式：[e-mail]（数据更新中，仅供学习参考）2第1章绪论1-1本章知识重点1-2教材配套习题解析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，使得对于所有的n≥n0，有f(n)≤cg(n)。上述定义表明，函数f顶多是函数g的c倍，除非n小于n0。因此对于足够大的n(如n≥n0)，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.9算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。(1)i++;(2)for(i=0;in;i++)if(a[i]x)x=a[i];(3)for(i=0;in;i++)for(j=0;jn;j++)printf(“%d”,i+j);【答】：（1）O（1）；（2）O（n）；（3）O（n2）34第2章线性表及其顺序存储2-1本章知识重点2-2教材配套习题解析2.1什么是顺序表？什么是栈？什么是队列？【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.2设计一个算法，求顺序表中值为x的结点的个数。【答】：顺序表的存储结构定义如下（文件名seqlist.h）：#includestdio.h#defineN100/*预定义最大的数据域空间*/typedefintdatatype;/*假设数据类型为整型*/typedefstruct{datatypedata[N];/*此处假设数据元素只包含一个整型的关键字域*/intlength;/*线性表长度*/}seqlist;/*预定义的顺序表类型*/算法countx（L,x）用于求顺序表L中值为x的结点的个数。intcountx(seqlist*L,datatypex){intc=0;inti;for(i=0;iL-length;i++)if(L-data[i]==x)c++;returnc;}2.3设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a[0]等于原来的最后一个元素，a[1]等于原来的倒数第2个元素，…，a的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题2.2，实现顺序表倒置的算法程序如下：voidverge(seqlist*L){intt,i,j;i=0;j=L-length-1;5while(ij){t=L-data[i];L-data[i++]=L-data[j];L-data[j--]=t;}}2.4已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题2.2，实现本题要求的算法程序如下：voidinsertx(seqlist*L,datatypex){intj;if(L-lengthN){j=L-length-1;while(j=0&&L-data[j]x){L-data[j+1]=L-data[j];j--;}L-data[j+1]=x;L-length++;}}2.5将下列中缀表达式转换为等价的后缀表达式。(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后缀表达式：567*+(8)(5-6)/7后缀表达式：56-7/(9)5-6*7*8后缀表达式：567*8*-(10)5*7-8后缀表达式：57*8-(11)5*(7-6)+8/9后缀表达式：576-*89/+(12)7*(5-6*8)-9后缀表达式：7568*-*9-2.6循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.7编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果6有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321是一个有效的出栈序列，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中惟一的元素；当n1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。依此递归定义，可设计产生perm(R)的递归算法如下：递归解法：(2_7_1.c)#includestdio.hintcont=1;/*全局变量，用于记录所有可能的出栈序列个数*/voidprint(intstr[],intn);/*求整数序列str[]从k到n的全排列*/voidperm(intstr[],intk,intn){inti,temp;if(k==n-1)print(str,n);else{for(i=k;in;i++){temp=str[k];str[k]=str[i];str[i]=temp;perm(str,k+1,n);/*递归调用*/temp=str[i];str[i]=str[k];str[k]=temp;}}}/*本函数判断整数序列str[]是否满足进出栈规则,若满足则输出*/voidprint(intstr[],intn){inti,j,k,l,m,flag=1,b[2];for(i=0;in;i++)/*对每个str[i]判断其后比它小的数是否为降序序列*/{m=0;for(j=i+1;jn&&flag;j++)if(str[i]str[j]){if(m==0)b[m++]=str[j];else{if(str[j]b[0]){flag=0;}elseb[0]=str[j];}}}if(flag)/*满足出栈规则则输出str[]中的序列*/{printf(%2d:,cont++);for(i=0;in;i++)printf(%d,str[i]);printf(\n);}}voidmain(){intstr[100],n,i;printf(inputaint:);/*输出排列的元素个数*/scanf(%d,&n);for(i=0;in;i++)/*初始化排列集合*/str[i]=i+1;printf(inputtheresult:\n);perm(str,0,n);printf(\n);getch();}当参与进出栈的元素个数为4时，输出的结果如下图所示。该算法执行的时间复杂度为O（n!）。随着n的增大，算法的执行效率非常的低。非递归解法：（2_7_2.c）对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为781,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为1