2013-2014 学年二学期数据结构期末考试模拟试卷(1~6 卷)一、应用题 (3 小题 ,共 24 分) 1．已知某字符串S 中共有 8 种字符，各种字符分别出现2 次、 1 次、 4 次、 5 次、 7 次、 3次、 4 次和 9 次，对该字符串用[0 ，1] 进行前缀编码，问该字符串的编码至少有多少位。【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路径长度 =2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为 98 位。2．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)= ［ i/2 」( 取下整数 ) ，其中 i 为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】 H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2采用链地址法处理冲突，得到的开散列表如下：平均查找长度 =(1×7+2×4+3×1)/12=18/123．分析下面各程序段的时间复杂度（1） s1(int n) { int p=1,s=0; for (i=1;i<=n;i++) { p*=i;s+=p; } return(s); } —— O(n)（2） s2(int n) x=0;y=0; For (k=1;k<=n;k++) x++; For (i=1;i<=n;i++) For (j=1;j<=n;j++) y++; —— O(n2) 1．下述算法的功能是什么? （1）（1）返回结点 *p 的直接前趋结点地址。（2）交换结点 *p 和结点 *q （p 和 q 的值不变）。1．对给定的一组权值W＝（ 5，2，9，11，8，3， 7），试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202．已知散列函数H(k)=k mod 12 ，键值序列为 (25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82) ，采用链表法处理冲突，试构造散列表。【解答】 H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10 构造的开散列表如下：3．分析下面各程序段的时间复杂度（1）for (i=0;i
