考生你好,本网站信息仅供学习交流参考使用,权威信息请以省教育考试院为准!
咨询电话:0731-88626137

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

时间:2024-07-29 访问量:0

三、应用题:本大题共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<q->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的结点处理)

}

上班族抢先定制【学历提升方案】
免责声明:由于考试政策、内容等各方面情况的不断调整与变化,湖南自学考试网(www.hunanzikao.com)提供的上述信息仅供参考,如对内容存在异议,请考生以权威部门公布的为准!

考试提醒

2024年湖南自学考试还有

考试时间:10月26日 - 27日

关注公众号

微信公众号
扫码关注可以更及时地获取自考政策、通知、公告以及各类学习资料、学习方法等。