软题库 移动APP 扫码下载APP 随时随地移动学习 培训课程
当前位置:信管网 >> 在线考试中心 >> 信息系统项目管理师题库 >> 试题查看
试卷名称 2008年下半年程序员考试下午真题试题(案例分析)
考试中心《2008年下半年程序员考试下午真题试题(案例分析)》在线考试
试卷年份2008年下半年
试题题型【分析简答题】
试题内容

阅读以下说明和C 函数,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
    已知某二叉树的非叶子结点都有两个孩子结点,现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下:
#define MAXLEAFNUM 30
struct node{
char ch; /*当前结点表示的字符,对于非叶子结点,此域不用*/
char *pstr; /*当前结点的编码指针,非叶子结点不用*/
int parent; /*当前结点的父结点,为0时表示无父结点*/
int lchild,rchild;
/*当前结点的左、右孩子结点,为0时表示无对应的孩子结点*/
};
struct node Ht[2 * MAXLEAFNUM]; /*数组元素Ht[0]不用*/
该二叉树的n个叶子结点存储在下标为1~n的Ht数组元素中。例如,某二叉树如图3-1所示,其存储结构如图3-2所示,其中,与叶子结点a对应的数组元素下标为1,a 的父结点存储在 Ht[5],表示为 Ht[1].parent=5。Ht[7].parent=0 表示 7 号结点是树根,Ht[7].lchild=3、Ht[7].rchild=6 分别表示 7 号结点的左孩子是 3号结点、右孩子是 6 号结点。

如果用“0”或“1”分别标识二叉树的左分支和右分支(如图 3-1 所示),从根结点开始到叶子结点为止,按所经过分支的次序将相应标识依次排列,可得到一个 0、1序列,称之为对应叶子结点的编码。例如,图3-1中a、b、c、d的编码分别是100、101、0、11。
函数LeafCode(Ht[],n)的功能是:求解存储在Ht中的二叉树中所有叶子结点(n个)的编码,叶子结点存储在Ht[1]~Ht[n]中,求出的编码存储区由对应的数组元素pstr域指示。
函数LeafCode从叶子到根逆向求叶子结点的编码。例如,对图3-1中叶子结点a求编码的过程如图3-3所示。

typedef enum Status {ERROR, OK} Status;
【函数】
    Status LeafCode(struct node Ht[], int n)
{
int pc, pf; /*pc用于指出树中的结点,pf则指出pc所对应结点的父结点*/
int i,start;
char tstr[31] = {‘\0’}; /*临时存储给定叶子结点的编码,从高下标开始存入*/
for(i=1;(1) ; i++) { /*对所有叶子结点求编码,i表示叶结点在HT数组中的下标*/
start = 29;
pc = i; pf = Ht[i].parent;
while (pf != (2) ) { /*没有到达树根时,继续求编码*/
if ( (3) .lchild == pc ) /*pc所表示的结点是其父结点的左孩子*/
   tstr[--start] = ‘0’;
else
tstr[--start] = ‘1’;
pc = (4) ; pf = Ht[pf].parent; /*pc和pf分别向根方向回退一层*/
}/* end of while */
Ht[i].pstr = (char *) malloc(31-start);
if (!Ht[i].pstr) return ERROR;
strcpy(Ht[i].pstr, (5) );
}/* end of for */
return OK;
}/* end of LeafCode */


相关试题

推荐文章
合作网站内容