助教：李伟力 电子科学与技术系 邮箱：lwl280@mail.ustc.edu.cn 数据结构第二次习题课 助教：李伟力 电子科学与技术系 邮箱：lwl280@mail.ustc.edu.cn

实验报告 提交格式：标题与附件名称统一为“第 几分组+学号+姓名” 内容要求：参见实验要求 提交时间：考试之前

考试安排 时间： 6月20日(周四)下午2:30-4:30 地点： 待定 时间有冲突的同学，下课到讲台登记。

树

填空题 设一棵完全二叉树具有1000个结点，则 此完全二叉树有___个叶子结点，有 ___ 个度为2的结点，有___个结点只有 非空左子树，有___个结点只有非空右 子树。

500,499,1,0 叶子数＝向上取整[n/2]＝500 ，n2=n0- 1=499。 另外，最后一结点为2i属于左叶 子，右叶子是空的，所以有1个非空左子 树。完全二叉树的特点决定不可能有左 空右不空的情况，所以非空右子树数＝0.

选择题 某二叉树的前序和后序序列正好相反， 则该二叉树一定是（ ）的二叉树。 A、空或只有一个结点 B、高度等于其结点数 某二叉树的前序和后序序列正好相反， 则该二叉树一定是（ ）的二叉树。  A、空或只有一个结点  B、高度等于其结点数  C、任一结点无左孩子  D、任一结点无左孩子 B

任何一棵二叉树的叶结点在先序、中序 和后序遍历序列中的相对次序（ ） A、不发生改变 B、发生改变 C、不能确定 任何一棵二叉树的叶结点在先序、中序 和后序遍历序列中的相对次序（ ） A、不发生改变 B、发生改变 C、不能确定 A

二叉树遍历 若已知一棵二叉树的前序序列是 BEFCGDH，中序序列是FEBGCHD，则 它的后序序列必是：？？？？？？。

思路： 前序遍历 中序遍历 二叉树 后序遍历

先序遍历 B E F C G D H 中序遍历 F E B G C H D

若已知一棵二叉树的中序序列是 FEBGCHD，后序序列必是FEGHDCB： 则它的前序序列是？

后序遍历 F E G H D C B 中序遍历 F E B G C H D

若已知一棵二叉树的前序序列是 BEFCGDH，后序序列必是FEGHDCB： 则它的中序序列是？

哈夫曼编码 假设某电文由（a,b,c,d,e,f,g,h,i）8个字母 组成，每个字母在电文中出现的次数分 别为（7,19,2,6,32,3,21,10,5），试解答 下列问题： （1）画出huffman树； （2）写出每个字母的huffman编码；

所有节点为什么都在叶子上？ 哈夫曼编码的意义 电文总长最短的二进制前缀编码。

一棵度为2的有序树与一棵二叉树有何 区别?

已知一棵度为m的树中有n1个度为1的 结点，n2个度为2的结点，...nm个度为 m的结点，问该树中有多少片叶子?   +1

二叉树与森林转换

编程题1 编写递归算法，计算二叉树中叶子结点 的数目。

思路，代码 思路：输出叶子结点比较简单，用任何一种遍历递归算 法，凡是左右指针均空者，则为叶子 int LeafCount_BiTree(Bitree T) { if(!T) return 0; //空树没有叶子 else if(!T->lchild&&!T->rchild) return 1; //左右子树为空， 返回一个叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild); //左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree

编程题 2 编写算法判别给定二叉树是否为完全二 叉树。 判断二叉树是否完全二叉树,是则返回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; //当p为空的时候flag置1 else if(flag) return 0; //当flag为1时，返回0 else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队 列 } } //while return 1; } //IsFull_Bitree

图

基础内容 设无向图的顶点个数为n，则该图最多有（ ）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 B D A）n*n B）n（n+1） C）n/2 D）n*（n-1） C 有向图中一个顶点的度是该顶点的（　　） A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2

实现图的广度优先搜索算法需使用的辅助数据结构为（　　） A） 栈 B） 队列 C） 二叉树 D） 树 B 实现图的非递归深度优先搜索算法需使用的辅助数据结构为（　　） A） 栈 B） 队列 C） 二叉树 D） 树 A 在一个有向图中所有顶点的入度之和等于出度之和的（　　）倍 A） 1/2 B）1 C） 2 D） 4 B 具有10个顶点的无向图至少有多少条边才能保证连通（　　） A） 9 B）10 C） 11 D） 12 A

求最小生成树的Prim算法 无向带权图如图所示，画出它的邻接矩 阵，并按Prim算法求其最小生成树

求最小生成树的Prim算法

最小生成树的Kruskal算法 无向带权图如图所示，画出它的邻接表， 并按Kruskal算法求其最小生成树

最小生成树的Kruskal算法

Dijkstra算法 利用Dijkstra算法求图中顶点A到其他各 顶点之间的最短路径。

生成树 无向带权图如图 画出它的邻接表，并按Kruskal算法求其 最小生成树

拓扑排序 有向图如图所示，试写出一种可能的拓 扑序列

图的遍历 该图从顶点1出发的深度优先搜索序列 和广度优先搜索序列 深度优先序列： 广度优先序列： 1，7，3，4，5，6，2，10，9，8 1，7，9，3，10，5，4，8，6，2

9.3 画出对长度为17的有序表进行折半查找的判定树， 并分别求其等概率时查找成功和查找不成功的ASL。

查找成功： ASL=1/17(1+2*2+4*3+8*4+2*5)=59/17 查找不成功： ASL=1/18(14*4+4*5)=38/9 在折半查找判定树中，查找不成功时的比较次数即是 查找相应外结点时与内结点的比较次数。整个判定树 代表的有序表在查找失败时的平均查找长度即为查找 每个外结点的比较次数之和除以外结点的个数。

写出判断一棵二叉树是否是二叉排序树 的算法，设二叉排序树中不存在关键字 值相同的结点 二叉排序树定义如下，二叉排序树或者是一棵空树；或者是具有下列性质的树。    1，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值    2，若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值    3，它的左右子树也分别为二叉排序树 2017/4/6

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排 序树,是则返回1,否则返回0 { int last=0,flag=1; int Is_BSTree(Bitree T)//判断二叉树T是否二叉排 序树,是则返回1,否则返回0 { if(T) {    if(T->lchild&&flag) Is_BSTree(T->lchild);    if(T->data<last) flag=0; //与其中序前驱相比较    last=T->data;    if(T->rchild&&flag) Is_BSTree(T->rchild); }   return flag; }//Is_BSTree 2017/4/6

编程题 折半查找算法有一个特点：如果待查找 的元素在数组中有多个则返回其中任意 一个，如定义数组 int a[8]={1,2,2,2,5,6,8,9};如果调用折半查找 则返回3，而有些场合要求其返回第一 个符合要求的数既a[1],试改下查找算法， 使其符合要求。 2017/4/6

int binarysearch(int number) { int mid, start = 0, end = LEN - 1; int result = -1; while (start <= end) { mid = (start + end) / 2; if (a[mid] < number) start = mid + 1; else if (a[mid] > number) end = mid - 1; else { if (number == a[mid]) { result = mid; } return result; for(result =mid;;result--) { if(a[result] != number) return result+1; } 2017/4/6

排序

排序 1.在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（ ）。 A）插入排序 B）冒泡排序 C）选择排序 D）堆排序 2.在各种排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。 A）希尔排序 B）冒泡排序 C）插入排序 D）选择排序 3.快速排序方法在（　）情况下最不利于发挥其长处。 A）要排序的数据量太大 B）要排序的数据含有多个相同值 C）要排序的数据已基本有序 D）要排序的数据个数为奇数 1.C 2.C 3. C

4．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 Ａ）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 5．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 E. 快速排序 4.C 5.C

6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,20,21,25,27,35,47,68,84 则所采用的排序方法是（　 ）。 A）选择排序 B）希尔排序 C）归并排序 D）快速排序 7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（　）。 A）插入排序 B）快速排序 C）归并排序 D）选择排序 6.D 7.A

8.一组记录的排序码为（20,29,11,74,35,3,8,56）,则利用堆排序方法建立的初始(小顶)堆为（　 ）。 A）20,29,11,74,35,3,8,56 B）3,29,8,56,35,11,20,74 C）3,8,11,20,29,35,56,74 D）20,29,3,8,11,35,74,56 9.下列关键码序列中，属于堆的是（　）。 A)（15，30，22，93，52，71） B)（15，71，30，22，93，52） C)（15，52，22，93，30，71） D)（93，30，52，22，15，71） 8.B 9.A

10.若要求尽可能快地对实数数组进行稳定的排序，则应选(　)。 A)快速排序 B)堆排序 C)归并排序 11.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。 A)起泡排序 B)快速排序 C)堆排序 D)基数排序 12.插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。( ) A)正确 B)不正确 10.C 11.C 12.B

14.直接插入排序是不稳定的排序方法。( ) A)正确 B)不正确 15.直接插入排序的最坏情况是初始序列为（ ）序。 A)正 B)反 C)正和反 D)无 16.在各排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。 A)希尔排序 B)归并排序 C)插入排序 D)选择排序 14.B 15.B 16.D

阅读以下程序 for(i=2; i<=n; i++) {    x=A[i];        j=i-1;  while(j>0&&A[j]>x) {    A[j+1]=A[j];           j--; }  A[j+1]=x  }

这一段代码所描述的排序方法称作（A） A．插入排序   B．冒泡排序    C．选择排 序       D．快速排序   这一段代码所描述的排序方法的平均执行时间为 （D）         A．O(log2n)     B．O(n)     C． O(nlog2n)    D．O(n2)   假设这段代码开始执行时，数组A中的元素已经按值 的递增次序排好了序，则这段代码的执行时间为 （B）。    A．O(log2n)    B．O(n)       C．O(nlog2n)    D．O(n2)  

谢谢！ 祝大家考试顺利！

参考文献 上届师兄的PPT 福州大学课程资源 http://ds.fzu.edu.cn/fine/resources/