Question

数据结构的几个题目,求高手解答(急)---

（1）证明：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。
（3）已知某系统在通信联络中只可能出现A、B、C、D、E、F、G、H八种字符，其频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试设计其哈夫曼编码。
（4）如果将交换语句看作基本操作，请指出以下算法的语句频度以及时间复杂度。
Void bubble-sort(int a[], int n)
{
for(i=n-1;change=1;i>1 && change;--i)
{
change=0;
for(j=0;j<i;++j)
if (a[j]>a[j+1])
{
a[j]←→a[j+1];
change=1}
}
}
}
（5）已知数据表为（48，70，33，65，24，56，12，92，86，22），写出采用快速排序算法进行排序的详细过程及结果。
四．算法设计
（1）假定数据域为整数类型的线性单链表定义如下：
typedef struct Lnode
{
int data;
struct Lnode *next;
}Lnode, *LinkList;
现有头指针为La和Lb的两个有序（从小到大）链表，它们均附设头结点，头结点的数据域保存着链表的长度信息。将两者合并为以Lc为头指针的链表，要求合并后表内数据元素仍然按从小到大的顺序排列，且新链表也附设一个头结点保存长度信息。请给出算法实现。
实现该算法的函数首部如下：
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
（2）假定数据域为字符类型的二叉链表定义如下：
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, * BiTree;
设计算法实现建立一个二叉链表，要求按先序遍历的次序输入二叉树中结点的值（一个字符），其中’#’字符表示空树。
实现该算法的函数首部如下：
int CreateBiTree(BiTree &T)
（3）假定静态查找表的类型定义如下：
typedef struct
{
int key;
Elemtype elem;
}Node;
typedef struct
{
Node data;
int length;
}SSTable;
设计算法实现在静态有序表ST中折半查找关键字为key的数据元素,若找到，则算法返回该元素在表中的位置，否则返回0。
实现该算法的函数首部如下：
int SearchBin(SSTable ST, int key)
（4）假定数据域为整数的顺序表定义如下：
typedef struct Lnode
{
int data[100];
int length;
}SqList;
现有La和Lb的两个有序（从小到大）顺序表，将两者合并为顺序表Lc，要求合并后表内数据元素仍然按从小到大的顺序排列。请给出算法实现。
实现该算法的函数首部如下：
void MergeList_L(SqList La, SqList Lb, SqList &Lc)
（5）以T为头指针的二叉排序树的类型定义如下：
typedef struct
{
int key;
Elemtype elem;
}Node;
typedef struct BSTNode
{
Node data;
struct BSTNode *lchild, *rchild;
} BSTNode, * BSTree;
设计算法实现在以T为头指针的二叉排序树中查找关键字为key的数据元素。如果找到，算法返回指向该结点的指针；如果没找到，算法返回空指针。
实现该算法的函数首部如下：
BSTree SearchBSTree(BSTree T, int key)

PS:求高手帮助,不甚感激

Answer 1

hj