讨论小课堂和习题解答

讨论小课堂 1

1.算法和程序的区别是什么呢？

【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

要设计一个好的算法通常要考虑以下的要求。

⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。 ⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。 ⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。 ⑷高效。有效使用存储空间和有较高的时间效率。

2，你认为应该如何评估一个数据结构或算法的有效性。

【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。

习题1

1. 抽象数据类型的定义由哪几部分组成？ 【参考答案】：数据对象、数据关系和基本操作三部分。 2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 【参考答案】：线性结构、树型结构、图状结构和集合四类。 5.数据结构和数据类型两个概念之间有区别吗？

【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

6. 简述线性结构与非线性结构的不同点。 【参考答案】：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 7. 有下列两段描述：

（1）void pro1( ) (2)void pro2( ) { {

n=2; y=0; While(n%2==0) x=5/y;

n=n+2; printf(―%d,%d\\n,x,y); printf(―%d\\n‖,n); }

}

这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？

【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。

8. 分析并写出下面的各语句组所代表的算法的时间复杂度。 (1) for (i=0; i

for (j=0; j

A[i][j]=0;

【参考答案】：O（m*n）

(2) k=0;

for( i=1; i<=n; i++) { for (j=i ; j<=n; j++) k++; } 【参考答案】：O（n2）

(3) i=1;

while(i<=n)

i=i*3; 【参考答案】：3 T(n)≤n即：T(n) ≤log3n =O（log3n）所以：T(n)= O（log3n） (4) k=0;

for( i=1; i<=n; i++) { for (j=i ; j<=n; j++)

for (k=j ; k<=n; k++) x += delta;; } 【参考答案】：O（n3）

(5) for(i=0,j=n-1;i

{t=a[i]; a[i]= a[j]; a[i]=t;}

【参考答案】：基本语句共执行了n/2次，T(n)=O（n） (6) x=0;

for(i=1; i

x++;

【参考答案】：因为x++共执行了n-1+n-2+??＋1= n(n-1)/2，所以执行时间为O（n2）

讨论小课堂2

1. 在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。（注意：对比顺序存储结构和链式存储结构表示。） 【参考答案】

⑴方法一：顺序存储结构

void insert(ElemType x) { i=length-1;

while(i>=0&&elem[i]>x) {elem[i+1]=elem[i]; i--; }

elem[i+1]=x;length++; }

⑵方法二：链式存储结构 void insert(ElemType x) { NodeType *p,*q,*s;

p=L;q=q->next;

while(q!=NULL&&q->data<=x) {p=q;q=q->next;} s=new NodeType; s->data=x;

p->next=s; s->next=q; }

2.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的元素。问：如何改进此算法，使得算法效率提高？

void Deletaz(ElemType x) { int i=0,j;

while (i

{ for(j=I;j

}

}

【答案】

void delete(ElemType x)

{ int i=0,j,n;

while(i

while(elem[i]==x) {n++;i++;} for(j=i;j

3．试设计一个算法，将线性表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, , ?, am, b1, b2, ?, bn ) 改变成

(b1, b2, ?, bn, a1, a2, ?, am )

要求采用顺序存储结构及链式存储结构分别完成，并比较采用这两种存储结构，其算法效率哪种存储结构更好？

【答案】试设计一个算法，顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, a2, ?, am, b1, b2, ?, bn ) 改变成 (b1, b2, ?, bn, a1, a2, ?, am ) 。

算法 1：进行三次“逆转顺序表”的操作。

算法 2：从 b1开始，从原地删除之后插入到 a1 之前直至 bn。

例如：具体实例：{ a, b, c, d, e, f, g ,1, 2，3，4，5}改变成{1, 2，3，4，5,a, b, c, d, e, f, g}

1 2 3 4 5 a b c d e f g 3 1 2 3 i j a b c d e f g 4 5

算法 1：

void invert( ElemType R[]，int s， int t )

/* 本算法将数组 R 中下标自 s 到 t 的元素逆置， 即将（Rs, Rs+1, …, Rt-1, Rt ） 改变为（Rt, Rt-1, …, Rs+1, Rs ）*/

void exchange ( SqList A; int m ) {

/*本算法实现顺序表中前 m 个元素和后 n 个元素的互换*/ n = A.length – m;

invert( A.elem, 0, A.length ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); } 算法 2:

void exchange( SqList A, int m ) {

/* 实现顺序表 A 中前 m 个元素和后 n 个元素互换*/ for ( i=0; j = m; ji; k-- ) A.elem[j] = A.elem[j-1]; A.elem[i] = x; }

算法的时间复杂度:为: O(m?n) 算法设计:

将 (b1, b2, …, bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。

ta L a1 a2 hb tb … am ∧ b1 b2 … bn ∧ ta->next=NULL; tb->next = L->next; L->next = hb;

void exchange( SLink &L, int m ) { // 互换链表中前 m 个和后 n 个结点 ta = L; i = 0;

while ( ta && i

ta = ta->next; i++;

}// while

if ( ta && ta->next ) { // m < 表长 hb = ta->next; tb = hb;

while (tb->next) tb = tb->next; // 查询表尾 bn修改指针 }

算法的时间复杂度:为:O(ListLength(L))

4．讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。 【答案】存储结构分为：

⑴顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 ⑵数据的逻辑结构—只抽象反映数据元素的逻辑关系

数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 ⑶数据的逻辑结构与存储结构密切相关： 算法设计 → 逻辑结构 算法实现 → 存储结构 ⑷顺序表：

可以实现随机存取：?(1)

插入和删除时需要移动元素：?(n) 需要预分配存储空间;

适用于―不常进行修改操作、表中元素相对稳定‖的场合。 链表：

只能进行顺序存取：?(n)

插入和删除时只需修改指针：?(1)

不需要预分配存储空间;

适用于―修改操作频繁、事先无法估计最大表长‖的场合。 —— 应用问题的算法时间复杂度的比较

例如，以线性表表示集合进行运算的时间复杂度为?(n2),

而以有序表表示集合进行运算的时间复杂度为?(n)

习 题 2

1．判断下列概念的正确性

(1) 线性表在物理存储空间中也一定是连续的。

(2) 链表的物理存储结构具有同链表一样的顺序。

(3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。

答：（1）（2）（3）都不正确。

2. 有如下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化？画出处理后的线性表。

void daorder()

{ int i, j, n ; ElemType x; n=length/2;

for( i=0 ; i

{ j=length-i-1;

x=elem[i]; elem[i]=elem[j]; elem[j]=x;

}

}

elem[0] ??

elem[7]

假设length=8

1 2 3 4 5 6 7 8 …

答：经过daorder 算法处理后，线性表发生了逆置。处理后的线性表为：

3．试比较顺序存储结构和链式存储结构的优缺点。 答：

顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。

4．试写出一个计算链表中结点个数的算法，其中指针ｐ指向该链表的第一个结点。 答：int linklist_num(linklist L,Lnode *p)

{ int n=0; While(p){n++;p=p->next;}

Return n:

8 7 6 5 4 3 2 1 … }

5．试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。

答：void Deletaz(Linklist L) { Lnode *p,*q,*r,*s; P=l->next;

while (p) {q=p;r=q->next;

while(r){if(r->data!=p->data){q=r;r=r->next};

else{s=r->next;q->next=s;free(r);r=s;}

} P=p->next; } }

6. 有一个线性表(a1,a2,...,an)，它存储在有附加表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为零。 答：int linklist_x(linklist L,datatype x)

H 10 15 18 15 10 ∧(a) 删除前 H 10 15 18 ∧(b) 删除后

{int i=0;Lnode *p;

P=L->next;

While(p&&p->dada!=x){i++;p=p->next;} If(!p)return 0; Else return I;

}

7．写一个算法将一单链表逆置。要求操作在原链表上进行。 答：void reverse (LinkList L) { p=L->next; L->next=NULL; while (p)

{ q=p->next; p->next=L->next; L->next=p; p=q; }

}

8．在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法。 答：void insert_x(Linklist L,Datatype x)

/*在递增有序的单链表L中插入值为x的元素，使得插入后L仍然有序*/ {Lnode *p,*q,*r; P=L;q=p->next;

While(q&&q->dada<=x) {p=q;q=q->next;}

R=(Lnode *)malloc(Lnode); r->dada=x; r->next=q; p->next=r;

}

9．写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点不存在，则插在表尾。

答: void Insert_LinkList( LinkList L, DataType a, DataType B)

{ /* 在值为a 的结点后插入值为B的结点，表中若无a则B接在表尾 */ LinkList p,q,s ;

s=( LinkList)malloc(sizeof(struct node)); s->data=B; s->next=NULL; q=L; p=L->next;

while( p!=NULL && p->data!=a ) { q=p; p=p->next; } if(p){s->next=p->next;p->next=s;} }

else{ s->next=q->next;q->next=s;}

10．试用循环链表为存储结构，写一个约瑟夫(Josephu)问题的算法。约瑟夫问题是：有N个人围成一圈，从第i个人开始从1报数，数到m时，此人就出列。下一个人重新从1开始报数，再数到m时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，N=5， i=1, m=3 时新的序列应为：3, 1, 5, 2, 4。 答：

typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ struct node *next; /* 指针域 */ }JOS;

void outs(JOS *h, int m) { int i; JOS *q=h, *p;

printf(―\\n ―);

while (q->next!=q)

{ for(i=1;inext;} /* 报数到第m个人 */ printf(―m‖,q->num); /* 输出第m个人的编号 */ p->next=q->next; free(q); /* 第m个人出列 */ q=p->next; }

printf(―m \\n‖,q->num); /* 输出最后一个结点的编号值 */ free(q);

} /* outs */

11. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。 答：void unit(Linklist A,Linklist B,Linklist C) {Lnode *p,*q,*r,*s;

P=A->next;q=>next;C=A;r=C; While(p&&q)

{if(p->dada<=q->dada){r=p;p=p->next;}

Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;}

}

If(!p)r->next=q;free(B) }

讨论小课堂 3

【参考内容】

1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。

2. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？

【答案】

1、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。 【答案】：

3、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。

4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之前。

? 【参考答案】： ? void trains(char *elem) ? {int i,k; ? k=0;

? for(i=0;i

? if(elem[i]==‘S’) //软席车厢S ? { push(); ? pop(); ? } ? else ? {push();

? k++}

? while(k>0){pop();k--;} ? }

5.对于一个具有N个单元（N>>2）的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2（T2>T1）个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。

? 【分析】

? 时刻t: 0 1 2 3 4 5 6 7 8 9 ? 个数： 1 1 2 1 2 2 3-2 2 3 2 ? 放取： + + - + + - + -

? 时刻t: 10 11 12 13 ? 个数： 3 3 4-3 …… ? 放取： + + - …… ?

? N=2

? 先放后取： 6时刻，放了4次，3个为溢出 ? 放取同时： 8时刻，放了5次，3个为溢出

如果同一时刻先放后取： int main( )

{ int y=1,i=0, n, m, front=0,rear=1; cin>>n; cin>>t1;cin>>t2; m=n+2; if (t1>=t2) cout<<\ else{

while((rear+1)%m!=front) { i++;

if (i%t1==0) {rear=(rear+1 )%m; y++; } if (i%t1==0&&(rear+1)%m==front) break; if (i%t2==0) {front=(front+1 )%m; } }

cout<

习题3

1.假定有编号为A、B、C、D的四辆列车，自右向左顺序开进一个栈式结构的站台，

如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开出站台的顺序有几种？写出每一种可能的序列。如果有n辆列车进行编组呢？如何编程？

注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许出栈后回退。

图3.16 火车编组栈

2.已知栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈以后栈的状态，然后再画出此时的栈顶元素出栈后的状态。

3.写出链表栈的取栈顶元素和置栈空的算法。

4.写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。 5.对于给定的十进制正整数N，转换成对应的八进制正整数。

（1）写出递归算法。 （2）写出非递归算法。

6.已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。 n?1? f(n)=??n*f(n/2)当n?0时当n?0时

7. 假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。

8.课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。

（1）试画出有２个元素Ａ、B的循环队列图，及将这2个元素出队后队列的状态图。 注：假设MAXSIZE=6，front=5，完成本题要求的图示。若erar=5，情况如何？ （2）试画出有２个元素C、D的链表队列图，及将这2个元素出队后链表队列的状态图。

9.对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。

10.对于一个具有n个单元(n>>2)的循环队列,若从进入第一个元素开始，每隔t1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2≥t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。

11.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。

12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i 的系数。图3.17是指数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。

讨论小课堂4

重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。

1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，… … 。编程统计其共有多少个整数，并输出这些数。

【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。 算法如下：

int CountInt（）

/* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/

｛int i=0，a[]； /* 整数存储到数组a，i记整数个数*/ char ch;

scanf(″%d″,&ch)；/* 从左到右读入字符串*/

while（ch!=?#‘） /*?#‘是字符串结束标记*/ if（（ch）>=48 && (ch)<=57）/* 是数字字符*/ ｛num=０； /*数初始化*/ while（（ch）>=48 && (ch)<=57 && ch!=?#‘）/* 拼数*/ ｛num=num＊10+?ch‘-?０‘； scanf(″%d″,&ch)；

｝

a[i]=num；i++；

if（ch!=?#‘）scanf(″%d″,&ch)；/* 若拼数中输入了?#‘，则不再输入*/ ｝while（ch！＝?#‘） /* 结束*/

Printf(‖共有%d‖,I,‖个整数，它们是：‖)； for（j=０；j

if（（j+1）％10==0）printf(―\\n‖);} /*每10个数输出在一行上*/ ｝/* 算法结束*/

假定字符串中的数均不超过32767，否则，需用长整型数组及变量。

2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。例如：若S=―abceebccadddddaaadd!‖， 则最长重复子串为―ddddd‖。位置是9。

【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。

算法如下：

int LongestString(char s[],int n)

/*串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。*/

{int index=0,max=0; /*index记最长的串在s串中的开始位置，max记其长度*/ int length=1,i=0,start=0; /*length记局部重复子串长度，i为字符数组下标*/ while(i

if(s[i]==s[i+1]) {i++; length++;} else /*上一个重复子串结束*/

{if(max

/*初始化下一重复子串的起始位置和长度*/

}

Printf(―最长重复子串的长度为:%d―;max;‖在串中的位置:%d‖;index);

return(max); }/*算法结束*/

算法中用i

算法的时间复杂度为O(n)，每个字符与其后继比较一次。

习题4

习题4

1．填空

（1）在计算机软件系统中，有两种处理字符串长度的方法：一种是采用 显式 ，第二种

是 隐式 。

（2）一个字符串相等的充要条件是 长度 和 对应字符都相等 。

（3）串是指 有限个字符组成 的序列；空串是指 长度 的串；空格串是指

一个或多个空格组成 的串。 （4）设s=―I︺AM︺A︺TEACHER‖,其长度是_14___。

（5）若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总

次数为 ○（m*n） 。

2．空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有何作用？ 答：空串时长度为0的字符串；空格串是一个或多个字符组成的字符串。字符串中的空格符充当界符的作用。空串在串的处理中可作为任意串的子串。

3．设计一算法，将两个字符串连接起来，要求不能利用strcat（）函数。

答：

Typedef struct {char *ch; /*串数组*/ int length; /*串长*/

}HString;

int StrConcat(HString *S, HString T) {

*/

free(S->ch);

S->ch=(char*)malloc(S->length+T.length); /* 为S分配新的空间*/ for(int i=0;i< S->length;i++)S->ch[i]=temp[i]; for(int j=0;j< T.length;j++)S->ch[i+j]=T.ch[j]; char *temp;temp=(char *)malloc(S->length); if(temp==NULL)return(0);

for(int i=0;ilength;i++)temp[i]=S->ch[i];

/* 先把串S放入临时串temp中

}//if

else Forest_Prim(G,k); /*对另外一个连通分量执行算法*/ }/*for*/

}/*Forest_Prim */

void Addto_Forest(CSTree &T,int i,int j)/*把边(i,j)添加到孩子兄弟链表表示的树T中*/ {

p=Locate(T,i); /*找到结点i对应的指针p,过程略*/ q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j;

if(!p) /*起始顶点不属于森林中已有的任何一棵树*/ {

p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i;

for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q;

} /*作为新树插入到最右侧*/

else if(!p->firstchild) /*双亲还没有孩子*/ p->firstchild=q; /*作为双亲的第一个孩子*/ else /*双亲已经有了孩子*/ {

for(r=p->firstchild;r->nextsib;r=r->nextsib);

r->nextsib=q; /*作为双亲最后一个孩子的兄弟*/ }

}/*Addto_Forest */ main()

{ ...

T=(CSTNode*)malloc(sizeof(CSTNode)); /*建立树根*/ T->data=1; Forest_Prim(G,1,T);

...

}/*main*/

分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得

到的,其时间复杂度为O(n^2).

11. 求出图7.27从顶点v1到其它各顶点之间的最短路径。绘制图表解题。 答:

dist path dist path dist path dist path dist path dist path V2 20 V1 20 V1 20 V1 20 V1 V3 5 V1 V4 ∞ V1 ∞ V1 V5 ∞ V1 ∞ V1 25 V6 25 V6 V6 ∞ V1 15 v3 S V1 V-S V2, v3,v4, v5, v6 shortpath v3 V1,v3 V2, v4,v5, v6 V6 19 V6 V1,v3, v6 v2, v4, v5 v4 V1,v3, v6,v4 V1,v3, v6,v4,v2 v2, v5 v5 v2 v5 25 V6 V1,v3, v6,v4,v2, v5

12. 写出图7.28的三种可能的拓朴排序结果。 答:

5,2,1,3,4,6,7,8 5,2,4,3,1,7,6,8 7,5,2,1,3,4,6,8

5 10 4 6 5 4 10 2 2 30 10 图7.27 1 20 1 5 2 3 8 7 4 3 5 4 图7.28 6

讨论小课堂8

[参考内容]

1．若二叉排序树中的一个结点存在两个孩子，那么它的中序后继结点是否有左孩子？它的中序前驱结点是否有右孩子？

【参考答案】：若p是给定的二叉排序树中的某个结点，且p有左、右孩子。按照中序遍历的思想，先中序遍历p的左子树，再访问根结点p，最后遍历p的右子树。左子树最后访问的结点x为p的前驱结点，x一定没有右子树，否者x不是左子树上中序遍历中最后访问的结点。因而，p的前驱结点x没有右孩子。同理，p的中序后继结点x没

有左孩子。

2．若将关键字1，2，3，┅，2k-1依次插入到一棵初始为空的AVL中，能证明结果树是完全平衡的吗？

【参考答案】：所谓“完全平衡”是指所有叶子结点处于树的同一层次上，并在该层是满的。

第一步，当k=1时，2-1=1，AVL树只有一个结点，它既是根又是叶子并处在第0层，根据二叉树性质，应具有20=1个结点。因此，满足完全平衡要求。

第二步，设k=n，插入关键码1，2，3，┅，2n-1到AVL树中，恰好每一层(层次号码是i=0，1，2，3，┅，n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k=n+1时，插入关键码为1，2，3，┅，2-1，2，┅，2-1，总共增加了从2n到2n+1-1的2n+1-1-2n+1=2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。

由上可的，能证明它是完全平衡的。

3．假设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树？AVL树有几种？完全二叉树有几种？请画出其中高度较小的6种。

【参考答案】：本题的含义是：给定中序序列1，2，3，4，有几种不同的二叉排序树，这是树的计数问题。设中序遍历序列中元素数为n，则二叉树的数目为1这里n=4，故有14种。

AVL树有4种。 完全二叉树有1种。

6种高度较小的二叉排序树如下所示。

A B B C A C A D B D D C C B D A D B A B C 1

nnn+1

(n?1)?C2n，

nD A C

习题8

1．设二叉排序树中记录关键字由1至1000的整数构成，现在要查找关键字为363的记录结点，下述关键字序列哪个不可能是在二叉排序树上查找到的序列？

(1){2，252，401，398，330，344，397，363}； (2){924，220，911，244，898，258，362，363}； (3){925，202，911，240，912，245，363}；

(4){2，399，387，219，266，382，381，278，363}。 【参考答案】：(3)

2．设有一记录集合，集合中各记录的关键字分别为：90，31，12，40，74，94，14，26，35，85，64，9，55，60。

(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。

(2)若对表中元素进行排序，构成有序表，求在等概率情况下对此有序表进行折半查找时，查找成功时的平均查找长度。 【参考答案】：

(1)

60 55 26 64 85 9 14 35 74 12 40 31 31 90

(2)折半查找判定树为

2 4 6 8 10 12 14 1 5 9 13 3 11 7

ASL=(1+2×2+3×4+4×7)/14=45/14

3．已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用折半查找90时，需进行多少次查找了确定成功；当查找47时，需要经过多少次确定查找成功；查找100时，需要经过多少次确定查找不成功。 【参考答案】：2、4、3

4．已知一组关键字序列为：（17，31，13，11，20，35，25，8，4，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。(湖南大学2003年考研题) 【参考答案】：

4 20 25 40 8 13 24 35 11 31 17

5．将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中(大小按照首字母在字母表中的先后次序)，请画出所得到的树T。然后画出删去for之后的二叉排序树T'，若再将for 插入T'中得到的二叉排序树T''是否与T相同?最后给出T\的先序、中序和后序序列。 【参考答案】：T\的先序序列是：do case class const while protected private if for int virtual public template

T\的中序序列是：case class const do for if int private protected public template virtual while

T\的后序序列是：const class case for int if private template public virtual protected

本文来源：https://www.bwwdw.com/article/5d1g.html