数据结构第7章
第7章搜索
一、复习要点
本章讨论了搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和A VL树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有n个对象的二叉搜索树中，搜索效率最高的是高度最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是A VL树。在A VL树的讨论中，4种平衡旋转，选择参加平衡旋转的3个结点是关键，必须加以注意。
本章复习的要点是：
1、基本知识点
理解理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握A VL树的构造、插入、删除时的调整方法及其性能分析，重点是A VL树的定义、平衡化旋转、A VL树的插入和删除、A VL树的高度。
2、算法设计
用有序链表表示集合时的求集合的并、交、差的算法
并查集中的构造函数、求根及合并算法
并查集中根据树的高度和根据树中结点个数进行合并的算法
设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法
有序顺序表的顺序搜索算法
有序顺序表的折半搜索的递归算法和非递归算法
二叉搜索树的搜索、插入和删除算法
计算A VL树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法
二、难点和重点
3、基本搜索方法
对一般表的顺序搜索算法(包括有监视哨和没有监视哨)
对有序顺序表的顺序搜索算法，包括递归和非递归算法
用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功与不成功)的计算。
对有序顺序表的折半搜索算法、包括递归和非递归算法
用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成功与不成功)的计算。
4、二叉搜索树
动态搜索树与静态搜索树的特性
二叉搜索树的定义、二叉搜索树上的递归和非递归搜索算法
二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算
二叉搜索树的插入与删除算法
A VL 树结点上的平衡因子、AVL 树的平衡旋转方法 高度为h 的A VL 树上的最少结点个数与最多结点个数 A VL 树的搜索方法、插入与删除方法(不要求算法)
三、教材中习题的解析
7-8 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】
7-9 若对有n 个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1) 搜索失败;
(2) 搜索成功, 且表中只有一个关键码等于给定值k 的对象;
(3) 搜索成功, 且表中有若干个关键码等于给定值k 的对象, 要求一次搜索找出所有对象。
【解答】
(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。
7-10 假定用一个循环链表来实现一个有序表，并让指针head 指向具有最小关键码的结点。指针current 初始时等于head ，每次搜索后指向当前检索的结点，但如果搜索不成功则current 重置为head 。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current 以减少搜索时的平均搜索长度。 【解答】
14
45
7)*44*32*2(1141C 141ASL 141i i succ =+++==∑=15
5914)*41*(3151C 151ASL 150i '
i unsucc =+==∑=
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template
ListNode
if ( key < current ) { p = head ; q = current ; }
//确定检测范围, 用p, q 指示
else { p = current ; q = head ; } while ( p != q && p ->data < key ) p = p ->link ; //循链搜索其值等于key 的结点 if ( p ->data == key ) { current = p ; return p ; } //找到, 返回结点地址 else { current = head ; return NULL ; }
//未找到, 返回空指针
}
7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p 总是指向最后成功搜索到的结点，搜索可以从p 指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head, p, key)，检索具有关键码key 的结点，并相应地修改p 。最后请给出搜索成功和搜索不成功时的平均搜索长度。 【解答】
template
DblListNode
DblListNode
if ( key < p ->data ) { while ( q != NULL && q ->data > key ) q = q -> lLink ; } //反向搜索 else { while ( q != NULL && q ->data < key ) q = q -> rLink ; } //正向搜索 if ( q != NULL && q ->data == key ) { p = q ; return p ; }
//搜索成功
else return NULL ; }
如果指针p 处于第i 个结点(i = 1, 2, …, n )，它左边有i -1个结点，右边有n -i 个结点。
找到左边第i -1号结点比较2次，找到第i -2号结点比较3次，…，找到第1号结点比较i 次，一般地，找到左边第k 个结点比较i -k+1次(k = 1, 2, …, i -1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…，找到第n 号结点比较n -i+1次，一般地，找到右边第k 个结点比较k -i+1次(k = i+1, i+2, …, n )。因此，当指针处于第i 个结点时的搜索成功的平均数据比较次数为
一般地，搜索成功的平均数据比较次数为
head
n n *i i i 23n n n *i i i 23)(n *n n 1)i (k )1k (i 122n
1i k 1i 1k --++=???
??--++=??
? ??+-+
+-+∑
∑+=-=3n
1
3n n n
n *i i i 2
3n n
1ASL 2n 1
i 2succ -+=
???
? ??--+
+=
∑=
如果指针p 处于第i 个结点(i = 1, 2, …, n )，它左边有i 个不成功的位置，右边有n -i+1个不成功的位置。
一般地，搜索不成功的平均数据比较次数为
7-12 在一棵表示有序集S 的二叉搜索树中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S 1；在该路径上的结点中的元素组成的集合S 2；在该路径右边结点中的元素组成的集合S 3。S = S 1 ? S 2 ? S 3。若对于任意的a ∈ S 1, b ∈ S 2, c ∈ S 3， 是否总有a ≤ b ≤ c ？为什么？ 【解答】
答案是否定的。举个反例：看下图粗线所示的路径
S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 } c = 40 ∈ S3，b = 45 ∈ S2，b ≤ c 不成立。
7-13 请给出下列操作序列运算的结果：Union(1, 2), Union(3, 4), Union(3, 5), Union(1, 7), Union(3, 6), Union(8, 9), Union(1, 8), Union(3, 10), Union(3, 11), Union(3, 12), Union(3, 13), Union(14, 15), Union(16, 17), Union(14, 16), Union(1, 3), Union(1, 14)，要求
(1) 以任意方式执行Union ； (2) 根据树的高度执行Union ； (3) 根据树中结点个数执行Union 。 【解答】
(1) 对于union(i, j)，以i 作为j 的双亲
(2) 按i 和j 为根的树的高度实现union(i, j)，高度大者为高度小者的双亲；
1)(n 1n *i i i 23)(n *n 1)(n 1)i (k k)(i 2n i k 1i 0k +???
??+--++=+??
? ??+-+-∑∑=-=∑=+++=??? ??+--+++=n 0i 222unsucc 1n 6
7n 2n 1n *i i i 23)(n *n 1)(n 1ASL
(3) 按i 和j 为根的树的结点个数实现union(i, j)，结点个数大者为结点个数小者的双亲。
7-14 有n 个结点的二叉搜索树具有多少种不同形态? 【解答】
7-15 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 【解答】
7-16 设有一个标识符序列{else, public, return, template}，p 1=0.05, p 2=0.2, p 3=0.1, p 4=0.05, q 0=0.2, q 1=0.1, q 2=0.2, q 3=0.05, q 4=0.05，计算W[i][j]、C[i][j]和R[i][j]，构造最优二叉搜索树。 【解答】 将标识符序列简化为 { e, p, r, t }，并将各个搜索概率值化整，有
e p r t p 1 = 1
p 2 = 4 p 3 = 2 p 4 = 1
q 0 = 4 q 1 = q 2 = 4 q 3 = 1 q 4 = 1
C n
2n
1n 1
空树 加46 加25
加78 加37 加29
2
(1) 首先构造只有一个内结点的最优二叉搜索树:
W[i][j]
C[i][j] R[i][j]
(2) 构造具有两个内结点的最优二叉搜索树
(3) 构造具有三个内结点的最优二叉搜索树
(4) 构造具有四个内结点的最优二叉搜索树
7-17 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1)
用左子树T L 上具有最大关键码的结点X 顶替，再递归地删除X 。
(2) 交替地用左子树
T L 上具有最大关键码的结点和右子树T R 上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3) 用左子树T L 上具有最大关键码的结点或者用右子树T R 上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】
① 在被删结点有两个子女时用左子树T L 中具最大关键码的结点顶替的算法：
template
//进到ptr 的左子树
C[0][2] = 22
T[0][2] = 2
C[1][3] = 20 T[1][3] = 2 C[2][4] = 12 T[2][4] = 2 T[0][3] = 2 C[1][4] = 27 T[1][4] = 2 C[0][4] = 39 T[0][4] = 2 左子树 T[0][1], 其 C[0][1] = 7 右子树 T[2][4], 其 C[2][4] = 12
while ( temp->rightChild != NULL ) temp = temp->rightChild;//搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
②在被删结点有两个子女时用右子树T R中具最小关键码的结点顶替的算法：
template
BstNode
while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点
ptr->data = temp->data;//用该结点数据代替根结点数据
return temp;
}
(1) 用左子树T L上具有最大关键码的结点X顶替，再递归地删除X。
template
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。
BstNode
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x, ptr->leftChild );//在左子树中执行删除
else if ( x > ptr->data ) Remove ( x, ptr->rightChild );//在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
temp = leftReplace ( ptr );//在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data, ptr->rightChild );//在ptr的右子树中删除该结点
}
else {// ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild;//只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;//只有左子女
delete temp;
}
}
(2) 交替地用左子树T L上具有最大关键码的结点和右子树T R上具有最小关键码的结点顶替，再递归地删除适当的结点。
template
//结点顶替被删关键码; 若dir = 1, 用右子树上具有最小关键码的结点顶替被删关键码结点, 在调//用它的程序中设定它的初始值为0。
BstNode
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x, ptr->leftChild, dir );//在左子树中执行删除
else if ( x > ptr->data ) Remove ( x, ptr->rightChild, dir );//在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( dir == 0 ) {
temp = leftReplace ( ptr );dir = 1;
//在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data, ptr->rightChild, dir );//在ptr的右子树中删除该结点
} else {
temp = rightReplace ( ptr );dir = 0;
//在ptr的右子树中搜寻中序下第一个结点顶替x
Remove ( ptr->data, ptr->leftChild, dir );//在ptr的左子树中删除该结点
}
}
else {// ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild;//只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;//只有左子女
delete temp;
}
}
(3) 用左子树T L上具有最大关键码的结点或者用右子树T R上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
#include
template
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在//程序中用到一个随机数发生器rand( ), 产生0~32767之间的随机数, 将它除以16384, 得到0~2 //之间的浮点数。若其大于1, 用左子树上具有最大关键码的结点顶替被删关键码; 若其小于或等//于1, 用右子树上具有最小关键码的结点顶替被删关键码结点, 在调用它的程序中设定它的初始//值为0。
BstNode
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x, ptr->leftChild );//在左子树中执行删除
else if ( x > ptr->data ) Remove ( x, ptr->rightChild );//在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( (float) ( rand ( ) / 16384 ) > 1 ) {
temp = leftReplace ( ptr );//在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data, ptr->rightChild );//在ptr的右子树中删除该结点
} else {
temp = rightReplace ( ptr );//在ptr的右子树中搜寻中序下第一个结点顶替x
Remove ( ptr->data, ptr->leftChild );//在ptr的左子树中删除该结点
}
}
else {// ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild;//只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;//只有左子女
delete temp;
}
}
7-18 (1) 设T 是具有n 个内结点的扩充二叉搜索树, I 是它的内路径长度, E 是它的外路径长度。试利用归纳法证明 E = I + 2n, n ≥ 1。
(2) 利用(1)的结果, 试说明: 成功搜索的平均搜索长度S n 与不成功搜索的平均搜索长度U n 之间的关系可用公式
S n = ( 1 + 1/n ) U n - 1, n ≥ 1 表示。 【解答】
(1) 用数学归纳法证明。当n = 1时，有1个内结点(I = 0)，2个外结点(E = 2)，满足E = I+2n 。设n = k 时结论成立，E k = I k + 2k 。则当n = k + 1时，将增加一个层次为l 的内结点，代替一个层次为l 的外结点，同时在第l+1层增加2个外结点，则E k+1 = E k – l + 2*(l+1) = E k + l +2，I k+1 = I k + l ，将E k = I k + 2k 代入，有E k+1 = E k + l +2 = I k + 2k + l +2 = I k+1+ 2(k +1)，结论得证。
(1) 因为搜索成功的平均搜索长度S n 与搜索不成功的平均搜索长度U n 分别为
其中，c i 是各内结点所处层次，c j 是各外结点所处层次。因此有
(n+1)U n = E n = I n + 2n = nS n – n +2n = nS n +n
7-19 求最优二叉搜索树的算法的计算时间为O(n 3)，下面给出一个求拟最优二叉搜索树的试探算法，可将计算时间降低到O(nlog 2n)。算法的思想是对于关键码序列{ key l , key l+1, …, key h }， 轮流以key k 为根，k = l, l+1, …, h ，求使得 | W[l -1][k -1] - W[k][h] | 达到最小的k ，用key k 作为由该序列构成的拟最优二叉搜索树的根。然后对以key k 为界的左子序列和右子序列，分别施行同样的操作，建立根key k 的左子树和右子树。要求：
(1) 使用7.17题的数据，执行这个试探算法建立拟最优二叉搜索树，该树建立的时间代价是多少？
(2) 编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog 2n)。 【解答】
(1) 各个关键码的权值为 { p 1, p 2, p 3, p 4 }，利用题7-17中的W 矩阵，轮流让 k = 1, 2, 3, 4为根，此时，下界l = 1, 上界h = 4。有 min ∣W[l -1][k -1] – W[k][h]∣ = ∣W[0][1] – W[2][4]∣ = 2
求得 k = 2。则根结点为2，左子树的权值为 { p 1 }，右子树的权值为 { p 3, p 4 }。 因为左子树只有一个结点，所以，权值为p1的关键码为左子树的根即可。对于右子树 { p 3, p 4 }，采用上面的方法，轮流让 k = 3, 4为根，此时，下界l = 3，上界h = 4。有 min ∣W[l -1][k -1] – W[k][h]∣ = ∣W[2][2] – W[3][4]∣
= 1
1
I n
1
1c n 11)(c n 1S n n 1i i n 1i i n +=+=+=∑∑==k
n
j j n E 1n 1
c 1n 1U +=+=∑=1S U n
1n n n +=
+1U n 11S n n -??? ??
+=
求得 k = 3。于是以权值为p 3的关键码为根，其左子树为空，右子树为 { p 4 }。这样，得到拟最优二叉搜索树的结构如下：
建立该拟最优二叉搜索树的时间代价为O(4+1+2+1) = O(8) (2) 建立该拟最优二叉搜索树的算法
void nearOptiSrchTree ( int W[n+1][n+1], int n, int left, int right ) { if ( left > right ) { cout << “Empty Sequence! “ << endl; return; } if ( left == right ) { cout << left ; return; } int p = 0; int k ;
for ( int j = left ; j <= right ; j++ ) if ( p > abs ( W[left -1][j -1] – W[j][right] )
{ p = abs ( W[left -1][j -1] – W[j][right] ); k = j ; }
cout << k ;
if ( k == left ) nearOptiSrchTree ( W[n+1][n+1], n, k+1, right ); else if ( k == right ) nearOptiSrchTree ( W[n+1][n+1], n, left, k -1 ); else { nearOptiSrchTree ( W[n+1][n+1], n, left, k -1 ); nearOptiSrchTree ( W[n+1][n+1], n, k+1, right );
}
}
7-20将关键码DEC, FEB, NOV , OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的A VL 树中，画出每插入一个关键码后的A VL 树，并标明平衡旋转的类型。 【解答】
加DEC 加FEB 加NOV 加OCT 加JUL
7-21 从第7-20题所建立的A VL 树中删除关键码MAY ，为保持A VL 树的特性，应如何进行删除和调整? 若接着删除关键码FEB ，又应如何删除与调整? 【解答】
左单旋 左右双旋
7-22 将关键码1, 2, 3, …, 2k -1依次插入到一棵初始为空的AVL 树中。试证明结果树是完全平衡的。 【解答】
所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。 当k = 1时，21-1 = 1，A VL 树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。 设k = n 时，插入关键码1, 2, 3, …, 2n -1到A VL 树中，恰好每一层(层次号码i = 0, 1, …, n -1)有2i 个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1, 2, 3, …, 2n -1, 2n , …, 2n+1-1，总共增加了从2n 到2n+1-1的2n+1-1-2n +1 = 2n 个关键码，使得A VL 树在新增的第n 层具有2n 个结点，达到该层最多结点个数，因此，满足完全平衡要求。
7-23 对于一个高度为h 的A VL 树，其最少结点数是多少？反之，对于一个有n 个结点的A VL 树, 其最大高度是多少? 最小高度是多少? 【解答】
设高度为h （空树的高度为 -1）的A VL 树的最少结点数为N h ，则N h = F h+3 – 1。F h 是斐波那契数。又设A VL 树有n 个结点，则其最大高度不超过3 / 2 * log 2 (n + 1)，最小高度为 ?log 2 ( n+1)? -1。
四、其他练习题
7-24 供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 对线性表进行折半搜索时，要求线性表必须（ A ）。 (2) 采用顺序搜索算法搜索长度为n 的线性表时，元素的平均搜索长度为（ B ）。 (3) 采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度为（ C ）。
(4) 采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度应（ D ）对应判定树的最大层次数。
(5) 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ E ）。 (6) 顺序搜索算法适合于存储结构为（ F ）的线性表。 供选择的答案
A ：① 以数组方式存储 ② 以数组方式存储且结点按关键码有序排列 ③ 以链接方式存储 ④ 以链接方式存储且结点按关键码有序排列
B ：① n/2 ② n ③ (n+1)/2 ④ (n-1)/2
C ：① O(n 2) ② O(nlog 2n) ③ O(log 2n) ④ O(n)
D ：① 小于 ② 大于 ③ 等于 ④ 大于等于
E ：① 相同 ② 完全不同 ③ 有时不相同
12 个结点的最小高度
F：①散列存储②顺序存储或链接存储
③压缩存储④索引存储
【解答】
A．②B．③C．③D．④E．③ F. ②
7-25 填空题
(1) 以折半搜索方法从长度为12的有序表中搜索一个元素时，平均搜索长度为________。
(2) 以折半搜索方法搜索一个线性表时，此线性表必须是_______存储的_______表。
(3) 从有序表（12, 18, 30, 43, 56, 78, 82, 95）中依次折半搜索43和56元素时，其搜索长度分别为_______和________。
(4) 对于折半搜索所对应的判定树，它既是一棵________，又是一棵_______。
(5) 假定对长度n = 50的有序表进行折半搜索，则对应的判定树高度为_______，判定树中前5层的结点数为_______，最后一层的结点数为________。
【解答】
(1) 37/12 (2) 顺序，有序(3) 1，3
(4) 二叉搜索树，理想平衡树(5) 5，31，19
7-26 判断题
(1) 任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。
(2) 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。
(3) 对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的。
(4) 在二叉搜索树上插入新的结点时，不必移动其他结点，仅需改动某个结点的指针，使它由空变为非空即可。
(5) 在二叉搜索树上删除一个结点时，不必移动其他结点，只要将该结点的双亲结点的相应的指针域置为空即可。
(6) 最优二叉搜索树的任何子树都是最优二叉搜索树。
(7) 在所有结点的权值都相等的情况下，只有最下面两层结点的度数可以小于2，其他结点的度数必须等于2的二叉搜索树才是最优二叉搜索树。
(8) 在所有结点的权值都相等的情况下，具有平衡特性的二叉搜索树一定是最优二叉搜索树。
(9) 最优二叉搜索树一定是平衡的二叉搜索树。
【解答】
(1) ?(2) ?(3) √(4) √(5) ?(6) √(7) √(8) ?(9) √
7-27设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行顺序搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
7-28 试仿照折半搜索方法编写一个Fibonacci搜索算法，并针对n = 12情况，画出Fibonacci 算法的判定树。
【解答】
Fibonacci数列为F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, …。Fibonacci搜索就是利用Fibonacci数列来划分搜索区间的搜索方法。下图是一个n = 12 的Fibnacci数列的树形结构，Fibonacci搜索就是利用Fibonacci树进行搜索的。
设有n个已经排序好的数据，每次搜索必须先找出Fibonacci树的根root和距离值。其原则如下：
第1步，计算满足Fib(a) <= n+1的Fibonacci数Fib(a)。在上例中，n = 12，由于Fib(7) <= 12+1 = 13，所以，a = 7。
第2步，求得树的根root = Fib(a-1) = Fib(6) = 8。与左子树根的距离dictance_1 = Fib(a-2) = Fib(5) = 5，与右子树根的距离distance_2 = Fib(a-3) = Fib(4) = 3。
第3步，进行迭代，直到找到满足给定值x的数据或距离等于0为止：
(1) 若根结点的数据值等于给定值x，搜索成功，返回root所指位置，算法结束。
(2) 若根结点的数据值小于给定值x，则必须搜索第Fib(a-1)个数据之后的数据，新的Fibonacci树是原树的右子树。root = root + distance_2，修改distance_1和distance_2：distance_1 = distance_1 – distance_2，distance_2 = distance_2 – distance_1。
(3) 若根结点的数据值大于给定值x，则必须搜索第Fib(a-1)个数据之前的数据，新的Fibonacci树是原树的左子树。root = root – distance_1，修改distance_1和distance_2：temp = distance_1，distance_1 = distance_2，distance_2 = temp – distance_2。
下面给出非递归的Fibonacci搜索算法：
#include "dataList.h"
template
int i = 1, root, dis1, dis2;
while ( Fib ( i ) < CurrentSize ) i++;//确定Fibnacci数的阶数
root = Fib ( i-1 ); dis1 = Fib ( i-2 ); dis2 = Fib ( i-3 );
while ( dis2 != 0 ) {
switch ( compare ( Element[root].key, value ) ) {
case '=' :return root;//搜索成功, 返回满足要求的位置
case '>' :root = root - dis1; //左缩搜索区间
temp = dis1;dis1 = dis2;dis2 = temp – dis2;
break;
case‘<’ :root = root + dst2;//右缩搜索区间
dis1 = dis1 – dis2;dis2 = dis2 – dis1;
break;
}
}
return –1;
}
template
if ( a – b == 0 ) return‘=’;
else if ( a – b < 0 ) return ‘<’;
else return‘>’;
}
7-29 假设二叉树存放于二叉链表中，树中结点的关键码互不相同。试编写一个算法，判别给定的二叉树是否二叉搜索树。
【解答】
判断给定二叉树是否二叉搜索树，可以采用递归算法。对于树中所有结点，检查是否左子树上结点的关键码都小于它的关键码，右子树上结点的关键码都大于它的关键码。相应算法如下：
template
void BinaryTree
//在以t为根的子树中递归判断该子树是否二叉搜索树。是，bs返回1，否则bs返回0 if ( t != NULL ) {
if ( ( t->leftChild == NULL || t->data > t->leftChild->data ) &&
( t->rightChild == NULL || t->data < t->rightChild->data ) ) {
bs = 1;
binSearchTree ( t->leftChild, bs );//递归到左子树判断
if ( bs ) binSearchTree ( t->rightChild, bs );//递归到右子树判断
}
else bs = 0;
}
}
7-30 回答下列问题：
(1) 直接在二叉搜索树中搜索关键码为key的对象与从中序遍历输出的有序序列中顺序搜索关键码为key的对象，其效率是否相同？
(2) 输入关键码有序序列来构造一棵二叉搜索树，然后对此树进行搜索，试分析其效率。【解答】
(1) 效率不相同。在二叉搜索树中平均搜索效率高于有序表的顺序搜索。
(2) 其效率等同于有序表的顺序搜索。因为按关键码有序序列构造出来的二叉搜索树是一棵向右倾斜的单支树，失去了二叉搜索树的优点。
7-31设在一棵二叉搜索树的每个结点中，含有关键码key域和统计相同关键码结点个数的count域，当向该树插入一个元素时，若树中已存在与该元素的关键码相同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。
【解答】
template
void BST
//向二叉搜索树中插入一个元素value, 若树中存在该元素, 则将匹配结点中的count域
//的值加1即可
BstNode
while ( p != NULL ) { //在树中搜索关键码为value的结点pr = p;
if ( value == p->data ) break;
else if ( value < p->data ) p = p->leftChild;
else p = p->rightChild;
}
if ( p != NULL ) p->count++; //若元素已存在，将其count域的值增1
else {//否则建立新结点并插入到合适位置BstNode
s->data = value;s->count = 1;
s->leftChild = s->rightChild = NULL;
if ( pr == NULL ) root = s; //空树情形
else if ( value < pr->data ) pr->leftChild = s; //非空树情形, 接在双亲下面
else pr->rightChild = s;
}
}
7-32 设有一个关键码的输入序列{ 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
(1) 构造平衡二叉搜索树的过程
(2) 计算在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
ASL succ = (1/9)*(1+2*2+3*4+4*2)=25/9
ASL unsucc = (1/10)*(3*6+4*4)=17/5
《数据结构》习题汇编07 第七章 图 试题
第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。
数据结构 第七章 图
7.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m
数据结构试题：第七章的练习
数据结构复习题：图 单选题 1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_____倍。A,1/2 B,1C,2 D,4 2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_____。 A,n B, n+1 C,n-1 D,n+e 3、具有n个顶点的无向完全图，边的总数为_____条。 A,n-1 B,n C,n+1 D,n*(n-1)/2 4、在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于_____ 。 A,i+j B,i-j C,1D,0 5、在n个结点的线索二叉树中,线索的数目为______. A,n-1 B,n C,n+1 D,2n 6、在二叉排序中,凡是新插入的结点,都是没有______的. A孩子B关键字C平衡因子D赋值 7、深度为5的二叉树至多有_______个结点. A,16 B,32 C,31 D,10 8、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为_________。 A,s B,s-1 C,s+1 D,n 9、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为_________。 A,s B,s-1 C,s+1 D,2s 10、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为_________。 A,n B,e C,n+e D,2e 11、在一个具有n个顶点的无向完全图中，所含的边数的_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 12、在一个具有n个顶点的有向完全图中，所含的边数为_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 13、在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为
数据结构第七章图
数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：
数据结构第7章习题答案
第7章 《图》习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 A ．0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 1 3 4 2 5 6 D. 0 3 6 1 5 4 2 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3
数据结构第7章 图习题
第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。
A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量
数据结构第七章图练习及答案
1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧
关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）
数据结构第七章图练习及答案
数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧
(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径
最新数据结构第7章-答案
一、单选题 C01、在一个图中，所有顶点的度数之和等于图的边数的倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A)1/2 B)1 C)2 D)4 B03、有8个结点的无向图最多有条边。 A)14 B)28 C)56 D)112 C04、有8个结点的无向连通图最少有条边。 A)5 B)6 C)7 D)8 C05、有8个结点的有向完全图有条边。 A)14 B)28 C)56 D)112 B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A)O(n) B)O(e) C)O(n+e) D)O(n2) C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2 B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6 D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3 A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2 A13、图的深度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 D14、图的广度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 B15、任何一个无向连通图的最小生成树。 A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在 A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A)n、2e B)n、e C)n、n+e D)2n、2e C17、判断有向图是否存在回路，可以利用___算法。 A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历 A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目
数据结构第7章 图习题
习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
数据结构作业系统_第七章答案
7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1)
数据结构第七章图练习及答案
一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n
11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。
数据结构作业系统 第七章答案
③试基于图的深度优先搜索策略写一算法， 判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(i≠j)。注意：算法中涉及 的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1;
数据结构第7章图习题
单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
数据结构第7章
第7章搜索 一、复习要点 本章讨论了搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和A VL树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有n个对象的二叉搜索树中，搜索效率最高的是高度最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是A VL树。在A VL树的讨论中，4种平衡旋转，选择参加平衡旋转的3个结点是关键，必须加以注意。 本章复习的要点是： 1、基本知识点 理解理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握A VL树的构造、插入、删除时的调整方法及其性能分析，重点是A VL树的定义、平衡化旋转、A VL树的插入和删除、A VL树的高度。 2、算法设计 用有序链表表示集合时的求集合的并、交、差的算法 并查集中的构造函数、求根及合并算法 并查集中根据树的高度和根据树中结点个数进行合并的算法 设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法 有序顺序表的顺序搜索算法 有序顺序表的折半搜索的递归算法和非递归算法 二叉搜索树的搜索、插入和删除算法 计算A VL树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法 二、难点和重点 3、基本搜索方法 对一般表的顺序搜索算法(包括有监视哨和没有监视哨) 对有序顺序表的顺序搜索算法，包括递归和非递归算法 用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功与不成功)的计算。 对有序顺序表的折半搜索算法、包括递归和非递归算法 用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成功与不成功)的计算。 4、二叉搜索树 动态搜索树与静态搜索树的特性 二叉搜索树的定义、二叉搜索树上的递归和非递归搜索算法 二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算 二叉搜索树的插入与删除算法
数据结构第7章 图习题
习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。