数据结构简明教程(李春葆版)课后习题答案

数据结构简明教程（第2版）配套练习题参考答案———————数据结构简明教程———————1.练习题1参考答案1.单项选择题（1）D（2）C（3）C（4）A（5）C（6）B（7）C（8）A（9）C（10）B2.填空题（1）①逻辑结构②存储结构③运算（不限制顺序）（2）①线性结构②非线性结构（不限制顺序）（3）①数据元素②关系（4）①没有②没有（5）①前驱②一③后继④任意多个（6）任意多个（7）①顺序②链式③索引④哈希（不限制顺序）（8）①时间②空间（不限制顺序）（9）问题规模（通常用n表示）。（10）辅助或临时空间3.简答题（1）答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是处理步骤。（2）答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)。（3）答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，s=60。第4次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。（4）答：语句s++的执行次数2)2)(3(3)1()1(12121nnnninniniinj。（5）答：其中x++语句为基本运算语句，ninijninninnT1112)1()(1)(=O(n2)。（6）答：由于内循环j的取值范围，所以i≤n/2，则，该程序段的时间复杂度为O(n2)。2/122/124/))12((ninijnininm3log2n32.练习题2参考答案1.单项选择题（1）A（2）C（3）A（4）B（5）C（6）D（7）C（8）B（9）A（10）C（11）B（12）A（13）C（14）D（15）D（16）D（17）A（18）C（19）A（20）D2.填空题（1）L.length=0（2）O(1)（3）O(n)（4）n-i（5）①物理存储位置②指针域（6）①前驱　②O(n)（7）q=p-next;p-next=q-next;free(q);（8）s-next=p-next;p-next=s;（9）O(1)（10）L-next==L3.简答题（1）答：顺序存储结构中，逻辑上相邻元素的存储空间也是相邻的，无需额外空间表示逻辑关系，所以存储密度大，同时具有随机存取特性。缺点是插入或删除元素时平均需要移动一半的元素，同时顺序存储结构的初始分配空间大小难以事先确定。链式存储结构中，逻辑上相邻元素的存储空间不一定是相邻的，需要通过指针域需表示逻辑关系，所以存储密度较小，同时不具有随机存取特性。优点是插入或删除时不需要结点的移动，仅仅修改相关指针域，由于每个结点都是动态分配的，所以空间分配适应性好。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）答：对于表长为n的顺序表，在等概率的情况下，插入一个元素所需要移动元素的平均次数为n/2，删除一个元素所需要移动元素的平均次数为(n-1)/2。（3）答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空；另外使得链表的操作（如插入和删除）在各种情况下得到统一，从而简化了算法的实现过程。（4）答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入———————数据结构简明教程———————结点的next域。所以共修改两个指针。（5）答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。4.算法设计题（1）解：设顺序表L中元素个数为n。i从0到n-2扫描顺序表L：若L.data[i]大于后面的元素L.data[i+1]，则返回false。循环结束后返回true。对应的算法如下：intIncrease(SqListL){inti;for(i=0;iL.length-1;i++)if(L.data[i]L.data[i+1])return0;return1;}（2）解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：voidReverse(SqList&L){inti;ElemTypex;for(i=0;iL.length/2;i++){x=L.data[i];//L.data[i]与L.data[L.length-i-1]交换L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=x;}}本算法的时间复杂度为O(n)。（3）解：通过扫描顺序表L求出最后一个最大元素的下标maxi。将L-data[maxi+1]元素及之后的所有元素均后移一个位置，将x放在L-data[mai+1]处，顺序表长度增1。对应的算法如下：voidInsertx(SqList&L,ElemTypex){inti,maxi=0;5for(i=1;iL.length;i++)if(L.data[i]=L.data[maxi])maxi=i;for(i=L.length;imaxi+1;i--)//将data[maxi+1..n-1]后移L.data[i]=L.data[i-1];L.data[maxi+1]=x;//插入元素xL.length++;//顺序表长度增1}（4）解：设顺序表L中元素个数为n。i从1到n-1扫描顺序表L：如果L.data[i-1]大于L.data[i]，将两者交换，扫描结束后最大元素移到L的最后面。对应的算法如下：voidMovemax(SqList&L){inti;ElemTypetmp;for(i=1;iL.length;i++)if(L.data[i-1]L.data[i]){tmp=L.data[i-1];//data[i-1]与data]i]交换L.data[i-1]=L.data[i];L.data[i]=tmp;}}（5）解：用p指针遍历整个单链表，pre总是指向p结点的前驱结点（初始时pre指向头结点，p指向首结点），当p指向第一个值为x的结点时，通过pre结点将其删除，返回1；否则返回0。对应的算法如下：intDelx(SLinkNode*&L,ElemTypex){SLinkNode*pre=L,*p=L-next;//pre指向p结点的前驱结点while(p!=NULL&&p-data!=x){pre=p;p=p-next;//pre、p同步后移}if(p!=NULL)//找到值为x的结点{pre-next=p-next;//删除p结点free(p);return1;}elsereturn0;//未找到值为x的结点}（6）解：判定链表L从第2个结点开始的每个结点值是否比其前驱结点值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下：intincrease(SLinkNode*L){SLinkNode*pre=L-next,*p;//pre指向第一个数据结点———————数据结构简明教程———————p=pre-next;//p指向pre结点的后继结点while(p!=NULL){if(p-data=pre-data)//若正序则继续判断下一个结点{pre=p;//pre、p同步后移p=p-next;}elsereturn0;}return1;}（7）解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下：voidSplit(SLinkNode*&A,SLinkNode*&B){SLinkNode*p=A-next,*ta,*tb;ta=A;//ta总是指向A链表的尾结点B=(SLinkNode*)malloc(sizeof(SLinkNode));//建立头结点Btb=B;//tb总是指向B链表的尾结点while(p!=NULL){if(p-data%2==0)//偶数结点{ta-next=p;//将p结点链到A中ta=p;p=p-next;}else//奇数结点{tb-next=p;//将p结点链到B中tb=p;p=p-next;}}ta-next=tb-next=NULL;}本算法的时间复杂度为O(n)，空间复杂度为O(1)。（8）解：用p指针遍历整个单链表，pre总是指向p结点的前驱结点（初始时pre指向头结点，p指向首结点），当p指向结点的结点值刚好大于x时查找结束。新创建一个结点s存放元素x，将其插入到pre结点之后。对应的算法如下：voidInsertorder(SLinkNode*&L,ElemTypex){SLinkNode*s,*pre,*p;pre=L;p=L-next;while(p!=NULL&&p-data=x)7{pre=p;p=p-next;//pre、p同步后移}s=(SLinkNode*)malloc(sizeof(SLinkNode));s-data=x;//建立一个待插入的结点pre-next=s;//在结点pre之后插入s结点s-next=p;}（9）解：扫描L的所有数据结点，复制产生L1的结点，采用尾插法创建L1。对应的算法如下：voidCopy(SLinkNode*L,SLinkNode*&L1){SLinkNode*p,*s,*tc;L1=(SLinkNode*)malloc(sizeof(SLinkNode));//创建L1的头结点tc=L1;p=L-next;while(p!=NULL)//扫描L的所有数据结点{s=(SLinkNode*)malloc(sizeof(SLinkNode));s-data=p-data;//由p结点复制产生s结点tc-next=s;//将s结点链接到L1末尾tc=s;p=p-next;}tc-next=NULL;//L1的尾结点next域置为空}（10）解：用p扫描单链表L，pre指向p结点的前驱结点，minp指向最小值结点，minpre指向最小值结点的前驱结点。当p不为L时循环：若p所指结点值小于等于minp所指结点值，置minpre=pre，minp=p，然后pre、p同步后移一个结点。循环结束后minp指向最后一个最小结点，通过minpre结点将minp结点从中删除，然后将其插入到表头即头结点之后。对应的算法如下：voidMove(SLinkNode*&L){SLinkNode*p=L-next,*pre=L;SLinkNode*minp=p,*minpre=L;while(