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
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的结点处理)
}