数据结构习题及答案.pdf

1 数据结构习题及答案数据结构习题及答案 2013 年 8 月 2013 年 8 月 2 第一章第五章第一章第五章 习题习题 一、 单选或填空题 1. 下列程序段中 S 语句的执行频度为 。 for(i0；in；i+ ） for(j0；ji；j+ ） S； 2. 下列算法的时间复杂度是（ ） 。 for(i0；in；i+ ） cii； 3. 算法的时间复杂度可表示为 O(1)、线性阶 、平方阶 O(n2)、对数阶 O(logn)和指数阶 O(2n)等。 4 以下关于数据结构的基本概念中，叙述正确的是 A) 数据元素是数据不可分割的最小单位。 B) 数据是数据对象的子集。 C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。 D) 数据结构在计算机中的表示又称为逻辑结构。 5. 在数据结构中，数据的逻辑结构包括（ ） 。 A) 线性结构和非线性结构 B) 逻辑结构和物理结构 C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 6. 在数据结构中，数据的存储结构包括 。 A) 线性结构和非线性结构 B) 逻辑结构和物理结构 C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 7. 线性结构的数据元素之间存在一种( )。 A一对多关系 B多对多关系 C多对一关系 D一对一关系 8. 在长度为 n 的顺序表中插入一个元素，需要平均移动 个元素。 A) n/2 B)n C) n(n- 1) D) n(n+1) 9. 在有 n 个元素的顺序表中做插入、删除运算，平均时间复杂度为 。 10. 顺序表中逻辑上相邻的元素物理位置 相邻，单链表中逻辑上相邻的元素的物理位 置 相邻。 A)必然、必然 B)必然、不一定 C)不一定、必然 D)不一定、不一定 11相对于顺序存储而言，链式存储的优点是（ ） 。 A随机存取 B节约空间 C增、删操作方便 D节点间关系简单 3 12 以下关于头结点的描述中，叙述错误 的是 A) 头结点是对链表首元结点的别称 B) 若链表中附设头结点，则头指针一定不为空 C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息 D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理 13已知 L 是无表头结点的单链表，且 P 所指结点既不是首元结点，也不是尾元结点，则 在 P 之后插入 S 所指结点，则执行（ ） 。 A) S- next=P- next； P- next=S； B) P- next=S- next； S- next=P； C) S- next=P； P- nextS； D) P- next=S； S- next=P； 14. 已知 L 是带表头结点的非空单链表， 且 P 结点是 S 结点的直接前驱。 则删除 S 结点的语 句序列为 。 I. P- next = S ;free(P) II. P- next = P- next- next; free(S) III. P- next = S- next; free(S) IV. P = P- next ;free(S) A) I 和 II 正确 B) II 和 III 正确 C) III 和 IV 正确 D) 全部正确 15. 已知 L 是带表头结点的单链表，则删除首元结点的语句序列是（ ） 。 A) L- next =L- next- next; free(L) B) P = L ;L= P- next ;free(P) C) P = L- next ; L- next= P- next ;free(P) D) P = L ;L= P- next ;free(P) 16. 已知 L 是一带有头结点的单链表的头指针，则该单链表为空的条件是 。 17. 已 知 P结 点 是 某 双 向 链 表 的 中 间 结 点 ， 则 删 除 P结 点 的 语 句 序 列 是 ， ，free(P); 18. 设将整数 1，2，3，4，5 依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进 行，则出栈序列不可能的是（ ） 。 A) 32415 B) 45231 C) 32145 D) 45321 19. 在栈中由顶向下已存放元素 c, b, a 在第 4 个元素 d 入栈前，栈中元素可以出栈，则不可 能 的出栈序列是 A) dcba B) cbda C) cdba D) cadb 20. 设有栈 S 和队列 Q，其初始状态为空，元素 a1,a2,a3,a4,a5,a6 依次入栈，出栈的元素进 入队列 Q。若元素出队列的顺序是 a2,a4,a3,a6,a5,a1，则栈的容量至少是 。 21. 某队列允许在其两端进行入队操作， 但仅允许在一端进行出队操作， 则 abcde 顺序入队， 不可能得到的顺序是（ ） 。 4 Abacde Bdbace Cdbcae Decbad 22. 设用一维数组 An存储一个栈， 令 An为栈底，用整型变量 T 指示当前栈顶位置， AT 为栈顶元素。当从栈中弹出一个元素时，变量 T 的变化为（ ） 。 A) T=T+1 B) T=T- 1 C) T 不变 D) T=n- 1 23. 在具有 m 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队首指针和队尾指 针，则判断队满的条件是（ ） A. front= (rear1) % m B. front1= rear C. front= rear D. rear= m 24. 在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队首指针和队尾指 针，则判断队空的条件是（ ） A)front= (rear1) % n B)front1=rear C)front=rear D)front=0 25. 循环队列用数组 A0m- 1存放其数据元素。设 front 指向其实际的队头，rear 指向其实 际队尾的下一个位置，则当前队列中的数据元素有 个。 26 在串的运算中，StrLength(Concat (aa，bb)的返回值为 A) 0 B) 8 C) 6 D) 4 27设 s1”I have_”，s2”a dream”，则 strcat(s1, s2)的值是 ，SubString(s1,4,3) 的值是 。 28. 设 s1”I am a student”，s2”a student”，则 Index(s1,s2)的值是 。 29. 假设有二维数组 A56，每个元素用相邻的 4 个字节存储，存储器按字节编址。已知 A 的基地址为 1000， 则数组 A 的最后一个元素 a45的第一个字节的地址是 ； 按行存 储时，元素 a14的第一个字节的地址是 ；按列存储时，元素 a25的第一 个字节的地址是 。 30. 一个非空广义表的表头（ ） 。 A一定是子表 B一定是原子 C不能是子表 D可以是原子，也可以是子表 31. 设广义表 L（(a,b),c,( )） ，则 head(L) ，tail(L) 。 二、 算法题 1. 写出下列程序段的功能。 Status A(LinkedList L) /L 是无表头结点的单链表 5 If(L L=L- next; P=L; While (P- next) P=P- next; P- next=Q; Q- next=NULL; Return OK; 2. 写出下列程序段的输出结果。 void main() Stack S; char x,y; InitStack(S); x=i; y=s; Push(S,x); Push(S,r); Push(S,y); Pop(S,x); Push(S,h); Push(S,x); Pop(S,x); Push(S,c); while (!StackEmpty(S) Pop(S,y);printf(y); printf(x); 3. 写出下列程序段的输出结果。 void main() Queue Q; InitQueue(Q); char x=e, y=c; EnQueue(Q, a);EnQueue(Q, d); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, r); while (!QueueEmpty(Q) DeQueue(Q, y); printf(y); printf(x); 4. 已知 L 是带头结点的单链表。试写一算法求该单链表的长度。 5. 已知 L 是带头结点的单链表。试写一算法在该链表上查找值为 x 的元素。 6. 将带头结点的 L 中的第 i 个数据元素删除。 7. 在带头结点的 L 中第 i 个元素之前插入数据元素 e 。 8. 正位序输入 n 个元素的值，建立带头结点的单链表 L。 9. 已知线性表中的元素以值递增有序排列，并以带有头结点的单链表作存储结构。试写一 算法删除表中所有值大于 mink 且小于 maxk 的元素，同时释放被删除的结点空间。 10. LA 和 LB 是两个数据元素按升序排列的单链表， 将 LA 和 LB 合并为有序单链表 LC。 写 出这两个有序链表合并的算法。 6 第六章习题第六章习题 一、单选或填空题 1. 已知完全二叉树的第 7 层上有 10 个叶子结点，则整个二叉树的结点数最多是 A) 73 B) 63 C) 235 D) 245 2. 300 个结点的完全二叉树的叶结点有 个。 3一个具有 1025 个结点的二叉树的高 h 为_。 A）11 B）10 C）11 至 1025 之间 D）10 至 1024 之间 4. m 叉树的第 i 层至多有 个结点 5. 将一棵有 100 个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的 编号为 1，则编号为 49 的节点的右孩子编号为（ ） 。 A99 B98 C50 D48 6把如右图所示的树转换成二叉树时，C 是（ ） A. A 的左子女 B. A 的右子女 C. B 的左子女 D. B 的右子女 7. 设森林 F 中有 3 棵树，其结点个数分别是 n1、n2 和 n3，则与森林对应的二叉树根结点 的右子树上的结点个数是 。 A) n1- 1 B)n1+n2 C) 0 D) n2+n3 8.在一颗度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，5 个度为 2 的结 点，10 个度为 1 的结点，则树 T 的叶结点个数有 个。 9. 一棵二叉树中序遍历结果为 DCBAEFG，后序遍历结果为 DCBGFEA。则此二叉树先序 遍历的结果应为 A) ABCDEFG B)ABECFDG C)AEBFCGD D)不能确定 10. 将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后根遍历是 h 的 A）先序遍历 B）中序遍历 C）后序遍历 C）层序遍历 11.现有一段电文共 100 个字符，其中 A 出现 50 次，B 出现 20 次，C 出现 5 次，D 出现 10 次，E 出现 15 次。现对这 5 个字符进行哈夫曼编码，则其平均码长为 。 二、解答题 1. 某二叉树的中序遍历结果为 DEFABCG；后序遍历结果为 FEDCBAG。 （1）画出此二叉树，并给出其先序遍历的结果。 （2）画出与这棵二叉树对应的树（森林） 。 7 2. 已知一个二叉树的先序遍历序列为：ABDGIECFH；中序遍历序列为：DIGBEAFHC。 （1）画出该二叉树 （2）画出下图所示森林对应的二叉树。 3. 某二叉树层序序列为 abcdefghij，中序序列为 bgdhjaecif。 （1）画出该二叉树； （2）画出该二叉树的后序后继线索树； （3）画出该二叉树对应的树或森林。 4. 已知某通讯用电文仅有 A、B、C、D、E、F 六个字符构成，其出现的频率分别为 26，8， 17，11，28，10，请首先建立哈夫曼树，然后给出六个字符的哈夫曼编码（注：建立哈夫曼 树时权值小的为左子树，权值大的为右子树） 。 三、算法题三、算法题 1. 以二叉链表作为二叉树的存储结构，编写以下算法： （1）求先序序列为 k 的结点的值 （2）求二叉树中叶子结点的数目 （3）交换所有结点的左右子树 （4）求二叉树的深度 A C B D E HI FG J K L 8 第七章习题第七章习题 一单选或填空题 1. 若某有向图的邻接矩阵 A 只有 0 和 1 两种元素，其中 aij1 表示有向图中存在弧， 则编号为 i 顶点的入度可用 表示。 A) 邻接矩阵中第 i 行元素之和 B) 邻接矩阵中第 i 列元素之和 C) 邻接矩阵中对角线元素之和 D) 以上均不正确 2. 使用邻接表作为某无向图的存储结构，若无向完全图中有 n 个顶点，则邻接表中必存在 个表结点。 A)n 2 B)2n C)n(n- 1) D) 2n- 1 3. 一个含有 n 个顶点和 e 条边的无向图，在其邻接矩阵存储结构中共有（）零元素。 Ae B2e Cn2- e Dn2- 2e 4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A1/2 B1 C2 D4 5下列关于图的叙述中，正确的是（ ） 、 回路是简单路径 、存储稀疏图，用邻接矩阵比邻接表更省空间 、若有向图中存在拓扑序列，则该图不存在回路 A仅 B仅、 C仅 D仅、 6. 有 n 个顶点的无向图至少有 条边才能确保是一个连通图。 7在有 n 个结点的无向图中，其边数最多为 。 8. 对于具有 n 个结点的连通图，它的最小生成树中有 条边。 A)n 2 B)n- 1 C)n(n- 1) D) n(n- 1)/2 9. 关键路径是 AOE 网中 A）从源点到汇点的最长路径 B）从源点到汇点的最短路径 C）最长回路 D）最短回路 10. 以下关于图的描述中，正确的是 A) n 个顶点的无向完全图有 2 ) 1( nn 条边。 B) 对任何用顶点表示活动的网络（AOV 网）进行拓扑排序的结果是唯一的。 C) 若图 G 的邻接矩阵是对称的，则 G 一定是无向图 D) 有向图的邻接矩阵一定是非对称矩阵 11. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（） A5 B3 C2 D1 12下图为用边表示活动的 AOE- 网。则 V8 的最早发生时间是 。 c a b e d 9 二、解答题 1. 已知某无向图的邻接表存储结构如下图所示，求解下列问题： （1）画出它的无向图； （2）画出它的的邻接矩阵存储结构； （3）从顶点 A 出发，画出其广度优先生成树。 2. 已知无向带权图 G 的邻接矩阵如下所示。 （1）从顶点 a 出发，求其深度优先生成树； （2） 从顶点 a 出发， 根据普里姆算法构造最小生成树， 过程在下面的图(1)至(5)中画出。 （3）给出邻接表存储结构； 3. 对于如下图所示的带权有向图，求解关键路径, 计算各事件（顶点）的最早发生时间和 最迟发生时间，各活动（弧）的最早开始时间和最迟开始时间。请填写在答题纸的表格中。 0 A 1 4 1 B 0 2 5 2 C 1 3 4 3 D 2 5 4 E 0 2 5 5 F 1 3 4 624 663 255 46552 356 526 f e d c b a fedcba 10 表 1 计算各事件（顶点）的最早发生时间和最迟发生时间，请填写在表 1 的空白处。 顶点 a b c d e f g h k ve 0 6 4 5 7 15 14 18 vl 0 8 10 16 14 18 表 2 计算各活动（弧）的最早开始时间和最迟开始时间，请填写在表 2 的空白处。 弧 ab ac ad be ce df eg eh fh gk hk e 0 0 0 6 4 5 7 15 14 l 3 8 10 16 14 4.对于右图，求解下列问题： （1）写出该图的邻接矩阵； （2）写出全部拓扑排序序列； （3）从顶点 V1 出发，给出深度优先遍历生成树； （4）按照迪杰斯特拉算法，求 V1 结点到各点的最 短路径，填写表 1 的空白处。 从 V1 到各终点的距离和最短路径的求解过程 终点 i=1 i=2 i=3 i=4 i=5 i=6 i=7 V2 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V3 3 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V4 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V5 13 13 - - - - - - - - - - - - - - - - V6 - - - - - - - - - - - - - - - - - - - - - - - - V7 - - - - - - - - V8 16 16 16 vj v2 v3 b d g 6 4 5 2 1 1 8 7 2 4 4 a c d e f h k 11 第八章第八章 习题习题 一单选或填空题 1已知一个长度为 11 的有序表，使用折半查找的方法，查找第 8 个元素时所需进行的关键 字比较次数为 。 2. 已知一个长度为 16 的有序表，使用折半查找的方法，查找一个不存在的元素，则所需进 行的关键字比较次数最多是 。 A4 B5 C6 D7 3. 在二叉排序树中，关键字值最大的结点 A）左指针一定为空 B）右指针一定为空 C）左右指针均为空 D）左右指针均不为空 4 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ） A95,22,91,24,94,71 B92,20,91,34,88,35 C21,89,77,29,36,38 D12,25,71,68,33,34 5AVL 树是一种平衡的二叉排序树，树中任一结点的 A左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过 1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 6. 以下关于查找方法的描述中，错误 的是 A) 平衡二叉树一定也是二叉排序树。 B) 有序表的折半查找判定树是二叉排序树。 C) 中序遍历一棵二叉排序树，可以得到其数据元素的升序排列。 D) 后序遍历一棵二叉排序树，可以得到其数据元素的降序排列。 7.下列二叉排序树中，满足平衡二叉树定义的是（ ） 8. 在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树， 在新平衡二叉树中， 关键字 37 所在结点的左、右子结点中保存的关键字分别是（ ） 12 A. 13，48 B. 24，48 C. 24，53 D. 24，90 9、从理论上讲，将数据以何（）结构存放，则查找一个数据所用时间不依赖于数据个数 n. A）二叉查找数 B）链表 C）二叉树 D）哈希表 二、解答题 1.画出对长度为 12 的有序表进行折半查找的判定树，并求其等概率查找成功时的平均查找 长度。 2.设记录关键字集合 key=33,20,53,55,23,38,40,65，选取哈希函数为 H(x)=key mod 11；解 决冲突的方法为“线性探测法” 。 （1）请按上述条件将 key 中各值依次填入下表中： （2）求该哈希表查找成功和查找不成功情况下的平均查找长度。 3.设记录关键字集合 key=32,13,49,55,22,39,20，选取哈希函数为 H(x)=key mod 7；解决冲 突的方法为“链地址法” 。 （1）画出所构造的哈希表； （2）求该哈希表查找成功和查找不成功情况下的平均查找长度。 4.设记录关键字集合 key=32,13,49,55,22,39,20，解决冲突的方法为“线性探测法” ，要求装 填因子为：0.7，哈希函数的形式为 H(x)=key mod P，散列表的地址从 0 开始。 （1）构造哈希函数； （2）画出所构造的哈希表； （2）求该哈希表查找成功和查找不成功情况下的平均查找长度。 13 第九章第九章 习题习题 一、单选或填空题 1. 数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一趟 排序后的结果。则 ABCD 四个选项中，说法正确的是 I 12，13，15，18，20，60 II 13，15，18，12，20，60 III 13，15，20，18，12，60 IV 12，13，20，18，15，60 V 13，15，18，20，12，60 A) I 快速排序；II 简单选择排序；III 直接插入排序；IV 冒泡排序；V 归并排序 B) I 冒泡排序；II 快速排序；III 归并排序；IV 简单选择排序；V 直接插入排序 C) I 快速排序；II 冒泡排序；III 直接插入排序；IV 简单选择排序；V 归并排序 D) I 直接插入排序；II 归并排序；III 快速排序；IV 简单选择排序；V 冒泡排序 2. 对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下： 第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是( ) A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法 3. 若一组记录的排序码为(45，78，56，36，40，87)，则初始小根堆的结果为 A36，45，56，78，40，87 B87，78，56，36，40，45 C40，36，45，56，78，87 D36，40，56，78，45，87 4下列排序算法中属于不稳定的排序方法是 A)直接插入排序 B)冒泡排序 C)简单选择排序 D)归并排序 5下列排序方法的时间复杂度不为线性对数阶的是 。 A）快速排序 B）2- 路归并排序 C）希尔排序 D） 堆排序 6最好和最坏时间复杂度均为 O(nlogn)且稳定的排序方法是 。 A）快速排序 B）2- 路归并排序 C）希尔排序 D） 堆排序 7. 对于快速排序，若初始关键字有序排列，则时间复杂度为 。 8分别采用堆排、快序速排序、直接插入排序和归并排序算法对初始状态为递增序列的表 按递增顺序排序，最省时间的是 算法。 二、解答题 1. 已知待排序的序列为37，65，56，8，76，3，89，34，21，46，试完成下列各题（本 题排序均指非递减有序排列） ： (1) 写出希尔排序每一趟排序的结果； （d1=5,d2 = 3,d3 = 1） (2) 写出第一趟快速排序过程及结果。 （3）画出初始堆，以及第一次交换后，经过堆调整重新形成的堆。 14 2. 已知待排序的序列为 ( 503，087，512，061，908，170，897，275，653，426，试完成 下列各题（本题排序均指非递减有序排列） ： (1) 写出直接插入排序每一趟排序的结果； (2) 写出希尔排序每一趟排序的结果； （d1=5,d2 = 3,d3 = 1） (3) 写出 2 路归并排序每一趟排序的结果。 15 第一章第一章- 第五章第五章 参考答案参考答案 一单选与填空一单选与填空 1. n(n- 1)/2 2.O(n) 3.常数阶常数阶 O(n) 4. C 5.A 6.C 7.D 8.A 9. O(n) 10.B 11.C 12.A 13.A 14.B 15.C 16.L- next=NULL 17. P- prior- next=P- next P- next - prior =P- prior 18.B 19.D 20.3 21.C 22.A 23.A 24.C 25. (rear- front+m)%m 26.D 27. I have a dream , ave 28. 6 29. 1116, 1040, 1108 30.D 31.(a,b) (c,( ) 二、算法题二、算法题 1. 程序的功能： 对长度大于等于 2 的单链表，将首元结点插入到表尾。 2. 程序的运行结果：chris 3. 程序的运行结果：card 4.- 10 题答案：. #define OK 1 #define ERROR 0 typedef int Status; typedef struct LNode int data; struct LNode *next; LNode,*LinkList; 4. 题答案 int Length(LinkList L)/求链表的长度 k=0; p=L; while (p- next) p=p- next; k+; return k; /Length 5. 题答案 LNode* Locate(LinkList L, Elemtype x)/链表上的元素查找,返回指针 p=L- next; while (p 16 return p; /Locate 6. 题答案 Status ListDelete_L(LinkList j=0; while(p- next +j; if(!(p- next)|ji- 1) return ERROR; /删除位置不合理 q=p- next; /临时保存被删结点的地址以备释放 p- next=q- next; /改变删除结点前驱结点的指针域 e=q- data; /保存删除结点的数据域 free(q); /释放删除结点的空间 return OK; /ListDelete_L 7. 题答案 Status ListInsert_L(LinkList j=0; while(p+j; /寻找第 i1 个结点 if(!p|ji1)return ERROR; /i 大于表长 + 1 或者小于 1 s= (LinkList) malloc ( sizeof (LNode); /生成新结点 s s- data=e; /将结点 s 的数据域置为 e s- next=p- next; /将结点 s 插入 L 中 p- next=s; return OK; /ListInsert_L 8. 题答案 17 void CreateList_L(LinkList L- next=NULL; r=L; /尾指针 r 指向头结点 for(i=0;idata); /输入元素值 p- next=NULL; r- next=p; /插入到表尾 r=p; /r 指向新的尾结点 /CreateList_L 9. 题答案 Status Delete_Between(Linklist p =L- next; while(p /q是最后一个不大于mink的元 素, /p 是第一个大于 mink 的元素 if(!p) return ERROR; /如果没有比 mink 更大的元素 while(p free(p); p =q- next; return OK; /Delete_Between 10. 题答案 void MergeList_L(LinkList pb=Lb- next; 18 pc=Lc=La; /用 La 的头结点作为 Lc 的头结点 while(pa pc=pa;pa=pa- next; elsepc- next=pb; pc=pb; pb=pb- next; pc- next=pa?pa:pb; /插入剩余段 free(Lb); /释放 Lb 的头结点 19 第六章第六章 参考答案：参考答案： 一单选与填空一单选与填空 1.C 2. 150 3.C 4.mi- 1 5.A 6.D 7.D 8. 86 9.A 10.B 11. 1.95 二解答题二解答题 1. （1）先序遍历：GADEFBC；二叉树的形态见下左图； （2）对应的树见下右图 2.（1）画出该二叉树； （2）画出对应的树（或森林） a cb ed f g i h a kb c f l e h d g i j 20 3. （1）二叉树 :树形结构同（2） （ 2 ） 二 叉 树 的 后 序 后 继 线 索 树 （ 3 ） 二 叉 树 对 应 的 森 林 4.（1）哈夫曼树 三、算法题答案三、算法题答案 （1） int c=0; /这里把计数器 c 作为全局变量处理,给计数器赋初值 0 void Get_PreSeq(Bitree T,int k)/求先序序列为 k 的结点的值 if(T) c+; /每访问一个子树的根都会使前序序号计数器加 1 if(c=k) printf(“Value is %cn“,T- data); return; Get_PreSeq(T- lchild, k); /在左子树中查找 Get_PreSeq(T- rchild, k); /在右子树中查找 /if /Get_PreSeq a b c j d e f h g i 8 10 C D B F A E 0 0 0 0 0 1 1 1 1 1 （2）电文中六个字符的哈夫曼编码如下： A：10 B：0110 C：00 D：010 E：11 F：0111 100 46 54 26 28 18 11 29 17 a b j d e f h g i c 21 main() . scanf(“%d“, Get_PreSeq(T,k); if(kc|klchild) / 对叶子结点计数 CountLeaf( T- lchild, count); CountLeaf( T- rchild, count); / if / CountLeaf main() . int s=0 /给计数器 s 赋初值 0 CountLeaf(T,s); . /main （3） void Bitree_Revolute(Bitree T)/交换所有结点的左右子树 if ( T ) T- lchildT- rchild; /交换左右子树 Bitree_Revolute(T- lchild); Bitree_Revolute(T- rchild); /左右子树再分别交换各自的左右子树 / if /Bitree_Revolute （4） int Depth (BiTree T ) / 返回二叉树的深度 int depthLeft,depthRight,depthval; if ( !T ) depthval = 0; else depthLeft = Depth( T- lchild ); depthRight= Depth( T- rchild ); if (depthLeft depthRight ) depthval = 1 + depthLeft; else depthval = 1 + depthRight; return depthval; 22 第七章第七章 参考答案：参考答案： 一单选与填空一单选与填空 1.B 2. C 3.D 4.B 5.C 6.n- 1 7.n(n- 1)/2 8. B 9.A 10.A 11. A 12. 15 二解答题二解答题 1. （1）无向图 （2）邻接矩阵存储结构 （3）广度优先生成树 2. （1） （3） （2） 3. 表 1 各事件（顶点）的最早发生时间和最迟发生时间为： 顶点 a b c d e f g h k ve 0 6 4 5 7 7 15 14 18 vl 0 6 6 8 7 10 16 14 18 B A F C D E 011010 100101 100100 011010 100101 010010 A B D C E F 23 表 2 各活动（弧）的最早开始时间和最迟开始时间为： 弧 ab ac ad be ce df eg eh fh gk hk e 0 0 0 6 4 5 7 7 7 15 14 l 0 2 3 6 6 8 8 7 10 16 14 关键路径为： , , , 4. (1)有向带权图的邻接矩阵为： （3）深度优先生成树。 0 10 602 30 40 1030 50 320 （2）拓扑排序有两种可能结果：V1V2V3V4V6V5V7V8 和 V1V3V2 V4V6V5V7V8 (4) 注：斜粗体的部分为所求。 从 V1 到各终点的距离和最短路径的求解过程 终点 i=1 i=2 i=3 i=4 i=5 i=6 i=7 V2 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V3 3 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V4 7 6 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - V5 13 13 12 - - - - - - - - - - - - - - - - V6 10 - - - - - - - - - - - - - - - - - - - - - - - - V7 15 - - - - - - - - V8 16 16 16 vj v2 v3 v4 v6 v5 v7 v8 V1 V2 V3 V4 V6 V5 V7 V8 24 第八章第八章 参考答案：参考答案： 一单选与填空一单选与填空 1.4 2. B 3.B 4.A 5.B 6.D 7.B 8. C 9.D 二解答题二解答题 1. 长度为 12 的有序表进行折半查找的判定树为： 等概率查找成功时的平均查找长度为： （11224354）/12=37/12 2. 成功：(1+2+2+5+1+1+1+2)/8=15/8; 不成功：(5+4+3+2+1+2+1+2+1+7+6)/11=34/11 3. 成功：ASLsucc= (1*4+2*2+3)/7=11/7; 不成功：ASLnsucc= (1+1+2+3)/7=7/7=1 4.由装填因子 0.7=n/m 可得表长为 10. 成功：(1*4+2*2+3)/7=11/7; 不成功：(3+2+1+1+6+5+4)/