………○…………线…………○…………订…………○…………装…………○…………内…………○…………○……
5．假设通信的电文由字符集a、b、c、d、e、f、g中的字母构
成。它们在电文中出现的频度分别为0.31、0.16、0.10、0.08、0.11、0.20、0.04，为这7个字母设计哈夫曼树。
答：
A0A21^1B0543^BC2C30^3D12^DEF4E51^5F14^图1图2
四、程序设计题 10分
建一个单链表，将10个学生的成绩放入单链表（学生的成绩从键盘上输入），然后再将单链表中的学生成绩打印出来。
#include \
#include
#include
#include
第 5 页，共 11 页
#define OK 1
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef int ElemType;
struct LNode {
ElemType data; struct LNode *next; };
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
Status InitList(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */ exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */ return OK; }
Status ListInsert(LinkList L,ElemType e)
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j=0;
LinkList p=L,s;
while(p&&p->next) /* 寻找第i-1个结点 */ {
p=p->next; }
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ s->data=e; /* 插入L中 */ p->next=s;
s->next=NULL;
return OK; }
第 6 页，共 11 页
………○…………线…………○…………订…………○…………装…………○…………内…………○…………○……
Status ListTraverse(LinkList L,void(*vi)(ElemType))
{ /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */ LinkList p=L->next; while(p) {
vi(p->data); p=p->next; }
printf(\
return OK; }
void visit(ElemType c) /* 与main2-1.c不同 */ {
printf(\}
int main(int argc, char* argv[]) {
LinkList L; int i,e;
i=InitList(&L);
printf(\请输入10个学生的成绩：\\n\ for(i=1;i<=10;i++) { scanf(\ ListInsert(L,e); }
printf(\在L的表尾依次插入10个学生的成绩后，输出链表结果：L=\
ListTraverse(L,visit); //************************* return 0; }
第 7 页，共 11 页
答题卡
得分 评卷人 一、 单选题：（40
分，每题2分）
题号 1 答案 题号 11 答案 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20 得分 评卷人 二、 填空题：（20
分，每空2分）
1．删除P结点的直接后继结点的语句序列是：
第 8 页，共 11 页
