课后题解答第一章

什么是数据结构?有关数据结构的讨论涉及哪三个方面?【解答】数据结构是指数据以及相互之间的关系。记为：数据结构={D,R}。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容：①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③施加于该数据结构上的操作。判断下列叙述的对错。如果正确，在题前打“”，否则打“”。(1)数据元素是数据的最小单位。（是基本，数据项中的初等项才是）(2)数据结构是数据对象与对象中数据元素之间关系的集合。(3)数据结构是具有结构的数据对象。(4)数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。(5)算法和程序原则上没有区别，在讨论数据结构时二者是通用的。【解答】(1)(2)(3)(4)(5)判断下列叙述的对错。如果正确，在题前打“”，否则打“”。(1)所谓数据的逻辑结构是指数据元素之间的逻辑关系。(2)同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。（但是可以做的操作相同）(3)数据的逻辑结构与数据元素本身的内容和形式无关。(4)数据结构是指相互之间存在一种或多种关系的数据元素的全体。P3(5)从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。【解答】(1)(2)(3)(4)(5)有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。(1)A=(K,R)，其中K={a1,a2,a3,a4}，R={}(2)B=(K,R)，其中K={a,b,c,d,e,f,g,h}，R={r}，r={a,b,b,c,c,d,d,e,e,f,f,g,g,h}(3)C=(K,R)，其中K={a,b,c,d,e,f,g,h}，R={r}，r={d,b,d,g,b,a,b,c,g,e,g,h,e,f}(4)D=(K,R)，其中K={1,2,3,4,5,6}，R={r}，r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}【解答】(1)(2)(3)(4)指出下列各个算法的功能并计算其时间复杂度(1)intPrime(intn){inti=2,x=(int)sqrt(n);while(i=x){if(n%i==0)break;i++;}if(ix)return1;elsereturn0;}(2)intsum1(intn){intp=1,s=0;for(inti=1;i=n;i++){p*=i;s+=p;}returns;}(3)intsum2(intn){ints=0;for(inti=1;i=n;i++){intp=1;for(intj=1;j=i;j++)p*=j;s+=p;}returns;}a1a3a4a2abcdefghdbdacgdehf123546(4)intfun(intn){inti=1,s=1;while(sn)s+=++i;returni;}(5)voidUseFile(ifstream&inp,intc[]){//假定inp所对应的文件中保存有n个整数。for(inti=0;i10;i++)c[i]=0;intx;while(inpx){i=x%10;c[i]++;}}(6)voidmtable(intn){for(inti=1;i=n;i++){for(intj=i;j=n;j++)couti*j=setw(2)i*j;coutendl;}}(7)voidcmatrix(inta[][],intM,intN,intd){//M和N为全局整型常量for(inti=0;iM;i++)for(intj=0;jN;j++)a[i][j]*=d;}(8)voidmatrimult(inta[][],intb[][],intc[][],intM,intN,intL){//数组a[M][N]、b[N][L]、c[M][L]均为整型数组inti,j,k;for(i=0;iM;i++)for(j=0;jL;j++)c[i][j]=0;for(i=0;iM;i++)for(j=0;jL;j++)for(k=0;kN;k++)c[i][j]+=a[i][k]*b[k][j];}【解答】(1)判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂性为O(n)。(2)计算n1i!i的值。时间复杂性为O(n)。(3)计算n1i!i的值。时间复杂性为O(n2)。(4)求出满足不等式1+2+3++i≥n的最小i值。时间复杂性为O(n)。(5)利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数。时间复杂性为O(n)。(6)打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法项为i与j（i≤j≤n）的乘积。时间复杂性为O(n2)。(7)使数组a[M][N]中的每一个元素均乘以d的值。时间复杂性为O(M×N)。(8)矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。时间复杂性为O(M×N×L)。设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。假定数组A[arraySize]中有多个零元素,试写出一个函数,将A中所有的非零元素依次移到数组A的前端A[i]（0iarraySize）。【解答】因为数组是一种直接存取的数据结构，在数组中元素不是像顺序表那样集中存放于表的前端，而是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面变成零元素的空间清零。函数中设置一个辅助指针free，指示当前可存放的位置，初值为0。先给出作为抽象数据类型数组的类声明。#includeiostream.h//在头文件“array.h”中#includestdlib.hconstintDefaultSize=30;templateclassTypeclassArray{//数组是数据类型相同的n（size）个元素的一个集合,下标范围从0到n-1。对数组中元素//可按下标所指示位置直接访问。private:Type*elements;//数组intArraySize;//元素个数public:Array(intSize=DefaultSize);//构造函数Array(constArrayType&x);//复制构造函数voidcompact();//数组压缩}templateclassTypevoidArrayType::compact(){intfree=0;//非零元素存放地址for(inti=0;iArraySize;i++)//检测整个数组if(elements[i]!=0){//发现非零元素elements[free]=elements[i];//前移free++;elements[i]=0;}}从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。(1)编写一个算法，从任一给定的位置(pr,p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。(2)编写一个算法，从任一给定的位置(pr,p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。【解答】(1)指针p右移k个结点templateclassTypevoidListType::siftToRight(ListNodeType*&p,ListNodeType*&pr,intk){if(p==NULL&&pr!=first){//已经在链的最右端cout已经在链的最右端，不能再右移。endl;return;}inti;ListNodeType*q;if(p==NULL)//从链头开始{i=1;pr=NULL;p=first;}//重置p到链头也算一次右移elsei=0;while(p!=NULL&&ik){//右移k个结点q=p-link;p-link=pr;//链指针p→link逆转指向prpr=p;p=q;i++;//指针pr,p右移}cout右移了i个结点。endl;}(2)指针p左移k个结点templateclassTypevoidListType::siftToLeft(ListNodeType*&p,ListNodeType*&pr,intk){if(p==NULL&&pr==first){//已经在链的最左端cout已经在链的最左端，不能再左移。endl;return;}inti=0;ListNodeType*q;while(pr!=NULL&&ik){//左移k个结点q=pr-link;pr-link=p;//链指针pr-link逆转指向pp=pr;pr=q;i++;//指针pr,p左移}cout左移了i个结点。endl;if(ik){pr=p;p=NULL;}//指针p移出表外，重置p,pr}设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。【解答1】templateclassTypevoidListType::Inverse(){if(first==NULL)return;ListNodeType*p=first-link,*pr=NULL;while(p!=NULL){first-link=pr;//逆转first指针pr=first;first=p;p=p-link;//指针前移}first-link=pr;}【解答2】templateclassTypevoidListType::Inverse(){ListNodeType*p,*head=newListNodeType();//创建表头结点,其link域默认为NULLwhile(first!=NULL){p=first;first=first-link;//摘下first链头结点p-link=head-link;head-link=p;//插入head链前端}first=head-link;deletehead;//重置first,删去表头结点}132)16/(1612C铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。【解答】(1)可能的不同出栈序列有种。(2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈，则1,