数据结构与数据库 习题课（2） 2016年11月25日

目 录 一、树 二、图 三、查找 四、排序

树

课后习题   5 6 7 2 8 9 10 3 11 12 13 4 1

课后习题   5 6 7 2 8 9 10 3 11 12 13 4 1

课后习题 6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。 int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树 T 的叶子数目 { if(!T->firstchild) return 1; //叶子结点 else { count=0; for(child=T->firstchild;child;child=child->nextsib) count+=LeafCount_CSTree(child); return count; //各子树的叶子数之和 } }//LeafCount_CSTree

课后习题 int CountLeaves(BiTree T) { if (T) if (T->lchild) return CountLeaves(T->lchild) + CountLeaves(T->rchild); } else return 1 + CountLeaves(T->rchild);//注意1 return 0;

设一棵完全二叉树具有1000个结点，则此完全二叉树有___个叶子结点，有 ___ 个度为2的结点，有___个结点只有非空左子树，有___个结点只有非空右子树。 注意：完全二叉树的定义与性质

写出判断两棵给定二叉树是否相似的算法。 (注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。)

Status SimilarTree(BiTree& T1,BiTree& T2) { if(!T1) // T1 是空树 { if(!T2) return TRUE; // T2 是空树 else return FALSE; } else// T1 是非空树 return FALSE; else// T2 是非空树 { if(SimilarTree(T1->lchild,T2->lchild) && SimilarTree(T1->rchild,T2->rchild)) return TRUE; else return FALSE; } } }

编写算法判别给定二叉树是否为完全二叉树，是则返回1,否则返回0 分析:该问题可以通过层序遍历的方法来解决.不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.

int IsFull_Bitree(Bitree T) { //判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { DeQueue(Q,p); if(!p) flag = 1; else if(flag == 1) return 0; else EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } } //while return 1; } //IsFull_Bitree

图

D. 这条路径由一个边的序列构成，不包含顶点 1.所谓简单路径是指_____。 A. 任何一条边在这条路径上不重复出现 B. 任何一个顶点在这条路径上不重复出现 C. 这条路径由一个顶点序列构成，不包含边 D. 这条路径由一个边的序列构成，不包含顶点 分析：B （1）定义：若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径 （2）对于A，考虑简单回路中任何一条边不重复出现，但简单回路不是简单路径，因为前者不满足简单路径中“顶点不重复出现”的要求。

2.一个有n个顶点的无向图最多有（）条边。 A.n B.n(n-1) C. n(n-1)/2 D.2n 分析：C 总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到 顶点i是同一条边，所以总共有n(n-1)/2条边。

3.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）。 1： A.n B.n+1 C.n-1 D.n+e 2: A.e/2 B.e C.2e D.n+e 分析：A C

4.已知一个图用邻接矩阵表示，计算第i个结点的入度的方法是_______，删除所有从第i个结点出发的边的方法是______。 5.如果n个顶点的图是一个环，则它有 ____棵生成树。 6. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为_______。 7.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为__ 。 分析：4.第i列非零元素之和 将矩阵第i行全部置为零 5.n 6. o(n*n) 7. o(n+e) 稠密图 稀疏图

1）只要无向网中有权值相同的边，其最小生成树就不可能是唯一的。 分析：错误

证明题：MST性质证明 设无向图N=(V, E),U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U, v∈V-U，则必存在一棵包含边(u,v)的最小生成树。 15 25 8 11 U V-U

将边(u,v)加入到T中时，由生成树的定义，T必存在一条包含(u,v)的闭合回路。 15 25 8 11 U V-U 设无向图N=(V, E),U是顶点V的一个非空 子集。若(u,v)是一条具有最小权值的边， 其中u∈U, v∈V-U，则必存在一棵包含 边(u,v)的最小生成树。 证明： 设N的任何一棵最小生成树都不包含(u,v)，T是一棵最小生成树。 将边(u,v)加入到T中时，由生成树的定义，T必存在一条包含(u,v)的闭合回路。 T上必存在另一条边(u’,v’)，其中u’∈U, v’∈V-U，且u和u’之间，v和v’之间均有路径相通。 删去边(u’,v’)，可消去回路，同时得到另一棵生成树T’。 由于(u,v)的代价不高于(u’,v’)，则T’的代价不高于T，T’是包含(u,v)的一棵最小生成树，与假设矛盾。

如右图所示，设源点为A，求源点 到其它各个顶点的最短路径 结果如下表所示 step S w D:B D:C D:D D:E D:F D:G {A} - 1 2 3 ∞ {AB} B {ABC} C {ABCE} E 4 {ABCED} D 6 5 {ABCEDG} G {ABCEDGF} F

7.5 试利用Dijkstra算法求图7-5中顶点A到其他各顶点之间的最短路径。要求写出执行算法过程中，数组D、P和S各步的状态。 作业题目分析 7.5 试利用Dijkstra算法求图7-5中顶点A到其他各顶点之间的最短路径。要求写出执行算法过程中，数组D、P和S各步的状态。 G A B D C E F 图7-5 15 12 2 5 6 8 4 9 10 3

查找

9.1 若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试 在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？ （1）查找不成功，即表中没有关键字等于给的值K的记录； （2）查找成功，且表中只有一个关键字等于给定值K的记录； （3）查找成功，且表中有若干关键字等于给定值K的记录，要求找出所 有这些记录。 答： （1）相同，有序n+1; 无序n+1 (P218) （2）相同，有序(n+1)/2；无序(n+1)/2 （3）不相同，对于有序表，找到了第一个与K相同的元素后，只要再找到 与K不同的元素，即可停止查找；对于无序表，则要一直查找到最后一 个元素。 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

9. 3 画出对长度为13的有序表进行折半查找的判定树，并分别求其等概 率时查找成功和查找不成功的ASL。 答：查找成功： ASL = （1 9.3 画出对长度为13的有序表进行折半查找的判定树，并分别求其等概 率时查找成功和查找不成功的ASL。 答：查找成功： ASL = （1*1+2*2+3*4+4*6）/13 = 41/13 查找失败： ASL = （2*3）/14+（4*12）/14 = 27/7 （P220:查找不成功的过程就是走了一条从根节点到外部节点的路径， 和给定值进行比较的关键字个数等于该路径上内部结点个数） 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

9.4 已知如下所示长度为12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec) 表中，每个元素的查找概率分别为： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (1)若对该表进行顺序查找，求查找成功的平均查找长度； (2)画出从初态为空开始，依次插入结点，生成的二叉排序树； (3)计算该二叉排序树查找成功的平均查找长度； (4)将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排 序树。 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

（1） ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02 +10*0.03+11*0.1+12*0.07=5.43 或者 ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4 *0.02+3*0.03+0.1*2+0.07=7.57 （2）画出初始为空，依次插入结点，生成的二叉排序树 (不是按照概率而是按照字母做二叉排序树，此题的题干没有表述清楚) 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

（3）该二叉排序树查找成功的平均查找长度。 ASL=0. 1+2. (0. 25+0. 05)+3. (0. 13+0. 01+0 （3）该二叉排序树查找成功的平均查找长度。 ASL=0.1+2*(0.25+0.05)+3*(0.13+0.01+0.06)+4*(0.11+0.07+0.02)+(0.03+ 0.07)*5+6*0.1=3.2 （4）将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序 树 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

9.5已知关键字序列{10,25,33,19,06,49,37,76,60}，哈希地址空间为0～ 10，哈希函数为H (Key)=Key % 11, 求： （1）用开放定址线性探测法处理冲突，构造哈希表HT1，分别计算在等 概率情况下HT1查找成功和查找失败的ASL； HT1：HT1[10] = 10; HT1[25]=3; HT1[33]=0; HT1[19]=8; HT1[06]=6; HT1[49]=5; HT1[37]=4; HT1[76]=10; HT1[60]=5. 查找成功ASL：(7+3+3)/9=1.44; 查找失败ASL：(3+2+1+7+6+5+4+3+2+1+4)/11=3.45. 1 2 3 4 5 6 7 8 9 10 33 76 25 37 49 06 60 19 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

9.5已知关键字序列{10,25,33,19,06,49,37,76,60}，哈希地址空间为0～ 10，哈希函数为H (Key)=Key % 11, 求： （2）用开放定址二次探测法处理冲突，构造哈希表HT2，计算在等概率 情况下HT2查找成功的ASL； HT2：HT1[10] = 10; HT1[25]=3; HT1[33]=0; HT1[19]=8; HT1[06]=6; HT1[49]=5; HT1[37]=4; HT1[76]=10; HT1[60]=5. 查找成功ASL：(7+3+5)/9=1.67. 1 2 3 4 5 6 7 8 9 10 33 60 25 37 49 06 19 76 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

9.5已知关键字序列{10,25,33,19,06,49,37,76,60}，哈希地址空间为0～ 10，哈希函数为H (Key)=Key % 11, 求： （3）用拉链法解决冲突，构造哈希表HT3，计算HT3在等概率情况查找 成功的ASL。 0 -> 33 1 2 3 -> 25 4 -> 37 5 -> 49 -> 60 6 -> 06 7 8 -> 19 9 10 -> 10 -> 76 查找成功ASL：(7+2+2)/9=1.22. 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

课堂测试题： 1. 在二叉排序树中，凡是新插入的点，都是没有_____的。 A. 孩子 B. 关键字 C. 平衡因子 D. 赋值 2 课堂测试题： 1.在二叉排序树中，凡是新插入的点，都是没有_____的。 A. 孩子 B. 关键字 C. 平衡因子 D. 赋值 2.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各 元素等概率情况下，查找成功所需的平均比较次数为_____。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 3.如下图所示的一棵二叉排序树，其不成功的平均查找长度是_____。 A. 21/7 B. 28/7 C. 15/6 D. 21/6 A B A 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率 相同，假设采用顺序查找来确定结点所在的块，则每块分为_____个结点 最佳。 A. 9 B. 25 C. 6 D. 625 (提示：教材p.226，容易证明，当s取n^1/2时，ASLbs取最小值n^1/2+1） 5.具有5层结点的AVL树，至少有_____个结点。 A. 10 B. 12 C. 15 D. 17 6.下面关于B-树和B+树的叙述中，不正确的结论是______。 A. B-树和B+树都能有效地支持顺序查找 B. B-树和B+树都能有效地支持随机查找 C. B-树和B+树都是平衡的多路查找树 D. B-树和B+树都可以用于文件索引结构 B B A 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

7.设哈希表长m=12，哈希函数H(key)=key MOD 11。表中已有4个结点， addr(15)=4,，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用 二次探测再散列法处理冲突，则关键字为49的结点的地址是_____。 A. 8 B. 3 C. 5 D. 9 D 1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

8. 写出折半查找的递归算法 int bin_search(int key[],int low, int high,int k) { {       int mid;       if(low>high)           return -1;       else{           mid = (low+high) / 2;           if(key[mid]==k)               return mid;           if(k>key[mid])               return bin_search(key,mid+1,high,k); /*在序列的后半部分查找*/           else               return bin_search(key,low,mid-1,k); /*在序列的前半部分查找*/       }   }  1. 没有弄清楚<>()的区别 或者说混淆了 以及他们所代表的箭头是什么 2. 把两个图画在一起了 而且有些还不作区别说明 3. 个别题目没看清，少画了几个

排序

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态（从小到大） （1）直接插入排序 （2）希尔排序（增量d=[5,2,1]） （3）快速排序 （4）堆排序（大根堆） （5）归并排序 （6）直接选择排序

以数组(256,301,751,129,937,863,742,694,076,438)为例，执行 以下排序算法，写出每一趟排序结束时的数组状态 （1）直接插入排序 第一趟： (256,301),751,129,937,863,742,694,076,438 第二趟： (256,301,751),129,937,863,742,694,076,438 第三趟： (129,256,301,751),937,863,742,694,076,438 第四趟： (129,256,301,751,937),863,742,694,076,438 第五趟： (129,256,301,751,863,937),742,694,076,438 第六趟： (129,256,301,742,751,863,937),694,076,438 第七趟： (129,256,301,694,742,751,863,937),076,438 第八趟： (076,129,256,301,694,742,751,863,937),438 第九趟： (076,129,256,301,438,694,742,751,863,937)

以数组(256,301,751,129,937,863,742,694,076,438)为例，执行以 下排序算法，写出每一趟排序结束时的数组状态 （2）希尔排序（增量d=[5,2,1]） 第一趟： 256 863 301 742 751 694 129 076 937 438 256,301,694,076,438,863,742,751,129,937 第二趟： 256 694 438 742 129 301 076 863 751 937 129,076,256,301,438,751,694,863,742,937 第二趟： 076,129,256,301,438,694,742,751,863,937

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态 （3）快速排序 第一趟： (076,129),256,(751,937,863,742,694,301,438) 第二趟： 076,129,256,(438,301,694,742),751,(863,937) 第三趟： 076,129,256,301,438,(694,742),751,863,937 第四趟： 076,129,256,301,438,694,742,751,863,937

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态 （4）堆排序（大根堆） 第一趟： (937,694,863,256,438,751,742,129,076,301)建立初始大根堆

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态 （4）堆排序（大根堆） 第一趟： (937,694,863,256,438,751,742,129,076,301)建立初始大根堆 第二趟：

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态 （4）堆排序（大根堆） 第一趟： (937,694,863,256,438,751,742,129,076,301)建立初始大根堆 第二趟： (863,694,751,256,438,301,742,129,076),937

以数组(256,301,751,129,937,863,742,694,076,438)为例，执行 以下排序算法，写出每一趟排序结束时的数组状态 （4）堆排序（大根堆） 第一趟： (937,694,863,256,438,751,742,129,076,301) 建立初始大根堆 第二趟： (863,694,751,256,438,301,742,129,076),937 第三趟： (751.694.742.256.438.301.742.129),863.937 第四趟： (742,694,301,256,438,129,076),751,863.937 第五趟： (694,438,301,256,076,129),742,751,863.937 第六趟： (438,256,301,129,076),694,742,751,863.937 第七趟： (301,256,076,129),438,694,742,751,863.937 第八趟： (256,129,076),301,438,694,742,751,863.937 第九躺： 076,129,256,301,438,694,742,751,863,937

以数组(256,301,751,129,937,863,742,694,076,438) 为例，执行以下排序算法，写出每一趟排序结束 时的数组状态 （5）归并排序 第一趟： [256],[301],[751],[129],[937],[863],[742],[694],[076],[ 438] 第二趟： [256,301],[129,751],[863,937],[694,742],[076,438] 第三趟： [129,256,301,751],[694,742,863,937],[076,438] 第四趟： [129,256,301,694,742,751,863,937],[076,438] 第五趟： [076,129,256,301,438,694,742,751,863,937]

以数组(256,301,751,129,937,863,742,694,076,438)为例，执行 以下排序算法，写出每一趟排序结束时的数组状态 （6）直接选择排序 第一趟： 076,301,751,129,937,863,742,694,256,438 第二趟： 076,129,751,301,937,863,742,694,256,438 第三趟： 076,129,256,301,937,863,742,694,751,438 第四趟： 076,129,256,301,937,863,742,694,751,438 第五趟： 076,129,256,301,438,863,742,694,751,937 第五趟： 076,129,256,301,438,742,863,694,751,937 第六趟： 076,129,256,301,438,742,694,863,751,937 第七躺： 076,129,256,301,438,742,694,751,863,937 第八趟： 076,129,256,301,438,742,694,751,863,937 第九趟： 076,129,256,301,438,742,694,751,863,937

1.在下列排序算法中，时间复杂度不受数据初始特 性影响，恒为O(n2)的是（ ）。 A）插入排序 B）冒泡排序 C）选择排序 D）堆 排序 2.对n个不同的排序码进行冒泡排序,在元素无序的 情况下比较的次数最多为（ ）. A）n+1 B）n C）n-1 D） n(n-1)/2 3.插入排序算法在每一趟都能选取出一个元素放在 其最终的位置上。( ) A)正确 B)不正确

1.在下列排序算法中，时间复杂度不受数据初始特 性影响，恒为O(n2)的是（C）。 A）直接插入排序 B）冒泡排序 C）直接选择排 序 D）堆排序

2.对n个不同的排序码进行冒泡排序,在元素无序的 情况下比较的次数最多为（D） A）n+1 B）n C）n-1 D） n(n-1)/2 解： 比较次数最多时元素是逆序的,需要n-1趟排序 第一趟,比较n-1次,确定第n个数据元素 第二趟,比较n-2次,确定第n-1个数据元素 第三趟,比较n-3次,确定第n-2个数据元素 … 第n-1趟,比较1次,确定第1、2个数据元素 总的比较次数=(n-1)+(n-2)+…+1=n(n-1)/2 n-1个

3.插入排序算法在每一趟都能选取出一个元素放在 其最终的位置上。( B ) A)正确 B)不正确 第一趟： (256,301),751,129,937,863,742,694,076,438 第二趟： (256,301,751),129,937,863,742,694,076,438 第三趟： (129,256,301,751),937,863,742,694,076,438 第四趟： (129,256,301,751,937),863,742,694,076,438 第五趟： (129,256,301,751,863,937),742,694,076,438 第六趟： (129,256,301,742,751,863,937),694,076,438 第七趟： (129,256,301,694,742,751,863,937),076,438 第八趟： (076,129,256,301,694,742,751,863,937),438 第九趟： (076,129,256,301,438,694,742,751,863,937)

能否用小于等于2n-3次的方法寻找到最大值和最小 值？ 对于一个长度为n的数组[a1,a2,…,an]，通常来说， 寻找一个最大值需要n-1次，再在剩下的n-1个数中 寻找最小值需要n-2次，因此，从数组中选择最大 值和最小值需要（n-1）+（n-2）=2n-3次 能否用小于等于2n-3次的方法寻找到最大值和最小 值？ 解：利用快速排序的思想，利用a1 为支点，将数组分为两个表，需要比较n-1次，设小于a1 表长为x，小于a1 表长为y。 对于左子表，需要比较x-1次 对于右子表，需要比较y-1次 共需要比较(n-1)+(x-1)+(y-1)=n+(x+y)-3=2n-4

已知一个单链表由3000个元素组成，每个元素是 一整数，其值在1~1000000之间。试问，在排序算 法中，哪些排序算法比较适用于链表的排序问题 ？ 解：理论排序算法均可实现。 但是单链表的特点是顺序查找并进行操作， 所以比较适用于单链表的排序方法有：直接插入排序，起泡排序，简单选择排序。