数据结构课程 课后习题答案.doc 68页

'练习题及参考答案《数据结构简明教程》练习题及参考答案练习题11.单项选择题（1）线性结构中数据元素之间是（）关系。A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。A.计算方法B.排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2.填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。答：①线性结构②非线性结构（3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。答：①数据元素②关系67 练习题及参考答案（4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。答：①没有②没有（5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。答：①前驱②1③后继④任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。答：任意多个（7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。答：①顺序②链式③索引④哈希（8）一个算法的效率可分为①效率和②效率。答：①时间②空间3.简答题（1）数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（2）简述线性结构、树形结构和图形结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。（3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。（4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)。（5）分析下面程序段中循环语句的执行次数。intj=0,s=0,n=100;do{j=j+1;s=s+10*j;}while(j=i;j--)s++;答：语句s的执行次数。（7）设n为问题规模，求以下算法的时间复杂度。voidfun1(intn){intx=0,i;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)x++;}答：其中x++语句属基本运算语句，=O(n2)。（8）设n为问题规模，是一个正偶数，试计算以下算法结束时m的值，并给出该算法的时间复杂度。voidfun2(intn){intm=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;}答：由于内循环j的取值范围，所以i≤n/2，则，该程序段的时间复杂度为O(n2)。上机实验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。解：maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：#includevoidmaxs(inta[],intn,int&max1,int&max2){inti;max1=max2=a[0];for(i=1;imax1)67 练习题及参考答案{max2=max1;max1=a[i];}elseif(a[i]>max2)max2=a[i];}voidmain(){inta[]={1,4,10,6,8,3,5,7,9,2};intn=10;intmax1,max2;maxs(a,n,max1,max2);printf("最大元素值=%d,次大元素值=%dn",max1,max2);}练习题21.单项选择题（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答：C（2）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。A.访问第i个结点（1≤i≤n）和求第i（2≤i≤n）个结点的前驱结点B.在第i（1≤i≤n）个结点后插入一个新结点C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序答：A（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.8B.63.5C.63D.7答：B（4）链式存储结构所占存储空间（）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的67 练习题及参考答案C.一定是不连续的D.连续或不连续都可以答：D（6）一个线性表在（）情况下适用于采用链式存储结构。A.需经常修改其中的结点值B.需不断对其进行删除插入C.其中含有大量的结点D.其中结点结构复杂答：B（7）单链表的存储密度（）A.大于1B.等于1C.小于1D.不能确定答：C2.填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（①）元素，具体移动的元素个数与（②）有关。答：①表中一半②表长和该元素在表中的位置（2）向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动（）个元素。答：n-i+1（3）向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。答：n-i（4）在顺序表中访问任意一个元素的时间复杂度均为（①），因此顺序表也称为（②）的数据结构。答：①O(1)②随机存取（5）顺序表中逻辑上相邻的元素的物理位置（①）相邻。单链表中逻辑上相邻的元素的物理位置（②）相邻。答：①一定②不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。答：其前驱结点的链域的值（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（①），其时间复杂度为（②）。答：①前驱结点的地址②O(n)（8）含有n（n>1）个结点的循环双向链表中，为空的指针域数为（）。答：03.简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是67 练习题及参考答案插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n>1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。①单链表；②仅有头指针不带头结点的循环单链表；③双链表；④仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。67 练习题及参考答案4.算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：voidreverse(SqList&L){inti;ElemTypex;for(i=0;ij)//表示L.data[i]和L.data[0..j]中所有元素都不相同{j++;L.data[j]=L.data[i];}}L.length=j+1;//顺序表长度置新值}本算法的时间复杂度为O(n2)，空间复杂度为O(1)。（3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data[0..0]，置e=L.data[0]，用i从1开始遍历L的所有元素：当L.data[i]≠e时，将它放在L.data[k]中，k增1，置e=L.data[i]，最后将L的length置为k。对应的算法如下：voiddelsame1(SqList&L)//L为引用型参数{inti,k=1;//k保存不重复的元素个数ElemTypee;67 练习题及参考答案e=L.data[0];for(i=1;inext;//p指向*q的前驱结点while(q!=NULL&&q->data!=x){p=q;q=q->next;}if(q!=NULL)//找到值为x的结点{p->next=q->next;free(q);return1;}elsereturn0;//未找到值为x的结点}（5）设计一个算法判定单链表L是否是递增的。解：判定链表L从第2个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下：intincrease(SLink*L){SLink*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;67 练习题及参考答案}（6）有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下：voidSplit(SLink*&A,SLink*&B){SLink*p=A->next,*ra,*rb;ra=A;B=(SLink*)malloc(sizeof(SLink));//建立头结点rb=B;//r总是指向B链表的尾结点while(p!=NULL){if(p->data%2==0)//偶数结点{ra->next=p;//将*p结点链到A中ra=p;p=p->next;}else//奇数结点{rb->next=p;//将*p结点链到B中rb=p;p=p->next;}}ra->next=rb->next=NULL;}本算法的时间复杂度为O(n)，空间复杂度为O(1)。（7）有一个有序单链表（从小到大排列），表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。解：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：voidinorderList(SLink*&L,ElemTypex){SLink*s,*p,*q;s=(SLink*)malloc(sizeof(SLink));//建立一个待插入的结点s->data=x;s->next=NULL;if(L==NULL||xdata)//若单链表为空或x小于第1个结点date域{s->next=L;//把*s结点插入到头结点之后L=s;}else{q=L;//寻找插入位置,p指向待比较的结点,q指向p的前驱结点p=q->next;67 练习题及参考答案while(p!=NULL&&x>p->data)//若x小于p所指结点的data域值if(x>p->data){q=p;p=p->next;}s->next=p;//将s结点插入到*q和*p之间q->next=s;}}（8）有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：用p遍历单链表，用r遍历*p结点之后的结点，q始终指向*r结点的直接前驱结点，若r->data==p->data，则删除*r结点，否则q、r同步后移一个结点。对应的算法如下：voiddels1(SLink*&L){SLink*p=L->next,*q,*r,*t;while(p!=NULL){q=p;r=q->next;while(r!=NULL){if(r->data==p->data)//r指向被删结点{t=r->next;q->next=t;free(r);r=t;}else{q=r;r=r->next;}}p=p->next;}}本算法的时间复杂度为O(n2)。（9）有一个递增有序单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：由于是有序表，所以相同值域的结点都是相邻的。用p遍历递增单链表，若*p结点的值域等于其后结点的值域，则删除后者。对应的算法如下：voiddels(SLink*&L){SLink*p=L->next,*q;while(p->next!=NULL){if(p->data==p->next->data)//找到重复值的结点67 练习题及参考答案{q=p->next;//q指向这个重复值的结点p->next=q->next;//删除*q结点free(q);}elsep=p->next;}}本算法的时间复杂度为O(n)。（10）有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。解：先找到第一个元素值为x的结点*p，q指向其后继结点，本题是将*p结点移到*q结点之后，实现过程是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：intswap(DLink*L,ElemTypex){DLink*p=L->next,*q;while(p!=NULL&&p->data!=x)p=p->next;if(p==NULL)//未找到值为x的结点return0;else//找到值为x的结点*p{q=p->next;//q指向*p的后继结点if(q!=NULL)//*p结点不是尾结点{p->prior->next=q;//先删除*p结点q->prior=p->prior;p->next=q->next;//将*p结点插入到*q结点之后if(q->next!=NULL)q->next->prior=p;q->next=p;p->prior=q;return1;}else//*p结点是尾结点return0;//无法与后继结点交换，返回0}}（11）对于有n（n≥1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。解：采用头插法重建循环单链表L的思路，先建立一个空的循环单链表，用p遍历所有数据结点，每次将*p结点插入到前端。对应的算法如下：voidReverse(SLink*&L){SLink*p=L->next,*q;67 练习题及参考答案L->next=L;//建立一个空循环单链表while(p!=L){q=p->next;p->next=L->next;//将*p结点插入到前端L->next=p;p=q;}}上机实验题2有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。#include#include"SLink.h"voidUnion(SLink*L1,SLink*L2,SLink*&L3)//求并集{SLink*p,*q,*s,*tc;L3=(SLink*)malloc(sizeof(SLink));tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL){if(p->datadata){s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;p=p->next;}elseif(p->data>q->data){s=(SLink*)malloc(sizeof(SLink));s->data=q->data;tc->next=s;tc=s;q=q->next;}else{s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;67 练习题及参考答案p=p->next;q=q->next;}}while(p!=NULL){s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;p=p->next;}while(q!=NULL){s=(SLink*)malloc(sizeof(SLink));s->data=q->data;tc->next=s;tc=s;q=q->next;}tc->next=NULL;}voidInterSection(SLink*L1,SLink*L2,SLink*&L3)//求交集{SLink*p,*q,*s,*tc;L3=(SLink*)malloc(sizeof(SLink));tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL){if(p->datadata)p=p->next;elseif(p->data>q->data)q=q->next;else//p->data=q->data{s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;p=p->next;q=q->next;}}tc->next=NULL;}voidSubs(SLink*L1,SLink*L2,SLink*&L3)//求差集67 练习题及参考答案{SLink*p,*q,*s,*tc;L3=(SLink*)malloc(sizeof(SLink));tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL){if(p->datadata){s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;p=p->next;}elseif(p->data>q->data)q=q->next;else//p->data=q->data{p=p->next;q=q->next;}}while(p!=NULL){s=(SLink*)malloc(sizeof(SLink));s->data=p->data;tc->next=s;tc=s;p=p->next;}tc->next=NULL;}voidmain(){SLink*A,*B,*C,*D,*E;ElemTypea[]={1,3,6,8,10,20};CreateListR(A,a,6);//尾插法建表printf("集合A:");DispList(A);ElemTypeb[]={2,5,6,10,16,20,30};CreateListR(B,b,7);//尾插法建表printf("集合B:");DispList(B);printf("求A、B并集Cn");Union(A,B,C);//求A、B并集Cprintf("集合C:");DispList(C);printf("求A、B交集Cn");InterSection(A,B,D);//求A、B并集Dprintf("集合D:");DispList(D);67 练习题及参考答案printf("求A、B差集En");Subs(A,B,E);//求A、B差集Eprintf("集合E:");DispList(E);DestroyList(A);DestroyList(B);DestroyList(C);DestroyList(D);DestroyList(E);}练习题31.单项选择题（1）栈中元素的进出原则是（）。A.先进先出B.后进先出C.栈空则进D.栈满则出答：B（2）设一个栈的进栈序列是A、B、C、D（即元素A～D依次通过该栈），则借助该栈所得到的输出序列不可能是（）。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C答：D（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde答：C（4）已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n）则第j（1≤j≤n）个出栈元素是（）。A.iB.n-iC.j-i+1D.不确定答：D（5）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（）。A.st.top==-1B.st.top!=-1C.st.top!=MaxSizeD.st.top==MaxSize答：A（6）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈满的条件是。A.st.top!=-1B.st.top==-1C.st.top!=MaxSize-1D.st.top==MaxSize-1答：D（7）队列中元素的进出原则是（）。A.先进先出B.后进先出C.栈空则进D.栈满则出67 练习题及参考答案答：A（8）元素A、B、C、D顺序连续进入队列qu后，队头元素是（①），队尾元素是（②）。A.AB.BC.CD.D答：①A②D。（9）一个队列的入列序列为1234，则队列可能的输出序列是（）。A.4321B.1234C.1432D.3241答：B（10）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队满条件是（）。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontA.qu.rear==qu.front答：C（11）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队空条件是（）。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D（12）设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r（队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（）。A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N答：D（13）设有4个数据元素a、b、c和d，对其分别进行栈操作或队操作。在进栈或进队操作时，按a、b、c、d次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（①），第二次出栈得到的元素是（②）；类似地，考虑对这4个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（③），第二次出队得到的元素是（④）。经操作后，最后在栈中或队中的元素还有（⑤）个。①～④：A.aB.bC.cD.d⑤：A.1B.2C.3D.0答：①B②D③A④B⑤B67 练习题及参考答案（14）设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A.5B.4C.3D.2答：C2.填空题（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（①）。不允许插入和删除运算的一端称为（②）。答：①栈顶②栈底（2）一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为（）。答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。（3）有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有（）。答：CDBAE、CDEBA、CDBEA。（4）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（）。答：data[top]=x;top++;（5）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（）。答：top--;x=data[top];（6）（）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。答：队列（7）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（）。答：rear=(rear+1)%(m+1);A[rear]=x;（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操作是（）。答：front=(front+1)%(m+1);x=A[rear];3.简答题（1）简要说明线性表、栈与队的异同点。答：相同点：都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①67 练习题及参考答案运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。（2）顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下：①设置一个布尔变量以区别队满还是队空；②浪费一个元素的空间，用于区别队满还是队空。③使用一个计数器记录队列中元素个数（即队列长度）。通常采用法②，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置，这样判断循环队列队空标志是：front=rear，队满标志是：(rear+1)%MaxSize=front。4.算法设计题（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成，不能直接用st.data[0]来得到栈底元素。解：假定采用顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。对应算法如下：intGetBottom(SqStackst,ElemType&x){ElemTypee;SqStacktmpst;//定义临时栈InitStack(tmpst);//初始化临时栈if(StackEmpty(st))//空栈返回0return0;while(!StackEmpty(st))//临时栈tmpst中包含st栈中逆转元素{Pop(st,x);Push(tmpst,x);}while(!StackEmpty(tmpst))//恢复st栈中原来的内容{Pop(tmpst,e);Push(st,e);}return1;//返回1表示成功}（2）设计一个算法，采用一个顺序栈逆向输出单链表L中所有元素。解：本题并不需要改变单链表L的结构。设置一个顺序栈st，先遍历单链表并将所有元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下：voidReverseDisp(SLink*L)67 练习题及参考答案{ElemTypex;structnode{ElemTypedata[MaxSize];inttop;}st;//定义一个顺序栈st.top=-1;SLink*p=L->next;while(p!=NULL)//遍历单链表，将所有元素进栈{st.top++;st.data[st.top]=p->data;p=p->next;}while(st.top!=-1)//栈不空循环，输出栈中所有元素{x=st.data[st.top];st.top--;printf("%d",x);}printf("n");}（3）设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空（0）或可能满（1），这样加上front==rear可以作为队空或队满的条件。要求设计队列的相关基本运算算法。解：设计的队列的类型如下：typedefstruct{ElemTypedata[MaxSize];intfront,rear;//队头和队尾指针inttag;//为0表示队空,为1时表示不空}QueueType;初始时tag=0，进行成功的插入操作后tag=1，进行成功的删除操作后tag=0；因为只有在插入操作后队列才有可能满，只有在删除操作后队列才有可能空，因此，这样的队列的基本要素如下：初始时：tag=0，front=rear队空条件：qu.front==qu.rear&&qu.tag==0队满条件：qu.front==qu.rear&&qu.tag==1对应的算法如下：//-----初始化队列算法-----voidInitQueue1(QueueType&qu){qu.front=qu.rear=0;qu.tag=0;//为0表示队空可能为空67 练习题及参考答案}//-----判队空算法-----intQueueEmpty1(QueueTypequ){return(qu.front==qu.rear&&qu.tag==0);}//-----判队满算法-----intQueueFull1(QueueTypequ){return(qu.tag==1&&qu.front==qu.rear);}//-----进队算法-----intenQueue1(QueueType&qu,ElemTypex){if(QueueFull1(qu)==1)//队满return0;qu.rear=(qu.rear+1)%MaxSize;qu.data[qu.rear]=x;qu.tag=1;//至少有一个元素,可能满return1;}//-----出队算法-----intdeQueue1(QueueType&qu,ElemType&x)//出队{if(QueueEmpty1(qu)==1)//队空return0;qu.front=(qu.front+1)%MaxSize;x=qu.data[qu.front];qu.tag=0;//出队一个元素,可能空return1;}（4）假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，设计出相应的队初始化、进队、出队和判队空的算法。解：假设链队是不带头结点的循环单链表，其示意图如图3.1所示。队空条件：rear==NULL；进队操作：在*rear结点之后插入结点并让rear指向该结点；出队操作：删除*rear结点之后的一个结点。对应的算法如下：图3.1不带头结点的循环单链表表示队列typedefstructnode{ElemTypedata;67 练习题及参考答案structnode*next;}QNode;//链队结点类型//-----初始化队列-----voidInitQueue(QNode*&rear){rear=NULL;}//-----进队算法-----voidEnQueue(QNode*&rear,ElemTypex){QNode*s;s=(QNode*)malloc(sizeof(QNode));//创建新结点s->data=x;if(rear==NULL)//原链队为空{s->next=s;//构成循环链表rear=s;}else{s->next=rear->next;//将*s结点插入到*rear结点之后rear->next=s;rear=s;//让rear指向这个新插入的结点}}//-----出队算法-----intDeQueue(QNode*&rear,ElemType&x){QNode*q;if(rear==NULL)//队空return0;elseif(rear->next==rear)//原队中只有一个结点{x=rear->data;free(rear);rear=NULL;}else//原队中有两个或以上的结点{q=rear->next;x=q->data;rear->next=q->next;free(q);}return1;}//-----判队空算法-----intQueueEmpty(QNode*rear){67 练习题及参考答案return(rear==NULL);}上机实验题3假设以I和O字符分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。设计一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）。并用相关数据进行测试。解：采用一个链栈来判断操作序列是否合法，其中str为存放操作序列的字符数组，n为该数组的元素个数（这里的ElemType类型设定为char）。对应的算法如下：#include#includetypedefstructnode{chardata;structnode*next;}LStack;//链栈结点类型voidInitStack(LStack*&ls)//初始化栈运算算法{ls=NULL;}voidDestroyStack(LStack*&ls)//销毁栈运算算法{LStack*pre=ls,*p;if(pre==NULL)return;//考虑空栈的情况p=pre->next;while(p!=NULL){free(pre);//释放*pre结点pre=p;p=p->next;//pre、p同步后移}free(pre);//释放尾结点}voidPush(LStack*&ls,charx)//进栈运算算法{LStack*p;p=(LStack*)malloc(sizeof(LStack));p->data=x;//创建结点*p用于存放xp->next=ls;//插入*p结点作为栈顶结点ls=p;}intPop(LStack*&ls,char&x)//出栈运算算法{LStack*p;if(ls==NULL)//栈空,下溢出返回0return0;67 练习题及参考答案else//栈不空时出栈元素x并返回1{p=ls;//p指向栈顶结点x=p->data;//取栈顶元素xls=p->next;//删除结点*pfree(p);//释放*p结点return1;}}intStackEmpty(LStack*ls)//判断栈空运算算法{if(ls==NULL)return1;elsereturn0;}intjudge(charstr[],intn)//判断str序列的合法性{inti,tag;charx;LStack*ls;InitStack(ls);//链栈ls初始化for(i=0;inext==NULL。（3）对于一个含有n个字符的链串s，查找第i个元素的算法的时间复杂度为（）。答：O(n)3.简答题（1）设s为一个长度为n的串，其中的字符各不相同，则s中的互异的非平凡子串（非空且不同于s本身）的个数是多少？答：由串s的特性可知，1个字符的子串有n个，2个字符的子串有n-1个，3个字符的子串有n-2个，…，n-2个字符的子串有3个，n-1个字符的子串有2个。所以，非平凡子串的个数=n+(n-1)+(n-2)+…+2=。（2）若s1和s2为串，给出使s1//s2=s2//s1成立的所有可能的条件（其中，“//”表示两个串连接运算符）。答：所有可能的条件为：（1）s1和s2为空串67 练习题及参考答案（2）s1或s2其中之一为空串（3）s1和s2为相同的串（4）若两串长度不等，则长串由整数个短串组成。4.算法设计题（1）设计一个算法RepChar(s,x,y)，将顺序串s中所有字符x替换成字符y。要求空间复杂度为O(1)。解：因要求算法空间复杂度为O(1)，所以只能对串s直接替换。从头开始遍历串s，一旦找到字符x便将其替换成y。对应算法如下：voidRepStr(SqString&s,charx,chary){inti;for(i=0;idata≥p->data时，p和q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下：intincrease(LinkString*s){LinkString*p=s->next,*q;if(p!=NULL){while(p->next!=NULL){q=p->next;//q指向*p的后续结点if(q->data>=p->data)p=q;else//逆序时返回0return0;}}return1;}（3）假设以链式结构存储一个串s，设计一个算法求串s中最长等值子串。解：假设串用带头结点的单链表存储串s。用max存放最大平台长度，扫描串s，计算一个平台的长度n，若n大于max，则置max为n。对应的算法如下：intmaxlength(LinkString*s){intn,max=0;LinkString*p=s->next,*q;while(p!=NULL){n=1;q=p;p=p->next;while(p!=NULL&&p->data==q->data){n++;67 练习题及参考答案p=p->next;}if(n>max)max=n;}returnmax;}上机实验题4两个非空串s和t采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下：#include#include"SqString.h"//包含顺序串的基本运算函数SqStringmaxcomstr(SqStrings,SqStringt){SqStringstr;intmidx=0,mlen=0,tlen,i=0,j,k;//用(midx,mlen)保存最大公共子串while(imlen)//将较大长度者赋给midx与mlen{midx=i;mlen=tlen;}j+=tlen;//继续扫描t中第j+tlen字符之后的字符}elsej++;}i++;//继续扫描s中第i字符之后的字符}for(i=0;i#definem3#definen4voidminmax(intA[m][n]){inti,j,have=0;intmin[m],max[n];for(i=0;imax[j])max[j]=A[i][j];}for(i=0;i=0)if(a[i][j]!=x)if(a[i][j]>x)j--;//修改列号elsei++;//修改行号else//a[i][j]==x{flag=1;break;67 练习题及参考答案}returnflag;}上机实验题5采用一维动态数组模拟二维数组的操作，即将一个二维数组的元素存放在一个一维数组中，一维数组的空间根据二维数组的大小动态分配。设计一个算法实现两个二维数组的相加运算。并用相关数据进行测试。解：对应的程序如下：#include#includetypedefintElemType;typedefstruct{ElemType*p;//存放二维数组元素intm,n;//存放二维数组的行数和列数}Mat2;voidInitMat(Mat2&M,intx,inty)//初始化二维数组M{M.m=x;M.n=y;M.p=(ElemType*)malloc(x*y*sizeof(ElemType));}intSetij(Mat2&M,inti,intj,ElemTypex)//置二维数组(i,j)位置值为x{intk;if(i>=0&&i=0&&j=0&&i=0&&jlchild==NULLB.p->ltag==1C.p->ltag==1且p->lchild==NULLD.以上都不对答：B67 练习题及参考答案（17）根据使用频率为5个字符设计的哈夫曼编码不可能是（）。A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,10答：C2.填空题（1）由3个结点所构成的二叉树有（）种形态。答：5（2）一棵深度为6的满二叉树有（①）个分支结点和（②）个叶子结点。答：①31②32（3）设一棵完全二叉树有700个结点，则共有（）个叶子结点。答：350（4）设一棵完全二叉树具有1000个结点，则此完全二叉树有（①）个叶子结点，有（②）个度为2的结点，有（③）个单分支结点。答：①500②499③1（5）一棵二叉树的第i（i≥1）层最多有（）个结点。答：2i-1（6）深度为h的完全二叉树至少有（①）个结点，至多有（②）个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（③）。答：①2h-1②2h-1③2h-1。（7）对含有n个结点的二叉树进行中序递归遍历，该算法平均空间复杂度为（）。答：O(n)（8）用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是（）。答：333.简答题（1）一棵度为2的树与一棵二叉树有何区别？答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的，即在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。另外，一棵度为2的树至少有3个结点，而一棵二叉树的结点个数可以为0。（2）试求含有n0个叶子结点的完全二叉树的总结点数。答：由二叉树的性质可知，n2=n0-1，在完全二叉树中，度为1的结点数n1至多为1，所以具有n0个叶子结点的完全二叉树结点数是n0+(n0-1)+1=2n0或2n0-1。（3）某二叉树的结点数据采用顺序存储结构如下：1234567891011121314151617181920EAF#D#H##C###GI####B①画出该二叉树；67 练习题及参考答案②写出结点值为D的双亲结点及左、右子树。③将此二叉树还原为森林。答：①该二叉树如图8.21所示。图8.21一棵二叉树图8.2二叉树还原成的森林②结点值为D的结点的双亲结点为结点值为A的结点，其左子树为以C为根结点的子树，其右子树为空。③由此二叉树还原成的森林如图8.2所示。（4）证明完全二叉树的每棵子树也都是完全二叉树。证明：让T是一棵完全二叉树，S是它的一棵子树。由子树定义可知，S是由T中某个结点及其所有子孙构成的。由于T是完全二叉树，T的所有叶子结点都在两个相邻的层次上，因此，S的所有叶子结点都在两个相邻的层次上。类似的，如果在S中存在不位于底层上结点层，那么，该层也不位于T的底层上，它必须在T中所有底层叶子结点的右边，因此它也必须在S中所有底层叶子结点的右边。从而得到S是完全二叉树。（5）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA答：由这些显示部分推出二叉树如图8.3所示。则先序序列为ABDFKICEHJG；中序序列为DBKFIAHEJCG；后序序列为DKIFBHJEGCA。图8.3一棵二叉树（6）如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0=n2+1，即n2=n0-1，则总结点数n=n0+n2=2n0-1。67 练习题及参考答案4.算法设计题（1）已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计一个算法求出离下标分别为i和j（0q)p=p/2;elseq=q/2;returnA[p];}（2）已知一棵二叉树采用顺序方式存储在数组A[1..n]中。设计一个先序遍历的递归算法。解：先序遍历树中结点的递归算法如下：voidPreOrder1(ElemTypeA[],inti,intn){if(idata只有一个结点时f(bt)=Max{f(bt->lchild),f(bt->rchild),bt->data}其他情况对应的算法如下：ElemTypeMaxNode(BTNode*bt){ElemTypemax,max1,max2;if(bt->lchild==NULL&&bt->rchild==NUL)returnbt->data;else{max1=MaxNode(bt->lchild);//求左子树的最大结点值max2=MaxNode(bt->rchild);//求右子树的最大结点值max=bt->data;if(max1>max)max=max1;if(max2>max)max=max2;//求最大值return(max);//返回最大值}67 练习题及参考答案}（4）假设含有n个结点的二叉树采用二叉链存储结构。设计一个算法输出中序遍历序列中的第k（1≤i≤n）个结点值。解：对应的算法如下：inti=0;//i为全局变量voidTrav(BTNode*bt,intk){if(bt!=NULL){Trav(bt->lchild,k);//遍历左子树i++;if(i==k){printf("%c",bt->data);return;}Trav(bt->rchild,k);//遍历右子树}}（5）假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树中结点值为x的结点的层数。解：对应的递归算法如下：intLevel(BTNode*bt,ElemTypex,inth)//调用h对应的实参置初值1{intl;if(bt==NULL)return0;elseif(bt->data==x)returnh;else{l=Level(bt->lchild,x,h+1);//在左子树中查找if(l!=0)returnl;else//在左子树中未找到,再在右子树中查找return(Level(bt->rchild,x,h+1));}}上机实验题6假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。解：采用递归和层次遍历两种求解方法，对应的程序如下：#include#include"BTree.h"67 练习题及参考答案voidPath1(BTNode*bt,ElemTypex,ElemTypepath[],intpathlen){inti;if(bt!=NULL){if(bt->data==x)//找到值为x的结点{printf("从根结点到%c结点的路径:",bt->data);for(i=0;idata);return;}else{path[pathlen]=bt->data;//将当前结点放入路径中pathlen++;//path中元素个数增1Path1(bt->lchild,x,path,pathlen);//递归遍历左子树Path1(bt->rchild,x,path,pathlen);//递归遍历右子树}}}voidPath2(BTNode*bt,ElemTypex){BTNode*p;ElemTypepath[MaxSize];inti,d;struct{BTNode*s;//存放结点指针intparent;//存放其双亲结点在qu中的下标}qu[MaxSize];//qu存放队中元素intfront=-1,rear=-1;//队头队尾指针rear++;qu[rear].s=bt;//根结点进队qu[rear].parent=-1;//根结点没有双亲,其parent置为-1while(front!=rear)//队不空循环{front++;p=qu[front].s;//出队一个结点*p,它在qu中的下标为frontif(p->data==x)//找到值为x的结点{printf("从根结点到%c结点的路径:",p->data);d=0;path[d]=p->data;i=qu[front].parent;while(i!=-1){d++;path[d]=qu[i].s->data;i=qu[i].parent;}printf("%c",path[d]);for(i=d-1;i>=0;i--)67 练习题及参考答案printf("→%c",path[i]);printf("n");}if(p->lchild!=NULL)//*p有左孩子,将左孩子进队{rear++;qu[rear].s=p->lchild;qu[rear].parent=front;//左孩子的双亲为qu[front]结点}if(p->rchild!=NULL)//*p有右孩子,将右孩子进队{rear++;qu[rear].s=p->rchild;qu[rear].parent=front;//右孩子的双亲为qu[front]结点}}}voidmain(){BTNode*bt;ElemTypepath[MaxSize],x="I";CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");//建立图6.14的二叉链printf("bt括号表示法:");DispBTree(bt);printf("n");printf("解法1:n");Path1(bt,x,path,0);printf("解法2:n");Path2(bt,x);}练习题71.单项选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。A.1/2B.1C.2D.4答：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.4答：B（3）有8个顶点的无向图最多有（）条边。A.14B.28C.56D.112答：B67 练习题及参考答案（4）有8个顶点的无向连通图最少有（）条边。A.5B.6C.7D.8答：C（5）有8个顶点的有向完全图有（）条边。A.14B.28C.56D.112答：C（6）n个顶点的强连通图中至少有（）条边。A.nB.n-1C.2nD.n(n-1)答：A（7）若一个图的邻接矩阵是对称矩阵，则该图一定是（）。A.有向图B.无向图C.连通图D.无向图或有向图答：D（8）设无向图G=(V,E)和G"=(V",E")，如果G"是G的生成树，则下面的说法中错误的是（）。A.G"为G的子图B.G"为G的连通分量C.G"为G的极小连通子图且V=V"D.G"是G的一个无环子图答：B（9）用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A.栈B.队列C.树D.图答：B（10）用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A.栈B.队列C.树D.图答：A（11）图的广度优先遍历算法中用到辅助队列，每个顶点最多进队（）次。A.1B.2C.3D.不确定答：A（12）一个无向图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（）次深度优先遍历算法。A.kB.1C.k-1D.k+1答：A（13）已知一个图的邻接表如图7.1所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）。图7.1一个邻接表67 练习题及参考答案A.0132B.0231C.0321D.0123答：D（14）已知一个图的邻接表如图7.1所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）。A.0132B.0231C.0321D.0123答：D（15）深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历答：A（16）广度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历答：D（17）最小生成树指的是（）。A.由连通网所得到的边数最少的生成树B.由连通网所得到的顶点数相对较少的生成树C.连通网中所有生成树中权值之和为最小的生成树D.连通网的极小连通子图答：C（18）任何一个无向连通图的最小生成树（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在答：B（19）用Prim和Kruskal两种算法构造图的最小生成树，所得到的最小生成树（）。A.是相同的B.是不同的C.可能相同，也可能不同D.以上都不对答：C（20）对于有n个顶点e条边的有向图，求最短路径的Dijkstra算法的时间复杂度为（）。A.O(n)B.O(n+e)C.O(n2)D.O(ne)答：C（21）对于有n个顶点e条边的有向图，求最短路径的Floyd算法的时间复杂度为（）。A.O(n)B.O(ne)C.O(n2)D.O(n3)答：D（22）若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图。A.是个有根有向图B.是个强连通图C.含有多个入度为0的顶点D.含有顶点数目大于1的强连通分量答：D（23）关键路径是事件结点网络中（）。A.从源点到汇点的最长路径B.从源点到汇点的最短路径67 练习题及参考答案C.最长的回路D.最短的回路答：A2.填空题（1）n个顶点的连通图至少（）条边。答：n-1（2）在图的邻接矩阵和邻接表表示中，（①）表示一定是唯一的，而（②）表示可能不唯一。答：①邻接矩阵②邻接表（3）具有10个顶点的无向图中，边数最多为（）。答：45（4）在有n个顶点的有向图中，每个顶点的度最大可达（）。答：2(n-1)。（5）n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。答：O(n2)（6）n个顶点e条边的有向图，若采用邻接表存储，则空间复杂度为（）。答：O(n+e)（7）n个顶点e条边的有向图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（①）；若采用邻接表存储时，该算法的时间复杂度为（②）。答：①O(n2)②O(n+e)（8）n个顶点e条边的有向图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（①）；若采用邻接表存储时，该算法的时间复杂度为（②）。答：①O(n2)②O(n+e)（9）一个连通图的生成树是该图的一个（）。答：极小连通子图（10）用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为（①）；用克鲁斯卡尔（Kruskal）算法的时间复杂度是（②）。若要求一个稀疏图G的最小生成树，最好用（③）算法来求解；若要求一个稠密图G的最小生成树，最好用（④）算法来求解。答：①O(n2)②O(elog2e)③Kruskal④Prim3.简答题（1）从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？答：设图的顶点个数和边数分别为n和e。邻接矩阵的存储空间大小为O(n2)，与e无关，因此适合于稠密图的存储。邻接表的存储空间大小为O(n+e)（有向图）或O(n+2e)（无向图），与e有关，因此适合于稀疏图的存储。（2）对于图7.2所示的带权有向图，求从顶点0到其他各顶点的最短路径。67 练习题及参考答案图7.2一个有向带权图答：求解过程如下：Sdistpath01234560123456{0}0∞∞∞11∞70-1-1-10-10{0,6}022∞1311∞706-160-10{0,6,4}022∞1311∞706-160-10{0,6,4,3}022∞131116706-16030{0,6,4,3,5}0222513111670656030{0,6,4,3,5,1}0222513111670656030{0,6,4,3,5,1,2}0222513111670656030求解结果如下：从0到1的最短路径长度为:22路径为:0,6,1从0到2的最短路径长度为:25路径为:0,6,3,5,2从0到3的最短路径长度为:13路径为:0,6,3从0到4的最短路径长度为:11路径为:0,4从0到5的最短路径长度为:16路径为:0,6,3,5从0到6的最短路径长度为:7路径为:0,6（3）某带权有向图及其邻接表表示如图7.3所示，给出深度优先遍历序列，将该图作为AOE网，给出C的最早开始时间及活动FC的最迟开始时间。图7.3有向图及其单邻接表答：深度优先遍历序列为：A,B,C,E,G,D,F。求最早开始时间和最迟开始时间的过程如下：ve(A)=0，ve(D)=3，ve(F)=ve(D)+3=6，ve(B)=1，ve(C)=MAX{ve(B)=3,ve(A)+2,ve(F)+3}=7，67 练习题及参考答案ve(E)=MAX{ve(B)+1,ve(C)+2}=9，ve(G)=MAX{ve(E)+1,ve(F)+5}=11，vl(G)=11，vl(E)=vl(G)-1=10，vl(C)=vl(E)-2=8，vl(B)=MIN{vl(E)-1,vl(C)-3}=5，vl(F)=MIN{vl(G)-5,vl(C)-1}=6，vl(D)=vl(F)-3=3，vl(A)=MIN{vl(B)-1,vl(C)-2,vl(D)-3}=0;则：l(FC)=vl(C)-1=7所以，事件C的最早开始时间为7，活动FC的最迟开始时间为7。（4）对于如图7.4所示的有向图G，给出它的4个不同的拓扑有序序列。答：该图的4个不同的拓扑有序序列是：12345678，12354678，12347856，12347568（实际上不止4个）。图7.4一个有向图4.算法设计题（1）假设图G采用邻接矩阵存储，给出图的深度优先遍历算法，并分析算法的时间复杂度。解：基于图的邻接矩阵表示的深度优先遍历算法如下：intvisited[MAXVEX];voidDFS1(MatGraphg,intv){inti;visited[v]=1;printf("%3d",v);for(i=0;in;i++)67 练习题及参考答案visited[i]=0;for(i=0;in;i++)if(visited[i]==0){n++;DFS(G,i);//对图g从顶点i开始进行深度优先遍历}returnn;}（3）假设以邻接表作为图的存储结构，分别写出基于DFS和BFS遍历的算法来判别图G中顶点i和顶点j（i≠j）之间是否有路径。解：先置全局变量visited[]为0，然后从顶点i开始进行某种遍历，遍历之后，若visited[j]=0，说明顶点i与顶点j之间没有路径；否则说明它们之间存在路径。基于DFS遍历的算法如下：intvisited[MAXVEX];//全局变量intDFSTrave(AdjGraph*G,inti,intj){intk;for(k=0;kn;k++)visited[k]=0;DFS(G,i);//从顶点i开始进行深度优先遍历if(visited[j]==0)return0;elsereturn1;}基于BFS遍历的算法如下：intvisited[MAXVEX];//全局变量intBFSTrave(AdjGraph*G,inti,intj){intk;for(k=0;kn;k++)visited[k]=0;BFS(G,i);//需将BFS算法中的visited[]定义改为全局变量if(visited[j]==0)return0;elsereturn1;}上机实验题7假设一个带权有向图采用邻接表存储。设计一个算法输出从顶点u到顶点v并经过顶点k的所有路径及其长度。并用相关数据进行测试。解：采用基于深度优先遍历的递归算法求解，对应的程序如下：#include67 练习题及参考答案#include"AdjGraph.h"//包含邻接表的基本运算函数intvisited[MAXVEX];intInpath(intk,intpath[],intd)//判断path是否含有顶点k{inti;for(i=0;i<=d;i++)if(path[i]==k)return1;return0;}voidFindallPath(AdjGraph*G,intu,intv,intk,intpath[],intd,intplength)//输出G中从u→v经过k的所有路径及其长度{ArcNode*p;intw,i;visited[u]=1;d++;path[d]=u;//顶点u加入到路径中if(u==v&&d>=1&&Inpath(k,path,d))//找到一条包含k的路径{printf("路径:%d",path[0]);for(i=1;i<=d;i++)//输出找到一条路径并返回printf("→%d",path[i]);printf(":t长度为%dn",plength);}p=G->adjlist[u].firstarc;//p指向u的第一个相邻点while(p!=NULL){w=p->adjvex;//相邻点的编号为wif(visited[w]==0){plength+=p->weight;//增加路径长度FindallPath(G,w,v,k,path,d,plength);//递归调用plength-=p->weight;//回退时减去相应长度}p=p->nextarc;//p指向下一个相邻点}visited[u]=0;//回溯找所有简单路径}voidmain(){AdjGraph*G;intn=6,e=11,i;intu=0,v=4,k=2;intpath[MAXVEX],d=-1;intA[][MAXVEX]={{0,50,10,INF,INF,INF},{INF,0,15,50,10,INF},{20,INF,0,15,INF,INF},{INF,20,INF,0,35,INF},67 练习题及参考答案{INF,INF,INF,30,0,INF},{INF,INF,INF,3,INF,0}};CreateGraph(G,A,n,e);//建立图7.30的邻接表printf("图G的存储结构:n");DispGraph(G);for(i=0;in;i++)visited[i]=0;printf("从顶点%d到%d并经过顶点%d的所有路径及其长度:n",u,v,k);FindallPath(G,u,v,k,path,d,0);DestroyGraph(G);}练习题81.单项选择题（1）要进行顺序查找，则线性表（①）；要进行二分查找，则线性表（②）；要进行散列查找，则线性表（③）。某顺序表中有90000个元素，已按关键项的值的升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为（④），最大比较次数为（⑤）。①②：A.必须以顺序方式存储B.必须以链表方式存储C.必须以散列方式存储D.既可以以顺序方式，也可以以链表方式存储E.必须以顺序方式存储且数据元素已按值递增或递减的次序排好F.必须以链表方式存储且数据元素已按值递增或递减的次序排好④⑤：A.25000B.30000C.45000D.90000答：①D②E③C④C⑤D（2）链表适用于（）查找A.顺序B.二分法C.顺序，也能二分法D.随机答：A（3）折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A.20,70,30,50B.30,88,70,50C.20,50D.30,88,50答：A（4）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A.3B.4C.5D.6答：C（5）有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。A.35/12B.37/12C.39/12D.43/1267 练习题及参考答案答：B（6）折半查找与二叉排序树的时间性能（）。A.相同B.完全不同C.有时不相同D.数量级都是O(log2n)答：C（7）用n个关键字构造一棵二叉排序树，其最低高度为（）。A.n/2B.nC.ëlog2nûD.ëlog2n+1û答：D（8）在二叉排序树中，关键字最小的结点，它的（）。A.左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空答：A（9）在二叉排序树中，每个结点的关键码值（①），（②）一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是（③）。①：A.比左子树所有结点的关键码值大，比右子树所有结点的关键码值小B.比左子树所有结点的关键码值小，比右子树所有结点的关键码值大C.比左右子树的所有结点的关键码值都大D.与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系②：A.先序遍历B.中序遍历C.后序遍历D.层次遍历③：A.除最下两层可以不满外，其余都是充满的B.除最下一层可以不满外，其余都是充满的C.每个结点的左右子树的高度之差的绝对值不大于1D.最下层的叶子结点必须在最左边答：①A②B③B（10）哈希法存储的基本思想是根据（①）来决定（②），碰撞（冲突）指的是（③），处理碰撞的两类主要方法是（④）。①②：A.存储地址B.元素的符号C.元素个数D.关键字值E.非关键字属性F.平均查找长度G.装填因子H.哈希表空间③：A.两个元素具有相同序号B.两个元素的关键字值不同，而非关键字属性相同C.不同关键字值对应到相同的存储地址D.装填因子过大E.数据元素过多④：A.线性探测法和双散列函数法B.建溢出区法和不建溢出区法C.除余法和折叠法D.拉链法和开放地址法答：①D②A③C④D（11）假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行（）次探测。A.k-1B.kC.k+1D.k(k+1)/267 练习题及参考答案答：D（12）哈希表在查找成功时的平均查找长度（）。A.与处理冲突方法有关，而与装填因子α无关B.与处理冲突方法无关，而与装填因子α有关C.与处理冲突方法有关和装填因子α都有关D.与处理冲突方法无关，也与装填因子α无关答：C（13）在一棵平衡二叉树中，每个结点的平衡因子的取值范围是（）。A.-1~1B.-2~2C.1~2D.0~1答：A（14）具有5层结点的AVL树至少有（）个结点。A.10B.12C.15D.17答：B（15）下述叙述中（）是不成立的。A.m阶B-树中的每个分支结点的子树个数都小于或等于mB.m阶B-树中的每个分支结点的子树个数都大于或等于ém/2ùC.m阶B-树中的任何一个结点的子树高度都相等D.m阶B-树具有k个子树的非叶子结点含有k-1个关键字答：B（16）下列叙述中，不符合m阶B树定义要求的是（）。A.根结点最多有m棵子树B.所有叶子结点都在同一层上C.各结点内关键字均升序或降序排列D.叶子结点之间通过指针链接答：D（17）高度为5的3阶B-树至少有（）个结点。A.32B.31C.64D.108答：B（18）下面关于B-树和B+树的叙述中，不正确的是（）。A.B-树和B+树都能有效地支持顺序查找B.B-树和B+树都能有效地支持随机查找C.B-树和B+树都是平衡的多分树D.B-树和B+树都可用于文件索引结构答：A2.填空题（1）顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为（①）次；若查找不成功，则比较关键字的次数为（②）次。答：①n②n（2）假设在有序顺序表A[1..20]上进行折半查找，比较1次查找成功的记录数为（①），比较2次查找成功的记录数为（②），比较3次查找成功的记录数为（③），比较4次查找成功的记录数为（④），比较5次查找成功的记录数为（⑤），等概率情况下成功查找的平均查找长度约为（⑥）。67 练习题及参考答案答：①1②2③4④8⑤5⑥3.7。（3）已知有序表为{12,18,24,35,47,50,62,83,90,115,134}，当用折半法查找90时，需进行（①）次关键字比较可确定成功；查找47时需进行（②）次关键字比较可确定成功；查找100时，需进行（③）次关键字比较才能确定失败。答：①2②4③3。（4）在分块查找方法中，首先查找（①），然后再查找相应的（②）。答：①索引表②数据表。（5）高度为5（除叶子层之外）的3阶B-树至少有（）个结点。答：31（6）按关键字13、24、37、90、53的次序建立一棵平衡二叉树，则该平衡二叉树的高度是（①），根结点关键字为（②），其左子树中的关键字是（③），其右子树中的关键字是（④）。答：①3②24③{13}④{37,53,90}（7）在哈希表中，装填因子α的值越大，则（①）；α的值越小，则（②）。答：①存取元素时发生冲突的可能性就越大②存取元素时发生冲突的可能性就越小3.简答题（1）简述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？答：三种方法对查找的要求分别如下。①顺序查找法：表中元素可以任意次序存放。②折半查找法：表中元素必须按关键字递增或递减排列，且最好采用顺序存储结构。③分块查找法：表中元素每块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）排列，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。三种方法的平均查找长度分别如下。①顺序查找法：查找成功的平均查找长度为(n+1)/2。②折半查找法：查找成功的平均查找长度为log2(n+1)-1。③分块查找法：若用顺序查找确定所在的块，平均查找长度为：(+s)+1；若用二分查找确定所在块，平均查找长度为log2(+1)+。其中，s为每块含有的元素个数。（2）折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？答：不适合。虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。折半查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。（3）给定关键字序列为{3,5,7,9,11,13,15,17}，回答以下问题：67 练习题及参考答案①按表中元素的顺序依次插入一棵初始值为空的二叉排序树。画出插入完成后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。②按表中元素顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度，与（1）比较，可得出什么结论？答：①按输入顺序构造的二叉排序树如图8.1所示。在等概率情况下查找成功的平均查找长度为：ASLsucc==4.5②构造的一棵平衡二叉树如图8.2所示。在等概率情况下查找成功的平均查找长度：ASLsucc==2.75由此可见在同样序列的查找中，平衡二叉树比二叉排序树的平均查找长度要小，查找效率要高。图8.1一棵二叉排序树图8.2一棵平衡二叉树（4）输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，建立一棵二叉排序树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。答：构造的二叉排序树如图8.3所示。为了删除结点72，在其左子树中找到最大结点54（只有一个结点），用其代替结点72。删除之后的二叉排序树如图8.4所示。图8.3二叉排序树图8.4删除72后的二叉排序树（5）在如图8.5所示的AVL树中，画出依次插入关键字为6和10的两个结点后的AVL树。67 练习题及参考答案图8.5一棵AVL树答：插入关键字为6和10的两个结点，其调整过程如图8.6所示。图8.6插入两个结点，AVL树调整过程（6）对一个固定的数据集，用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么？如果要求时间复杂度更小，你采用什么方法？此方法的时间复杂度是多少？答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O(1)。（7）设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数：H(key)=key%13采用开放地址法的线性探测法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表，并求成功和不成功情况下的平均查找长度。解：依题意，m=19，线性探测法计算下一地址计算公式为：d1=H(key)dj+1=(dj+1)%m;j=1,2,...其计算函数如下：H(19)=19mod13=6H(01)=01mod13=1H(23)=23mod13=1067 练习题及参考答案H(14)=14mod13=1冲突H(14)=(1+1)mod19=2H(55)=55mod13=3H(20)=20mod13=7H(84)=84mod13=6冲突H(84)=(6+1)mod19=7仍冲突H(84)=(7+1)mod19=8H(27)=27mod13=1冲突H(27)=(1+1)mod19=2冲突H(27)=(2+1)mod19=3仍冲突H(27)=(3+1)mod19=4H(68)=68mod13=3冲突H(68)=(3+1)mod19=4仍冲突H(68)=(4+1)mod19=5H(11)=11mod13=11H(10)=10mod13=10冲突H(10)=(10+1)mod19=11仍冲突H(10)=(11+1)mod19=12H(77)=77mod13=12冲突H(77)=(12+1)mod19=13因此，构建的哈希表如表8.1所示。表8.1哈希表下标0123456789101112131415161718k011455276819208423111077探测次数121431131132ASL成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=1.92ASL不成功=(1+9+8+7+6+5+4+3+2+1+5+4+3+2+1+1+1+1+1)/19=3.42（8）线性表的关键字集合{87,25,310,08,27,132,68,95,187,123,70,63,47}，共有13个元素，已知哈希函数为：H(k)=kmod13采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功和不成功情况下的平均查找长度。解：依题意，得到：H(87)=87mod13=9H(25)=25mod13=12H(310)=310mod13=11H(08)=08mod13=8H(27)=27mod13=1H(132)=132mod13=267 练习题及参考答案H(68)=68mod13=3H(95)=95mod13=4H(187)=187mod13=5H(123)=123mod13=6H(70)=70mod13=5H(63)=63mod13=11H(47)=47mod13=8采用拉链法处理冲突的哈希表如图8.7所示。成功查找的平均查找长度：ASL成功=(1×10+2×3)/10=1.6ASL不成功=(1×7+2×3)/13=1图8.7采用拉链法处理冲突的哈希表4.算法设计题（1）对含有n个元素的整型数组A，设计一个较优的算法同时找最大元素和最小元素。解：通过一趟扫描并比较，可以找出最大元素max和最小元素min。对应的算法如下：voidMaxMin(intA[],intn,int&min,int&max){inti;min=max=A[0];for(i=1;imax)max=R[i];}（2）设计二分查找的递归算法。解：对应的递归算法如下：intBinSearch1(SqTypeR[],KeyTypek,intlow,inthigh){intmid;67 练习题及参考答案if(low>high)return(-1);else{mid=(low+high)/2;if(k==R[mid].key)return(mid);elseif(k>R[mid].key)return(BinSearch1(R,k,mid+1,high));//在左子树中递归查找elsereturn(BinSearch1(R,k,low,mid-1));//在右子树中递归查找}}（3）假设二叉排序树bt的各元素值均不相同，设计一个算法按递增次序输出所有结点值。解：按中序序列遍历二叉排序树即按递增次序遍历，对应值的算法如下：voidincrorder(BSTNode*bt){if(bt!=NULL){incrorder(bt->lchild);printf("%d",bt->data);incrorder(bt->rchild);}}（4）设计一个递归算法，从大到小输出二叉排序树中所有其值不小于k的关键字。解：由二又排序树的性质可知，右子树中所有结点值大于根结点值，左子树中所有结点值小于根结点值。为了从大到小输出，要先遍历右子树，再访问根结点，后遍历左子树。对应的算法如下：voidOutput(BSTNode*bt,KeyTypek){if(bt!=NULL){Output(bt->rchild,k);if(bt->key>=k)printf("%d",bt->key);Output(bt->lchild,k);}}（5）假设二叉排序树中所有结点关键字不同，设计一个算法，求出指定关键字的结点所在的层次。解：设二叉排序树采用二叉链存储结构。采用二叉排序树非递归查找算法，用h保存查找层次。对应的算法如下：intlevel(BSTNode*bt,KeyTypek){inth=0;if(bt!=NULL){h++;67 练习题及参考答案while(bt->data!=k){if(kdata)bt=bt->lchild;//在左子树中查找elsebt=bt->rchild;//在右子树中查找h++;//层数增1}returnh;}}上机实验题8假设二叉树的数据域为int类型，由其括号表示建立对应的二叉链存储结构，设计一个算法判断该二叉树是否为一棵二叉排序树。并用相关数据进行测试。解：结合第6章的二叉树基本运算算法和二叉排序树的特点设计对应的程序如下：#include#include#defineMaxSize100typedefintElemType;//二叉树的data域设为int类型typedefstructtnode{ElemTypedata;//数据域structtnode*lchild,*rchild;//指针域}BTNode;//二叉树结点类型BTNode*pre=NULL;//pre为全局变量,保存当前结点中序前驱结点地址,初值为NULLintjudgeBST(BTNode*bt)//判断二叉树bt是否是一棵二叉排序树{intb1,b2;if(bt==NULL)//空树是BSTreturn1;else{b1=judgeBST(bt->lchild);if(b1==0)//左子树不是BST,整个二叉树也不是BSTreturn0;if(pre!=NULL&&pre->data>=bt->data)return0;pre=bt;//pre指向当前访问的结点b2=judgeBST(bt->rchild);//判断右子树是否为BSTreturnb2;//返回右子树的判断结果}}voidCreateBTree(BTNode*&bt,char*str)//由str建立二叉链bt{BTNode*St[MaxSize],*p=NULL;67 练习题及参考答案ElemTyped;inttop=-1,k,j=0;charch;bt=NULL;//建立的二叉树初始时为空ch=str[j];while(ch!="")//str未扫描完时循环{switch(ch){case"(":top++;St[top]=p;//为"(",其后结点为栈顶结点的左孩子k=1;break;case")":top--;break;//为")",当前子树结束case",":k=2;break;//为",",其后结点为栈顶结点的右孩子default://为数字符,提取数字并建相应的结点d=0;while(str[j]>="0"&&str[j]<="9"){//str[j]为数字符,将数字串转换成数值dd*=10;d+=str[j]-"0";j++;}j--;//后退一个字符p=(BTNode*)malloc(sizeof(BTNode));p->data=d;p->lchild=p->rchild=NULL;if(bt==NULL)//*p为二叉树的根结点bt=p;else//已建立二叉树根结点{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}break;}j++;ch=str[j];}}voidDestroyBTree(BTNode*&bt)//销毁二叉树{if(bt!=NULL){DestroyBTree(bt->lchild);DestroyBTree(bt->rchild);free(bt);67 练习题及参考答案}}voidDispBTree(BTNode*bt)//输出二叉树{if(bt!=NULL){printf("%d",bt->data);if(bt->lchild!=NULL||bt->rchild!=NULL){printf("(");//有子树时输入"("DispBTree(bt->lchild);//递归处理左子树if(bt->rchild!=NULL)//有右子树时输入"."printf(",");DispBTree(bt->rchild);//递归处理右子树printf(")");//子树输出完毕，再输入一个")"}}}voidmain(){BTNode*bt;chara[]="25(18(2(,4(,11))),46(39(32),53(,74(67(60)))))";CreateBTree(bt,a);printf("二叉树:");DispBTree(bt);printf("n");if(judgeBST(bt))printf("该二叉树是一棵BSTn");elseprintf("该二叉树不是一棵BSTn");DestroyBTree(bt);}练习题91.单项选择题（1）内排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。A.希尔排序B.冒泡排序C.直接插入排序D.简单选择排序答：C（2）对有n个记录的表进行直接插入排序，在最坏情况下需进行（）次关键字比较。A.n-1B.n+1C.n/2D.n(n-1)/2答：D（3）在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A.堆排序B.冒泡排序C.直接插入排序D.快速排序答：C67 练习题及参考答案（4）对数据序列{15,9,7,8,20,-1,4}进行排序，进行一趟后数据的排序变为{9,15,7,8,20,-1,4}，则采用的是（）算法。A.简单选择排序B.冒泡排序C.直接插入排序D.堆排序答：C（5）数据序列{5,4,15,10,3,1,9,6,2}是某排序方法第一趟后的结果，该排序算法可能是（）。A.冒泡排序B.二路归并排序C.堆排序D.简单选择排序答：B（6）从未排序序列中挑选元素，并将其依次插入已排序序列的一端的方法，称为（）。A.希尔排序B.归并排序C.直接插入排序D.简单选择排序答：D（7）在以下排序方法中，关键字比较的次数与元素的初始排列次序无关的是（）。A.希尔排序B.冒泡排序C.插入排序D.简单选择排序答：D（8）对n个不同的关键字进行递增冒泡排序，在下列哪种情况下比较的次数最多（）。A.元素无序B.元素递增有序C.元素递减有序D.都一样答：C（9）快速排序在下列哪种情况下最易发挥其长处（）。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据随机分布D.被排序的数据中最大值和最小值相差悬殊答：C（10）序列{5,2,4,1,8,6,7,3}是第一趟递增排序后的结果，则采用的排序方法可能是（）。A.快速排序B.冒泡排序C.堆排序D.直接插入排序答：D（11）序列{3,2,4,1,5,6,8,7}是第一趟递增排序后的结果，则采用的排序方法可能是（）。A.快速排序B.冒泡排序C.堆排序D.简单选择排序答：A（12）以下关于快速排序的叙述中正确的是（）。A.快速排序在所有排序方法中为最快，而且所需辅助空间也最少B.在快速排序中，不可以用队列替代栈C.快速排序的空间复杂度为O(n)D.快速排序在待排序的数据随机分布时效率最高答：D（13）堆排序是一种（）排序。A.插入B.选择C.交换D.归并67 练习题及参考答案答：B（14）以下序列不是堆的是（）。A.{100,85,98,77,80,60,82,40,20,10,66}B.{100,98,85,82,80,77,66,60,40,20,10}C.{10,20,40,60,66,77,80,82,85,98,100}D.{100,85,40,77,80,60,66,98,82,10,20}答：D（15）有一组数据{15,9,7,8,20,-1,7,4}，用堆排序的筛选方法建立的初始堆为（）。A.{-1,4,8,9,20,7,15,7}B.{-1,7,15,7,4,8,20,9}C.{-1,4,7,8,20,15,7,9}D.以上都不对答：C（16）下述几种排序方法中，要求辅助内存最大的是（）。A.插入排序B.快速排序C.归并排序D.选择排序答：C（17）以下排序方法中，（）不需要进行关键字的比较。A.快速排序B.归并排序C.基数排序D.堆排序答：C（18）采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k（）。A.有关B.无关答：B2.填空题（1）大多数内排序算法都有两个基本的操作：（①）和（②）。答：①比较②移动（2）对含有n个元素的数序进行直接插入排序，在最好情况下移动元素的个数是（①），关键字比较的次数是（②）。答：①0②n-1。（3）对于n个记录的顺序表进行冒泡排序，在最坏的情况下的时间复杂度是（①），若对其进行快速排序，在最坏的情况下的时间复杂度是（②）。答：①O(n2)②O(n2)（4）在直接插入和简单选择排序中，若初始数据基本正序，则选用（①），若初始数据基本反序，则选用（②）。答：①直接插入②简单选择排序（5）每趟通过基准间接比较两个元素，若出现逆序排列时就交换它们的位置，一趟排序后将基准元素放在最终位置上。此种排序方法叫做（）。答：快速排序（6）在堆排序和快速排序中，若初始记录接近正序或反序，则选用（①），若初始记录基本无序，则最好选用（②）。答：①堆排序②快速排序（7）对于n个记录的顺序表进行二路归并排序时，平均时间复杂度是（①），空间复杂度是（②）。答：①O(nlog2n)②O(n)67 练习题及参考答案（8）对于n个记录的表进行二路归并排序，整个归并排序需进行（）趟。答：élog2nù（9）在一个大根堆中，元素值最小的结点是（）。答：某个叶子结点。（10）已知关键字序列k1k2…kn构成一个小根堆，则最小关键字是（①），并且在该序列对应的完全二叉树中，从根结点到叶子结点的路径上关键字组成的序列具有（②）的特点。答：①k1②递增。（11）外排序有两个基本阶段，第一阶段是①，第二阶段是②。答：①生成初始归并段②对这些初始归并段采用某种归并方法，进行多遍归并。3.简答题（1）简要叙述如何选择好的内排序方法。答：没有哪一种内排序方法是绝对好的。每一种排序方法都有其优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况做选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定方法中选取，否则可以在所有方法中选取；其次要考虑待排序结点数n的大小，若n较大，则可在改进方法中选取，否则在简单方法中选取；然后再考虑其他因素。下面给出综合考虑了以上几个方面所得出的大致结论：①当待排序的结点数n较大，关键字的值分布比较随机，并且对排序稳定性不作要求时，宜选用快速排序法。②当待排序的结点数n较大，内存空间又允许，并且要求排序稳定时，宜采用归并排序法。③当待排序的结点数n较大，关键字的值的分布可能出现升序或者逆序的情况，并且对排序稳定性不作要求时，宜采用堆排序方法或者归并排序方法。④当待排序的结点数n较小，关键字的值基本有序（升序）或者分布比较随机，并且有排序稳定性要求时，宜采用插入排序法。⑤当待排序的结点数n较小，对排序稳定性不作要求时，宜采用选择排序方法，若关键字的值不接近逆序，亦可采用直接插入排序法。⑥已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是归并排序方法。（2）给出关键字序列{4,5,1,2,8,6,7,3,10,9}的希尔排序过程。答：希尔排序过程如图9.1所示。图9.1希尔排序各趟排序结果67 练习题及参考答案（3）一个有n个整数的数组R[1..n]，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给一个反例，若是，请说明理由。答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k1、k2、…、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有ki=0;i--){tmp=R[i];j=i+1;while(jR[j].key)j++;//在有序区找到一个刚大于tmp.key的位置R[j]for(k=i;kR[n].key)return(0);for(i=n/2-1;i>=1;i--)//判断所有双分支结点if(R[i].key>R[2*i].key||R[i].key>R[2*i+1].key)return(0);}else//n为奇数时,所有分支结点均为双分支结点{for(i=n/2;i>=1;i--)//判断所有双分支结点if(R[i].key>R[2*i].key||R[i].key>R[2*i+1].key)return(0);}67 练习题及参考答案return(1);}上机实验题9有一个整型数组A[0..n-1]，前m（0#include#defineMaxSize100voidSort1(intA[],intm,intn)//将A[0..m-1]和A[m..n-1]两个相邻的有序表归并为一个有序表A[0..n-1]{int*A1;inti=0,j=m,k=0;A1=(int*)malloc(n*sizeof(int));//动态分配空间while(i<=m-1&&j<=n-1)//在第1子表和第2子表均未扫描完时循环if(A[i]<=A[j])//将第1子表中的记录放入A1中{A1[k]=A[i];i++;k++;}else//将第2子表中的记录放入A1中{A1[k]=A[j];j++;k++;}while(i<=m-1)//将第1子表余下部分复制到A1{A1[k]=A[i];i++;k++;}while(j<=n-1)//将第2子表余下部分复制到A1{A1[k]=A[j];j++;k++;}for(i=0;i=0&&A[j]>tmp){A[j+1]=A[j];//将大于tmp的元素后移j--;//继续向前比较}A[j+1]=tmp;//在j+1处插入A[i]}}voidDisp(intA[],intn){inti;for(i=0;i