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

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

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

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

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

4 树

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19 二叉树与森林转换

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

21 思路，代码 思路：输出叶子结点比较简单，用任何一种遍历递归算 法，凡是左右指针均空者，则为叶子
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

22 编程题 2 编写算法判别给定二叉树是否为完全二 叉树。 判断二叉树是否完全二叉树,是则返回1, 否则返回0

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

24 代码 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

25 图

26 基础内容 设无向图的顶点个数为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/ D）n*（n-1） C 有向图中一个顶点的度是该顶点的（　　） A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2

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

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

29

30 求最小生成树的Prim算法

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

32 最小生成树的Kruskal算法

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

34

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

36

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

38

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

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

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

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

43 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

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

45 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

46 排序

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

48 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

49 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

50 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

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

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

53 阅读以下程序 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  }

54 这一段代码所描述的排序方法称作（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)  

55 谢谢！ 祝大家考试顺利！

56 参考文献 上届师兄的PPT 福州大学课程资源