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

《数据构造(c语言版)第三版习题解答.docx》由会员分享，可在线阅读，更多相关《数据构造(c语言版)第三版习题解答.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造(c语言版)第三版习题解答当前位置：文档视界数据构造(c语言版)第三版习题解答数据构造(c语言版)第三版习题解答第1章绪论1.1什么是数据构造？【答】：数据构造是指按一定的逻辑构造组成的一批数据，使用某种存储构造将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2数据构造涉及哪几个方面？【答】：数据构造涉及三个方面的内容，即数据的逻辑构造、数据的存储构造和数据的运算集合。1.3两个数据构造的逻辑构造和存储构造都一样，但是它们的运算集合中有一个运算的定义不一样，它们能否能够认作是同一个数据构造？为什么？【答】：不能，运算集合是数据构造的重要组成部分，不同的运算集合所确定的数

2、据构造是不一样的，例如，栈与队列它们的逻辑构造与存储构造能够一样，但由于它们的运算集合不一样，所以它们是两种不同的数据构造。1.4线性构造的特点是什么？非线性构造的特点是什么？【答】：线性构造元素之间的关系是一对一的，在线性构造中只要一个开场结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性构造则没有这个特点，元素之间的关系能够是一对多的或多对多的。1.5数据构造的存储方式有哪几种？【答】：数据构造的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有1有穷性2确定性30个或多个输入41个或多个输

3、出5可行性等特征。程序是算法的一种描绘方式，通经过序能够在计算机上实现算法。1.7抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及详细实现，程序设计中就能够像使用基本数据类型那样，特别方便地使用抽象数据类型。抽象数据类型的设计者根据这些描绘给出操作的详细实现，抽象数据类型的使用者根据这些描绘使用抽象数据类型。1.8算法

4、的时间复杂度指的是什么？怎样表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，由于一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行经过中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法的时间复杂度，大写O符号给出了函数f的一个上限。其它义如下：定义：f(n

5、)=O(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)cg(n)。上述定义表明，函数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常数l

6、ogn对数n线性nlognn个lognn2平方n3立方2n指数n!阶乘1.9算法的空间复杂度指的是什么？怎样表示？【答】：算法的空间复杂度是指算法在执行经过中占用的额外的辅助空间的个数。能够将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。1i+;2for(i=0;iaj+1)k=j;t=ak;ak=ai;ai=t;5for(i=0;i第2章线性表及其顺序存储2.1选择题1表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为E，删除一个元素所

7、需移动元素的平均个数为A。An?1/2BnCn+1Dn?1En/2F(n+1)/2G(n?2)/22设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为C。A6B4C3D23设栈的输入序列为1、2、3n，若输出序列的第一个元素为n，则第i个输出的元素为B。A不确定Bn?i+1CiDn?i4在一个长度为n的顺序表中删除第i个元素1【答】：当线性表采用顺序存储构造时，即为顺序表。栈是一种特殊的线性表，它的特殊性表如今约定了在这种线性表中数据的插入与删除操作只能在

8、这种线性表的同一端进行即栈顶，因而，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表如今约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因而队列具有先进先出，后进后出的特点。2.3设计一个算法，求顺序表中值为x的结点的个数。【答】：顺序表的存储构造定义如下：#include#defineN100/*预定义最大的数据域空间*/typedefintdatatype;/*假设数据类型为整型*/typedefstructdatatypeaN;/*此处假设数据元素只包含一个整型的关键字域*/intsize;/*线性表长度*/sequence_list;/*

9、预定义的顺序表类型*/算法count()用于求顺序表H中值为x的结点的个数。intcount(sequence_list*H,datatypex)intj=0;inti;for(i=0;isize;i+)if(H-ai=x)j+;returnj;2.4设计一个算法，将一个顺序表倒置。即，假如顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a0等于原来的最后一个元素，a1等于原来的倒数第2个元素，a的最后一个元素等于原来的第一个元素。【答】：实现顺序表倒置的算法程序如下：voidverge(seqlist*L)intt,i,j;i=0;j=L-length-1;while(idat

10、ai;L-datai+=L-dataj;L-dataj-=t;2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。【答】：实现此题要求的算法程序如下：voidinsertx(seqlist*L,datatypex)intj;if(L-lengthlength-1;while(j=0&L-datajx)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

11、/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.7循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能

12、得到的调度结果有哪些？假如有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈1入栈后的操作：a.该元素出栈；b.下一个元素入栈；2出栈后的操作：a.栈中其他元素继续出栈；b.原始序列中下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回，实际上就是恢复。程序代码：(2_8_1.c)#include#defineMAX26typedefstructscha

13、raMAX;inttop;Stack;/*定义一些全局变量*/StackS;/*定义全局性的栈*/chardMAX,seqMAX;/*dMAX用于存储原始入栈序列，seqMAX用于存储输出序列*/intlen;/*定义将通过栈的元素个数*/intcount=0;/*用于统计输出序列的个数*/voidinitStack(Stack*S)/*初始化空栈*/S-top=-1;voidpush(Stack*S,charx)/*进栈*/if(S-top=MAX)return;S-top+;S-aS-top=x;charpop(Stack*S)/*出栈*/if(S-top=-1)printf(ERROR,

14、POPEmptyStack);return-1;S-top-;returnS-aS-top+1;intisEmpty(Stack*S)/*判定栈能否为空*/if(S-top=-1)return1;return0;voidoutSeq(char*seq,intlen)/*输出顶点序列*/inti;for(i=0;i/*pos:处理到原始数据中的第pos个元素，seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置*/inti=0;chart;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素用递归*/if(pos=len&isEmpty(&S)outS

15、eq(seq,len);count+;intmain()inti;printf(npleaseinputthenumbescheduled:);scanf(%d,/*用len存储待调度的火车数量*/for(i=0;i列，1423不是一个有效的出栈结果4后面比它小的两个数2，3不是倒序。据此，此题能够通过算法产生n个数的全排列，然后将知足出栈规则的序列输出。产生n个数的全排列有递归与非递归两种实现算法。产生全排列的递归算法：设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r

16、i得到的排列。R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。依此递归定义，可设计产生perm(R)的递归算法如下：递归解法：(2_8_2.c)#includeintcont=1;/*全局变量，用于记录所有可能的出栈序列个数*/voidprint(intstr,intn);/*求整数序列str从k到n的全排列*/voidperm(intstr,intk,intn)inti,temp;if(k=n-1)print(str,n);elsefor(i=

17、k;istrj)if(m=0)bm+=strj;elseif(strjb0)flag=0;elseb0=strj;if(flag)/*知足出栈规则则输出str中的序列*/当前位置：文档视界数据构造(c语言版)第三版习题解答数据构造(c语言版)第三版习题解答字中选出比数字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个数的全排列，对知足进出栈规则的排列则计数并输出。/*本程序输出12.n个序列进栈出栈的序列*/#includeintpl(intn)inta100;/*最大处理范围为99个数*/intflag=1,flag1=0;FILE*rf;inti,j,k,x,count=0;rf=fopen(stack.txt,w);/*pl.txt用于存放进出栈序列结果*/for(i=1;iai)j+;/*找ai后第一个比ai小的元素aj*/k=j+1;while(k1&aij&ai