数据结构期末考试试题A卷

………○…………线…………○…………订…………○…………装…………○…………内…………○…………○……

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 /* malloc()等 */

#include /* EOF(=^Z或F6),NULL */ #include

#include /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0

第 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 页