《数据结构与算法(徐凤生)》习题答案

《数据结构与算法》习题答案2目录第1章——————————————————2第2章——————————————————7第3章——————————————————13第4章——————————————————21第5章——————————————————26第6章——————————————————32第7章——————————————————42第8章——————————————————54第9章——————————————————60第10章——————————————————643习题11.解释下列术语：数据、数据元素、数据对象、数据结构。解：数据是用于描述客观事物的数值、字符以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合，是计算机操作的对象的总称。数据元素是数据的基本单位，它是数据中的一个“个体”。有时，一个数据元素可有若干数据项组成，。数据项是数据的不可分割的最小单位。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？解：数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如，C语言中的整型变量，其值为某个区间上的整数(依赖于机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。抽象数据类型(AbstractDataType，简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，“整数”是一个抽象数据类型，其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。ADT的定义取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部的使用。抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西，忽略非本质的细节，从而使所设计的数据结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节，使用者仅需了解抽象操作，或界面服务，通过界面中的服务来访问这些数据。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分。3.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。(4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不4能顺序存储，也不能折半存取。4.简述数据结构的三个层次、五个要素。解：数据结构的三个层次是指抽象、实现和评价三个层次，五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面。5.举一个数据结构的例子，说明其逻辑结构、存储结构及其运算三个方面的内容。并说明数据的逻辑结构、存储结构及其运算之间的关系。解：例如复数数据结构，其逻辑结构是复数的表示，而存储结构是指复数在计算机内的表示，运算是指对复数初始化、相加等操作。数据的逻辑结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。6.设n为整数，试给出下列各程序段中标号为@的语句的频度。（1）i=1;while(in)@i=i+2;（2）i=1;k=0;while(i=n-1){@k+=10*i;i++;}（3）i=1;k=0;while(i=n-1){i++;@k+=10*i;}（4）i=1;j=0;while(i+j=n){@if(ij)j++;elsei++;}（5）x=n;y=0;//n是不小于1的常数while(x=(y+1)*(y+1)){@y++;}（6）x=91;y=100;5while(y0){@if(x100){x-=10;y--;}elsex++;}解：（1）21n；（2）n-1；（3）n-1；（4）21n；（5）n；（6）1007.调用下列C函数)(nf，回答下列问题：（1）试指出)(nf值的大小，并写出)(nf值的推导过程。（2）假定n=5，试指出)5(f值的大小和执行)5(f时的输出结果。intf(intn){inti,j,k,sum=0;for(i=1;in+1;i++){for(j=n;ji-1;j--)for(k=1;kj+1;k++)sum++;printf(sum=%d\n,sum);}return(sum);}解：第一层for循环判断n+1次，往下执行n次，第二层for执行次数为(n+(n-1)+(n-1)+…+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i=123…nj=nnnn…nj=n-1n-1n-1n-1…………j=3333j=222j=11执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n*n-1)/6。在n=5时，)5(f=55，执行过程中，输出结果为：sum=15，sum=29，sum=41，sum=50，sum=55(每个sum占一行)。8.试写一算法，从小到大依次输出顺序读入的3个整数x、y和z的值。解：voidprint_descending(intx,inty,intz){//按从大到小顺序输出三个数inttemp;scanf(%d,%d,%d,&x,&y,&z);if(xy){temp=x;x=y;y=temp;}6if(yz){temp=y;y=z;z=temp;}if(xy){temp=x;x=y;y=temp;}printf(%d%d%d,x,y,z);}9.将下列各函数，按它们在n时的无穷阶数，从小到大排序：n，537nnn，nnlog，2/2n，3n，nlog，nnlog2/1，n)2/3(，!n，nnlog2。解：从大到小排列为：nlog，nnlog2/1，n，nnlog，nnlog2，3n，537nnn，2/2n，n)2/3(，!n。10.已知k阶裴波那契序列的定义为00f，01f，…，02kf，11kfknnnnffff21，n=k，k+1，…试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。解：intfib(intk,intm,int&f){//求k阶斐波那契序列的第m项的值finttemp[MAX],i,j,sum;if(k2||m0)return0;if(mk-1)f=0;elseif(m==k-1)f=1;else{for(i=0;i=k-2;i++)temp[i]=0;temp[k-1]=1;//初始化for(i=k;i=m;i++){//求出序列第k至第m个元素的值sum=0;for(j=i-k;ji;j++)sum+=temp[j];temp[i]=sum;}f=temp[m];}return1;}7习题21.描述头指针、头结点、首元结点的区别，并说明头指针和头结点的作用。解：在线性表的链式存储结构中，头指针是指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用。故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一个结点之前，其数据域一般无意义，有结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其他结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一个元素结点，它是头结点后面的第一个结点。2.在顺序表中插入和删除一个结点需平均移动多少个元素？具体的移动次数取决于哪两个因素？解：在顺序表中插入和删除一个结点需平均移动表中一半元素。具体的移动次数取决于表长和该元素在表中的位置两个因素。3.在单链表和双向链表中，是否从当前结点出发访问到任何一个结点？解：在单链表中不能从当前结点出发访问到任何一个结点，但在双向链表中可以从当前结点出发访问到任何一个结点。4.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？解：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用的结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。5.有线性表(niiiaaaaaa,,,,,,,1121)，采用单链表存储，头指针为H，每个结点中存放线性表中的一个元素，现查找某个元素值为x的结点。分别写出下面三种情况的查找语句，要求时间尽量少。（1）线性表中元素无序。（2）线性表中元素按递增有序。（3）线性表中元素递减有序。解：设单链表带头结点，工作指针p初始化为p=H-next。（1）while(p!=NULL&&p-data!=x)p=p-next;if(p==NULL)returnNULL;//查找失败elsereturnp;//查找成功（2）while(p!=NULL&&p-datax)p=p-next;if(p==NULL||p-datax)returnNULL;//查找失败elsereturnp;//查找成功（3）while(p!=NULL&&p-datax)p=p-next;if(p==NULL||p-datax)returnNULL;//查找失败elsereturnp;//查找成功6.下面是一算法的核心部分，试说明该算法的功能。pre=L-next;//L是一带头结点的单链表，结点有数据域data和指针域nextif(pre!=NULL)8while(pre-next!=NULL){p=pre-next;if(p-data=pre-data)pre=p;elsereturn(FALSE);}return(TUURE);解：该算法的功能是判断链表L是否非递减有序，若是则返回TRUE，否则返回FALSE。pre指向当前结点，p指向pre的后继。7.设pa、pb分别指向两个带头结点的有序（从小到大）单链表。阅读下列程序，并回答问题：（1）程序的功能；（2）1s、s2中的值的含义；（3）pa、pb中值的含义。voidexam(LinkListpa,LinkListpb){p1=pa-next;p2=pb-next;pa-next=NULL;s1=0;s2=0;while(p1&&p2){switch{case(p1-datap2-data):p=p1;p1=p1-next;s2++;deletep;case(p1-datap2-data):p2=p2-next;case(p1-data=p2-data):p=p1;p1=p1-next;p2-next=p2-next;pa-next=p;p2=p2-next;s1++;}while(p1){p=p1;p1=p1-next;deletep;s2++;}}}解：本程序的功能是将pa和pb链表中值相同的结点保留在pa链表中（p