数据结构C语言版习题解答

1、设n是正整数。试写出下列程序段中用记号“标注的语句的频度:(2) i=1; k二0;do k+二10*i;i+；)whi Ie (i <=n-1)当nh时，执行1；当n>二2时，执行n-1次；(3) i=1; k=0;do k+ 二 10*i; i+;)whi I e (i二二n);当n二2时，执行2次；当n!二2时，执行1次；(4) i=1; j二0;whi le(i+jWn) if(i<j) i+; eIse j+;)执行n次；(5) x二n; y二0;如 左壬(_沪咻+ 1严+ 2)., a)逆置为(务心l-o6a2, ai).,an)。试写一时间复杂度为0(n)的算法

2、，将L改造为 L二(ait 83,an> ,a© a2)。void Reform(DuLinkedList &L). 4, 2的顺序重排双向循环链表L中的所有结点p=: whi le(p->next!=L&&p->next->next!=L) p->next=p->next->next: p=p->next;到数字直接发送2遇到'('直接入栈3遇到')'则将栈内元素发送直至遇到'('4.栈空则直接入栈5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈 int Ra

3、nkOfOperator (char c) switch (c) case1: return -1;case'(':return 0;case + case'-1: return 1;case *casecase')':return 2;int Precede (char cf char ch)return RankOfOperator (c)>RankOfOperator (ch); void Express ionTOPoIandStyIe (char suffix,char *exp)Stack s; InitStack (s,100); i

4、nt i二0; char c;whi le(*exp) if (isdigital (*exp)suff i xi +=*exp;e I se switch(*exp) case ' (' : push(s,'case ')'： whiIe(c=pops(s)!='(')suffixi+二c;break;defauIt: i f (IsEmpty(s)push (s, *exp);e I se suff ixi+二pop(s);exp；all a22為 3«345a44a2m-L2ntaij 2m-1.2m2m. 2m写出由一对

5、下标(i, j)求k的转换公式。因为i行前有2(i-1)个元素。现考虑i行情况，当j是奇数，i行有1个元>.k=2(i-1)+1-1=2(i-1)；否则 i 行有 2 个元素,k=2(iH)+2-1=2i-1o 故：18丿为奇数川偶数或若 i 为奇数,k二2(iT)+jT二i+j-2;当 i 为偶数时,k二2i-(i-j)T二i+jT已知稀疏矩阵A4X5如下:04= 2010 0 53 0 6 00 0 0 0(1) 用三元组表作为存储结构，绘出相应的三元组表示意图;(2) 用十字链表作为存储结构，绘出相应的十字链表示意图。(1) 三元组表:1JV12115521222324642445

6、7(2) 十字链表A212A121223V424A155A246AA457A第六章数和二叉树已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点，问该树中有多少个叶子结点设叶子结点有x个，则树的结点总数为n1+n2+-nk+x;同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总 数为：n1+2* n2+k nk+1 ;_kn1+n2+nk+x= n1+2* n2+nk+1可得x二另(i_l)ni+li-2已知一棵树如图6T所示，画出与该树对应的二叉树，并写出该树的先根遍历序 列和后根遍历序列。图6-1先根遍历:ABCEIJFGKHD后根遍历:BI

7、JEFKGHCDA对应的二叉树：将如图6-2所示的森林转化为对应的二叉树。图6-2树对应的二叉树森林对应的二叉树:0已知某二叉树的中序序列为DCBGEAHFIJK,后序序列为DCEGBFHKJIAo请画出该二叉树。假设某个电文由(1 b, c, d, e, f, g. h)8个字母组成，每个字母在电文中出现的次数分别为(7, 19, 2, 6, 32, 3,21,10),试解答下列问题:(1)画出出huffman树；(2) 写出每个字母的huffman编码；a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011(3) 在对该电文进行最优二进制编码

8、处理后，电文的二进制位数。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=261写出按层次遍历二叉树的算法。思路：用队列存储结构，并用递归方法StatusLeveIOrderTraverse(BitT reeT,Status(*Visit) (TElemTypee)0123450 0 01 0 00 1 00 0 11 0 01 1 00 0 01 0 00 0 10 1 10 0 00 1 001234厂31010丄 1+2+. + (/?+1)= (将该项看作一项混入原有序列中，问题转变成n+1个元 n +12素序列的成功查找问题)C 11 CH+12. 1 + 2

9、 + + "=7723. - 1 + 2 + 一仗一1)="一 将此K项看作一项 一伙 一1)2对无序顺序表：1nC 11 n”+121+2+ 72 =n22Ln + k “ 一 k +11n + k3.=二斗 考虑最后一个记录的岀现位置i=k2n-K+12画岀对长度为17的有序表进行折半查找的判定树，并分别求其等概率时查找长度和查找失 败的ASL。159解：ASL = 1x1 + 2x2 + 3x4 + 4x815x2 =一171717KASL = 4x715x2 + 4x7 + 5x2 = 增加虚结点已知如下所示长度为 12 的表：(Jan, Feb, Mar, Apr

10、, May, Jun, July, Aug, Sept, Oct,Nov, Dec)表中，每一个元素的查找概率分别为：( )(1) 若对该表进行顺序查找，求查找成功的平均查找长度；(2) 画出从初态为空开始，依次插入结点，生成的二叉排序树；(3) 计算该二叉排序树查找成功的平均查找长度；(4) 将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树。解:(1) ASL = 0.1x1 +0.25 x2 + +0.07 xl2 = 5.43(2)与初始输入序列有关(3) AS厶= 0lxl + 025x2+ + 007x5 = 32(4) 找到Mar的直接后继，将Mar的左子树移动到最左孩子的左孩子处，然后用直接后继取代当前结点。数为 H(key)=Key%11,求:(1)用开放定址线性探测法处理冲突，构造哈希表HTJ分别计算在等概率情况下HT1查 找成功和查找失败的ASL；(2)用开放定址二次探测法处理冲突，构造哈希表HT2,计算在等概率下HT2查找成功的ASL；(3) 用拉链法解决冲突，构造哈希表HT3,计算HT3在等概率情况查找成功的ASL。解：这 9 个数的 hash 值为：10. 3. 0. 8, 6. 5, 4,10.5冲突有2个。0123456789103376