数据结构课后习题参考答案资料

1、.选择题：CCBDCA.试分析下面各程序段的时间复杂度。O (1)O (m*n)O (n2)O (log 3n)(5)因为x+共执行了 n-1+n-2+1= n(n-1)/2 ,所以执行时间为 O ( n2)(6) O( . n )第2章线性表.选择题babadbcabdcddac.算法设计题(6)设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next;法设计题(2)回文是指正读反读均相同的字符序列，如“abba”和“ abdba”均是回文，但“ good”不是回文

2、。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)?根据提示，算法可设计为：合应用题(1)已知模式串t= abcaabbabcab 写出用KM附求得的每个字符对应的next和nextval函数值。存放该数组所需多少单元？存放数组第4列所有元素至少需多少单元？数组按行存放时，元素 A7,4的起始地址是多少？数组按列存放时，元素 A4,7的起始地址是多少？每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至 1到11。(1) 242(2) 22(3) s+182(4) s+142(4)请将香蕉banana用工具H( ) Head( ) , T( ) Tai

3、l() 从L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H (H (T (H (T (H (T (L)(5)写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为 A-Z这26个字母和0-9这10个数字)。void Count ()/统计输入字符串中数字字符和字母字符的个数。int i , num36char ch ;/初始化表示输入字符串结束。 /算法结束。if (0 =ch= 9) i=ch 48;numi+else ifforfor；(，A，=ch=，Z，) i=ch-65+10;numi+

4、printf/ 数字字符; /字母字符(i=0； i10 ； i+) / 输出数字字符的个数printf (数字% d 的个数=% dn”, i , numi);(i =10; i36 ; i+ ) /求出字母字符的个数(“字母字符% c 的个数=% dn，i +55, numi);第5章树和二叉树.选择题ADDCA CCBDC CCACC.应用题(2)设一棵二叉树的先序序列：A B D F C E G H ,中序序列：B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树(或森林)O(2)试设计另一种由二进制表示的编码万暮(3)假设用于通信白电文

5、仅由 8个字母组成，字母在电文中出现的频率分别为, 试为这8个字母设计赫夫曼对于上述实例，比较两种方案的优缺点解：方案1;哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10,按哈夫曼规则：(2,3), 6, (7,10)1 ,19, 21,32197(40)2111字母 编P对应 编码出现频率1110042001、1 一端馅三三作为-11a标存储4土杓铝41110510万案万案J wpl夕+4+5+=+= 2的物Pl编码3+=3123出现频率吉论：哈夫.3.算一设I*题写以下算法 3(1)统int Lea001010计二叉杈他叶结点个011fNode

6、CoUnt(BiTree T)00-6 if(T=NULL)101for (i =0; ilchild=NULL&T-rchild=NULL) return 1; /判断该结点是否是叶子结点(左孩子右孩子都为空)，若是则返回1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);(3)交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree &T) BiTree temp;if(T-lchild=NULL&T-rchild=NULL) return;elsetemp = T-lchild;T-lchild =

7、T-rchild;T-rchild = temp;ChangeLR(T-lchild);ChangeLR(T-rchild);1.选择题CBBBCBABAADCCDDB2.应用题(1)已知如图所示的有向图，请给出: 每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表。(2)已知如图所示的无向网，请给出：邻接矩阵；邻接表；ab4c3ba4c5d5ca3b5d5db5c5e7eb9d7f3Afd6e3g2Agd5f2h6Ahc5d4g6Ae9h5f6图无向网4A最小生成树D、弋 点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b

8、)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,f)gooOO16(a,c,f,g)16(a,c,f,g)卫(acf.d.g)S终 点集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b(3)已知图的邻接矩阵如所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。(4)有向网如图所示，试用迪杰深度优先生成树广度优先生成树斯特拉算法求出从顶 点a到其他各顶点间 的最短路径，完成表。第7章查找.选择题CDCABCCCDCBCADA.

9、应用题(1)假定对有序表：(3,4,5,7, 24, 30, 42,54,63,72,87,95)进行折半查找，试回答下列问题:画出描述折半查找过程的判定树；若查找元素54,需依次与哪些元素比较？若查找元素90,需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出判定树如下(注：mid= (1+12)/2 =6):30634 2454 7295查找元素54,需依次与 30, 63, 42, 54元素比较；查找元素90,需依次与 30, 63,87, 95元素比较；求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1+2X 2 + 4X3=17次；但最

10、后一层未满,不能用8X4,只能用5X4=20次，所以 ASL = 1/12 ( 17+20) = 37/12 (2)在一棵空的二叉排序树中依次插入关键字序列为12 , 7, 17, 11 ,16, 2, 13, 9, 21, 4,请画出所得到的二叉排序树。12 、2111621 / /4913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17, 21(5)设哈希表的地址范围为017,哈希函数为：H (key) =key%16。用线性探测法处理冲突，输入关键字序列：(10, 24, 32, 17, 31 , 30, 46, 47, 40, 63, 49),构造哈希表

11、，试回答下列问题：画出哈希表的示意图；若查找关键字63,需要依次与哪些关键字进行比较？若查找关键字60,需要依次与哪些关键字比较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：012345678910111213141516173217634924401030314647查找63,首先要与 H(63)=63%16=15号单元内容比较，即 63 vs 31 ,no;然后顺移，与46,47,32,17,63 相比，一共比较了 6次！查找60,首先要与H(60)=60%16=12号单元内容比较，但因为 12号单元为空(应当有空标记)，所以应当只比较这一次即可。对于黑色数据元素，

12、各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以 ASL=1/11 (6 + 2+3X3+6) = 23/11(6)设有一组关键字(9, 01, 23, 14, 55, 20, 84, 27),采用哈希函数：H (key) =key %7 ,表长为10,用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520比较次数11123412平均查找长度： ASLucc= (1+1 + 1+2+3

13、+4+1+2) /8=15/8以关键字 27为例：H (27) =27%7=6(冲突)H产(6+1) %10=7(冲突)H2= (6+22) %10=0(冲突) H 3= (6+33) %10=5 所以比较了 4 次。第8章排序.选择题CDBDCBCDBCBCCCA.应用题(1)设待排序的关键字序列为 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,试分别写出使用以下排序方法,每趟排序结束后关键字序列的状态。222222222102166212261022222222126281816*直接插入排序折半插入排序希尔排序（增量选取 5, 3, 1）冒泡排序快速排序简单

14、选择排序堆排序二路归并排序直接插入排序121630281016*20121630281016*20121630281016*20121628301016*20101216283016*2010121616*28302010121616*202830610121616*20286101216 16*1820折半插入排序排序过程同希尔排序（增量选取 5, 3, 1）6181216*20302810181616*203028121616* 1820 2830冒泡排序1216281016*20612161016*2061812101616* 61820101216616*1820101261616*1

15、820106121616*1820610121616*1820610121616*1820快速排序62 10 12 28 30 16* 202610122830 16*20261012 18 16 16* 20 ：2610 1216*16 18202610 1216* 1618 2061861861861861861861830182830（增量选取（增量选取（增量选取1830283028302830283028302830283016 1816 18 28 30 28 3028 305）3）1）22222222儿J厅列处IV律皮刃I）后厅列处IV律皮7简单选择排序121630281016*2

16、061630281016*2061030281616*2061012281616*2061012162816*20610121616*28 20610121616*1820610121616*182036121230303030281818181818182830 TOC o 1-5 h z 2610121616*18202830二路归并排序2 1216 3010 2816 * 206 182 12 16 3010 16* 20 286 182 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 28 30堆排序第一步，形成初始大根堆（详细过程略），第二步做堆排序。交换1与9对象从1到8重新形成堆218181612161261016*2121016*303016*16*1216121626101826101830301016121612102616*182616*18202830202830612121061021616*18216167重新形成堆1到6重新形成堆1到5重新形成堆20282028202820282830交换1与5对象从1到4重新形成堆12610121616*18202830交换1与4对象1062121616*18202830从1到3重新形成堆交换1与3对象从1到2重新形成堆交换1与2对象得到