当前位置:首页 >> 工学 >>

2011福建专升本数据结构复习资料


2011 年计算机科学与技术、软件工程、数字媒体艺术(专升本) 年计算机科学与技术、软件工程、数字媒体艺术(专升本) 专业课考试<数据结构 复习纲要 专业课考试 数据结构>复习纲要 数据结构
第 1 章 引论................................................................................................................................... 3 1.1. 算法的性质(要素) ................................................................................................... 3 1.2. 时间复杂度、空间复杂度 ........................................................................................... 3 第 2 章 表....................................................................................................................................... 4 1.3. 表的顺序存储结构及其运算的实现。 ....................................................................... 4 1.4. 表的链接存储结构及其运算的实现 ........................................................................... 4 1.5. 单链表、循环链表、双向链表的特点。 ................................................................... 5 1.6. 单链表算法设计........................................................................................................... 5 第 3 章 栈....................................................................................................................................... 9 3.1. 栈的顺序实现及其运算 ............................................................................................... 9 3.2. 栈和队列的链接实现及其运算的实现。 ................................................................... 9 3.3. 栈的应用。................................................................................................................... 9 第 4 章 队列................................................................................................................................... 9 3.4. 队列的顺序实现(循环队列)及其运算的实现。 ................................................... 9 3.5. 队列的链接实现及其运算的实现。 ......................................................................... 10 3.6. 队列的应用................................................................................................................. 10 第 5 章 递归................................................................................................................................. 10 第 6 章 排序与选择..................................................................................................................... 10 6.1. 排序的基本概念(内外排序、稳定性、时间效率、空间效率) ......................... 10 6.2. 选择排序的方法(简单选择排序、堆排序) ......................................................... 10 6.3. 插入排序的方法(直接插入排序) ......................................................................... 11 6.4. 交换排序的方法(冒泡排序、快速排序) ............................................................. 12 第 7 章 树..................................................................................................................................... 14 7.1. 树的表示法。............................................................................................................. 14 7.2. 二叉树的定义和术语、性质。 ................................................................................. 14 7.3. 二叉树的存储结构,包括顺序存储实现和指针实现。 ......................................... 14 7.4. 二叉树的遍历算法及其应用。 ................................................................................. 14 第 8 章 集合................................................................................................................................. 18 8.1. 集合上的基本运算 ..................................................................................................... 18 第 9 章 符号表............................................................................................................................. 18 9.1. 散列函数构造方法以及处理冲突的办法。 ............................................................. 18 9.2. 线性再散列技术。 ..................................................................................................... 19 第 10 章 字典............................................................................................................................... 22 10.1. 二叉搜索树及其实现 ............................................................................................. 22 第 11 章 优先队列 ....................................................................................................................... 25 11.1. 堆的概念及其实现 ..................................................................................................... 25 11.2. 哈夫曼树及其应用 ..................................................................................................... 25 第 12 章 图................................................................................................................................... 28 12.1. 图的存储结构(邻接矩阵、邻接表) ................................................................. 28

1

12.2. 12.3. 12.4.

图的遍历方法(深度优先遍历、广度优先遍历) ............................................. 30 图的最小生成树的算法( prim 算法、 kruskal 算法) ................................ 31 。 图的单源最短路径的 dijkstra 算法。 ................................................................. 35

2

第 1 章 引论
2.1. 算法的性质(要素) 算法的性质(要素)
【例1-1】 计算机算法必须具备输入、输出和 B 等 5 个特性。 A) 可行性、可移植性和可扩充性 C) 确定性、有穷性和稳定性 【例1-2】 根据以下描述确定数据结构: B) 可行性、确定性和有穷性 D) 易读性、稳定性和安全性

D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }

2.2. 时间复杂度、空间复杂度 间复杂度、
【例1-3】 分析以下程序段的时间复杂度。
for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;

解:该程序段的时间复杂度为 O(m*n)。 【例1-4】 分析以下程序段的时间复杂度。
i=1; ① ②
f (n)

while(i<=n) i=2*i;

解:其中语句①的执行次数是 1,设语句②的执行次数为 f(n),则有: 2 得:T(n)=O( log 2 n )

≤ n。

【例1-5】 设语句 x++的时间是单位时间,则以下语句的时间复杂度为( B ) 。
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 )

3

3

第 2 章 表
2.3.表的顺序存储结构及其运算的实现。 表的顺序存储结构及其运算的实现。 表的顺序存储结构及其运算的实现
【例3-1】 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个 元素的地址是 ( B ) (A)110 (B)108 (C)100 (D)120 【例3-2】 表长为 n 的顺序存储的线性表,当在任何位置上插入一个元素的概率相等 时,插入一个元素所需移动元素的平均个数为( B ) A.n B. n/2 C. (n-1)/2 D. (n+1)/2 【例3-3】 在一个长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为 ( B ) 。 A.O(n) 2 C.O(n ) B.O(1) D.O(log2n)

2.4.表的链接存储结构及其运算的实现 表的链接存储结构及其运算的实现
单链表中的插入与删除 插入 第一种情况:在第一个结点前插入 newnode→link = first ; first = newnode; newnode first (插入前) 第二种情况:在链表中间插入 newnode→link = p→link; p→link = newnode; (插入后) newnode first

(插入前) (插入后) 第三种情况:在链表末尾插入 newnode→link = p→link; p→link = last = newnode;

4

(插入前)

(插入后)

2.5.单链表、循环链表、双向链表的特点。 单链表、循环链表、双向链表的特点。 单链表
【例3-4】 1. 线性表L在 情况下适用于使用链式结构实现。 B ) ( (A)需经常修改L中的结点值 (B)需不断对L进行删除插入 (C)L中含有大量的结点 (D)L中结点结构复杂 【例3-5】 2.在一个单链表中,若删除 p 所指结点的后续结点,则执行____。A (A)p—>next= p—>next—>next; (B)p= p—>next; p—>next= p—>next—>next; (C)p—>next= p—>next; (D)p= p—>next—>next; 【例3-6】 3.在一个单链表中,若 p 所指结点不是最后结点,在 p 之后插入 s 所指 结点,则执行。B (A)s—>next=p; p—>next=s; (B)s—>next=p—>next; p—>next=s; (C)s—>next=p—>next; p=s; (D)p—>next=s; s—>next=p; 【例3-7】 设单链表中结点的结构为(data,link) 。已知指针 q 所指点是指针 p 所指 结点的直接前驱,若在*q 与*p 之间插入结点*s,则应执行下列哪一个操 作?( B ) 。 A.s->link=p->link;p->link=s B.q->link=s;s->link=p C.p->link=s->link;s->link=p D.p->link=s;s->link=q 【例3-8】 4. 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是 d____。 A.p—>right=s; s—>left=p; p—>right—>left=s; s—>right=p—>right; B.p—>right=s; p—>right—>left=s; s—>left=p; s—>right=p—>right; C.s—>left=p; s—>right=p—>right; p—>right=s; p—>right—>left=s; D.s—>left=p; s—>right=p—>right; p—>right—>left=s; p—>right=s;

2.6.单链表算法设计 单链表算法设计 单链表算法
【例3-9】 1.设计算法,求带表头的单循环链表的表长。 解: int length(Linklist L) { int I;
5

listnode *p; I=0; P=L; while (p->next!=L){ p=p->next; I++; } return I; } 【例3-10】 2.已知单链表 L,写一算法,删除其重复结点。 算法思路:用指针 p 指向第一个数据结点,从它的后继结点开始到表的结束,找与其值相同 的结点并删除之;p 指向下一个;依此类推,p 指向最后结点时算法结束。算法如下: 解: void pur_LinkList(LinkList H) { LNode *p,*q,*r; p=H->next; /*p 指向第一个结点*/ if(p==NULL) return; while (p->next) {q=p; while (q->next) /* 从*p 的后继开始找重复结点*/ { if (q->next->data==p->data) { r=q->next; /*找到重复结点,用 r 指向,删除*r */ q->next=r->next; free(r); } /*if*/ else q=q->next; } /*while(q->next)*/ p=p->next; /*p 指向下一个,继续*/ } /*while(p->next)*/ } 该算法的时间性能为 O(n2)。 【例3-11】 4.写一算法,将一带有头结点的单链表就地逆置,即要求逆置在原链表 上进行,不允许重新构造新链表。 25 ∧ 29 ∧ (a) (b)

L L

29 25


76 45

18 18

45 76

单链表的倒置

函数原型如下: void LinkList_reverse(LinkList &L); 答:void LinkList_reverse(LinkList &L)
6

{ LinkList p,q,s; 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; } q->next=p;s->next=q;L->next=s; } 【例3-12】 5.写一算法,将带有头结点的非空单链表中数据域值最小的那个结点移 到链表的最前面。要求:不得额外申请新的链结点。函数原型如下: void delinsert(LinkList &L); 答:void delinsert(LinkList &L) { p=L->next; //p 是链表的工作指针 pre=L; //pre 指向链表中数据域最小值结点的前驱 q=p; //q 指向数据域最小值结点,初始假定是第一结点 while(p->next!=NULL) { if(p->next->data<q->data) //找到新的最小值结点 { pre=p; q=p->next; } p=p->next; } if(q!=L->next) //若最小值是第一元素结点,则不需再操作 { pre->next=q->next; //将最小值结点从链表上摘下 q->next=L->next; //将 q 结点插到链表最前面 L->next=q; } } 【例3-13】 【例 2-2】写一算法实现单链表的逆置。 解:假设单链表的表头指针用 head 表示,其类型为上面定义的 LinkList,并且单链表 不带头结点。 逆置后原来的最后一个结点成为第一个结点, 于是从第一个结点开始逐个修改 每个结点的指针域进行逆置,且刚被逆置的结点总是新链表的第一个结点,故令 head 指向 它(如图 2-1 所示) 。具体算法描述如下: head
(a)单链表初始状态





head


head

q

q

p …

(b)第三个结点逆置 图 2-1 单链表逆置示意图

7

void {

contray(LinkList *head)

//将 head 单链表中所有结点按相反次序链接 LinkList *p, *q; p=head; //p 指向未被逆序的第一个结点,初始时指向原表头结点

head=NULL; while(p!=NULL) { q=p; //q 指向将被逆序链接的结点

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

【例3-14】 试设计实现删除单链表中值相同的多余结点的算法。 解:该例可以这样考虑,先取开始结点的值,将它与其后的所有结点值一一比较,发现 相同的就删除掉,然后再取第二结点的值,重复上述过程直到最后一个结点。 设单链表(其类型为 LinkList)的头指针 head 指向头结点,则可按下列步骤执行: 首先,用一个指针 p 指向单链表中第一个表结点,然后用另一个指针 q 查找链表中其 余结点元素,由于是单链表,故结束条件为 p= =NULL,同时让指针 s 指向 q 所指结点的前 趋结点,当查找到结点具有 q->data= =p->data 时删除 q 所指的结点,然后再修改 q,直到 q 为空;然后使 p 指针后移(即 p=p->next) ,重复进行,直到 p 为空时为止。算法描述如下:
del(LinkList *head) { //删除单链表中值相同的多余结点 LinkList *p, *s, *q; p=head->next; while(p!=NULL && p->next!=NULL) { s=p; //s 指向要删除结点的前趋

q=p->next; while (q!=NULL) { if (q->data= =p->data)} { s->next=q->next; free(q); q=s->next; } else { s=q; q=q->next; } } p=p->next; } 8 //查找值相同的结点并删除

}

第 3 章 栈
3.1.栈的顺序实现及其运算 栈的顺序实现及其运算
【例3-15】 1.判定一个栈 ST(最多元素为 m0)为空的条件是( B ) A.ST->top<>0 B.ST->top=0 C.ST->top<>m0 D.ST->top=m0 【例3-16】 2.设一个栈的入栈序列是 ABCD,则借助于一个栈所得到的出栈序列不 可能是( ) 。 A. ABCD B. DCBA C. ACDB D. DABC

3.2.栈和队列的链接实现及其运算的实现。 栈和队列的链接实现及其运算的实现。 栈和队列的链接实现及其运算的实现

3.3.栈的应用。 栈的应用。 栈的应用
【例3-17】 1.设一个栈的入栈序列是 ABCD,则借助于一个栈所得到的出栈序列不 可能是( ) 。 A)ABCD B)DCBA C)ACDB D)DABC 【例3-18】 2.设栈最大长度为 3,入栈序列为 1、2、3、4、5、6,则不可能的出栈 序列是( ) 。 A)1、2、3、4、5、6 C)3、4、2、1、5、6 B)2、1、3、4、5、6 D)4、3、2、1、5、6

第 4 章 队列

?考点
3.4.队列的顺序实现(循环队列)及其运算的实现。 队列的顺序实现(循环队列)及其运算的实现。 队列的顺序实现
【例3-19】 1.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位 置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元 素的公式为( D ) (A)r-f; (B) (n+f-r)% n; (C)n+r-f; (D) (n+r-f)% n 【例3-20】 2.判定一个队列 QU(最多元素为 m0)为满队列的条件是( A ) A.QU->rear - QU->front = = m0 C.QU->front = = QU->rear B.QU->rear - QU->front -1= = m0 D.QU->front = = QU->rear+1

9

3.5.队列的链接实现及其运算的实现。 队列的链接实现及其运算的实现。 队列的链接实现及其运算的实现

3.6.队列的应用 队列的应用
【例3-21】 若循环队列以数组 Q[0..m-1]作为其存储结构, 变量 rear 表示循环队列中的 队尾元素的实际位置,其移动按 rear=(rear+1) Mod m 进行,变量 length 表示当前循环队列中的元素个数,则循环队列的队首元素的实际位置是 ( C ) A.rear-length B.(rear-length+m) Mod m C.(1+rear+m-length) Mod m D.M-length

第 5 章 递归
递归的概念与应用 1. 数学函数 F( n ) 的递归定义如下: 1 当 n<=4 时 F(n)= 5*F( n – 2 ) + 3 当 n>4 时 试用 C 语言写出计算 F(n)之值的递归函数 F ( );并写出 F(5)的值。

第 6 章 排序与选择
6.1.排序的基本概念(内外排序、稳定性、时间效率、空间效率) 排序的基本概念(内外排序、稳定性、时间效率、空间效率) 排序的基本概念
【例3-22】 8.若一组记录的排序码为(46, 79, 56, 38, 40, 84) ,则利用快速排序的方 法,以第一个记录为基准得到的一次划分结果为( C ) A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46 , 79, 56, 84 C. 40, 38,46, 56, 79, 84 D. 40, 38, 46, 84, 56, 79 【例3-23】 2. 在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入 排序时,当把第 7 个记录 60 插入到有序表时,为寻找插入位置至少需比 较 6 次。

6.2.选择排序的方法(简单选择排序、堆排序) 选择排序的方法(简单选择排序、堆排序) 选择排序的方法
【例3-24】 12.若一组记录的排序码为(46, 79, 56, 38, 40, 84) ,则利用堆排序的方法 建立的初始堆为( B ) A. 79, 46, 56, 38, 40, 84 B. 84, 79, 56, 38, 40, 46
10

C. 84, 79, 56, 46, 40, 38

D. 84, 56, 79, 40, 46, 38

6.3.插入排序的方法(直接插入排序) 插入排序的方法(直接插入排序) 插入排序的方法
直接插入排序是稳定排序。 【例3-25】 【例 8-1】已知关键字序列(12,77,21,65,38,7,38,53) ,给出采 用直接插入排序方法按关键字递增序排列时的每一趟结果。 解: 初始 12 1 趟 12 2 趟 12 3 趟 12 4 趟 12 5趟 7 6趟 7 7趟 7 表示有序区) 77 77 21 21 21 12 12 12 21 21 77 65 38 21 21 21 65 65 65 77 65 38 38 38 38 38 38 38 77 65 38 38 7 7 7 7 7 77 65 53 38 38 38 38 38 38 77 65 53 53 53 53 53 53 53 77



【例3-26】 1.写出对线性表(65,15,48,6,34,97,1,26)进行直接插入排序的 每一趟结果。 第一趟:15 65(48 6 34 97 1 26) 第二趟:15 48 65(6 34 97 1 26) 第三趟:6 15 48 65(34 97 1 26) 第四趟:6 15 34 48 65(97 1 26) 第五趟:6 15 34 48 65 97(1 26) 第六趟:1 6 15 34 48 65 97(26) 第七趟:1 6 15 26 34 48 65 97 【例3-27】 2.写出对线性表(37,15,98,25,10,47,83,32)进行冒泡排序的每 一趟结果。 第一趟:15 37 25 10 47 83 32 98 第二趟:15 25 10 37 47 32 83 98 第三趟:15 10 25 37 32 47 83 98 第四趟:10 15 25 32 37 47 83 98 第五趟:10 15 25 32 37 47 83 98 【例3-28】 3.写出对线性表(69,45,8,16,74,27,1,29)进行简单选择排序的 每一趟结果。 第一趟:1(45 8 16 74 27 69 第二趟:1 8(45 16 74 27 69 第三趟:1 8 16(45 74 27 69 第四趟:1 8 16 27(74 45 69 第五趟:1 8 16 27 29(45 69 第六趟:1 8 16 27 29 45(69 29) 29) 29) 29) 74) 74)

11

第七趟:1 8 16 27 29 45 69 74

6.4.交换排序的方法(冒泡排序、快速排序) 交换排序的方法(冒泡排序、快速排序) 交换排序的方法
【例3-29】 【例 8-3】已知序列(17,18,60,40,7,32,73,65,85) ,请给出采 用冒泡排序法对该序列作升序排序时的每一趟的结果。 解: 初始 1 趟 2 趟 17 17 17 18 18 18 60 40 7 40 7 32 7 32 40 32 60 60 73 65 65 65 73 73 85 85 85 ( 表示有序区)

3趟 17 7 18 32 40 60 65 73 85

4趟 7 17 18 32 40 60 65 73 85

5趟 7 17 18 32 40 60 65 73 85

【例3-30】 27、给定一个关键字序列{24,19,32,43,38,6,13,22} ,请写出快 速排序第一趟的结果;堆排序时所建的初始堆;然后回答上述两种排序方 法中哪一种方法使用的辅助空间最小,在最坏情况下哪种方法的时间复杂 度最差? 快速排序的第一趟结果为{22,19,13,6,24,38,43,12} ;堆排序时所建立的初始大顶堆如所图所 示:

两种排序方法所需辅助空间:堆是 O(1),快速排序是 O(logn),可见堆排序所需辅助空间较 少;在最坏情况下两种排序方法所需时间:堆是 O(nlogn),快速排序是 O(n2),所以,可见 快速排序时间复杂度最差。 注意:快速排序的平均时排序速度最快,但在最坏情况下不一定比其他排序方 法快。 【例3-31】 【例 8-4】已知关键字序列(38,12,21,77,65,7,38,53)给出采用 快速排序方法按关键字增序排序时的第一趟块排过程,并举出一个反例说 明快速排序是不稳定排序。 解:(1)
12

初始

38 12 21 77 65 ↑ low

7 38 53 ↑ high

第一次交换 从 high 开始比较,得到的结果: 7 12 21 77 65 □ 38 53 ↑ ↑ low high 从 low 开始比较,得到的结果: 7 12 21 □ 65 77 38 53 ↑ ↑ low high 第二次交换 从 high 开始比较,得到的结果: 7 12 21 □ 65 77 38 53 ↑↑ low high low=high,所以第一趟快速排序的结果为: 7 12 21 38 65 77 38 53 (2)关键字序列(2,2,1)可以作为一个反例。取第一个关键字作为支点,在一趟快排之 ,由于 2 已在排序后的最终位置,2 在 2 划分出的前一部分子表中, 后的结果是(1,2,2) 所以 2 不可能再出现在 2 之后, 即不可能与原始序列中两者的顺序一致。 此反例说明快速排 序不是稳定排序。 【例3-32】 (例 12—32) 已知序列{25,18,60,40,7,21,32,73,68},请给出 分别采用冒泡排序方法、直接选择排序方法和快速排序方法对该序列做升 序排列时的每一趟结果。 解析:(1)采用冒泡排序方法排序的各趟结果如下:(加框为每次冒出元素) 解析 初始序列:25, 18, 60, 40, 7, 21, 32, 73, 68 7 第——趟:□, 25, 18, 60, 40, 21, 32, 68, 73 第二趟: 7, 18, 25, 21, 60, 40, 32, 68, 73 □ 21 第三趟: 7, 18, □, 25, 32, 60, 40, 68, 73 第四趟: 7, 18, 21, 25, 32, 40, 60, 68, 73 □ 第五趟: 7, 18, 21, 25, 32, 40, 60, 68, 73 第五趟无元素交换,排序结束。 (2)采用直接选择排序方法排序的各趟结果如下:(加框为每次选出元素) 7 初始序列:25, 18, 60, 40, □, 21, 32, 73, 68 18 第——趟:[7] □, 60, 40, 25, 2l, 32, 73, 68 21 第二趟: [7, 18] 60, 40, 25, □, 32, 73, 68 第三趟: [7, 18, 21] 40, 25, 60, 32, 73, 68 □ 第四趟: [7, 18, 21, 25] 40, 60, 32, 73, 68 □ 第五趟: [7, 18, 21, 25, 32] 60, 40, 73, 68 □ 60, 73, 68 第六趟: [7, 18, 21, 25, 32, 40] □ 第七趟: [7, 18, 21, 25, 32, 40, 60] 73, 68 □
13

第八趟: [7, 18, 21, 25, 32, 40, 60, 68] 73 结束: 7, 18, 21, 25, 32, 40, 60, 68, 73 (3)采用快速排序方法排序的各趟结果如下: 初始序列:25, 18, 60, 40, 7, 21, 32, 73, 68 第一趟: [21 18 7] 25 [40 60 32 73 68] 第二趟: [7 18] 21 25 [32] 40 [60 73 68] 第三趟: 7 [18] 21 25 32 40 60 [73 68] 第四趟: 7 18 21 25 32 40 60 [68] 73 结束: 7 18 21 25 32 40 60 68 73

第 7 章 树
7.1.树的表示法。 树的表示法。 树的表示法
【例3-33】 1. 一棵二叉树的结点数据采用顺序存储结构,存储于数组 t 中,如下图 所示,则该二叉树的链接表示形式为____。

e

a

f

d

g

c

j

l

h

b

7.2.二叉树的定义和术语、性质。 二叉树的定义和术语、性质。 二叉树的定义和术语
【例3-34】 1.一棵深度为 6 的满二叉树有 n1+n2=0+ n2= n0-1=31 26-1 =32 个叶子。 个分支结点和

7.3.二叉树的存储结构,包括顺序存储实现和指针实现。 二叉树的存储结构,包括顺序存储实现和指针实现。 二叉树的存储结构

7.4.二叉树的遍历算法及其应用。 二叉树的遍历算法及其应用。 二叉树的遍历算法及其应用
【例3-35】 1.给定二叉树的两种遍历序列,分别是:前序遍历序列:D,A,C,E,B, H,F,G,I; 中序遍历序列:D,C,B,E,H,A,G,I,F,试画出 二叉树 B, 并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉
14

树 B 的思想方法。 的左、右子树。 解:方法是:由前序先确定 root,由中序可确定 root 的左、右子树。然后由其左子树的元 方法是: , 素集合和右子树的集合对应前序遍历序列中的元素集合, 的左右孩子。 素集合和右子树的集合对应前序遍历序列中的元素集合,可继续确定 root 的左右孩子。将 他们分别作为新的 root,不断递归,则所有元素都将被唯一确定,问题得解。 ,不断递归,则所有元素都将被唯一确定,问题得解。 D A C E G F

B H I 【例3-36】 一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则 后序遍历结果为( A ) A. CBEFDA B. FEDCBA C. CBEDFA D. 不确定 【例3-37】 某二叉树的后序遍历序列为 dabec,中序遍历序列为 debac,则前序遍历序 列为(D) 。 A.acbed B.decab C.deabc D.cedba 【例3-38】 具有 10 个叶子结点的二叉树中有( B)个度为 2 的结点。 A. 8 B. 9 C. 10 D. 11 【例3-39】 5.已知二叉树中的结点类型用 BinTreeNode 表示,被定义为: struct BinTreeNode{ char data; BinTreeNode *leftChild,*rightChild; }; 其中 data 为结点值域;leftChild 和 rightChild 分别为指向左、右孩子结点的指针域,根 据下面函数声明编写出求一棵二叉树高度的算法,该高度由函数返回。参数 BT 初始指向这 棵二叉树的根点。 int BtreeHeight(BinTreeNode *BT) ; 答:算法如下 int BtreeHeight(BinTreeNode * BT) { int h1,h2,h; if(BT==NULL)h=0; else{ h1 = BTreeHeight(BT->leftChild) ; h2 = BTreeHeight(BT->rightChild) ; if(hl>h2)h=h1+1; else h=h2+1; } return h; } 【例3-40】 6、一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示 出来。试求出空格处的内容,并画出该二叉树。
15

先序序列: B F ICEH G 中序序列:D KFIA EJC 后序序列: K FBHJ G A 在先序序列空格中依次填 ADKJ,中序中依次填 BHG,后序中依次填 DIEC。 【例3-41】 7、设有序列:w={23,24,27,80,28},试给出: (1)二叉排序树; (2)哈夫曼树; (1)二叉排序树如下图所示:

(2)哈夫曼树如下图所示:

【例3-42】 32、已知一棵二叉树的先序序列与中序序列分别如下,试画出此二叉树。 先序序列:ABCDEFGHIJ 中序序列:CBEDAGHFJI 先由先序序列的第一个结点确定二叉树的根结点, 再由根结点在中序序列中左侧部分为左子 树结点, 在右侧部分为右子树结点, 再由先序序列的第一个结点确定根结点的左右孩子结点, 由类似的方法可确定其他结点,如下图所示。

【例3-43】 7. 假 设 一 棵 二 叉 树 的 先 序 序 列 为 EBADCFHGIKJ , 中 序 序 列 为 ABCDEFGHIJK,请写出该二叉树的后序遍历序列。 【例3-44】 8. 假 设 一 棵 二 叉 树 的 后 序 序 列 为 DCEGBFHKJIA , 中 序 序 列 为 DCBGEAHFIJK,请写出该二叉树的后序遍历序列。 【例3-45】 【例 5-11】将图 5-7 所示的树转换为二叉树。 A B F K L C G M
图 5-7

D H

E I J

16

解:第一步,加线。第二步,抹线。第三步,旋转。过程如图 5-8 所示。 A B F K L C G M
加线

A D H E I J K B F L C G M
抹线

D H

E I J

图 5-8(a) 第一步

图 5-8(b) 第二步

A B C F K L M
图 5-8(c) 第三步

D G H I J
旋转

E

【例3-46】 【例 5-12】将如图 5-9 所示的二叉树转换为树。 A B C E I F J
图 5-9

D H

解: 第一步,加线。第二步,抹线。第三步,调整。过程如图 5-10 所示。

A B C E I
第一步

A B B H J
第二步 图 5-10

A D J H

D F J H E

C F I

D C E

F I

第三步

17

【例3-47】 【例 5-13】将如图 5-11 所示的森林转换成二叉树。

A B

C

D E F G
图 5-11

H I J K L

解: 步骤略,结果如图 5-12 所示。 A B C D E F G J K
图 5-12

H I L

第 8 章 集合
8.1.集合上的基本运算 集合上的基本运算

第 9 章 符号表
9.1.散列函数构造方法以及处理冲突的办法。 散列函数构造方法以及处理冲突的办法。 散列函数构造方法以及处理冲突的办法
【例3-48】 1.已知一组关键字为(19,14,23,1,68,20,84,27,55,11,10, 79) ,哈希函数:H(key)=key MOD 13,哈希地址空间为 0~12,请构造用 链地址法处理冲突的哈希表,并求平均查找长度。 【例3-49】 2.已知哈希表地址空间是 0..8,哈希函数是 H(k)=k%7,采用线性探测再 散列处理冲突,将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表 中,列出插入时的比较次数,并求出在等概率下的平均查找长度。 【例3-50】 23、已知一组关键字为(19,14,23,1,68,20,84,27,55,11,10,79) ,哈希函数: H(key)=key MOD 13,哈希地址空间为 0~12,请构造用链地址法处理冲突 的哈希表,并求平均查找长度。 用链地址法处理冲突的哈希表如下图所示:

18

ASL=

1 (1*6+2*4+3*1+4*1)=1.75 12

9.2.线性再散列技术。 线性再散列技术。 线性再散列技术
【例3-51】 1.使用散列函数 hashf(x)=x MOD 11,把一个整数值转换成散列表下标, 现要把数据 1、13、12、34、38、33、27、22 插入到散列表中。 (1)使用线性探查再散列法来构造散列表并同时列出每个数据的比较次数。 (2)使用链地址法来构造散列表。 【例3-52】 1.设散列表的长度为 13,散列函数为 H(K)=K%13,给定的关键字序列为: 19,14,23,01,68,20,84,27,55,11,10,79。试画出用线性探测 再散列解决冲突时所构成的散列表。并求等概率情况下这两种方法查找成 功和查找不成功时的平均查找长度。 答: 线性探测再散列的散列表: 0 1 2 3 4 5 14 1 1 2 68 1 27 4 55 3

6 19 1

7 20 1

8 84 3 9

9 79

10 23 1

11 11 1

12 10 3

查找成功的平均长度为 ASL=1/12(1*6+2*1+3*3+4*1+9)=2.5 查找不成功的平均长度为 ASL=1/13(1+2+3+4…….+13)=7 【例3-53】 8、有关键字序列{7,23,6,9,17,19,21,22,5},Hash 函数为 H(key)=key % 5, 采用链地址法处理冲突,试构造哈希表。 哈希表如下图所示:

【例3-54】 14、已知哈希表地址空间为 0..8,哈希函数为 H(key)=key%7,采用线性探 测再散列处理冲突,将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希 表中,列出插入时的比较次数,并求出在等概率下的平均查找长度。 哈希表及查找各关键字要比较的次数如下所示:

19

A SL= (4×1+1×2+1×4+2×5)=2.5 【例3-55】 【例 7-3】关键字集为(47,7,29,11,16,92,22,8,3) ,哈希表表 长为 11。H(key)= key MOD 11,用线性探测法处理冲突。 解:建表如下: 0 11 1 22 △ 2 3 47 4 92 5 16 6 3 ▲ 7 7 8 29 △ 9 8 △ 10
1 8

分析:47、7、11、16、92 均是由哈希函数得到的没有冲突的哈希地址而直接存入的。 H(29)= 7,哈希地址上冲突,需寻找下一个空的哈希地址: 11 = 8 ,哈希地址 8 为空,将 29 存入。另外,22、8 由 Hi =(H(29)+1) MOD 同样在哈希地址上有冲突,也是由 Hi 找到空的哈希地址的。 而 H(3)= 3,哈希地址上冲突,由:H1=(H(3)+1)MOD 11 = 4,仍然冲突。 H2=(H(3)+2)MOD 11 = 5,仍然冲突。H3=(H(3)+3)MOD 11 = 6,找到空的哈 希地址,存入。 【例3-56】 【例 7-4】关键字序列为 (47,7,29,11,16,92,22,8,3,50,37, 89,94,21) ,哈希函数为:Hash(key)=key mod 11,用拉链表处理冲突。 解:建表如下: 0 1 2 ^ 3 4 5 6 7 8 9 ^ 10 11 89 22 ^ ^

47 92 16 50 7 8 10 ^ ^

3 37

^ ^

29 ^ ^

^

【例3-57】 【例 7-5】设有一组关键字(19,01,23,14,55,20,84,27,68,11, 10,77) ,采用哈希函数:H(key)= key % 13,若用开放定址法的线性探 测法解决冲突,试在 0~13 的哈希地址空间中对该关键字序列构造哈希表 并求其成功查找时的 ASL。 解:依题意,m=13,线性探测法的下一个地址计算公式为:
20

di = H(key) di+1 = (di+1)% m ;i=1,2,… 其计算函数如下: H(19)= 19 % 13 = 6 H(01)= 01 % 13 = 1 H(23)= 23 % 13 = 10 H(14)= 14 % 13 = 1 (冲突) H(14)=(1+1)% 14 = 2 H(55)= 55 % 13 = 3 H(20)= 20 % 13 = 7 H(84)= 84 % 13 = 6 (冲突) H(84)=(6+1)% 14 = 7 (仍冲突) H(84)=(7+1)% 14 = 8 H(27)= 27 % 13 = 1 (冲突) H(27)=(1+1)% 14 = 2 (仍冲突) H(27)=(2+1)% 14 = 3 (仍冲突) H(27)=(3+1)% 14 = 4 H(68)= 68 % 13 = 3 (冲突) H(68)=(3+1)% 14 = 4 (仍冲突) H(68)=(4+1)% 14 = 5 H(11)= 11 % 13 = 11 H(10)= 10 % 13 = 10 (冲突) H(10)=(10+1)% 14 = 11 (仍冲突) H(10)=(11+1)% 14 = 12 H(77)= 77 % 13 = 12 (冲突) H(77)=(12+1)% 14 = 13 哈希表如下:
哈希地址 关键字 比较次数 0 1 1 1 2 14 2 3 55 1 4 27 4 5 68 3 6 19 1 7 20 1 8 84 3 9 10 23 1 11 11 1 12 10 3 13 77 2

共有 12 个关键字,等概率查找,则成功查找时 ASL=(1+2+1+4+3+1+1+3+1+1+3+2)/12=23/12≈1.9 【例3-58】 [例 13—32] 假设一个散列表为 HT[0. .12],表长为 m=13。采用再散列 法解决冲突。散列函数和再散列函数分别为 Ho(key)=key%13 Hi=(Hi-1 十 REV(key+1)%11+1)%13 (i=l,2,…,m-1) 其中:函数 REV(x)表示首尾颠倒 10 进制数 x 的各位,如 REV(12)=21,REV(9)=9 等。 若插入关键字序列为{2,8,31,20,19,18,53,27}。 (1)试画出插入这 8 个关键字后的散列表。 (2)计算查找成功的平均查找长度。 解析:(1)散列表如图 13.14 所示。 解析

21

(2) ASL = )

1× 6 + 3 + 2 11 = ) 8 8

第 10 章 字典
10.1. 二叉搜索树及其实现
【例3-59】 1.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入 一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树; (2)若查找元素 17,它将依次与二叉排序树中哪些元素比较大小? (3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。 (4)对该树进行中序遍历,试写出中序遍历序列。 【例3-60】 15、设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树 起,逐个输入各个数据而生成的二叉搜索树。

【例3-61】 24、已知关键字序列{23,13,5,28,14,25},试构造二叉排序树。 构造二叉排序树的过程如下图所示。

构造的二叉排序树如下图所示:

22

【例3-62】 26、 设有一个输入数据的序列是{ 46, 25, 78, 62, 12, 80 }, 试画出从空树起, 逐个输入各个数据而生成的二叉排序树。 如下图所示:

【例3-63】 设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二 叉排序树并给出构造过程。

【例3-64】 33.程序填空:对有序表 R[1]至 R[n]进行二分查找,成功时返回记录在表 中的位置,失败时返回 0。 分) (6 struct sqlist key; { keytype key; }; int binsrch(sqlist R[ ],keytype k) //在表 //在表 R 中查找关键字 k { int low, high, mid; low=1 low=1; high=n; while( mid=(low+high)/2; mid=(low+high)/2; ==R[mid].key R[mid].key) if (k==R[mid].key) return mid; k<R[mid].key else if( k<R[mid].key ) else } return 0; eturn 0; } 【例3-65】 【例 7-1】有序表按关键字排列如下:7,14,18,21,23,29,31,35, 38,42,46,49,52,在表中查找关键字为 14 和 22 的数据元素,并画出 折半查找过程的判定树。 解:折半查找的过程描述如下: ① low=1;high=length; ② 当 low>high 时,返回查找失败信息
23

)

; ;

//设置初始区间 //表空,查找失败

③ low≤high,mid=(low+high)/2; //取中点 a. 若 kx<tbl.elem[mid].key,high=mid-1;转② //查找在左半区进行 b. 若 kx>tbl.elem[mid].key,low=mid+1;转② //查找在右半区进行 c. 若 kx=tbl.elem[mid].key,返回数据元素在表中位置 //查找成功 查找关键字为 14 的过程如下: 0 1
7

2
14

3
18

4
21

5
23

6
29

7
31

8
35

9 10
38 42

11
46

12
49

13
52

↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试,非空; mid=7 ③得到中点,比较测试为 a 情形 ↑ ↑ low=1 high=6 high=mid-1,调整到左半区 ──────────────────────────── ↑ ②表空测试,非空; mid=3 ③得到中点,比较测试为 a 情形 ↑ ↑ low=1 high=2 high=mid-1,调整到左半区 ──────────────────────────── ②表空测试,非空; ↑ mid=1 ③得到中点,比较测试为 b 情形 ↑↑ low=2 high=2 low=mid+1,调整到右半区 ──────────────────────────── ↑ ②表空测试,非空; mid=2 ③得到中点,比较测试为 c 情形
查找成功,返回找到的数据元素位置为 2

查找关键字为 22 的过程如下:

0

1
7

2 3
14 18

4
21

5
23

6
29

7 8
31 35

9 10
38 42

11 12 13
46 49 52

↑ ↑ low=1 ①设置初始区间 high=13 ──────────────────────────── ↑ ②表空测试,非空; mid=7 ③得到中点,比较测试为 a 情形 ↑ ↑ low=1 high=6 high=mid-1,调整到左半区 ─────────────────────────── ↑ ②表空测试,非空; mid=3 ③得到中点,比较测试为 b 情形 ↑ ↑ low=4 high=6 low=mid+1,调整到右半区 ──────────────────────────── ↑ ②表空测试,非空; mid=5 ③得到中点,比较测试为 a 情形 ↑↑ low=4 high=4 high=mid-1,调整到左半区 ──────────────────────────── ↑ ②表空测试,非空; mid=4 ③得到中点,比较测试为 b 情形 ↑ ↑ high=4 low=5 low=mid+1,调整到右半区 ────────────────────────────
②表空测试,为空;查找失败,返回查找失败信息为 0

24

查找过程的判定树如图 7-1 所示。 7 3 1 2 4 5 6 8 9 11 10 12 13

图 7-1 折半查找过程的判定树

第 11 章 优先队列
11.1. 堆的概念及其实现
【例3-66】 1.下列关键字序列中,___是堆。 D ) ( A. 16, 72, 31, 23, 94, 53 B. 94, 23, 31, 72, 16, 53 C. 16, 53, 23, 94,31, 72 , D. 16, 23, 53, 31, 94, 72 【例3-67】 2. 将数据序列(25,19,7,41,29,12,23,26)按升序排序,请写出初建 极大堆的过程图示。

11.2. 哈夫曼树及其应用
【例3-68】 1.用 5 个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 ______ 33 。 =(4+ + ) +( +(1 解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出 WPL=( +5+3)×2+( 先构造哈夫曼树, =( +2)×3=33 ) (15) (9) (6) 两个合并值先后不同会导致编码不同, 即哈夫曼编码不唯一) (注: 两个合并值先后不同会导致编码不同, 即哈夫曼编码不唯一) 4 5 3 (3) 合并值应排在叶子值之后) (注:合并值应排在叶子值之后) 1 2 (注: 原题为选择题: 32 A. B. 33 C. 34 D. 15) 【例3-69】 2.给定 30 个字符组成的电文: D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D 试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。 (1)画出相应的哈夫曼树; (2)分别列出 A、B、C、D、E、F 的哈夫曼码; (3)计算该树的带权路径长度 WPL。 【例3-70】 5. 有一份电文中共使用 6 个字符:a,b,c,d,e,f,它们的出现频率依 次为 2,3,4,7,8,9,试构造一棵哈夫曼树,计算其加权路径长度 WPL 和字符 c 的编码(要求将频率小的结点出现在左子树上) 。

25

参考答案: 参考答案: WPL= 7*2+8*2+9*2+4*3+2*4+3*4 =80 c 的编码为 110

【例3-71】 4.有七个带权结点,其权值分别为 3,7,8,2,6,10,14,试以它们为叶子结点 构造一棵哈夫曼树,并计算出带权路径长度 WPL。 答:
50

21 10 5 2 3 11 6 14

29 15 7 8

WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131 【例3-72】 5、给定字母 a,b,c,d,e 的使用频率为 0.09,0.17,0.2,0.23,0.31。设计以该权值 为基础的哈夫曼树,并给出哈夫曼编码?平均长度是多少? 答: 构造的哈夫曼树如下:

哈夫曼编码如下: c(00) d(01) a(100) b(101) e(11)
26

平均长度=0.09*3+0.17*3+0.2*2+0.23*2+0.31*2=2.26 【例3-73】 【例 5-14】假定用于通信的电文由 8 个字符 A、B、C、D、E、F、G、H 组成,各字母在电文中出现的概率为 5%、25%、4%、7%、9%、12%、 30%、8%,试为这 8 个字母设计哈夫曼编码。 解: 根据题意,设这 8 个字母对应的权值分别为(5,25,4,7,9,12,30,8) ,并 且 n=8。 (1)设计哈夫曼树的步骤如图 5-13 所示。
第一步:

5

25

4

7

9

12

30

8

第二步:

25

7

9

12

30

8 4

9 5 9

第三步:

25

9

12

30 7

15 8 4

5

第四步:

25

12

30 7

15 8 9

18 9 4 5

第五步:

25

30 12

27 15 7 8 43 15 18 8 9 4 9 5 25 9

18 9 4 5

第六步:

30 12

27

7

第七步:

57 27 12 7 15 8
27

43 30 9 4 18 9 5 25

第八步:

100 43 57

(2)设计哈夫曼编码 利用第八步得到的哈夫曼树,规定左分支用 0 表示,右分支用 1 表示,字母 A、B、C、 D、E、F、G、H 的哈夫曼编码如下表示: A:0011 B:01 C:0010 D:1010 E:000 F:100 G:11 H:1011 【例3-74】 [例 10-30] 设给定字符集合{a,b,c,d,e,f} 的权值集合 w={2,3, 4,?,8,9},试构造关于 w 的一颗哈夫曼树,并求其带权路径长度及各 字符的哈夫曼编码。 解析:根据给定的权值集合构造的哈夫曼树如图 10.19 所示。 解析 其加权路径长度 WPL=(9+7+8)×2+4×3 十(2+3)×4=80。 各字符的哈夫曼编码如下: a 0000 b 0001 c 001 d 10 e 11 f 0l

注意:此题哈夫曼树形不唯一,因此哈夫曼编码也有多种方案,但 WPL 是一定的。 注意

第 12 章 图
12.1. 图的存储结构(邻接矩阵、邻接表) 图的存储结构(邻接矩阵、邻接表)
【例3-75】 1. 画出图的邻接矩阵、邻接表。 (注意相互转换)

28

【例3-76】 10、已知一个无向图的顶点集为{a, b, c, d, e},其邻接矩阵如下所示:
?01001? ?10010? ? ? ?00011? ? ? ?01101? ?10110? ? ?

(1)画出该图的图形; (2) 根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历, 写出相应的遍历序列。 【解答】 (1)该图的图形如下图所示:

(2)深度优先遍历序列为:abdce;广度优先遍历序列为:abedc。

【例3-77】 【 例 6-2 】 图 G = (V , E) , 其 中 V={1,2,3,4,5,6} , E = {<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6>}, 请画出图 G, 并 写出其邻接矩阵和邻接表表示。 解:图 G 如图 6-4 中的(a)所示,图 G 的邻接矩阵和邻接表表示分别如图(b)和(c)所示。 对于这类问题, 只要掌握了图的概念和存储结构就可以做出正确的答案。 通常情况下. 对 图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求, 因此, 在写出邻接矩阵和邻 接表表示时,只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是,对于邻 接矩阵表示,如果顶点结点的顺序不同,那么邻接矩阵就不相同;对于邻接表表示,如果顶 点结点的顺序或者邻接点的顺序不同,那么邻接表就不相同。 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0
(b)

1 2 3 5
(a)

4

6

1 0 0 0 0 0

0 1 1 0 1 0

0 0 1 1 1 0

1 2 3

2 5 2 ∧

3 29

4



5

6



【例3-78】 【例 6-3】已知一个无向图的邻接表如图 6-5 所示,要求: (1)画出该无向图; (2)根据邻接表,分别写出用 DFS(深度优先搜索)和 BFS(广度优先搜索)算法从顶 点 V0 开始遍历该图后所得到的遍历序列。 V0 V1 V2 V3 V4 V5 V6 2 3 0 1 1 0 2 5 0 3 2 3 6 5 ∧ ∧ 0 ∧ 6 4 6 4 ∧ 1 2 1 ∧ ∧ ∧

解: (1)该无向图如图 6-6 所示。

图 6-5 图的邻接表存储

v2 v6 v0 v5 v1 v4 v3

图 6-6 无向图

(2)根据该无向图的邻接表表示,从顶点 V0 开始的深度优先遍历序列为:V0、V2、 V3、V1、V4、V6、V5。广度优先遍历序列为 V0、V2、V5、V6、V1、V3、V4。

12.2. 图的遍历方法(深度优先遍历、广度优先遍历) 图的遍历方法(深度优先遍历、广度优先遍历)
【例3-79】 1.设 G=(V,E)以邻接表存储,如图所示,试画出图的深度优先和广度优先
30

生成树。
1 2 3 4 5 2 1 1 1 2 3 3 2 2 4 Λ 4 Λ 4 4 Λ 3 5 Λ 5 Λ

【例3-80】 31、对于如下图所示的 G,用 Kruskal 算法构造最小生成树,要求图示出 每一步的变化情况。

用 Kruskal 算法构造最小生成树的过程如下图所示:

12.3. 图的最小生成树的算法( prim 算法、 kruskal 算法) 图的最小生成树的算法( 算法、 算法) 。
【例3-81】 1.找出下面网络的最小生成树。

31

【例3-82】 2.如图所示,用 Prim 算法从结点 1 出发构造出一棵最小生成树,要求图 示出每一步的变化情况。

【例3-83】 3、对于如下图所示的有向图若存储它采用邻接表,并且每个顶点邻接表 中的边结点都是按照终点序号从小到大的次序链接的,试写出: (1)从顶点 v1 出发进行深度优先搜索所得到的深度优先生成树; (2)从顶点 v2 出发进行广度优先搜索所得到的广度优先生成树。

(1)DFS:v1 v2 v3 v4 v5 (2)BFS:v2 v3 v4 v5 v1 【例3-84】 4、已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}; 请画出该图。 【例3-85】 设有无向图 G,要求给出用普里姆算法构造最小生成树所走过的边的集 合。

【例3-86】 请画出下图的邻接矩阵和邻接表。

32

【例3-87】 已知一个图的顶点集 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}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。 【例3-88】 17、已知一个图的顶点集 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}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为: (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 【例3-89】 【例 6-4】对于如图 6-8 所示的带权无向图,用图示说明: (1)利用 Prim 算法从顶点 a 开始构造最小生成树的过程; (2)利用 Kruskal 算法构造最小生成树的过程; a 8 9 f 6 b
图 6-8 带权无向图

3 2 4 e 5 1 4 1 9

d

7 g 8 c

解: (1)利用 Prim 算法从顶点 a 开始构造最小生成树的过程如图 6-9 所示。 a e f g f d a 2 e g f d a 2 e 1 g d

b
初始状态

c

b
连通 e

c

b
连通 g

c

a

3 2 e f 1 g f c
连通 d

3 d a 2 4 e 1 g d

3 a 2 4 f 6
33

d e 1 g

b

b
连通 f

c

b
连通 b

c

a 2 4 f 6

3 e

d 1 g

1 b
连通 c 图 6-9 用 Prim 算法构造最小生成树的过程

c

(2)利用 Kruskal 算法构造最小生成树的过程如图 6-10 所示。 a e f g f c
初始状态

d

a e 1 g

d

a e f 1 1 g

d

b

b
增加第 1 条边

c 3

b
增加第 2 条边

c 3

a

2 e f 1 1 g

d

a

2 e f 1 g 1

d

a 2 4 f 1 e 1 g

d

b
增加第 3 条边

c

b
增加第 4 条边

c

b
增加第 5 条边

c

a

3 2 4 f e 1 g 1

d

6 b
增加第 6 条边 图 6-10 用 Kruskal 算法构造最小生成树的过程

c

34

【例3-90】 18、请画出如下图所示的邻接矩阵和邻接表。

邻接矩阵: ?0 ?

?1 ?1 ? ?1 ?0 ?

1 1 1 0? 0 1 0 1? ? 1 0 1 1? ? 0 1 0 1? 1 1 1 0? ?

邻接表如下图所示:
1 2 3 4 5 2 1 1 1 2 3 3 2 3 3 4 5 4 5 4 ∧ ∧ ∧ ∧ 5 ∧

12.4. 图的单源最短路径的 dijkstra 算法。 算法。
【例3-91】 1.有如下数据结构的形式定义,试画出此结构的图形表示。 (南方名校经 典试题) DS={D,S},其中: D={1,2,3,4} S=={R} R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>} 【例3-92】 2.给出如图所示的所有拓扑有序序列。

【例3-93】 5. 已知加权有向图 G 的邻接矩阵如下:

?∞ 15 2 12 ∞ ∞ ∞ ? ?∞ ∞ ∞ ∞ 6 ∞ ∞ ? ? ? ?∞ ∞ ∞ ∞ 8 4 ∞ ? ? ? ?∞ ∞ ∞ ∞ ∞ ∞ 3 ? ?∞ ∞ ∞ ∞ ∞ ∞ 9 ? ? ? ?∞ ∞ ∞ ∞ 5 ∞ 10? ?∞ 4 ∞ ∞ ∞ ∞ ∞ ? ? ?
(1) 画出该有向图 G

35

(2) 试利用 Dijkstra 算法求 G 中从顶点 a 到其他各顶点间的最短路径,并给出求解过程。 答: (1)

(2) 终点 Dist k=1 k=2 k=3 k=4 k=5 k=6

b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b)

c 2 (a,c)

d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d)

e

f

g

S {a,c}

10 (a,c,e) 10 (a,c,e)

6 (a,c,f) 16 (a,c,f,g) 16 (a,c,f,g) 14 (a,c,f,d,g)

{a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b}

【例3-94】 13、试列出如下图中全部可能的拓扑排序序列。

36

1

2

3

4

5

6

全部可能的拓扑排序序列为:1523634、152634、156234、561234、516234、512634、512364 【例3-95】 4. 请用图示说明从顶点 a 到其余各顶点之间的最短路径。

37


相关文章:
专升本数据结构复习题
专升本数据结构复习题_小学作文_小学教育_教育专区。1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 ⑵()是数据的最小单位, (...
数据结构复习资料及答案
2011福建专升本数据结构复... 42页 免费 2011福建专升本数据结构复... 42页 ...计算机应用(独立本科段) 数据结构复习资料及答案计算机应用(独立本科段) 数据结构...
专升本试题(数据结构)_图文
数据结构专升本考试试题(2015 年 3 月) 一、单项选择题(本大题共 20 小题,每小题 2 分,共 40 分) 1.对于一个算法,当输入非法数据时,也要能作出...
福建专升本数据结构讲解
福建专升本数据结构复习课... 180页 2财富值 2011福建专升本数据结构复... 37...二、数据结构=逻辑结构,物理结构 数据逻辑结构(顶层):三种,线性、层次(树) 、...
专升本《数据结构》_试卷_答案
专升本数据结构》_试卷_答案_教育学_高等教育_教育专区。专升本数据结构》 一、 (共 75 题,共 150 分) 1. 数据的基本单位是()。(2 分) A.数据元素 ...
05到09年福建专升本数据结构真题详解
2011福建专升本数据结构... 42页 免费 考题解答07年福建专升本... 6页 免费0...口腔执业医师实践技能复习资料 中医护理学基础重点 执业医师实践技能考试模拟试题 ...
2011级专升本管理信息系统复习资料
2011专升本管理信息系统复习资料_管理学_高等教育_教育专区。名词解释 1.专家系统...输入部分、输出部分和内部的处理过程及相应的数据库/文件、在总体 结构中的位置...
专升本数据结构考前必看
专升本数据结构考前必看_司法考试_资格考试/认证_教育专区。1.名词解释:栈和队列...对于合法序列 ABC,我们使用本题约定的 SXSXSX 操作序列;对于合法序列 BAC,我们...
专升本数据结构5年真题和详细解析
年山东省专升本考试数据结构真题一、单项选择题(10 ...[i]中的记录放入第 j+1 个位置 2011 年山东省...05到09年福建专升本数据... 33页 5下载券 211...
(2013年)专升本十套-数据结构(试题及答案)
(2013年)专升本十套-数据结构(试题及答案)_文学_高等教育_教育专区。(2013年)专升本十套数据结构(试题及答案) 数据结构试卷(一)一、单选题(每题 2 分,共 20...
更多相关标签: