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

数据结构与算法习题答案第1章2第2章7第3章13第4堂21第5章26第6章32第7章42第8章54第9章60第10章641 .说明下列术语：数匏、数据元素、数据对双、数制结构.解：数据是用于描述客观货物的数值、字符以及一切可以输入到计算机中并由计豫机程序加以处理的符号的集合是计算机操作的对象的总称.数据元素是数据的基本垠位，它是数据中的一个“个体有时,一个数据元案可有若干数据项组成.数据项是数据的不行分割的m小单位，数据对象是具有相同性质的数据元泰的集合，是数据的一个子集，数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合.2 .数据类型和抽象数据类型是如何定义的？两者彳f何异同？抽象数据类型的主要特点是什么？运用抽象数据类型的主要好处是什么？解：数据类型是一个值的集合和定义在此集合上的一组操作的总称.例如.C混才中的整型变1ft.其做为某个区间上的整数(依拳于机器)，定义在其上的操作为加、诚、乘、除和取模等算术运算,抽象数据类型(AbSIraClDalaType,简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作.例如,“整数'是一个抽像数据类型,其数学特性和洋细的计舞机或谙音无关.“抽象”的意义在于强网数据类型的数学特性.抽象数据类型和数据类型实质上及一个概念,只是抽象数据类型的范困更广，除了已有的数据类里外,抽取数据类型还包括用户在设计软件系统时自己定义的数据类型.ADT的定义取决干它的一组逻相特性.与其在计匏机内的我示和实现无关.因此，不论ADT的内部结构如何改变，只要其数学特性不变，都不影响其外部的运用。抽象数据类型的最重要的特点是抽望和信息吃藏.抽象的本质是抽取反映问题本质的东西.忽视非本历的细默环节，从而使所设计的数据结构更具有一般性,可以解决一类同ss.信息吃效就是对用户Ra双数据存储和操作实现的细修环节，运刖者仅衢了解抽象操作，述界面服务，通过界面中的服务来访问这些数据。一个含抽望数据类型的软件模块通常应包含定义、衣示和实现三部分.3 .数据元素之间的关系在计算机中有几种表示方法？各有什么特点？解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)依次存储方法，数据元素依次存放，每个结点只含有一个元素.存储位置反映数据元素间的逻辑关系.存储密度大，但有些操作(如插入、州除)效率较差。(2)链式存储方法。每个结点除包含数据元素信息外还包含一姐指针。指计反映数据元素间的爱科关系.这种操作不要求存储空间连续.使干进行插入和酬除等操作但存储空间利用率较低.另外,Hl于逻排上相邻的数据元索在存储空间上不肯定相邻，所以不悭对JUS行的机存取，(3)卷引存储方法。除数据元泰存储在一地址连续的内行空间外,尚需建立一个隹引表,索引表中的索引指示结点的存储位置.兼有动态和静态特性.14)哈希(或散列)存储方法.通过哈希画数和解决冲突的方法，将关键字侬列在连续的有限的地址空间内,并将哈希函数的值作为该数据元泰的存储地址,其特点是存取逑度快，只能按关雄字随机存取，不能依次存储.也不能折半存取.4 .简述数据结构的三个层次、五个要素。解：数据结构的三个层次是指抽象、实现和评价三个层次，五个要素是指逻轼结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面.5 .举一个数据结构的例子，说明其逻辑结构、存储结构及其运灯:个方面的内容.并说明数据的逻辑结构、存储结何及其运尊之间的关系。解：例如复数数据结构.其逻辑结构是复数的表示.而存储结构是指更数在计算机内的表示，运算是指对宛数初始化、相加等操作.数据的遗物结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示.数据的运算是对数据定义的一组操作.运算是定义在逻辑结构.的.和存储结构无关，而运算的实现则依靠于存储结构.6 .设“为整数，试给出下列各程序段中标号为0的语句的频度.(1) 1=1;ile(i<n)«i=i+2:(2) i=ljk=O:il(i<-n1)(«k+=10*i;i+;<3)i=ljk=O;il(i<=n-1)(i"«k+=10*i：(4)i=l：j=0;il(i+j<=n)I.«if(i>j)j;leei+;<5)x=n：y=0：/n是不小于1的常数whil(x>=(y+l)*(y+l)«y:(6)x=9hy=100:while(y>0)gif(>100)iX-=IOiy-;)elsex+;裤：(1)J：(2)n-1：(3>n-li<4>ls(5)1.nJ：(6)1007 .调用下列C函数/（三）.回答下列问造：(1)试指出,00值的大小,并写出/5)值的推导过程.<2)假定”=5,试指出/(5)值的大小和执行人5)时的输出结果.intf(intn)(inti,j,k.sum-0:fori=hi<n+1.i+)for(j=n:j>i-l:j)for<k=ljk<j*lk)sum+;priatf("sum-%dn"lsun);return(sum)：)解：第一层for循环推妍n+1次，往下执行n次，其次层for执行次数为(n+(n-D+S-D+1),第三层循环体受第一层循环和其次层循环的限制，其执行次数如下去：i=123,nj=n-ln-1n-1n-1j=3333j=222j=l1执行次数为(1+2+n)+(2+3+n>+n=n*n(n+D2-n(n*uT)6°在n=5时，/(5)=55»执行过程中.输出结果为：sum-15.sum-29.sum-41,sum-50.SUnH55(短个SUm占一行).8 .试写一算法，从小到大依次输出依次读入的3个整数x、y和2的值。解：voidprinl_dcsccndinx(intx,inty,intz)/按从大到小依次输出三个数inttemp;scanf(*%d,%d,%d,Sx,ty,&z)：if(x<y)temp=x：x=y;y=teap;if(y<z)(temp-y：y-z：zteap;if(x<y)tomp-x：x=y：y=teap;printf%d%d%d*,x,y,z>：)9将下列各函数，按它们在“roc时的无穷阶数，从小到大排序：“，”一+7'，Mlogn,T,z,logn,*+log/i.(32)",n:+Iogn-解:从大到小排列为：Iogn.n',ilgn.n.nlog.w'+logn.n'.n-n'+7n,.2"2.(32)°.ri,10 .已知Jt阶裴波那契序列的定义为=-=o，.j=O-l=I/.=Z1-I+九+九，n=k.k+l,试编写求上阶裴波那契序列的笫视项值的函数律法，k和M均以值调用的形式在函数参数表中出现.解：intfib(intk,intm.int(求k阶斐波那契序列的第m项的值finttempMAX,itjtsum;if(k<2m<0)returnO;if(三<k-l)f=0:elseif(三=k-l)f=l;else(for(i=0：i<=k-2：i*+>teapiO:te三pk-l=l;初始化for(i=k;i=m;i+)求出序列第k至第个元素的值su三=O:for(j=i-k;j<i：j+)sum÷=tempj;tew>i=s11:)f=tempm：return1：1 .描述头指针、头结点、首元结点的区分，并说明头指叶和头结点的作用.解：在戏性表的饿式存偌结肉中，头指针是指链表的指针，芥链表有头结点则是链表的头结点的指针,头指针具行标识作用,故常用头指针冠以超表的名字.头结点是为了操作的统一、便利而设立的,放在第一个结点之演，其数据域一般无意义，有结点后，对在第一个元索结点前插入结点和捌除第一个结点，其操作与对其他结点的操作统一了，而且无论链表是否为空，头指针均不为空，首元站点也就是第一个元素结点,它是头结点后面的第一个结点。2 .在依次发中嫡入和删除一个结点需平均移动多少个元素？详细的移动次数取决于哪两个因素？解：在依次表中插入和删除一个结点需平均移动表中一半元素，详细的移动次数取决于表长和该元素在表中的位置两个因素。3 .在华融表和双向於表中,是否从当前结点动身访问到任何一个结点？解：在总链表中不能从当前结点动身访问到任何一个结点，但在双向班表中可以从当前结点动身访问到任何一个结点。4 .若较频繁地对一个线性表进行插入和删除操作.该线性表宜采纳何种存谛结构？为什么？解：采纳族式存储结构，它依照实际须要巾请内存空间，而当不须要时又可将不用的结点空间返还给系统。在链式存储结构中插入和删除操作不须要移动元素。5 .有线性表(4g,泓力,w,.aj,采纳单链表存储，头指针为H,集个结点中存放我性表中的一个元素，现更找某个元素值为X的结点,分别写出下面三种状况的查找语句，要求时间尽埴少。<1)线性表中元素无序.(2)线性表中元素按递增有序。(3)雄性表中元素通她有序。解：设单鞋表带头结点,工作指针P初始化为p=M->next.(1) vhiIe(p!=NU1.1.M->data!=x)p=p->next;if(P=NlWrcturnNU1.1.;皆找失败elsereturnp:查找胜利(2) whiIe(p!=NUI.I.&&p->data<x)p=p->next;if(p=NU1.1.Ip->data>x)returnNU1.1.;/皆找失败elsereturnp:查找胜利(3) WhiIe(P!=NUI.1.4Sp->data>x)p=p->next;iHp=NU1.1.p->data<x)returnNU1.1.;杳找失败elsereturnp:查找胜利6 .下面是一免法的核心部分，试说明该究法的功能.pre=1.->next1.是一带头结点的单链表，结点有数据域data和指针域nextif(pre!=NlWwhile(pre->next!=NIJI.I.)p-pre->next;if(p->data>=pre->data)pre=p;elseIZurn(FA1.SE);return(Tl.IRE);解：该簿法的功俯是推断链表1.是否非通战有序，若是则返回TRUE否则返回FA1.SE。Pre指向当前结点P指向PrB的后维.7 .设/力分别指向两个带头结点的有序(从小到大)单魅表C阅读下列程序，并I可答问咫：<1)程序的功能：(2)$、$2中的侑fF含义；(3)pa.而中ft的含义。voidCxaBdJnk1.istpu.1.ink1.istb)pl=pa->next;p2=pb->next;pa->next=MJU.;s1=0：s2=0;while(plSAp2)svitchcase(pl->data<p2->data):p-pl；pl-pl>next;s2*：deletep;case(pl->data>p2->data):2=p2->next：case(pl->data=2->data):p=plpl=l->cxtzp2->nexl=2->ncxt;