数据结构(第3版)习题答案

十二五普通高等教育国家级本科规划教材第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的一个上限。其它义如下：3函数名称1lognnnlogn2n3nn2n!常数对数线性n个logn平方立方指数阶乘十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程定义：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);（4）for(i=1;i=n-1;i++){k=i;for(j=i+1;j=n;j++)if(a[j]a[j+1])k=j;t=a[k];a[k]=a[i];a[i]=t;}（5）for(i=0;in;i++)for(j=0;jn;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的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（为（A）。E），删除一个元素所需移动元素的平均个数A．（n−1）/2E．n/2B．nF．(n+1)/2C．n+1G．(n−2)/2D．n−1（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（C）。A．6B．4C．3D．2（3）设栈的输入序列为1、2、3…n，若输出序列的第一个元素为n，则第i个输出的元素为（B）。A．不确定B．n−i+1C．iD．n−i（4）在一个长度为n的顺序表中删除第i个元素（1=i=n）时，需向前移动（A）个元素。A．n−iB．n−i+1C．n−i−1D．i（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。A．O(n)B．O(1)C．O(n2)D．O(n3)（6）表达式a*(b+c)−d的后缀表达式是（B）。A．abcd*+−B．abc+*d−C．abc*+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=front−1C．(rear)%n=frontB．(rear+1)%n=frontD．rear+1=front（10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。A．5和1B．2和4C．1和5D．4和22.2什么是顺序表？什么是栈？什么是队列？5十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3设计一个算法，求顺序表中值为x的结点的个数。【答】：顺序表的存储结构定义如下（文件名seqlist.h）：#includestdio.h#defineN100typedefintdatatype;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.4设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a[0]等于原来的最后一个元素，a[1]等于原来的倒数第2个元素，…，a的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下：voidverge(seqlist*L){intt,i,j;i=0;j=L-length-1;while(ij){t=L-data[i];L-data[i++]=L-data[j];L-data[j--]=t;}}2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下：6十二五普通高等教育国家级本科规划教材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.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(8)(5-6)/7(9)5-6*7*8(10)5*7-8(11)5*(7-6)+8/9(12)7*(5-6*8)-9后缀表达式：567*+后缀表达式：56-7/后缀表达式：567*8*-后缀表达式：57*8-后缀表达式：576-*89/+后缀表达式：7568*-*9-2.7循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈1．入栈后的操作：a.该元素出栈；b.下一个元素入栈；2．出栈后的操作：a.（栈中其他元素）继续出栈；b.（原始序列中）下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”，7十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程实际上就是恢复。程序代码：(2_8_1.c)#includestdio.h#defineMAX26typedefstructs{chara[MAX];inttop;}Stack;/*定义一些全局变量*/StackS;/*定义全局性的栈*/chard[MAX],seq[MAX];/*d[MAX]用于存储原始入栈序列，seq[MAX]用于存储输出序列*/intlen;/*定义将通过栈的元素个数*/intcount=0;/*用于统计输出序列的个数*/voidinitStack(Stack*S)/*初始化空栈*/{S-top=-1;}voidpush(Stack*S,charx)/*进栈*/{if(S