内容发布更新时间 : 2024/11/8 18:38:21星期一 下面是文章的全部内容请认真阅读。
③ 数组按行存放时，元素A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素A[4,7]的起始地址是多少？
每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
（1）242 （2）22 （3）s+182 （4）s+142
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从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，num[36]； char ch；
for（i＝0；i<36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符 else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符
for（i=0；i<10；i++） // 输出数字字符的个数 printf（“数字％d的个数＝％d\\n”，i，num[i]）； for（i＝10；i<36；i++）// 求出字母字符的个数 printf（“字母字符％c的个数＝％d\\n”，i＋55，num[i]）； ｝// 算法结束。
第5章 树和二叉树
1．选择题
ADDCACCBDCCCACC 2．应用题
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
AB BAC CA
DnullEC
D F
EMG
H
BMDEFFGHGH
(1) (2)
（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
① 试为这8个字母设计赫夫曼编码。
② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32
（100）
0 1 （40） （60） 19 21 32 （28） 0 1 0 1 （17） （11） 19 21 32 0 1 7 10 6 （5）
0 1 0 1 2 3
7 10 6 0 1
2 3
方案比较： 字母对应出现字母对应出现 编号 编码 频率 编号 编码 频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 4 1110 0.06 4 011 0.06 10 0.32 5 100 0.32 5 6 101 0.03 方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码
3．算法设计题
以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。 int LeafNodeCount(BiTree T) {
if(T==NULL)
return 0; //如果是空树，则叶子结点个数为0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); }
（3）交换二叉树每个结点的左孩子和右孩子。 void ChangeLR(BiTree &T) { BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; } ChangeLR(T->lchild); ChangeLR(T->rchild); }
第6章 1．选择题
CBBBCBABAADCCDDB 2．应用题
（1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
图
（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树
??43?????? ? 4 ? 5 59??????3 5 ? ? 5 ? ? ? 5 ? ?? ??55?7654???9?7?3??? ????63?2???? ????5?2?6??????54??6??? ? a b c d e f g h → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f
2 → c 5 → d 4
5 5 7 3 2 6 6
→ d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^
9 ^ 5 ^
图6.28 无
6 → g 5 → h 4^ （3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图6.29所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
图6.29 邻接矩阵
D 终点 b c d e f g S 终点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b} 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) 15 (a,b) 14 (a,c,f,d,g) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6