第1章 绪论
1.1 选择题
1. 算法的时间复杂度取决于（ ）
A）问题的规模 B） 待处理数据的初态 C） A和B 【答案】C
2.计算机算法指的是解决问题的步骤序列，它必须具备（ ） 这三个特性。 A）可执行性、可移植性、可扩充性 B） 可执行性、确定性、有穷性 C） 确定性、有穷性、稳定性 D） 易读性、稳定性、安全性 【答案】B
5．从逻辑上可以把数据结构分为（ ）两大类。
A）动态结构、静态结构 B）顺序结构、链式结构 C）线性结构、非线性结构 D）初等结构、构造型结构 【答案】C
6．在下面的程序段中，对x的赋值的语句频度为（ ） for(i=0;i for(j=0;j A） O(2n) B）O(n) C．O(n2) D．O(log2n) 【答案】C 7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（ ） for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) if (A[j]>A[j+1]) A[j]与A[j+1]对换； A. O（n） B） O(nlog2n) C） O(n3) D） O(n2) 【答案】D 1.2 填空题 2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________， _____________，_____________四种。 【答案】（1）集合 （2）线性结构 （3）树形结构（4）图状结构或网状结构 4．数据结构中评价算法的两个重要指标是_____________。 【答案】算法的时间复杂度和空间复杂度。 5. 数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。 【答案】（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。 6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。 【答案】（1）有穷性 （2）确定性 （3）可行性。 9．已知如下程序段 for(i=n;i>0;i--) {语句1} 1 { x=x+1; {语句2} for(j=n;j>=i;j--) {语句3} y=y+1; {语句4} } 语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。 【答案】（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2 10．在下面的程序段中，对ｘ的赋值语句的频度为_____________（表示为n的函数） for(i=0;i>n;i++) for(j=0;j>i;j++) for(k=0;k>j;k++) ｘ=ｘ+delta; 【答案】1+（1+2）+（1+2+3）+?+（1+2+?+n）=n(n+1)(n+2)/6 ， O(n3) 11.下面程序段中带下划线的语句的执行次数的数量级是_____________。 i=1; while(i 12. 计算机执行下面的语句时，语句s的执行次数为_____________。 for(i=l;i for(j=n;j>=i;j--) s; 【答案】(n+3)(n-2)/2 13. 下面程序段的时间复杂度为_____________。(n>1) sum=1; for (i=0;sum 第2章 线性表 2.1 选择题 1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（ ）最节省时间 A）顺序表 B）带头结点的双循环链表 C）单链表 D）带尾结点的单循环链表 【答案】A 2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（ ）(1≤i≤n+1)。 A） O(0) B） O(1) C） O(n) D） O(n2) 【答案】C 3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） A） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; B） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next; C） q->next=p; p->next=q; p->prior->next=q; q->next=p; D） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q; 【答案】D 2 4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ） A）O(nlog2n） B） O(1） C） O(n） D） O(n2） 【答案】C 5． 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（ ） A）p->next==NULL B） p->next==h C）p->next->next==h D） p->data==-1 【答案】B 6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（ ） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】A 8．在双向链表存储结构中，删除p所指的结点时须修改指针（ ） A）p->prior->next=p->next p->next->prior=p->prior; B）p->prior=p->prior->prior p->prior->next=p; C）p->next->prior=p p->next=p->next->next D）p->next=p->prior->prior p->prior=p->next->next; 【答案】A 9．线性表采用链式存储时，其元素地址（ ） A）必须是连续的 B）一定是不连续的 C）部分地址是连续的 D）连续与否均可 【答案】D 2.2 填空题 1．线性表L=（a1，a2，?，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____________。 【答案】（n-1）/2 2．在单链表中设置头结点的作用是_____________。 【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。 3．线性表的顺序存储是通过_____________来反应元素之间的逻辑关系，而链式存储结构是通过_____________来反应元素之间的逻辑关系。 【答案】（1）数据元素的前后顺序 （2）元素中的指针 4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_____________存储结构最节省时间，相反当经常进行插入和删除操作时，则采用_____________存储结构最节省时间。 【答案】（1）顺序 （2）链式 5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_____________，在给定值为x的结点后插入一个新结点的时间复杂度为_____________。 【答案】（1）O(1) （2）O(n) 7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____________个，单链表为_____________个。 【答案】（1）4 （2）2 8. 循环单链表的最大优点是_____________。 3 【答案】从任一结点出发都可访问到链表中每一个元素。 9．若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作： s->next=_____________; p->next=s; t=p->data; p->data= _____________; s->data=_____________; 【答案】（1）p->next （2）s->data （3） t 10．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为_____________。 【答案】144 11．带头结点的双循环链表L中只有一个元素结点的条件是_____________。 【答案】L->next->next==L 2.3 判断题 1．取线性表的第i个元素的时间同i的大小有关（ ） 【答案】× 2．线性表的特点是每个元素都有一个前驱和一个后继（ ） 【答案】× 3． 顺序存储方式的优点是存储密度大，且插入、删除运算效率高（ ） 【答案】× 4．线性表采用链表存储时，结点的存储空间可以是不连续的（ ） 【答案】√ 5．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（ ） 【答案】√ 6．顺序存储方式只能用于存储线性结构（ ） 【答案】× 【解析】线性结构、树型结构和图状结构均可用顺序存储表示。 9．顺序存储结构的主要缺点是不利于插入或删除操作（ ） 【答案】√ 10．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ） 【答案】× 2.4 程序设计题 1．设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 【算法源代码】 void Insert_SqList(SqList va,int x)/*把x插入递增有序表va中*/ { int i; if(va.length> MAXSIZE) return; 4 for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; va.length++; }/*Insert_SqList*/ 2．设 A=（a1，a2，?，am） 和 B=（b1，b2，?，bn）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。 【算法分析】比较顺序表A和B，并用返回值表示结果，值为1，表示A>B；值为-1，表示A 1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1； 2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大 【算法源代码】 int ListComp(SqList A,SqList B) { for(i=1;i<=A.length&&i<=B.length;i++) if(A.elem[i]!=B.elem[i]) return A.elem[i]>B.elem[i]?1:-1; if(A.length==B.length) return 0; return A.length>B.length?1:-1; /*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/ }/*ListComp */ 3．已知指针 ha和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。 【算法分析】 1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha； 2）查找单链表ha的最后一个结点，由指针p指向，即p->next==NULL； 3）将单链表hb的首元结点（非头结点）连接在p之后，即p->next=hb->next； 4）回收单链表hb的头结点空间 【算法源代码】 void ListConcat(LinkList ha,LinkList hb,LinkList *hc) /*把链表hb接在ha后面形成链表hc*/ { *hc=ha; p=ha;/*由指针p指向ha的尾元结点*/ p=p->next; p->next=hb->next; free(hb); }/*ListConcat */ 4．试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。 【算法分析】 1）生成新结点存放元素b，由指针new指向； 2）将new插入在单链表的第i个元素的位置上：若i==1，new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。 【算法源代码】 void Insert(LinkList *L,int i,int b) { LinkList new; 5 new=(LinkList*)malloc(sizeof(LNode)); new->data=b; if(i==1) {/*插入在链表头部*/ New->next=*L; *L=new; } else { /*插入在第i个元素的位置*/ p=*L; while(--i>1) p=p->next; new->next=p->next;p->next=new; } }/*Insert */ 5．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于 mink且小于 maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同）。 【算法分析】 1）查找最后一个不大于mink的元素结点，由指针p指向； 2）如果还有比mink更大的元素，查找第一个不小于maxk的元素，由指针q指向； 3）p->next=q，即删除表中所有值大于 mink且小于 maxk的元素。 【算法源代码】 void Delete_Between(LinkList *L,int mink,int maxk) { p=*L; while(p->next->data<=mink) p=p->next; /*p是最后一个不大于mink的元素*/ if(p->next) /*如果还有比mink更大的元素*/ { q=p->next; while(q->data }/*Delete_Between */ 6．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间。 【算法分析】 1）初始化指针p和q，分别指向链表中相邻的两个元素； 2）当p->next不为空时，做如下处理： ①若相邻两元素不相等时，p和q都向后推一步； ②否则，当相邻元素相等时，删除多余元素。 【算法源代码】 void Delete_Equal(LinkList *L) { p=(*L)->next;q=p->next; /*p和q指向相邻的两个元素*/ while(p->next) { if(p->data!=q->data) /*若相邻两元素不相等时，p和q都向后推一步*/ { p=p->next; q=p->next; 6 } else { while(q->data==p->data) /*当相邻元素相等时删除多余元素*/ { r=q; q=q->next; free(r); } p->next=q;p=q;q=p->next; }/*else*/ }/*while*/ }/*Delete_Equal */ 7．试设计一个算法，对带头结点的单链表实现就地逆置。 【算法分析】 1）空表或长度为1的表，不做任何处理； 2）表长大于2时，做如下处理： ①首先将整个链表一分为二，即从链表的第一元素结点处断开； ②逐个地把剩余链表的当前元素q插入到链表的头部。 【算法源代码】 void LinkList_reverse(LinkList L) { if(!L->next||!L->next->next) return; p=L->next; q=p->next; s=q->next; p->next=NULL; /*从链表的第一元素结点处断开*/ while(s->next) {q->next=p;p=q; q=s;s=s->next; /*把L的元素逐个插入新表表头*/ } q->next=p;s->next=q;L->next=s; }/*LinkList_reverse*/ 8．设线性表A=（a1，a2，?，am） 和 B=（b1，b2，?，bn），试设计一个按下列规则合并A，B为线性表C的算法，即使得 C=（a1，b1，?，am，bm，bm+1 ，?，bn ）当 m≤n时； 或者 C=（a1，b1，?，an，bn，an+1 ，?，am ）当m＞n时。 线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。 【算法分析】 1）初始化指针p指向链表A的当前元素，指针q指向链表B的当前元素； 2）当链表A和B均为结束时，做如下处理： ①将B的元素插入 ②若A非空，将A的元素插入 ③指针p和q同时后移 【算法源代码】 void merge1(LinkList A,LinkList B,LinkList *C) {p=A->next;q=B->next;*C=A; while(p&&q) { s=p->next;p->next=q; /*将B的元素插入*/ if(s) { t=q->next; q->next=s; /*若A非空，将A的元素插入*/ } 7 p=s;q=t; /*指针p和q同时后移*/ }/*while*/ }/*merge1 */ 9．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请设计一个算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即 A表和B表）的结点空间构造C表。 【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素。 【算法源代码】 void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre; pa=A->next;pb=B->next; /*pa和pb分别指向A和B的当前元素*/ pre=NULL; while(pa||pb) { if(pa->data { pc=pb;q=pb->next;pb->next=pre;pb=q; } pre=pc; } *C=A; A->next=pc; /*构造新表头*/ }/*reverse_merge*/ 10．已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 【算法分析】先从B和C中找出共有元素，记为same，再在A中从当前位置开始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个same。 【算法源代码】 void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) {i=0;j=0;k=0;m=0; /*i指示A中元素原来的位置，m为移动后的位置*/ while(i<(*A).length&&j else if(B.elem[j]>C.elem[k]) k++; else{ same=B.elem[j]; /*找到了相同元素same*/ while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; /*j和k后移到新的元素*/ while(i<(*A).length&&(*A).elem[i] (*A).elem[m++]=(*A).elem[i++]; /*需保留的元素移动到新位置*/ while(i<(*A).length&&(*A).elem[i]==same) i++; /*跳过相同的元素*/ } }/*while*/ while(i<(*A).length) (*A).elem[m++]=(*A).elem[i++]; /*A的剩余元素重新存储*/ (*A).length=m; }/* SqList_Intersect_Delete*/ 11．设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。 【算法分析】本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开始，将各结点依次插入到有序 8 链表中。 【算法源代码】 void InsertSort (LinkList la) {if(la->next!=NULL) /*链表不为空表*/ {p=la->next->next; /*p指向第一结点的后继*/ la->next->next=NULL; /*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/ while(p!=NULL) {r=p->next;/*暂存p的后继*/ q=la; while(q->next!=NULL&&q->next->data 12．设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。 【算法分析】 1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步； 2）修改x结点的访问频度freq，并将结点从链表上摘下； 3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。 【算法源代码】 DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)->next; while(p.data!=x&&p!= (*L)) p=p->next; if(p==(*L)) return NULL; /*没找到x结点*/ p->freq++; p->pre->next=p->next;p->next->pre=p->pre; /*将x结点从链表上摘下*/ q=p->pre; while(q->freq<=p->freq&&p!= (*L)) q=q->pre; /*查找插入位置*/ if(q!=p->pre) /*将x结点插入*/ {q->next->pre=p;p->next=q->next; q->next=p;p->pre=q; /*调整位置*/ } return p; }/*Locate_DuList */ 13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。 【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。 【算法源代码】 9 LinkList Common(LinkList A, LinkList B, LinkList C) {pa=A->next;pb=B->next; pc=C->next; /*pa，pb和pc是工作指针*/ pre=A; while(pa && pb && pc) /*当三表均不空时，查找共同元素*/ { while(pa && pb) if(pa->data else if(pa->data> pb->data)pb=pb->next; else if (pa && pb) /*处理A和B表元素值相等的结点*/ {while(pc && pc->data {if(pc->data>pa->data) /*处理pa结点，后移指针*/ {u=pa;pa=pa->next;free(u);} else {if(pre==A) /*结果表中第一个结点*/ { pre->next=pa;pre=pa;pa=pa->next} else if(pre->data==pa->data) /*重复结点不链入A表*/ {u=pa;pa=pa->next;free(u);} else {pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表 */ pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/ } } else if(pa==NULL)pre->next=NULL; /*若A表已结束，置A表表尾*/ else /*处理原A表未到尾而B或C到尾的情况*/ {pre->next=NULL; /*置A表表尾标记*/ while(pa!=NULL) /*删除原A表剩余元素。*/ {u=pa;pa=pa->next;free(u);} } } 14．设 head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将 head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。 【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。 【算法源代码】 discreat(LinkList p, LinkList q, LinkList head) { p=NULL; q=NULL;/*p和q链表初始化为空表*/ s=head; while(s!=NULL) {r=s->next; /*暂存s的后继*/ if(s->data%2==0) /*处理偶数*/ if (p==NULL) {p=s;p->next=NULL;} /*第一个偶数结点*/ else { pre=p; if(pre->data>s->data) {s->next=pre;p=s;}/*插入当前最小值结点*/ else {while (pre->next!=NULL) if (pre->next->data s->next=pre->next; /*链入结点*/ 10 pre->next=s;} } else/*处理奇数链 if (q==NULL) {q=s;q->next=NULL;} /*第一奇数结点*/ else {pre=q; if (pre->data>s->data) {s->next=pre; q=s;} /*修改头指针*/ else {while (pre->next!=NULL) /*查找插入位置*/ if (pre->next->data 第3章 桟和队列 3.1 选择题 1．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ） A）不确定 B）n-i+1 C）i D）n-i 【答案】B 【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1， ?，3，2，1。 2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ） A）6 B）4 C）3 D）2 【答案】C 【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。 3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ） A）top=top+1; V[top]=x B）V[top]=x; top=top+1 C）top=top-1; V[top]=x D）V[top]=x; top=top-1 【答案】C 【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。 4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（ ） A）正常动作 B）溢出 C）下溢 D）同步 【答案】B 【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。 5．栈在（ ）中应用。 11 A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ 【答案】D 7．用链接方式存储的队列，在进行删除运算时（ ） A）仅修改头指针 B）仅修改尾指针 C）头、尾指针都要修改 D）头、尾指针可能都要修改 【答案】D 【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。 8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( ) A）(rear-front+m)%m B）rear-front+1 C）rear-front-1 D）rear-front 【答案】A 【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。 9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A）1和 5 B）2和4 C）4和2 D）5和1 【答案】B 【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。 10．栈和队列的共同点是（ ） A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 【答案】C 【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。 11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（ ） A）front->next=s;front=s; B）s->next=rear;rear=s; C）rear->next=s;rear=s; D）s->next=front;front=s; 【答案】C 【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。 12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（ ） A）S->top!=-1 S->top!=MAXSIZE-1 B）S->top=-1 S->top=MAXSIZE-1 C）S->top=-1 S->top!=MAXSIZE-1 D）S->top!=-1 S->top=MAXSIZE-1 【答案】B 3.2 填空题 1．栈是_____________的线性表，其运算遵循_____________的原则。 【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作） （2）后进先出 2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值 12 是_____________H。设栈为顺序栈，每个元素占4个字节。 【答案】（1）23 （2）100CH 【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1，输出数据为2，然后经过PUSH,POP，3入栈，3出栈，然后经过PUSH,PUSH之后4，5入栈，此时出栈序列为2，3，栈中元素为1，4，5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH（十六进制数） 3．循环队列的引入，目的是为了克服_____________。 【答案】假溢出时大量移动数据元素。 4．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____________。 【答案】先进先出 5．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_____________。 【答案】 s=(LinkList)malloc(sizeof(LNode)); s->data=x; s->next=r->next; r->next=s; r=s; 【解析】根据队列的性质，新插入的元素永远插在队尾。 8．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_____________。 【答案】(M+1)% N； 【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。 9．当两个栈共享一存储区时，栈利用一维数组stack[1..n]表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_____________，栈2空时，top[2]为_____________，栈满时为_____________。 【答案】（1）0 （2）n+1 （3）top[1]+1=top[2] 【解析】为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生上溢，即top[1]+1=top[2]。 10．在作进栈运算时应先判别栈是否_____________；在作退栈运算时应先判别栈是否 _____________；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_____________。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____________分别设在内存空间的两端，这样只有当______________时才产生溢出。 【答案】（1）满 （2）空 （3）n （4）栈底 （5）两栈顶指针相邻 13．无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为_____________。 【答案】O(1) 【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。 14．在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。 13 【答案】假溢出 【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。 3.5 程序设计题 1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 【算法源代码】 int EXYX (char E[]){ /*E[]存放字符串表达式，以‘#’结束*/ char s[30]; /*s是一维数组，容量足够大，用作存放括号的栈*/ int top=0,i; /*top用作栈顶指针*/ s[top]='#'; /*‘#’先入栈，用于和表达式结束符号‘#’匹配*/ i=0; /*字符数组E的工作指针*/ while(E[i]!='#') /*逐字符处理字符表达式的数组*/ switch (E[i]) {case '(': s[++top]= '('; i++ ; break ; case ')': if(s[top]=='('){top--; i++; break;} else{printf(\括号不配对\ case '#': if(s[top]=='#'){printf(\括号配对\\n\ else {printf(\括号不配对\\n\括号不配对*/ default : i++; /*读入其它字符，不作处理*/ } }/*算法结束*/ 2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。 【算法分析】 根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。 【算法源代码1】 void EnQueue (LinkList rear, ElemType x) /* rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/ { s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/ s->data=x; s->next=rear->next; /*将s结点链入队尾*/ rear->next=s; rear=s; /*rear指向新队尾*/ } 【算法源代码2】 void DeQueue (LinkList rear) /* rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息*/ { if(rear->next==rear) {printf(\队空\\n\ s=rear->next->next; /*s指向队头元素*/ rear->next->next=s->next; /*队头元素出队*/ printf (\出队元素是:%d\ if(s==rear) rear=rear->next; /*空队列*/ free(s); } 14 3．设整数序列a1，a2，?，an，给出求解最大值的递归程序。 【算法分析】根据题意，本题的函数定义为： a[1] n=1 maxvalue(a,n)= a[n] a[n]>maxvalue(a,n-1) maxvalue(a,n-1) a[n] int MaxValue (int a[],int n) /*设整数序列存于数组a中，共有n个，本算法求解其最大值*/ {int max; if (n==1) max=a[1]; else if (a[n]>MaxValue(a,n-1)) max=a[n]; else max=MaxValue(a,n-1); return(max); } 4．试将下列递归函数改写为非递归函数。 void test(int *sum) { int x; scanf(\if(x==0) *sum=0 ; else {test(&sum); (*sum)+=x;} printf(\} 【算法分析】 该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。 【算法源代码】 int test() { int x,sum=0,top=0,s[30]; scanf(\while (x!=0) {s[++top]=a; scanf(\printf(\while (top) {sum+=s[top--]; printf(\ } 5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。 【算法分析】 利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。 【算法源代码】 reverse(SqStack *s) {SqStack *s1,*s2; /*s,s1,s2均为栈类型 ElemType x; /*栈中元素的类型，用于存储从栈中取出元素的临时变量*/ initstack(s1); /*栈的初始化*/ initstack(s2); while(!stackempty(s)) /*如果栈不空，将s栈中的内容移到s1栈中*/ {pop(s,x); /*取栈顶元素放入变量x中*/ push(s1,x); /*将变量x入栈*/ } while(!stackempty(s1)) /*如果栈不空，将s1栈中的内容移到s2栈中*/ 15 {pop(s1,x); push(s2,x); } while(!stackempty(s2)) /*如果栈不空，将s2栈中的内容移到s栈中*/ {pop(s2,x); push(s,x); } } 6．假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 【算法分析】 该题的关键问题是如何确定头指针，根据为指针rear和元素个数length很容易确定头指针。front=(rear-length+MAXSIZE)%MAXSIZE 【算法源代码】 #define MAXQSIZE 100 //最大队列长度 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; //队列存储空间 int rear; //尾指针，若队列不空，指向队列尾元素 int length; //队列内含元素的个数 }CyQueue; int FullQueue( CyQueue *Q) {/*判队满,队中元素个数等于空间大小*/ return Q->length==Maxsize; } void EnQueue( CyQueue *Q, ElemType x) {/* 入队 if(FullQueue( Q)) {printf(\队已满，无法入队\ Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE /*在循环意义上的加1*/ Q->length++; } ElemType DeQueue( CyQueue *Q) {/*出队*/ int front; /*设一个临时队头指针*/ if(Q->length==0) Error(\队已空，无元素可出队\ front=(Q->rear + MAXSIZE - Q->length)%MAXSIZE; Q->length --; return Q->Data[front]; } 7．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 【算法分析】 双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。 【算法源代码】 void InitStack( DuStack *S )/*初始化双向栈*/ {S->top[0] = -1; S->top[1] = STACKSIZE; } 16 int EmptyStack( DuStack *S, int i ) /*判栈空(栈号 i) */ {return (i == 0 && S->top[0] == -1|| i == 1 && S->top[1] == STACKSIZE) ; } int FullStack( DuStack *S) /*判栈满,满时肯定两头相遇*/ {return (S->top[0] == S-top1-1); } void Push(DuStack *S, int i, ElemType x) /*进栈(栈号i) */ {if (FullStack( S )) Error(\上溢、退出运行*/ if ( i == 0) S->Data[ ++ S->top0]= x; /*栈0入栈*/ if ( i == 1) S->Data[ -- S->top[1] ]= x; /* 栈1入栈*/ } ElemType Pop(DuStack *S, int i) /*出栈(栈号i) */ {if (EmptyStack ( S,i) ) Error(\下溢退出*/ if( i==0 ) return ( S->Data[ S->top0--] );/*返回栈顶元素，指针值减1*/ if( i==1 ) return ( S->Data[ S->top[1] ++] ); /*该栈是以另一端为底的，所以指针加1*/ } 8．回文是指正读反读均相同的字符序列，如\和\均是回文，但\不是回文。设计一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 【算法源代码】 void sympthy(LinkList head, stack *s)/*判断长为n的字符串是否中心对称*/ { int i=1; LinkList p=head->next; while(i<=n/2) /* 前一半字符进栈*/ { push(s,p->data); p=p->next; } if(n%2!==0) p=p->next;/* 奇数个结点时跳过中心结点*/ while(p&&p->data==pop(s)) p=p->next; if (p==NULL) printf(\链表中心对称\ else printf(\链表不是中心对称\} /* 算法结束*/ 9．用标志位方式设计出在循环队列中进行插入和删除运算的算法。 【算法分析】 可引入标志位flag，且规定当flag=0时表示队列空，当flag=1时表示队列非空。同时设front，rear和MAXSIZE分别为队头指针，队尾指针和队列的长度。其中，队头指针指向队头元素所在的实际存储单元的前一个位置，队尾指针指向队尾元素所在的位置。从而可得队满的条件是：(rear==front)&&(flag==1) 【算法源代码】 int flag; /*设置全局变量flag作为标志位*/ enqueue(SqQueue*sq,ElemType x) { /*将x插入循环队列sq中，sq具有队头和队尾指针*/ if((flag==1)&&(sq->rear==sq->front)) /*判断队满*/ printf(\ else {sq->rear=(sq->rear+1)%MAXSIZE; sq->data[sq->rear]=x; } if(flag==0) flag=1; 17 } ElemType dequeue(SqQueue*sq) /*删除队列sq的队头元素，并返回该元素*/ {ElemType x; if(flag==0) printf(\ /*判断队空*/ else{sq->front=(sq->front+1)%MAXSIZE; x=sq->data[sq->front]; } if(sq->front==sq->rear) flag=0; return x; } 第4章 串 4.1 选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ ） A）串是字符的有限序列 B）空串是由空格构成的串 C）模式匹配是串的一种重要运算 D）串既可以采用顺序存储，也可以采用链式存储 【答案】B 【解析】空串是不含任何字符的串，即空串的长度是零。空格串是由空格组成的串，其长度等于空格的个数。 2．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A）求子串 B）联接 C）匹配 D）求串长 【答案】C 3．若串s=\，其子串个数是（ ） A）8 B）37 C）36 D）9 【答案】C 【解析】s的长度为8，长度为8的子串有1个，长度为7的子串有2个，长度为6的子串有3个，长度为5的子串有4个，?，长度为1的子串有8个，共有(1+8)*8/2=36个。 4．串的长度是指（ ） A）串中所含不同字母的个数 B）串中所含字符的个数 C）串中所含不同字符的个数 D）串中所含非空格字符的个数 【答案】B 5．若串S1=\，S2=\，S3=\，S4=\，则执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))其结果为（ ） A）ABC###G0123 B）ABCD###2345 C）ABC###G2345 D）ABC###G1234 【答案】D 【解析】函数concat(x,y)返回x和y的连接串，substr(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，length(s)返回串s的长度。replase(s,t,v)用v替换s中出现的所有与t相等的子串,index(s,t,i)当s中存在与t值相同的子串时，返回它在s中的第i个字符之后第一次出现的位置。 substr(S1,length(S2),length(S3))=substr(S1,4,3)= \ replase(S1,substr(S1,length(S2),length(S3)),S3)=replase(S1, \substr(S4,index(S2, '8'),length(S2))=substr(S4,2,4)= \ 18 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))=concat(\ 4.2 填空题 1．空格串是指_____________，其长度等于_____________。 【答案】（1）由空格字符（ASCII值32）所组成的字符串 （2）空格个数 2．组成串的数据元素只能是_____________。 【答案】字符 【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。 3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_____________。 【答案】O(m+n) 【解析】朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m*n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。 4．两个字符串相等的充分必要条件是_____________。 【答案】两串的长度相等且两串中对应位置上的字符也相等。 5．一个字符串中_____________称为该串的子串 。 【答案】任意个连续的字符组成的子序列 4.3 判断题 1．KMP算法的特点是在模式匹配时指示主串的指针不会变小（ ） 【答案】√ 【解析】KMP算法的改进在于：每当一趟匹配过程中出现字符比较不相等时，不需回溯主串指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。 2．串是一种数据对象和操作都特殊的线性表（ ） 【答案】√ 【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。字符型数据的操作符合字符型数据的操作规范，具有它的特殊性。 3．如果一个串中的所有字符均在另一串中出现，那么说明前者是后者的子串（ ） 【答案】× 【解析】一个字符串中任意个连续的字符组成的子序列称为该串的子串，注意其中字符的连续性。 4.4 应用题 1．描述以下概念的区别：空格串与空串。 【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。 2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。 【答案】 （1）s1和s2均为空串； （2）两串之一为空串； （3）两串串值相等（即两串长度相等且对应位置上的字符相同）。 （4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 19 3．已知：s ＝\＋*\，t ＝\＋z)*y\。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。 【答案】本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） /*取出子串：\（2） s2=substr（s,6,1） /*取出子串：\ （3） s3=substr（s,1,5） /*取出子串：\ （4） s4=substr（s,7,1） /*取出子串：\ （5） s5=replace（s3,3,1,s2）/*形成部分串：\ （6） s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下： /*：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 4.4 应用题 1．描述以下概念的区别：空格串与空串。 【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。 2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。 【答案】 （1）s1和s2均为空串； （2）两串之一为空串； （3）两串串值相等（即两串长度相等且对应位置上的字符相同）。 （4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 3．已知：s ＝\＋*\，t ＝\＋z)*y\。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。 【答案】本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） /*取出子串：\（2） s2=substr（s,6,1） /*取出子串：\ （3） s3=substr（s,1,5） /*取出子串：\ （4） s4=substr（s,7,1） /*取出子串：\ （5） s5=replace（s3,3,1,s2）/*形成部分串：\ （6） s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下： /*：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 4.5 算法设计题 1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。 【算法分析】 判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0==t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。 20 【算法源代码】 int index(char s[ ], char t[ ],int m,int n) {int i=0,j=0; while (i<=m-n && j<=n-1) if (s[i]==t[j]){i++;j++;} /*对应字符相等，指针后移*/ else {i=i-j+1;j=0;} /*对应字符不相等，i回溯，j仍为0*/ if(i<=m-n && j==n) {printf(\在s串中位置是%d\ return(i-n+1); }/*匹配成功*/ else return(0); /*匹配失败*/ } 2．函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数） 【算法分析】 本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。 对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。 【算法源代码】 void insert(char *s,char *t,int pos) /*将字符串t插入字符串s的第pos个位置*/ { int i=1,x=0,j; char *p=s,*q=t; /*p，q分别为字符串s和t的工作指针*/ if(pos<1) {printf(\参数位置非法\\n\while(*p!='\\0'&&i {printf(\位置大于字符串s的长度\ else /*查找字符串的尾*/ while(*p!= '/0') {p++; i++;} /*查到尾时，i为字符'\\0'的下标，p也指向'\\0'*/ while(*q!= '\\0') {q++; x++; } /*查找字符串t的长度x，循环结束时q指向'\\0'*/ for(j=i;j>=pos ;j--) {*(p+x)=*p; p--;}/*串s的pos后的子串右移，空出串t的位置*/ q--; /*指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p--=*q--; /*将t串插入到s的pos位置上*/ } 3．设计一个算法，统计在输入字符串中各个不同字符出现的频度。（字符串中的合法字符为'A'-'Z'这26个字母和'0'-'9'这10个数字）。 【算法分析】 由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符'0'的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符'A'的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。 【算法源代码】 void Count() 21 /*统计输入字符串中数字字符和字母字符的个数*/ {int i,num[36]; char ch; for(i=0;i<36;i++)num[i]=0;/* 初始化*/ while((ch=getchar())!='#') /*‘#’表示输入字符串结束*/ if(('0'<=ch)&&(ch<='9')) {i=ch-'0';num[i]++;} /* 数字字符*/ else if(('A'<= ch)&&(ch <='Z')) {i=ch-'A'+10;num[i]++;}/* 字母字符*/ for(i=0;i<10;i++) /* 输出数字字符的个数*/ printf(\数字％d的个数＝％d\\n\for(i=10;i<36;i++)/* 求出字母字符的个数*/ printf(\字母字符％c的个数＝％d\\n\}/* 算法结束*/ 4．若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 【算法分析】 查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。 【算法源代码】 char SearchNo( LinkString S, LinkString T) /*查找不在T中出现的字符*/ { LinkString p,q; p=S; q=T; while (p) {/*取S中结点字符*/ while(q&&p->data!=q->data)/*进行字符比较*/ q->next; if(q==NULL)return p->data;/*找到并返回字符值*/ q=T; /*指针恢复串T的开始结点*/ p=p->next; } printf(\ return NULL; } 5．如果一个字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一个算法，输入字符串s，以“！”作为结束标志。如果串s中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。 【算法分析】 用字符数组s接受用户输入的字符串。设head指向当前发现的最长等值子串的串头，max记录此子串的长度。对s进行扫描，若发现新的等值子串，用count变量统计其长度，若他的长度大于原有的max，则对head和max进行更新。重复上述过程直到s末尾。 【算法源代码】 #define MAXSIZE 100 {int i,j,k,head,max,count; char s[MAXSIZE]; printf(\输入字符串：\ k=0; scanf(\ while(s[k]!='!') 22 scanf(\ i=0,j=1,head=0,max=1; for(;s[i]!='!'&&s[j]!='!';i=j,j++) {count=1; while(s[i]==s[j]) {j++; count++; } if(count>max) {head=i; max=count; } } if(max>1) {printf(\最大等值子串：\for(k=head;k<(head+max);k++) printf(\} else printf(\无等值子串\printf(\} 6．采用顺序存储结构存储的串，编写一个程序，将两个字符串进行比较，若s>t时返回1，s=t时返回0，s 从两个字符串的第一个字符开始逐个进行比较（按字符的ASCII码大小比较），直到出现不同的字符或遇到'\\0'为止。如果全部字符都相同，就认为两个字符串相等，返回0。若出现了不相同的字符，则以第一个不相同的字符的比较结果为准。若前者字符大于后者字符，则返回1，否则返回-1。 【算法源代码】 int comp(SString *s1,SString *s2) { int i=0,minlen; minlen=s1->len>s2->len?s1->len:s2->len; /*minlen存放s1与s2中的较短的字符串的长度*/ while(i<=minlen) { if(s1->data[i]==s2->data[i]) /*如果s1与s2的当前字符相等，则比较下一个*/ i++; else if(s1->data[i] else return 1; /*s1的当前值大于s2的当前值，返回1*/ } if(s1->len==s2->len) return 0; /*s1与s2所有字符均相等，且长度相等，则返回0*/ } 7．输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计其中的单词数。 【算法分析】 单词的数目可以有空格出现的次数来决定（连续的多个空格作为出现一次空格；不包含一行开头的空格）。如果当前字符为非空格，而他前面的字符是空格，则表示新的单词出现，此时让num（单词数）累加1。如果当前字符为非空格，而他前面的字符也是非空格，则表示此字符仍然是原单词的继续，num不应累加。前面一个单词是否为空格，可以设置一个变量 23 word，若word=0，则表示前一个字符时空格，如果word=1，表示前一个字符为非空格。 【算法源代码】 int count(s) char s[80]; {char c; int i,num=0,word=0; for(i=0;s[i]!='\\0';i++) {if(s[i]==' ') word=0; else if(word==0) {word=1; num++; } } return num; } 8．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的data字段只存放一个字母。试设计一个函数，去掉字符串中所有的X字母，并将串中的一个最小字母排列到串尾。 【算法分析】 从链表的表头开始查找每一个结点，如果该结点的数据值为X，则删除该结点。同时在查找的过程中，顺便比较该结点与前驱结点的大小，如果该结点的值闭其前驱结点的值大，则顺便交换，直到整个链表结束。 【算法源代码】 search(LinkList s,char x) /*在带头结点的单链表s中查找数据值为x的结点*/ { LinkList p,q,r; char temp; p=s->next; q=s;/*p表示当前操作的结点，q表示p的前驱结点*/ while(p!=NULL) {if(p->data==x) {r=p; q-next=p->next; p=p->next; free(r); } /*找到释放结点*/ else {q=p; p=p->next; } if(q!=s&&p->data>q->data) /*将结点值最小的结点移到表尾*/ { temp=p->data; p->data=q->data; q->data=temp; } } } 9．设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。 【算法分析】 要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到'\\0'，'\\0'一同复制过去，'\\0'之后的字符不复制。 【算法源代码】 copy(char s[],char t[]) 24 { int i; for(i=0;s[i]!='\\0';i++) t[i]=s[i]; t[i]=s[i]; } 10．编写一个实现串通配符匹配的函数，其中的通配符只有'?'，它可以和任何一个字符匹配成功。 【算法分析】 本题基本思想与模式匹配的基本思想相似，只是增加了'?'的处理功能。因为'?'可以与任何字符匹配成功，所以当字串中遇到'?'时，可以直接让主串和子串同时后移。 【算法源代码】 int pattern(SString s,SString t) { int i=1,j=1; while(i<=s[0]&&j<=t[0]) {if(s[i]==t[j]) {i++;j++; } else if(t[j]=='?') /*若字串中遇到'?'时，主串和子串同时后移*/ {i++;j++; } else {i=i-j+2;j=1; } if(j>t[0]) return(i-t[0]); else return 0; } 第5章 多维数组和广义表 5.1 选择题 1．数组A中，每个元素的长度为3个字节，行下标I从1到8，列下标J从1到10，从首地址SA开始连续存放在存储器内，该数组占用的字节数为（ ） A）80 B）100 C）240 D）270 【答案】C 2．数组A中，每个元素的长度为3个字节，行下标I从1到8，列下标J从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ） A）SA＋141 B）SA＋144 C）SA＋222 D）SA＋225 【答案】C 【解析】数组A有8行10列，按行存放时，LOC（A[8][5]）=SA+（（8-1）*10+（5-1））*3=SA+222。 3．一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为（ ） A）n*n B）n*n／2 C）（n+1）*n／2 D）（n+1）*（n+1）／2 【答案】C 【解析】对称矩阵可用上（或下）三角矩阵存储，第一行存1个，第二行存2个，?，第n行存n个，共1+2+?+n=（n+1）*n/2。 4．稀疏矩阵一般的压缩存储方法有两种，即（ ） A）二维数组和三维数组 B）三元组和散列 25 C）三元组和十字链表 D）散列和十字链表 【答案】C 5．设有广义表D=（a,b,D），则其长度为（ ），深度为（ ） A）1 B）3 C）∞ D）5 【答案】B C 6．广义表运算式（Tail（（a，B），（c，d）））的操作结果是（ ） A）（c，d） B）c,d C）（（c，d）） D）d 【答案】C 【解析】由于表中共2个元素，分别是两个广义表（a,b），（c,d），（a,B）是表头，因此Tail求得除表头外的元素构成的表即（（c,d））。 5.2 填空题 1．一维数组的逻辑结构是_____________，存储结构是_____________。 【答案】（1）线性结构 （2）顺序结构 2．对于二维数组或多维数组，分为按_____________和按_____________两种不同的存储方式存储。 【答案】（1）以行为主序 （2）以列为主序 3．二维数组A[c1..d1,c2..d2]共含有_____________个元素。 【答案】（d1-c1+1）*（d2-c2+1） 4．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，且A[0][0]的地址是200，则A[6][12]的地址是 。 【答案】326 【解析】采用列主序时，LOC（A[6][12]）=LOC（A[0][0]+（12*10+6）*1=326 5．有一个10阶对称矩阵A，采用以行为主序的压缩存储方式，A[0][0]的地址为1，则A[8][5]的地址是 。 【答案】42 【解析】A[8][5]前有8行，第0行1个元素，第1行2个元素，?，第7行8个元素，共（1+8）*8/2=36个元素，第8行前有5个元素，所以A[8][5]的地址为36+5+1=42。 6．广义表运算式HEAD（TAIL（（a，b，c），（x，y，z）））的结果为_____________。 【答案】（x,y,z） 5.3 判断题 1．数组中存储的数可是任意类型的任何数据（ ） 【答案】× 【解析】同一数组中数据元素的类型应该相同（ ） 2．N*N对称矩阵的经过压缩存储后占用的存储单元是原先的1/2。 【答案】× 【解析】应为（N＋1）*N/2个存储单元。 3．稀疏矩阵在用三元组表示法时，可节省空间，但对矩阵的操作会增加算法的难度及耗费更多的时间（ ） 【答案】√ 4．广义表不是线性表（ ） 26 【答案】× 【解析】广义表是特殊的线性表，其特殊性在于表中的数据元素还可以是广义表。 5．tail（a,b,c,d）得到的是（b,c,d）（ ） 【答案】√ 5.4 应用题 1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？ 【答案】设数组元素A[i][j]存放在起始地址为Loc （ i, j ） 的存储单元中。 ∵ Loc （ 2, 2 ） = Loc （ 0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = （ 676 - 2 - 644 ） / 2 = 15 ∴ Loc （ 3, 3 ） = Loc （ 0, 0 ） + 3 * 15 + 3 = 644 + 45 + 3 = 692. 2．设有一个n?n的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问： （1） 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？ （2） 若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。 【答案】 （1） 数组B共有1＋2 + 3 +?????? + n= （ n+1 ）*n / 2个元素。 （2） 只存下三角部分时，若i ? j，则数组元素A[i][j]前面有i-1行（1?i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，??????，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为： 1 + 2 + ?????? + （i-1） + j = （ i-1）*i / 2 + j 若i < j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第 （j-1）*j / 2 + i位置中找到。 如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为： 当i ? j时，= i*（i+1） / 2 + j 当i < j时，= j*（j+1） / 2 + i 3．利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来： （1） L1（apple, pear, banana, orange） （2） L2（（apple, pear）, （banana, orange）） （3） L3（（（apple）, （pear）, （bananA）, （orange））） （4） L4（（（（apple）））, （（pear））, （bananA）, orange） （5） L5（（（（apple）, pear）, bananA）, orange） （6） L6（apple, （pear, （bananA）, orange）） 【答案】 （1） Head （Tail （Tail （L1） ） ） （2） Head （Head （Tail （L2） ） ） （3） Head （Head （Tail （Tail （Head （L3） ） ） ） ） （4） Head （Head （Tail （Tail （L4） ） ） ） （5） Head （Tail （Head（L5） ） ） （6） Head （Head （Tail （Head （Tail （L6） ） ） ） ） 3．一个稀疏矩阵为 ，则对应的三元组线性表是什么？其对应的十字链表是什么？ 【答案】由于线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列，这个线性表用顺序的方法存储在连续的存储区，则对应的三元组为 27 其十字链表形式为： 5.5 算法设计题 1．假定数组A[n]的n个元素中有多个零元素，编写算法将A中所有的非零元素依次移到A的前端。 【算法分析】从前向后找零元素A[i]，从后向前找非零元素A[j]，将A[i]与A[j]交换。 【算法源代码】 void move(int A[],int n) {int i=0,j=n-1; int temp; while(i while(A[i]!=0) i++; while(A[j]==0) j--; if(i {temp=A[i];A[i]=A[j];A[j]=temp;} } } 2．给定有m个整数的递增有序数组A[1..m]和有n个整数的递减有序数组B[1..n]。试写出算法：将数组A和B归并为递增有序数组C[1..m+n]。（要求：算法的时间复杂度为O（m+n）。） 【算法分析】为保证算法的时间复杂度为O（m+n），即需要对数组A和B的数据元素仅扫描一次就能生成C数组，我们可采用设三个下标指针i,j,k初始时分别指向A数组的最后一个元素（A数组的最大值）、B数组的第一个元素（B数组的最大值）、C数组将存放最大值的位置，然后比较A与B数组的最大值大者放C数组k所指单元；在上述比较中若A数组i所指单元数大，则送完后i前移，否则j所指单元数送完后j后移，同时k前移，直到把A与B数组的所有元素扫描完。 【算法源代码】 #define m 3 #define n 4 void Merge(int A[],int B[],int C[]) {int i,j,k; i=m-1; j=0; k=m+n-1; while((i>=0)&&(j<=n-1)) {if(A[i]>B[j]) {C[k]=A[i]; i--;} else {C[k]=B[j]; j++; } k--; } while(i>=0) {C[k]=A[i];i--;k--;} while(j<=n-1) {C[k]=B[j];j++;k--; } } 3．假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也用三元组表示。 28 【算法分析】三元组表示中要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换，还必须使得列按顺序存放。因此在A中首先找出第一列中的所有元素，它们是转置矩阵中第一行非0元素，并把它们依次放在转置矩阵三元组数组B中；然后依次找出第二列中的所有元素，把它们依次放在数组B中；按照同样的方法逐列进行，直到找出第n列的所有元素，并把它们依次放在数组B中。 【算法源代码】 void transpose(TSMatrix A,TSMatrix *B) /*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组*/ {int i,j,k; B->mu=A.nu; B->nu=A.mu; B->tu=A.tu; if(B->tu>0) {j=1; for(k=1;k<=A.nu;k++) for(i=1;i<=A.tu;i++) if(A.data[i].col==k) {B->data[j].row=A.data[i].col; B->data[j].col=A.data[i].row; B->data[j].e=A.data[i].e; j++; } } } 4．求广义表深度的递归算法。 【算法分析】在求广义表深度的递归算法中，若结点为原子则深度为0，若是空表深度为1，否则返回头指针与尾指针所指广义表的深度最大值。 【算法源代码】 int Glist_Getdeph(Glist L) {int m,n; if(!L->tag) return 0; else if(!L) return 1; m=Glist_Getdeph(L->ptr.hp)+1; n=Glist_Getdeph(L->ptr.tp); return m>n?n:n; } 5．按层序输出广义表A中的所有元素。 【算法分析】层次遍历的问题，一般都是借助队列来完成的，每次从队头中取出一个元素的同时把它的下一层的孩子插入队尾，这就是层序遍历的基本思想。 【算法源代码】 void Glist_printf(Glist L) {InitQueue(Q); for(p=L;p;p=p->ptr.tp) EnQueue(Q,p); while(!QueueEmpty(Q)) {DeQueue(Q,r); if(!r->tag) printf(\ else for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); } } 第6章 树 6.1 选择题 1．一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A）?log2n ?+1 B）log2n +1 C）? log2n ? D）log2n-1 【答案】A 2．有关二叉树下列说法正确的是（ ） 29 A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 【答案】B 3．二叉树的第I层上最多含有结点数为（ ） I I-1I-1I A）2B）2-1 C）2 D）2-1 【答案】C 4．具有10个叶结点的二叉树中有（ ）个度为2的结点 A）8 B）9 C）10 D）11 【答案】B 5．在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③ B）②③④ C）②④ D）①④ 【答案】D 6．由3 个结点可以构造出多少种不同的二叉树？（ ） A）2 B）3 C）4 D）5 【答案】D 7．引入二叉线索树的目的是（ ） A）加快查找结点的前驱或后继的速度 B）为了能在二叉树中方便的进行插入与删除 C）为了能方便的找到双亲 D）使二叉树的遍历结果惟一 【答案】A 8．有n个叶子的哈夫曼树的结点总数为（ ） A）不确定 B）2n C）2n+1 D）2n-1 【答案】D 9．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） A）所有的结点均无左孩子 B）所有的结点均无右孩子 C）只有一个叶子结点 D）是任意一棵二叉树 【答案】C 【解析】先序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，单支树的特点是只有一个叶子结点或高度等于其结点数，故选C。 10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A）250 B）500 C）505 D）以上答案都不对 【答案】D 【解析】若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。因此，叶子结点数为1001-500=501。故答案为D。 11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（ ） A）ACBED B）DECAB C）DEABC D）CEDBA 【答案】D 【解析】依据后序遍历序列可确定根结点为C；再依据中序遍历序列可知其左子树由DEBA构成，右子树为空；又由左子树的后序遍历序列可知其根结点为E，由中序遍历序列可知E的左子树为D，右子树由BA构成，所以求得该二叉树的先序遍历序列为选项D）。 12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A）9 B）11 C）15 D）不确定 【答案】B 13．利用二叉链表存储树时，根结点的右指针是（ ） A）指向最左孩子 B）指向最右孩子 C）空 D）非空 30 【答案】C 【解析】利用二叉链表存储树时，即用孩子兄弟链表存储树，根结点的左指针指向其第一子女，根结点的右指针指向其下一兄弟，所以为空。 14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ） A）M1 B）M1+M2 C）M3 D）M2+M3 【答案】D 【解析】当森林转化为对应的二叉树时，二叉树的根结点及其左子树是由森林的第一棵树转化而来，二叉树的右子树是由森林的其余树转化而来。 15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ ） A）X的双亲 B）X的右子树中最左的结点 C）X的左子树中最右结点 D）X的左子树中最右叶结点 【答案】C 16．n个结点的线索二叉树上含有的线索数为（ ） A）2n B）n-l C）n+l D）n 【答案】C 【解析】线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 17．在一棵高度为k的满二叉树中，结点总数为（ ） k-1 k kk A）2B）2C）2-1 D）?log2?+1 【答案】C 18．一棵树高为K的完全二叉树至少有（ ）个结点 kk-1k-1 k A）2-1 B）2-1 C）2D）2 【答案】C 6.2 填空题 1．在二叉树中，指针p所指结点为叶子结点的条件是_____________。 【答案】p->lchild==NULL && p->rchlid==NULL 2．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点；H和结点总数N之间的关系是_____________。 H-1H 【答案】（1）2 （2）2-1 （3）H=?log2N?+1 3．一棵有n个结点的满二叉树有_____________个度为1的结点，有_____________个分支（非终端）结点和_____________个叶子，该满二叉树的深度为_____________。 【答案】（1）0 （2）(n-1）/2 （3）(n+1）/2 （4）?log2n? +1 4．对于一个具有n个结点的二叉树，当它为一棵_____________时，具有最小高度，当它为一棵_____________时，具有最大高度。 【答案】（1）完全二叉树 （2）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。 5．在一棵二叉树中，度为0的结点的个数为N0，度为2的结点的个数为N2，则有N0 =_____________ 【答案】N2+1 6．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 【答案】99 【解析】在二叉树中，N0 = N2+1，所以，有50个叶子结点的二叉树，有49个度为2的结点。若要使该二叉树的结点数最少，度为1的结点应为0个，即总结点数N= N0 +N1+ N2 =99。 7．具有n个结点的满二叉树，其叶结点的个数是_____________。 【答案】(n+1）/2 8． 每一棵树都能惟一的转换为它所对应的二叉树。若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_____________。设上述二叉树是由某森林转换而成，则其第一棵的 31 先根次序序列是_____________。 【答案】 （1）FEGHDCB （2）BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是BEF） 9．已知一棵二叉树的先序序列为ABDECFHG，中序序列为DBEAHFCG，则该二叉树的根为_____________，左子树中有_____________， 右子树中有_____________。 【答案】（1）A （2）DBE （3）HFCG 10．先根次序周游树林正好等同于按_____________周游对应的二叉树；后根次序周游树林正好等同于_____________周游对应的二叉树。 【答案】（1）先根次序 （2）中根次序 11．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_____________；编号是i的结点所在的层次号是_____________（根所在的层次号规定为1层）。 k-2 【答案】（1）2+1 （2）?log2i?+1 k-1k-1k2 【解析】第k层1个结点，总结点个数是2，其双亲是2/2=2-。 12．某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____________。 【答案】69 【解析】在二叉树中，N0 = N2+1，所以，有20个叶子结点的二叉树，有19个度为2的结点。又已知该二叉树中度为1的结点有30个，则总结点数N= N0 +N1+ N2 =69。 13．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_____________，带权路径长度WPL为_____________。 【答案】（1）6 （2）261 14．有一份电文中共使用 6个字符：a，b，c，d，e，f，它们的出现频率依次为2，3，4，7，8，9，试构造一棵哈夫曼树，则其加权路径长度WPL为_____________，字符c的编码是_____________。 【答案】（1）80 （2）001（不惟一） 15．具有N个结点的二叉树，采用二叉链表存储，共有_____________个空链域。 【答案】N+1 【解析】在二叉树中， N= N0 +N1+ N2 ，N0 = N2+1，空分支数为2 N0+N1= N0 +N1+ （N2+1）= N+1。 16．8层完全二叉树至少有_____________个结点，拥有100个结点的完全二叉树的最大层数为_____________。 【答案】（1）128（第7层满，加第8层１个） （2）7 17．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_____________。 【答案】21 【解析】已知该树中结点数和分支数的关系分别如下： N= N0 +N1+ N2+N3+ N4 （1） N-1= N1+ 2N2+3N3+ 4N4 （2） 由（2）式求得N=（1+2*2+3*3+4*4）+1=31，再由（1）式求得N0=21。 18． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 【答案】（1）2 （2）n-1 （3）1 （4）n （5）1 （6）n-1 19．设y指向中序二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild，rchild分别代表左，右孩子) x->ltag= _____________; x->lchild= _____________; y->ltag= _____________; y->lchild= _____________; x->rtag= _____________; 32 x->rchild= _____________; if (x->lchild!=NULL) && (x->lchild->rtag==1) x->lchild->rchild=_____________; 【答案】（1）1 （2）y->lchild （3）0 （4）x （5）1 （6）y （7）x 6.3 判断题 1．二叉树是度为2的有序树（ ） 【答案】× 2．完全二叉树一定存在度为1的结点（ ） 【答案】× 3．深度为K的二叉树中结点总数≤2k-1（ ） 【答案】√ 4．由一棵二叉树的先序序列和后序序列可以惟一确定它（ ） 【答案】× 5．完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ） 【答案】√ 6．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（ ） 【答案】√ 7．完全二叉树的存储结构通常采用顺序存储结构（ ） 【答案】√ 8．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ） 【答案】√ 9．在中序线索二叉树中，每一非空的线索均指向其祖先结点（ ） 【答案】√ 【解析】在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 10．二叉树中序线索化后，不存在空指针域（ ） 【答案】× 【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 6.4 应用题 1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。 树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。 2．若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作： （1）寻找某个结点双亲 ； （2）寻找某个结点的子女； 请问应该用何种结构来存储该二叉树？ 【答案】用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是?i/2?(i=1时无双亲)，其左子女是2i(若2i≤n，否则i无左子女)，右子女是2i+1(若2i+1≤n，否则无右子女)。 3．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。 33 【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是?n/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是?n/2?+1。 4．试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc，后序bca，中序bac。 【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。 5．试找出满足下列条件的二叉树： 1）先序序列与后序序列相同； 2）中序序列与后序序列相同； 3）先序序列与中序序列相同； 4）中序序列与层次序列相同； 【答案】先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根”，根据以上原则，解答如下： 1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。 2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 （3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 （4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树 6．已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA （1）给出这棵二叉树；（2）转换为对应的森林。 7．一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。 【答案】先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下： 8．假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。 【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。 9．已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树， 34 再构造出森林。 10．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A 【答案】 11．设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，设计一套二进制编码，使得上述正文的编码最短。【答案】字符A，B，C，D出现的次数为9，1，5，3。其哈夫曼编码如下：A:1，B:000，C:01，D:001 。 12．已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。 6.5 算法设计题 35 1．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。 【算法分析】 二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲…等等，直至找到最近的公共祖先。 【算法源代码】 typedef int ElemType; void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j) if(i>j) i=i/2; /*下标为i的结点的双亲结点的下标*/ else j=j/2; /*下标为j的结点的双亲结点的下标*/ printf(\所查结点的最近公共祖先的下标是%d,值是%d\ }/* Ancestor*/ 2．编程求以孩子兄弟表示法存储的森林的叶子结点数，要求描述结构。 【算法分析】 当森林（树）以孩子兄弟表示法存储时，若结点没有左子树（fch=NULL），则它必是叶子，否则，总的叶子结点个数是左子树（fch）上的叶子数和右子树（nsib）上叶结点个数之和。 【算法源代码】 typedef struct node{ ElemType data; /*数据域*/ struct node *fch, *nsib; /*孩子与兄弟域 */ }*Tree; int Leaves (Tree t){/*计算以孩子-兄弟表示法存储的森林的叶子数*/ if(t) if(t->fch==NULL) /*若结点无孩子，则该结点必是叶子*/ return(1+Leaves(t->nsib)); else return (Leaves(t->fch)+Leaves(t->nsib)); }/*结束Leaves*/ 3．假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…， N的二叉树的存储结构。L[i]和R[i]分别指示结点 i的左子女和右子女；L[i]=0（R[i]=0）表示i的左（右）子女为空。设计一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。 【算法分析】 由指示结点i 左子女和右子女的两个一维数组L[i]和R[i]，很容易建立指示结点i 的双亲的一维数组T[i]，根据T数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。 【算法源代码】 int generation (int u, int v, int n, int l[],int r[],int t[]){ /*l[]和r[]是含有n个元素且指示二叉树结点i左子女和右子女的一维数组本算法据此建立结点i的双亲数组t，并判断结点u是否是结点v的后代*/ int parent,i; for(i=1;i<=n;i++) t[i]=0; /*t数组初始化*/ for (i=1;i<=n;i++){ /*根据l和r填写t*/ if(l[i]!=0) t[l[i]]=i; /*若结点i的左子女是l，则结点l的双亲是结点i*/ if (r[i]!=0) t[r[i]]=i; /*i的右子女是r，则r的双亲是i*/ parent=u; /*判断u是否是v的后代*/ while (parent!=v && parent!=0) parent=t[parent]; if (parent==v) {printf(\结点u是结点v的后代\ else { printf(\结点u不是结点v 的后代\ } }/*结束generation*/ 4．要求二叉树按二叉链表形式存储： （1）写一个建立二叉树的算法。 （2）写一个判别给定的二叉树是否是完全二叉树的算法。 【算法分析】 二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完 36 全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 【算法源代码】 BiTree Creat() { /*建立二叉树的二叉链表形式的存储结构*/ ElemType x; BiTree bt; scanf(\ if(x==0) bt=NULL; else if(x>0) {bt=(BiTNode *)malloc(sizeof(BiTNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } return(bt); }/*结束 creat*/ int JudgeComplete(BiTree bt){ /*判断二叉树是否是完全二叉树，如是，返回1，否则，返回0*/ int tag=0; BiTree p=bt, Q[50]; /* Q是队列，元素是二叉树结点指针，容量足够大*/ if(p==NULL) return 1; QueueInit(Q); QueueIn(Q,p); /*初始化队列，根结点指针入队*/ while(!QueueEmpty(Q)){ p=QueueOut(Q); if (p->lchild && !tag) QueueIn(Q,p->lchild); /*左子女入队*/ else if (p->lchild) return 0; /*前边已有结点为空，本结点不空*/ else tag=1; /*首次出现结点为空*/ if (p->rchild && !tag) QueueIn(Q,p->rchild); /*右子女入队*/ else if (p->rchild) return 0; else tag=1; }/*while*/ return 1; } /*JudgeComplete*/ 5．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 【算法源代码】 typedef int ElemType; BiTree Creat(ElemType A[],int i){ BiTree tree; if (i<=n) { tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i]; if(2*i>n) tree->lchild=NULL; else tree->lchild=Creat(A,2*i); if(2*i+1>n) tree->rchild=NULL; else tree->rchild=Creat(A,2*i+1); } return (tree); }/*Creat*/ 6．编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。 【算法源代码】 int c,k; /*这里把k和计数器c作为全局变量处理 */ void Get_PreSeq(BiTree T) /*求先序序列为k的结点的值 */ { if(T) { c++; /*每访问一个子树的根都会使前序序号计数器加1 */ if(c==k) { printf(\ return; } else { Get_PreSeq(T->lchild); /*在左子树中查找 */ Get_PreSeq(T->rchild); /*在右子树中查找 */ } }/*if */ }/*Get_PreSeq */ 7．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注 37 ：已知树中结点数） 【算法分析】 由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树的深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。 【算法源代码】 int Depth(PTree t){ int maxdepth=0; int i,f,temp; for(i=1;i<=t.n;i++){ temp=0; f=i; while(f>0) {temp++; f=t.nodes[f].parent; } /* 深度加1，并取新的双亲*/ if(temp>maxdepth) maxdepth=temp; } /*最大深度更新*/ } return(maxdepth);/*返回树的深度*/ } /*结束Depth*/ 8．二叉树采用二叉链表存储 （1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。 （2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 【算法分析】 二叉树是递归定义的，其运算最好采取递归方式。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 【算法源代码】 int Height(BiTree bt) /*求二叉树bt的深度*/ {int hl,hr; if (bt==NULL) return(0); else { hl=Height(bt->lchild); hr=Height(bt->rchild); if(hl>hr) return (hl+1); else return(hr+1);} } int Width(BiTree bt)/*求二叉树bt的最大宽度*/ {if (bt==NULL) return (0); /*空二叉树宽度为0*/ else {BiTree p,Q[50];/*Q是队列，元素为二叉树结点指针，容量足够大*/ int front=1,rear=1,last=1; int temp=0, maxw=0; /*temp记局部宽度, maxw记最大宽度*/ Q[rear]=bt; /*根结点入队列*/ while(front<=last) {p=Q[front++]; temp++; /*同层元素数加1*/ if (p->lchild!=NULL) Q[++rear]=p->lchild; /*左子女入队*/ if (p->rchild!=NULL) Q[++rear]=p->rchild; /*右子女入队* if (front>last) /*一层结束*/ {last=rear; /*last指向下层最右元素, 更新当前最大宽度*/ if(temp>maxw) maxw=temp; temp=0;}/*if*/ }/*while*/ return (maxw); } }/*结束width*/ 9．设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。 【算法源代码】 void exchange(BiTree bt)/*将二叉树bt所有结点的左右子树交换 { BiTree p; if(bt){ p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; /*左右子女交换 exchange(bt->lchild); /*交换左子树上所有结点的左右子树 exchange(bt->rchild); /*交换右子树上所有结点的左右子树 } } 【算法讨论】 38 将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。 10．已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储。 （1）编写用先根遍历二叉树中每个结点的递归算法； （2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。 【算法分析】 K 高度为K的二叉树，按顺序方式存储，要占用2-1个存储单元，与实际结点个数n关系不大，对不是完全二叉树的二叉树，要增加“虚结点”，使其在形态上成为完全二叉树。注意：二叉树中最大序号的叶子结点，是在顺序存储方式下编号最大的结点。 【算法源代码】 K int m=2-1; /*全局变量*/ void PreOrder(ElemType bt[], int i ) {if (i<=m) /*设虚结点以0表示*/ {printf(\ /*访问根结点*/ if(2*i<=m && bt[2*i]!=0) PreOrder(bt,2*i); /*先序遍历左子树*/ if(2*i+1<=m && bt[2*i+1]!=0) PreOrder(bt,2*i+1);/*先序遍历右子树*/ } }/*结束PreOrder*/ void Ancesstor(ElemType bt[]){ /*打印最大序号叶子结点的全部祖先*/ c=m; while(bt[c]==0) c--; /*找最大序号叶子结点，该结点存储时在最后*/ f=c/2; /*c的双亲结点f*/ while(f!=0){ /*从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点*/ printf(\ f=f/2; }/*逆序输出，最老的祖先最后输出*/ }/*结束*/ 11．编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。 【算法源代码】 void Del_Sub(BiTree T)/*删除子树T */ { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }/*Del_Sub */ void Del_Sub_x(BiTree T,int x)/*删除所有以元素x为根的子树*/ { if(T->data==x) Del_Sub(T); /*删除该子树 */ else {if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); /*在左右子树中继续查找 */ }/*else */ }/*Del_Sub_x */ 12．设计一个算法，在中序全线索二叉树中，查找给定结点* p在中序序列中的后继（二叉树的根结点指针并未给出），并中序遍历该线索二叉树。 【算法源代码】 BiThrTree insucc(BiThrTree p)/*找p结点的后继*/ { if(p->rtag==1) /*后继线索*/ return p->rchild; else /*右子树的最左下结点*/ { p=p->rchild; while(p->ltag==0) p=p->lchild; return p; } } void inorder_thr(BiThrTree T) { BiThrTree p=T; if(p) { while(p->ltag==0) p=p->lchild;/*找中序遍历的第1个结点*/ do{ printf(\ 39 p=insucc(p);/*找当前结点的后继结点*/ }while(p); } } 7.5 算法设计题 1．设计一个算法，删除无向图的邻接矩阵中给定顶点。 【算法分析】 要在邻接矩阵中删除某顶点i主要操作有以下三步：（1）图的边数要减去与顶点i相关联的边的数目；（2）在邻接矩阵中删除第i行与i列,即把第i+１行到第n行依次前移，第i+１列到第n列依次前移。（3）图中顶点的个数-1。 【算法源代码】 void Delvi(MGraph *G,int i)/*在图 G中删除顶点I*/ {int num,j,k; if(i<1||i>G->vexnum) {printf(\ exit(0);} else {num=0; for(j=1;j<=G->vexnum;j++) {if(G->arcs[i][j]) num++; if(G->arcs[j][i]) num++; } G->arcnum-=num; for(j=i+1;j<=G->vexnum;j++) for(k=1;k<=G->vexnum;k++) G->arcs[j-1][k]=G->arcs[j][k]; for(j=i+1;j<=G->vexnum;j++) for(k=1;k<=G->vexnum-1;k++) G->arcs[k][j-1]=G->arcs[k][j]; G->vexnum--; } } 2．设计一个算法，求出分别用邻接矩阵和邻接表表示的有向图中顶点的最大出度值。 【算法分析】 用邻接矩阵表示的有向图中顶点的最大出度是该顶点所在行上非零元的个数。邻接表表示的有向图中顶点的最大出度值是该顶点所连接的单链表中结点的个数。 【算法源代码1】 void Max_du(MGraph *G) {int num,i,j; int max=0; for(i=1;i<=G->vexnum;i++) {num=0; for(j=1;j<=G->vexnum;j++) if(G->arcs[i][j]) num++; if(max printf(\ } 【算法源代码2】用邻接表表示 void Max_du(ALGraph *G) {ArcPtr p; int num,i,j; int max=0; for(i=1;i<=G->vexnum;i++) {num=0; p=G->ag[i].firstarc; while(p) {p=p->nextarc; num++; } if (max printf(\ } 3．已知某有向图用邻接表表示，设计一个算法，求出给定两顶点间的简单路径。 【算法分析】 因为在遍历的过程中每个顶点仅被访问一次，所以从顶点u到顶点v遍历的过程中走过的路径就是一条简单路径。我们只需在遍历算法中稍作修改，就可实现该算法。为了记录路径中访问过的顶点，只需设一数组存储走过的顶点即可。 【算法源代码】 40 int visited[MAX_VERTEX_NUM]; int found; void DFSpath(ALGraph *G,int u,int v){ int i; for(i=1;i<=G->vexnum;i++)visited[i]=0; found=0; DFS(G,u,v); } int path[MAX_VERTEX_NUM]; void DFS(ALGraph *G,int u,int v) { /*用深度优先遍历算法实现简单路径的求解*/ ArcPtr p; if(found) return; if(G->ag[u].firstarc==NULL){printf(“no path\\n”);return;} visited[u]=1; for(p=G->ag[u].firstarc;p;p=p->nextarc) { if (v==p->adjvex) {path[u]=v; found=1; Print(u,v); return;} else if(!visited[p->adjvex]) {path[u]=p->adjvex; DFS(G,p->adjvex,v);} } }/*DFS*/ void Print(int u,int v){ int m; printf(\ for(m=path[u];m!=v;m=path[m]) printf(\ printf(\ } 4．设计一个深度优先遍历图的非递归算法。（图用邻接矩阵存储） 【算法分析】 在相应的深度优先遍历的非递归算法中，使用一个辅助数组visited[ ]，在visited[i]中记忆第i个顶点是否访问过。使用了一个栈s，存储回退的路径。 【算法源代码】 void DFS ( int v ,Mgraph *G) {/*从顶点v开始进行深度优先搜索*/ int visited[MAX_VERTEX_NUM]; int s[MAX_VERTEX_NUM]; int i, j, k,top; top=0;s[++top]=v; for ( i = 0; i < G->vexnum; i++ ) visited[i] = 0; while (!top ) { k = s[top]; top--; /*栈中退出一个顶点*/ if (!visited[k] ) { printf(“%d”,k); visited[k] = 1; /*访问，并作访问标记*/ for ( j =Vertex_num-1; j >= 0; j-- ) /*检查k的所有邻接顶点*/ if ( k!= j &&!G->arcs[k][j]) s[++top]=j;/*所有邻接顶点进栈*/ } } } 5．设计一个算法，输出距离顶点v0的最短路径长度为k的所有顶点，其中路径长度指的是弧或边的数目。 【算法分析】 本题用广度优先遍历的层次遍历法求解比较简单，要输出到v0的路径长度为k的所有顶点，也就是由v0开始作为第一层，它的邻接点作为第二层，依次?，输出第k+1层上的所有元素。故在访问每一个顶点的同时，记录下它所在的层次数。为此需设置两个队列分别存放被访问的顶点及层次，且两个队列要同步操作。 【算法源代码】 #define MAX_VERTEX_NUM 20 int visited[MAX_VERTEX_NUM]; /*visited[i]=0表示i未被访问, visited[i]=1表示i已被访问*/ /**************************************/ 41 void Init(SqQueue *q){ q->front=q->rear=0; } /**************************************/ int Empty(SqQueue *q){ if (q->rear==q->front) return 1; return 0; } /**************************************/ void Inqueue(SqQueue *q,int x){ if((q->rear+1) % MAX_VERTEX_NUM==q->front) {printf(\ return; } else{ q->rear=(q->rear+1) %MAX_VERTEX_NUM; q->data[q->rear]=x; } } /**************************************/ int Outqueue(SqQueue *q){ if(Empty(q)){ printf(\ return -1; } else{ q->front=(q->front+1) % MAX_VERTEX_NUM; return(q->data[q->front]); } } /**************************************/ void bfsk(int v0,int k,ALGraph *G){ /*在图G中查找距离v0的路径长度为k的所有顶点*/ int i,level,v,visited[MAX_VERTEX_NUM]; /*定义访问数组*/ ArcPtr w; SqQueue Q1,Q2;/*定义两个队列*/ Init(&Q1); Init(&Q2);/*两个队列初始化*/ for(i=1;i<=G->vexnum;i++) visited[i]=0; visited[v0]=1; level=1; Inqueue(&Q1,v0); Inqueue(&Q2,level); /*v0及层次入队列*/ while(!Empty(&Q1)&&(level w=G->ag[v].firstarc;/*取v的第一个邻接点*/ while(w){ if(!visited[w->adjvex]){ if(level==k) printf(\输出满足条件的邻接点*/ visited[w->adjvex]=1; Inqueue(&Q1,w->adjvex); Inqueue(&Q2,level+1); } w=w->nextarc; /*取v的下一个邻接点*/ } } } 6．设计一个算法，用深度优先遍历法对AOV网进行拓扑排序，检测其中是否存在环。 【算法分析】 如果从有向图中的某个顶点v出发开始遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生 42 成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。本算法以邻接表作为存储结构，函数返回１表示无环，返回０表示有环． 【算法源代码】 #define MAX_VERTEX_NUM 20 int visited[MAX_VERTEX_NUM]; /*visited[i]=0表示i未被访问, visited[i]=1表示i已被访问*/ int finished[MAX_VERTEX_NUM]; /*finished[i]=1表示i已被访问，finished[i]=０表示i未被访问*/ int flag=1; void dfs(ALGraph *G,VertexType v){ /*遍历时若不存在环，输出的全部顶点序列即为拓扑序列，*/ /*否则flag置为0,表示存在环*/ ArcPtr p; finished[v]=0; visited[v]=1; p=G->ag[v].firstarc; while(p){ if(visited[p->adjvex]&&(!finished[p->adjvex])) flag=0; else if(!finished[p->adjvex]){ dfs(G,p->adjvex); finished[p->adjvex]=1; } p=p->nextarc; } } void dfs_sort(ALGraph *G){ int i; for(i=0;i for(i=0;i while(flag&&i 第7章 图 7.1 选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（ ） A） 无向图中的极小连通子图 B） 无向图中的极大连通子图 C） 有向图中的极小连通子图 D） 有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（ ） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 43 ）【答案】D 5．关键路径是（ ） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（ ） A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（ ）边结点。 A） e B） 2e C） e-1 D） 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】A 10．存储无向图的邻接矩阵一定是一个（ ） A） 上三角矩阵 B）稀疏矩阵 C） 对称矩阵 D） 对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（ ）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ ） 23 A） O(n) B） O(n+e) C） O(n) D） O(n) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（ ） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（ ） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ） 22 A） e B）2e C） n-e D）n-2e 【答案】D 7.2 填空题 1．无向图中所有顶点的度数之和等于所有边数的_____________倍。 【答案】2 2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。 【答案】（1）n(n-1)/2 （2） n(n-1) 44 3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。 【答案】n-1 4．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为_____________和_____________。 2 【答案】（1）O(n) （2） O(n+e) 5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。 2 【答案】（1）O(n) （2） O(e) 6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。 【答案】（1）e （2）2e 7． 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。 【答案】（1）出边 （2） 入边 8． 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。 【答案】（1）O(n) （2）O(e+n) 9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。 【答案】（1）n （2） n-1 10．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。 2 【答案】（1）O(n) （2）O(eloge) 11．针对下图所示的连通网络，试按如下格式给出在Kruscal算法构造最小生成树过程中顺序选出的各条边 。 【答案】设边的信息表示为（始点，终点，权值），则在Kruscal算法构造最小生成树过程中顺序选出的各条边为：（3 ，5，1），（2，4，2），（1，5，3），（1，2，3）。 7.3 判断题 1．图是一种非线性结构，所以只能用链式存储。（ ） 【答案】× 2．图的最小生成树是唯一的。（ ） 【答案】× 3．如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。（ ） 【答案】√ 4．有n-1 条边的图一定是生成树。（ ） 【答案】× 5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（ ） 【答案】√ 6．用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价为O(n+e)。（ ） 【答案】√ 45 7．逆邻接表只能用于有向图，邻接表对于有向图和无向图的存储都适用。（ ） 【答案】√ 8．任何一个关键活动提前完成, 那么整个工程将会提前完成。（ ） 【答案】× 9．在AOE网络中关键路径只有一条。（ ） 【答案】× 10．在AOV网络中如果存在环，则拓扑排序不能完成。（ ） 【答案】√ 11．图的邻接矩阵存储是唯一的，邻接表存储也是唯一的。（ ） 【答案】× 12．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是O(n*e) 。（ ） 【答案】× 13．任意一个图都是其自身的子图。（ ） 【答案】√ 14．一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（ ） 【答案】× 7.4 应用题 1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={ （1）边集E中 2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。 【答案】 【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则 n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。 3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题： （1）图中有多少条边? （2）任意两个顶点i和j是否有边相连? 46 （3）任意一个顶点的度是多少? 【答案】 （1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。 （2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。 （3）任意一个顶点vi的度是第i行或第i列上非0元的个数。 4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。 【答案】 邻接矩阵如下： 邻接表如下： 逆邻接表如下： 十字链表如下： 47 深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF 5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。 【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。 【答案】该无向图如下所示： 深度优先搜索生成树为： 广度优先搜索生成树为： 6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。 48 【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。 【答案】 【解析】Kruscal算法的操作步骤： 首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。 【答案】 7． 写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 49 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); （3）计算e(i),l(i)：设ai由弧 l(i)=vl(k)-dut( （4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为：a0->a4->a6->a9 8． 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 9．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。 50