习题1 DS概述
一、单项选择题
1. 数据结构是指（ ）。
A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义
2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。
A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。
A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系
4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。
for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;
A.O(1)
B.O(n)
2 C.O(n)
D.O(n)
35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系
C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性
C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法
C.解决问题的有限运算序列 D.调度方法
（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性
C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性
7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。
A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ ）年。
A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。
A.正确 B.错误
C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ ）。
A.数据 B.数据元素 C.数据项 D.数据库
11 下面程序的时间复杂为（ ）
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}
234
(A) O(n) (B) O(n) (C) O(n) (D) O(n)
12设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构
13 数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 14 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。
(A) O(n) (B) O(nlog2n) (C) O(n) (D) O(n/2) 15 下列程序段的时间复杂度为（ ）。
for(i=0； i for(i=0； i i=0，s=0； while (s 1/21/32 (A) O(n) (B) O(n) (C) O(n) (D) O(n) 17 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。 2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。 3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。 4. 一个算法的效率可分为__________________效率和__________________效率。 5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。 6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。 7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。 8. 下面程序段的时间复杂度是__________________。 for(i=0;i A[i][j]=0; 23 9. 下面程序段的时间复杂度是__________________。 i=s=0; while(s 10. 下面程序段的时间复杂度是__________________。 s=0; for(i=0;i 11. 下面程序段的时间复杂度是__________________。 i=1; while(i<=n) i=i*3; 12. 衡量算法正确性的标准通常是____________________________________。 13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。 14 for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。 15通常从四个方面评价算法的质量：_________、_________、_________和_________。 16 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 数据的物理结构主要包括_____________和______________两种情况。顺序存储结构、链式存储结构 三、求下列程序段的时间复杂度。 1. x=0; for(i=1;i 2. x=0; for(i=1;i 3. int i,j,k; for(i=0;i for(k=0;k c[i][j]=a[i][k]*b[k][j] } 4. i=n-1; while((i>=0)&&A[i]!=k)) j--; return (i); 5. fact(n) { if(n<=1) return (1); else return (n*fact(n-1)); } 习题1 参考答案 DS概述 一、单项选择题 1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B 11.B 12B 13A 14A 15A 16A 17D 二、填空题 1. 线性结构，非线性结构 2. 集合，线性，树，图 3. 一对一，一对多或多对多 4. 时间，空间 5. 前趋，一，后继，多 6. 有多个 7. 一对一，一对多，多对多 8. O(n) 9. O(n) 10. O(n) 11. O(log3n) 12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13. 事后统计，事前估计 14 O(n) 15正确性 易读性 强壮性 高效率 15 O(n) 三、算法设计题 1. O(n) 2. O(n) 3. O(n) 4. O(n) 5. O(n) 22322习题2 顺序表和链表 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。 A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i A．n-i B．n-i+l C．n-i-1 D．i 8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行 A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是______。 A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种_______的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 11. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小 12. 在等概率情况下，顺序表的插入操作要移动______结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在______运算中，使用顺序表比链表好。 A．插入 B．删除 C．根据序号查找 D．根据元素值查找 14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 A．O(1) B．O(n) 2 C．O(n) D．O(log2n) 15 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 16 下面关于线性表的叙述错误的是（ ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 17 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 18 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 19 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。 (A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s； 20 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。 (A) 单向链表 (B) 单向循环链表 (C) 双向链表 (D) 双向循环链表 21 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。 (A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p； (C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q； 22 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 23建立一个长度为n的有序单链表的时间复杂度为（ ） 2 (A) O(n) (B) O(1) (C) O(n) (D) O(log2n) 1．线性表中的所有元素都有一个前驱元素和后继元素。（F ） 2．线性表的顺序存储结构比链式存储结构更好。（ F ） 顺序表查找指的是在顺序存储结构上进行查找。（ F ） 对链表进行插入和删除操作时不必移动链表中结点。( T ) 非空的双向循环链表中任何结点的前驱指针均不为空。（ T ） 二、填空题 1. 线性表是一种典型的_________结构。 2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。 3. 顺序表中逻辑上相邻的元素的物理位置________。 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。 5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。 6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。 7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。 8. 顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。 9. 线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。 10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。 11. 在单链表中设置头结点的作用是________。 12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。 13 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 14 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。 15 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。 16设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为： 1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t； 17设指针变量p指向单链表中结点A，则删除结点A的语句序列为： q=p->next；p->data=q->data；p->next=___________；feee(q)； 18下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。 typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) { for (i=1;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;____________;} } } 19 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删 除第i个位置上的数据元素需要移动表中_______个元素。 20设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。 21设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。 三、简答题 1. 描述以下三个概念的区别：头指针，头结点，表头结点。 2. 线性表的两种存储结构各有哪些优缺点？ 3. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变 化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？ 4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。 5. 在单循环链表中设置尾指针比设置头指针好吗？为什么? 6 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点 B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 7 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 四、算法设计题 1. 设计在无头结点的单链表中删除第i个结点的算法。 2. 在单链表上实现线性表的求表长ListLength(L)运算。 3. 设计将带表头的链表逆置算法。 4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。 5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。 6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。 8. 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 9 统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) 10 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 11 设计在单链表中删除值相同的多余结点的算法。 13设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 14 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 3 5 7 2 0 4 1 } 15设计判断单链表中元素是否是递增的算法。 五、阅读算法 1 LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）改程序的整体功能是什么？ （2） 说明语句S1的功能； （3） 说明语句组S2的功能； （4）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。 习题2参考答案 顺序表和链表 一、单项选择题 1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．A 16．D 17.A 18.A 19.D 20.D 21.B 22.C 23C 二、填空题 1．线性 2．n-i+1 3．相邻 4．前移，前，后 5．物理存储位置，链域的指针值 6．前趋，后继 7．顺序，链接 8．一定，不一定 9．线性，任何，栈顶，队尾，队头 10．单链表，双链表，非循环链表，循环链表 11．使空表和非空表统一；算法处理一致 12．O(1)，O(n) 13 s->left=p，p->right 14 p->next=s 15 head->rlink，p->llink 16 p->next，s->data 17 q->next 18 lklist，q=p 19 n+1-i，n-i 20 s->next=p->next; p->next=s 21 m-1 三、简答题 1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。 5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为 O(n)。 6 q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 7线性表为：（78，50，40，60，34，90） 四、算法设计题 1．算法思想为： （1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作； （2）当i=0时，删除第一个结点： （3）当０ delete(LinkList *q,int i) { //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0) printf(\ else if(i= =0) { s=q; q=q->next; free(s); } else { j=0; s=q; while((j j++; } if (s= =NULL) printf(\ delete\ else { p->next=s->next; free(s); } } } 2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下： int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L; while ( p->next!=NULL ) { p=p->next; len++; } return (len); } 3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前 趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下： void invert(LinkList *head) { //逆置head指针所指向的单循环链表 linklist *p, *q, *s; q=head; p=head->next; while (p!=head) //当表不为空时，逐个结点逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; } 4．定义类型LinkList如下： typedef struct node { int data; struct node *next,*prior; }LinkList; 此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下： insert (LinkList *head) { LinkList *p,*s,*q; p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL) { s=head; // s指向q结点的前趋结点 q=head->prior; //q指向由prior域构成的链表中待比较的结点 while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置 { s=q; q=q->prior; } s->prior=p; p->prior=q; //结点p插入到结点s和结点q之间 p=p->next; } } 5．算法描述如下： delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next; while((p!=NULL) && (p->data<=min)) { q=p; p=p->next; } while((p!=NULL) && (p->data } } 6．算法描述如下： delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next; while (p!=NULL) if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } } 8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下： int InsertDecreaseList( SqList *L, elemtype x ) { int i; if ( (*L).len>= maxlen) { printf(“overflow\ return(0); } for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); } 9. int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时i中的值即为x结点个数 return i; }//CountX 11 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构 表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 12设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 13设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 14 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 15设计判断单链表中元素是否是递增的算法。 int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 五、算法阅读 （1）该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为 新的开始结点，返回新链表的头指针。 （2）查询链表的尾结点 （3）将第一个结点链接到链表的尾部，作为新的尾结点 （4）返回的线性表为（a2,a3,?,an,a1） 习题3 栈和队列 一 单项选择题 1. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 3 设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 4. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列__________。 A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, A 5. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。 A．top不变 B．top=0 C．top-- D．top++ 6. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。 A．hs->next=s; B．s->next=hs; hs=s; C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next; 7. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。 A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 8. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。 A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front 9. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。 A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next 10．设输入序列是1、2、3、??、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 11 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要 入队列的结点X，则入队列的操作序列为（ ）。 (A) front->next=s；front=s； (B) s->next=rear；rear=s； (C) rear->next=s；rear=s； (D) s->next=front；front=s； 11 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 12．设输入序列是1、2、3、??、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元 素是（ C ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 13．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 二 填空题 1. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。 2. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_________。 3. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。 4不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。 5设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。 6设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。 7 设输入序列为1、2、3，则经过栈的作用后可以得到____5_______种不同的输出序列。 8不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___O(1)____。 9设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储_ m-1，(R-F+M)%M_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。 三 简答题 1. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。 2. 什么是队列的上溢现象？一般有几种解决方法，试简述之。 四 算法设计题 1. 假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法： （1）向循环链队列插入一个元素值为x的结点； （2）从循环链队列中删除一个结点。 五 程序阅读 1. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) { if (stack.top==m-1) printf(“overflow”); else {____________________;_________________;} } 习题3参考答案 栈和队列 一 单项选择题 1A 2C 3A 4C 5C 6B 7D 8C 二 填空题 1．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 2．2、3 O(1) 4 O(1) 5 top1+1=top2 6 F==R 三 简答题 1．共有14种可能的出栈序列，即为： ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA 2．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法： （1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。 四 算法设计题 1．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下： （1）插入（即入队）算法： insert(LinkList *rear, elemtype x) { //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p; p=(LinkList *)malloc(sizeof(LinkList)); if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p; rear->next=p; //链接成循环链表 } else //否则在队尾插入p结点 { p->next=rear->next; rear->next=p; rear=p; } 9A 10C 11C 12D } （2）删除（即出队）算法： delete(LinkList *rear) { //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf(\ if(rear->next= =rear) //队中只有一个结点 rear=NULL; else rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点 } 五 程序阅读 1. stack.top++，stack.s[stack.top]=x 习题4 串 一、单项选择题 1. 空串与空格字符组成的串的区别在于（ ）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ ）。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ ）是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ ）。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。 A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N” 6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。 A.2 B.3 C.4 D.5 7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。 A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。 A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1 9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 10．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE” (B) “DATA” (C) “ASTRUCTUR” (D) “DATASTRUCTURE” (A) 20 (B) 30 (C) 40 (D) 45 11 两个字符串相等的充要条件是（C）。 (A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等 (C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对 字符串的长度是指（C ）。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 二、填空题 1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。 2. 两个字符串相等的充要条件是_____________________和___________________。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。 4. 串是指___________________。 5. 空串是指___________________，空格串是指___________________。 三、算法设计题 1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m 2. 设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。 习题参考答案 串 一、单项选择题 1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D 二、填空题 1. 固定长度，设置长度指针 2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE” 4. 含n个字符的有限序列 （n≥0） 5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为： int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j; for(i=1;i<=m;i++) r[s+i]=r[i]; for(j=m+t-i;j<=s;j++) r[s-t+j]=r[j]; return (1); } //delete 2．算法思想为： （1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较； （2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。 设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。 LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s; while(ps!=NULL) { pt=t; while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL) ps=NULL; else { ps=ps->next; s=ps; } } return s; } //find 1. 设计在顺序存储结构上实现求子串算法。 void substring(char s[ ], long start, long count, char t[ ]) { long i,j,length=strlen(s); if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i 习题5 数组和广义表 一、单项选择题 1. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。 A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k 2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ ）。 A.520 B.522 C.524 D.518 3. 若数组A[0?m][0?n]按列优先顺序存储，则aij地址为（ ）。 A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i] C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1] 4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0?(n+1)n/2]中，则非零元素aij的地址为（ ）。（设每个元素占d个字节） (j?2)(j?1)+i-1]*d 2(j?2)(j?1)B. [(j-1)*n-+i]*d 2(j?2)(j?1)C．[(j-1)*n-+i+1]*d 2(j?2)(j?1)D．[(j-1)*n-+i-2]*d 2A. [(j-1)*n-5. 设有广义表D=(a,b,D)，其长度为（ ），深度为（ ）。 A.无穷大 B.3 C.2 D.5 6. 广义表A=（a），则表尾为（ ）。 A.a B.(( )) C.空表 D.(a) 7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（ ）。 A.x B.(a,B) C.(x,(a,B)) D.A 8. 下列广义表用图来表示时，分支结点最多的是（ ）。 A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B)) C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D) 9. 通常对数组进行的两种基本操作是（ ）。 A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引 10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。 A.80 B.100 C.240 D.270 11. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。 A.SA+141 B.SA+144 C.SA+222 D.SA+225 12. 稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。 A.正确 B.不正确 14. 一个广义表的表头总是一个（ ）。 A.广义表 B.元素 C.空表 D.元素或广义表 15. 一个广义表的表尾总是一个（ ）。 A.广义表 B.元素 C.空表 D.元素或广义表 16. 数组就是矩阵，矩阵就是数组，这种说法（ ）。 A.正确 B.错误 C.前句对，后句错 D.后句对 17 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 18 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 19 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55 二、填空题 1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。 2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。 3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。 4. 一个稀疏矩阵为 ? 2 0 ? ，则对应的三元组线性表为_____________。 0 0 5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。 6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。 7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。 8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。 9. 三维数组R[c1?d1,c2?d2,c3?d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3） 10. 数组A[1?10，-2?6，2?8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。 11设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_ i(i+1)/2+j-1_个数据元素。 三、判断题 1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ ） 2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（ ） 3. 以行为主序或以列为主序对于多维数组的存储没有影响。（ ） 4. 对于不同的特殊矩阵应该采用不同的存储方式。（ ） 5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（ ） 6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（ ） 7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（ ） 8. 距阵中的数据元素可以是不同的数据类型。（ ） 9. 矩阵中的行列数往往是不相等的。（ ） 10. 广义表的表头可以是广义表，也可以是单个元素。（ ） 11. 广义表的表尾一定是一个广义表。（ ） 12. 广义表的元素可以是子表，也可以是单元素。（ ） 13. 广义表不能递归定义。（ ） ?3000????00?15????0000?14. 广义表实际上是基本线性表的推广。（ ） 15. 广义表的组成元素可以是不同形式的元素。（ ） 16 画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 LS1^---->110e---->11^---->10a1^---->10b---->10c^0d^1 习题5 参考答案 数组和广义表 一、单项选择题 1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 17C 二、填空题 1. 线性结构，顺序结构，以行为主序，以列为主序 2. i×n+j个元素位置 3. 5，3 4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）） 5. n×(n+1)/2 6. e 7. 41 8. head(head(tail(Ls))) 9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1） 10. 913 三、判断题 1.× 2.√ 3.√ 4.√ 5.× 6.× 7.√ 8.× 9.× 10.√ 11.√ 13.× 15.√ 12.√ 14.√ 习题6 树 一、单项选择题 1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。 A. 4 B. 5 C. 6 D. 7 2. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。 A. 15 B. 16 C. 17 D. 47 3. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。 A. 3 B. 4 C. 5 D. 6 4. 在一棵二叉树上第4层的结点数最多为（ ）。 A. 2 B. 4 C. 6 D. 8 5. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ ）。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A. 24 B. 48 C. 72 D. 53 7. 线索二叉树是一种（ ）结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 8. 线索二叉树中，结点p没有左子树的充要条件是（ ）。 A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不对 9. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙 10. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。 A. 中序 B. 前序 C. 后序 D. 层次序 11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ ）存储结构。 A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序 12. 下面叙述正确的是（ ）。 A. 二叉树是特殊的树 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分 13. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 14. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ ）。 A. 1 B. 2 C. 3 D. 4 15. 根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（ ）。 A. 是完全二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树 16树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 17 二叉树的第k层的结点数最多为( ). kk-1 A． 2-1 B.2K+1 C.2K-1 D. 2 18 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 19设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 20 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 (D) 15，10，14，18，20，36，40，21 21 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 22 设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1 23 在二叉排序树中插入一个结点的时间复杂度为（ B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 24 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l 25 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，??，度数为m的结点数为Nm，则N0=（B ）。 (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm 26 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ D ）。 (A) 空或只有一个结点 (B) 高度等于其结点数 (C) 任一结点无左孩子 (D) 任一结点无右孩子 27 设某棵三叉树中有40个结点，则该三叉树的最小高度为（ B ）。 (A) 3 (B) 4 (C) 5 (D) 6 28深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1 29 设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B ）个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102 30 设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ D ）。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n) 31设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 32（ B ）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历 33 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。 (A) 8 (B) 7 (C) 6 (D) 5 34 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ C ）个度数为0的结点。 (A) 5 (B) 6 (C) 7 (D) 8 35 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ A ）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 36设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C ）个。 (A) 4 (B) 5 (C) 6 (D) 7 37 设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，??，Nm个度数为m的结点，则该树中共有（ D ）个叶子结点。 (A) (B) (C) (D) 38 二叉排序树中左子树上所有结点的值均（ A ）根结点的值。 (A) < (B) > (C) = (D) != 39 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。 (A) 129 (B) 219 (C) 189 (D) 229 40 设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ C ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 41 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。 (A) 20 (B) 256 (C) 512 (D) 1024 二、判断题 1. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。 （ ） 2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。 （ ） 3. 线索二叉树是一种逻辑结构。 （ ） 4. 哈夫曼树的总结点个数（多于1时）不能为偶数。 （ ） 5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 （ ） 6. 树的后序遍历与其对应的二叉树的后序遍历序列相同。 （ ） 7. 根据任意一种遍历序列即可唯一确定对应的二叉树。 （ ） 8. 满二叉树也是完全二叉树。 （ ） 9. 哈夫曼树一定是完全二叉树。 （ ） 10. 树的子树是无序的。 （ ） 11 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( T ) 12 中序遍历一棵二叉排序树可以得到一个有序的序列。( T ) 13 堆是完全二叉树，完全二叉树不一定是堆。（ T ） 14 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ T ） 15 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ T ） 16 完全二叉树中的叶子结点只可能在最后两层中出现。（ T ） 17先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（T ） 18由树转化成二叉树，该二叉树的右子树不一定为空。（ F ） 19满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ T ） 20设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（F ） 21设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（T ） 22中序遍历二叉排序树可以得到一个有序的序列。（ T ） 三、填空题 1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。 2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。 3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。 4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。 5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。 6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。 7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。 8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。 9. 由三个结点构成的二叉树，共有____种不同的形态。 10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。 11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。 12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。 13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。 14. 哈夫曼树是指________________________________________________的二叉树。 15. 空树是指________________________，最小的树是指_______________________。 16. 二叉树的链式存储结构有______________和_______________两种。 17. 三叉链表比二叉链表多一个指向______________的指针域。 18. 线索是指___________________________________________。 19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。 20. 本节中我们学习的树的存储结构有_____________、___________和___________。 21假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。 22后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。 23若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 24 中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。 25 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为 _________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。(N0-1，2N0+N1 ) 26 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存 储结构，则共有___________个空指针域。9，501 27 设哈夫曼树中共有n个结点，则该哈夫曼树中有___0_____个度数为1的结点。 28 ___中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 29 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点 编号为____________，右孩子结点的编号为___________。i/2，2i+1 30 设哈夫曼树中共有99个结点，则该树中有___50______个叶子结点；若采用二叉链表作为存储结构，则该树 中有__51___个空指针域。 k-1 31 深度为k的完全二叉树中最少有__2____个结点。 32 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____3________。 33 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为 __BDCA___。 34 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________， 中序遍历序列为___________，后序遍历序列为___________。(ABDECF，DBEAFC，DEBFCA) 35 设一棵完全二叉树有128个结点，则该完全二叉树的深度为__8__，有__64_个叶子结点。 36 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________， 第i列中所有非零元素个数之和等于顶点i的__________。(出度，入度) 36 设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_129_个结点数。 37 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_ p->lchild==0&&p->rchild==0_。 37 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有_14_个。 38 高度为h的完全二叉树中最少有________个结点，最多有________个结点。(2h-1，2h-1) 39 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据 这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为__6__。 40下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree; void bstinsert(bitree *&t,int k) { if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else__________________________; } t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k) 40 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__ CABD__。 42 完全二叉树中第5层上最少有_1__个结点，最多有__16_个结点。 43 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_____CBDA____。 44 设某棵完全二叉树中有100个结点，则该二叉树中有__50__个叶子结点。 45 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_ n(m-1)+1_个空指针域。 46 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;________________;}bitree; void createbitree(bitree *&bt) { scanf(“%c”,&ch); if(ch=='#') ___________;else { bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);} } struct node *rchild，bt=0，createbitree(bt->lchild) 四、应用题 1. 已知一棵树边的集合为{ （1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点g的双亲？ （4）哪些是结点g的祖先？ （5）哪些是结点g的孩子？ （6）哪些是结点e的孩子？ （7）哪些是结点e的兄弟？哪些是结点f的兄弟？ （8）结点b和n的层次号分别是什么？ （9）树的深度是多少？ （10）以结点c为根的子树深度是多少？ 2. 一棵度为2的树与一棵二叉树有何区别。 3. 试分别画出具有3个结点的树和二叉树的所有不同形态？ 4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。 5. 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题： （1）各层的结点数目是多少？ （2）编号为n的结点的父结点如果存在，编号是多少？ （3）编号为n的结点的第i个孩子结点如果存在，编号是多少？ （4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 6. 找出所有满足下列条件的二叉树： （1）它们在先序遍历和中序遍历时，得到的遍历序列相同； （2）它们在后序遍历和中序遍历时，得到的遍历序列相同； （3）它们在先序遍历和后序遍历时，得到的遍历序列相同； 7. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。 9. 给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。 A B D C E F H G I J 图5-14 K L M N O 10给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。 11设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。(树的链式存储结构略，二叉树略) 12 已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 AEFNULLDHFKJGBC 13 下图所示的森林： (1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树； ABD(a)CEFIGHJ(b)K 答：(1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树； ABCDEFIJKHG 14设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。(DEBCA) 15 设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 E={(1,5),(5,2),(5,3),(3,4)},W=10 五、算法填空（共8分） 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); }//if } true BST->left BST->right 五、算法设计题 1. 一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。 2. 给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。 3. 写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。 4. 给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息；若结点n有双亲，输出其双亲的值。 5 void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< 该算法的功能是：递归地后序遍历链式存储的二叉树。 6设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s) { if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} } 7 设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnode(bitree *bt,int &count) { if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 8设计判断两个二叉树是否相同的算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 9设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 10设计一个求结点x在二叉树中的双亲结点算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\ else if (i<=r) printf(\} 习题6 参考答案 树 一、单项选择题 1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A 16 C 17D 二、判断题 1.× 2.√ 3.× 4.√ 5.× 6.√ 7.√ 8.√ 9.× 10.× 三、填空题 1. 3，4，6，1，1，2，A，F，G 2. n+1 3. 完全，??log2(n?1)??，最大，n 4. 55 5. 中序 6. 2n，n-1，n+1 7. n2+1 8. 2k-1，2k-1，2k-1 9. 5 10. 2h-1 11. 单支树，完全二叉树 12. 2i，2i+1，i/2（或?i/2?） 13. 2n，n-1，n+1 14. 带权路径长度最小 15. 结点数为0，只有一个根结点的树 16. 二叉链表，三叉链表 17. 双亲结点 18. 指向结点前驱和后继信息的指针 19. 1，RChild 20. 孩子表示法，双亲表示法，长子兄弟表示法 20 9 3 3 22 -1 3 4 X * + 2 Y * 3 / - 23 2n n-1 n+1 四、应用题 1. 解答： 根据给定的边确定的树如图5-15所示。 其中根结点为a； 叶子结点有：d、m、n、j、k、f、l； c是结点g的双亲； a、c是结点g的祖先； j、k是结点g的孩子； m、n是结点e的子孙； e是结点d的兄弟； g、h是结点f的兄弟； 结点b和n的层次号分别是2和5； a b d e i m n 图5-15 c g j f k h i 树的深度为5。 2. 解答： 度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。 3. 解答： 略 4. 解答： 先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA 5. 解答： （1）第i层上的结点数目是mi-1。 （2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。 （3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。 （4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。 6. 解答： （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 7. 解答：后序序列：ACDBGJKIHFE 8. 解答：先序序列：ABCDGEIHFJK 9. 解答： 先根遍历：ABCDEFGHIJKLMNO 后根遍历：BDEFCAHJIGKNOML A B C H D E F J I M N O 森林转换成二叉树如图5-16所示。 10. 解答：构造而成的哈夫曼树如图5-17所示。 50 20 9 30 11 14 7 7 2 图5-17 图5-16 G K L 16 5 五、算法设计题 1. 解答：这个问题可以用递归算法，也可用非递归算法，下面给出的为非递归算法。假设该完全二叉树的结点以层次为序，按照从上到下，同层从左到右顺序编号，存放在一个一维数组R[1..n]中，且用一个有足够大容量为maxlen的顺序栈作辅助存储，算法描述如下： preorder (R) //先序遍历二叉树R int R[n]; { int root; SqStack *s; //s为一个指针栈，类型为seqstack，其中包含top域和数组data s->top= -1; //s栈置空 root=1; while ((root<=n) && (s->top>-1)) { while (root<=n) { printf(R[root]); } } s->top++; } if (s->top>-1) //栈非空访问，遍历右子树 { root=s->data[s->top]*2+1; s->top--; } s->data[s->top]=root; root=2*root; 2. 解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。 levelorder (BiTree *t) //按层次遍历二叉树t { BiTree *que[maxnum]; int rear,front; if (t!=NULL) { front=0; //置空队列 rear=1; que[1]=t; do { front=front%maxsize+1; //出队 t=que[front]; printf(t->data); if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild; } if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; } }while (rear= =front); //队列为空时结束 } } 3. 解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。 insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q; if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild; s->rtag=1; p->rchild=s; p->rtag=0; } else { q=p->rchild; while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点 q=q->lchild; q->lchild=p->rchild; s->rtag=0; p->rchild=s; } s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1; } 4. 解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。 parentjudge(t,n) BiTree *t; int n; { BiTree *que[maxnum]; int front,rear; BiTree *parent; parent=NULL; if (t) if (t->data= =n) printf(“no parent!”); //n是根结点，无双亲 else { front=0; //初始化队列 rear=1; que[1]=t; //根结点进队 do { front=front%maxsize+1; t=que[front]; if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear; printf(“parent”,t->data); } else { if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; } if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; que[rear]=t->lchild; } } }while(rear= =front); //队空时结束 } } if (parent = =NULL) printf(“结点不存在”); 习题7 图 一、单项选择题 1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( )。 A. s B. s-1 C. s+1 D. n 2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( )。 A. s B. s-1 C. s+1 D. 2s 3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。 A. n B. e C. n+e D. 2e 4. 在一个具有n个顶点的无向完全图中，所含的边数为( )。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 5. 在一个具有n个顶点的有向完全图中，所含的边数为( )。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。 A. k B. k+1 C. k+2 D. 2k 7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。 A. 0 B. 1 C. n D. n+1 8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。 A. k B. 1 C. k-1 D. k+1 9. 若要把n个顶点连接为一个连通图，则至少需要( )条边。 A. n B. n+1 C. n-1 D. 2n 10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。 A. n B. n?e C. e D. 2?e 11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。 A. n B. n?e C. e D. 2?e 12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。 A. n B. n?e C. e D. 2?e 13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为( )。 A. n B. 2n C. e D. 2e 14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。 A. 1 B. 2 C. 3 D. 4 15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为( )。 A. k1 B. k2 C. k1-k2 D. k1+k2 16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为( )。 A. k1 B. k2 C. k1-k2 D. k1+k2 17. 对于一个无向图，下面( )种说法是正确的。 A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和 C. 每个顶点的入度为0 D. 每个顶点的出度为0 18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。 A. 出边数 B. 入边数 C. 度数 D. 度数减1 19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( )。 A. A,B,C,F,D,E B. A,C,F,D,E,B C. A,B,D,C,F,E D. A,B,D,F,E,C 20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为( )。 A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,C,B,F,D,E 21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为( )。 A. 1,2,5,4,3 B. 1,2,3,4,5 C. 1,2,5,3,4 D. 1,4,3,2,5 22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为( )。 A. 1,2,3,4,5 B. 1,2,4,3,5 C. 1,2,4,5,3 D. 1,4,2,5,3 23. 由一个具有n个顶点的连通图生成的最小生成树中，具有( )条边。 A. n B. n-1 C. n+1 D. 2?n 24. 已知一个有向图的边集为{ A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 25 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 26 设某完全无向图中有n个顶点，则该完全无向图中有（A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 设某有向图中有n个顶点，则该有向图对应的邻接表中有（B ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 27设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（D ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 28 设某强连通图中有n个顶点，则该强连通图中至少有（ C ）条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 29设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D ）。 (A) n (B) e (C) 2n (D) 2e 30设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（C ）条有向边。 (A) n (B) n-1 (C) m (D) m-1 31设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ B ）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 32设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ B ）。 (A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和 33设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ A ）。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 34设某无向图有n个顶点，则该无向图的邻接表中有（B ）个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 35设无向图G中有n个顶点，则该无向图的最小生成树上有（ B ）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 36设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ A ）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 37 设完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 38设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑 排序序列的是（ A ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 二、填空题 1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。 2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{ 4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 5. 表示图的两种存储结构为__________和__________。 6. 在一个连通图中存在着________个连通分量。 7. 图中的一条路径长度为k，该路径所含的顶点数为________。 8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。 9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________?________。 10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。 11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。 12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。 13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。 14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。 15. 一个图的边集为{ 16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。 17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。 18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。 19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。 20. 假定一个有向图的边集为{ 21 AOV网是一种___________________的图。 22 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有 ________条边。 23 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和 ________个。 24已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是 ，BFS遍历的输出序列是 (1，3，4，5，2)，(1，3，2，4，5) 25设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=__ d/2_____。 26设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。出度，入度 27设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为e=d。 28设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。(1，4，3，2) 29设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是__ A[i][j]=1_。 30设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数__等于__第i列上非0元素的个数（填等于，大于或小于）。 31在图的邻接表中用顺序存储结构存储表头结点的优点是__可以随机访问到任一个顶点的简单链表___。 ．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列_(1，3，2，4，5)__。 32设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_n-1_。 33设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。(n(n-1)，n(n-1)/2) 34设连通图G中有n个顶点e条边，则对应的最小生成树上有__n-1_条边。 35设有向图中不存在有向边 37设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。 O(n2)， O(n+e) 38设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为__124653__。 判断题 1 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( F ) 2 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( F ) 3 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ） 4 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ T ） 5 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ T ） 6对连通图进行深度优先遍历可以访问到该图中的所有顶点。（T ） 7带权无向图的最小生成树是唯一的。（F ） 三、应用题 1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 0 1 7 2 8 (a) 图6-11 0 5 9 3 4 3 6 1 4 7 (b) 2 5 8 6 3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 图6-12 5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。 6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。 V1 65 50 V5 60 52 V4 V3 42 30 70 V6 (a) (b) 50 V2 40 45 V7 图6-13 7. 图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。 100 V0 30 10 V5 60 V4 20 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ (b) 带权邻接矩阵 图6-14 有向带权图及其邻接矩阵 10 V1 5 V2 50 V3 (a) 有向带权图 8. 图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。 v4 a3=2 a7=6 v2 a1=3 a4=1 v7 a8=8 a11=7 v1 a2=4 v5 a5=3 a9=4 v3 a6=5 a13=10 v8 a12=4 v1001 a14=1v11 a15=6 v6 a10=2 v9 图6-15 9请画出下图的邻接矩阵和邻接表。 10已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 11 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。(E={(1，3)，(1，2)，(3，5)，(5， 6)，(6，4)}) 四、算法设计题 1. 编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degree1(Graph & ga, int numb) 2. 编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。 int degree2(Graph & ga, int numb) 3. 编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。 int degree3(GraphL & gl, int numb) 4. 编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。 int degree4(GraphL & gl, int numb) 5 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j; glinklistnode *p; for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } 习题7 参考答案 图 一、单项选择题 1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. C 10. D 11. C 12. D 13. A 14. B 15. B 16. C 17. A 18. A 19. B 20. D 21. A 22. C 23. B 24. A 25A 二、填空题 1. 2 2. n(n-1)/2，n(n-1) 3. 2，4 4. n-1 5. 邻接矩阵，邻接表 6. 1 7. k+1 8. 3 9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n） 2 13.O（n），O（n+e） 14. acdeb，acedb （答案不唯一） 15. acfebd，acefbd （答案不唯一） 16. 深度，广度 17. n，n-1 18. 唯一 19. 唯一 20. aebdcf（答案不唯一） 21 e 2e 22 有向无回路 23 n(n-1)/2 n(n-1) 三、应用题 1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8 3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 4. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,1 5. 过程如图6-16所示 60 V1 V3 V1 V1 V3 V3 50 50 45 52 42 65 V4 V7 V2 V4 V4 V7 V7 V2 V2 50 30 40 V5 V6 V5 V5 V6 V6 70 (c) (b) (a) V1 V1 V3 V1 V3 V3 50 50 50 V2 V4 V7 V2 V4 V7 V4 V7 V2 50 30 50 40 40 40 V5 V6 V5 V6 V5 V6 (f) (d) (e) V1 V3 V1 V3 50 50 45 42 42 V2 V4 V7 V7 V4 V2 50 30 50 30 40 40 V5 V6 V5 V6 6. 求解过程如图6-17所示。 V1 V1 V3 V3 V4 V4 V7 V2 V7 V2 30 V5 V6 (a) V1 V3 45 42 V7 V4 V2 30 40 V5 V6 (d) 40 V5 30 (b) V1 V2 40 V5 V4 30 (c) V3 42 V7 V6 V6 50 V2 40 V1 V4 V5 30 (e) V3 42 45 V7 V6 42 V4 V7 V2 50 30 40 V5 V6 (f) 50 V1 V3 45 图6-17 7. 求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 V1 V2 ∞ 10 (v0,v2) V3 V4 ∞ 30 60 (v0,v2,v3) 30 (v0,v4) (v0,v4) V5 Vj S 100 (v0,v5) V2 100 (v0,v5) V4 90 (v0,v4,v5) V3 {v0,v2,v3,v4} 60 (v0,v4,v3,v5) V5 {v0,v2,v3,v4,v5} 50 (v0,v4,v3) i=2 ∞ i=3 ∞ i=4 ∞ i=5 ∞ 无 {v0,v2} {v0,v2,v4} 8. 求解过程如下： ①事件的最早发生时间ve[k]。 ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5 ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9 ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11 ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28 ②事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19 vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15 vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0 ③活动ai的最早开始时间e[i]和最晚开始时间l[i]。 活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22 ④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。 a9=4 v1 a2=4 v5 v3 a5=3 v11 v8 a13=10 a15=6 v9 9 邻接矩阵 邻接表如图11所示： 图6-18 v1001 a14=1