2024年4月自考02142《数据结构导论》之应用算法设计题

三、应用题：本大题共5小题，每小题6分，共30分。

29、有5个元素，其入栈次序为：A、B、C、D、E,写出以元素C、D最先出栈(即C第一个且D第二个出栈)的各种可能的出栈次序。

答：C，D，E，B，A:

C，D，B，E，A:

C，D，B，A，E。

30、假设某通信系统中电文使用的字符集为{A,B,C,D,E,F,G,H},各字符在电文中出现的频率分别为：0、07,0、19,0、02,0、06,0、32,0、03,0、21和0、10。试画出哈夫曼树(要求树中任一结点的左孩子结点的权值不小于其右孩子结点的权值),并按左分支为0和右分支为1的规则分别写出与每个字符对应的哈夫曼编码。

答：

每个字符对应的哈夫曼编码分别为

A:0101 B:11 C:01111 D:0110

E:00 F:01110 G:10 H:0100

31、某有向图G如题31图所示，试画出图G的邻接表存储结构。

答：

32、已知一棵二叉排序树(结点值大小按字母顺序)的先序遍历序列为FBADCEGH,试画出此二叉排序树，并且写出此二叉排序树的后序遍历序列。

答：

后序遍历序列为CEDBHGF。

33、对关键字序列{72,87,61,23,94,16,5,58)进行堆排序，使之按关键字递减次序排列。写出排序过程中得到的初始堆和前两趟排序后的序列状态。

答：初始堆:5，23，16，58，94，72，61，87

第1趟:16，23，61，58，94，72，87，5

第2趟:23，58，61，87，94，72，16，5

四、算法设计题：本大题共2小题，每小题7分，共14分。

34、已知单链表的类型定义如下：

typedef int DataType;

typedef struct node(

DataType data;

struct node*next;

}LinkNode,*LinkList

编写一个函数DataType minValue(LinkList L),求非空的带头结点单链表L中各结点data域的最小值。

答：

DataTypeminValue(LinkList L)

{

LinkList p,q;

p=L->next;

q-p;//(初始化部分)

while(p->next!=NULL)//(循环语句及条件描述)

{

if(p->next->data            data)//(查最小值结点)    

q=p->next;

p=p->next;

}//(p指针后移)

retum(q->data);//(返回最小值)

35、已知二叉树的存储结构类型定义如下：

Typedef struct btnode

{

DataType data;

Struct btnode*lchild,*rchild

}*BinTree;

编写递归算法int CountD2Node(BinTree bt),求二叉树bt中所有度为2的结点的个数。

答：

int CountD2Node(BinTree bt)

{

int d;

if(lbt)return 0;// (对于空树，结点数为0)

d=CountD2Node(bt->lchild)+CountD2Node(bt->rchild);

// (递归求左右子树结点数)

if(bt->lchild&&bt->rchild)

returnd+1; // (度为2的结点处)

else

return d; //(度不为2的结点处理)

}