当前位置:首页计算机类软件水平考试初级程序员->阅读以下说明和C函数,将应填入(n)处的字句写在答题纸的对应

阅读以下说明和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 */

查看答案 纠错
答案:
本题解析:

(1) i<=n,或其等价表示   (2) 0 (3) Ht[pf],或(*(Ht+pf))

(4) pf       (5)&tstr[start],或tstr+start

本题考查C语言的基本控制结构、数组以及参数传递基础知识。

哈夫曼算法构造最优二叉树的过程如下。

(1)根据给定的n个权值{W 1,W2,…,Wn]构成n棵二叉树的集合F={T1,T2,…, Tn},其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左、右子树均空。

(2)在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。

(3)在F中删除这两棵二叉树,同时将新得到的二叉树加入F中。

(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是最优二叉树。

最优二叉树是从叶子到根构造起来的,每次都是先确定一棵二叉树的左、右子树,然后再构造出树根结点,因此,最优二叉树中只有叶子结点和分支数为2的内部结点。若已知叶子的数目为n,则内部结点数比叶子少1,因此,整棵树所需的存储空间规模是确定的,可以采用数组空间来存储最优二叉树。

题目中已经指出该二叉树的n个叶子结点存储在下标为1~n的Ht数组元素中,同时举例说明父结点编号为0的结点式树根结点。因此,空(1)处应填入“i<=n”。同时,除了根结点之外,每个结点都有唯一的父结点,因此到达树根的标志为结点的父结点编号为0,因此,空(2)处应填入“0”。

根据代码中pc和pf的作用:pc用于指出树中的结点,pf则指出pc所对应结点的父结点,则空(3)处应填入“Ht[pf]”,空(4)处填入“pf”使得pc回退至其父结点位置。

空(5)考查了标准函数的调用,对于函数strcpy(),其原型为char* strcpy (char*,constchar*)。两个参数都是字符指针,根据代码中tstr的作用,应将tstr+start( tstr[start]~tstr[29]存放编码)作为实参调用strcpy,因此空(5)处应填入“tstr+start”或“&tstr[start]”。

更新时间:2021-12-02 10:06

你可能感兴趣的试题

单选题

( )is that it provides guidance and direction on how quality will be managed and verified throughout the project.

  • A.Plan Quality Management
  • B.Manage Quality
  • C.Control Quality
  • D.Project Charter
查看答案
单选题

( )the process of determining,documenting,and managing stakeholder needs and requirements to meet Project objectives.

  • A.Plan Scope Management
  • B.Collection Requirements
  • C.Validate Scope
  • D.Control Scope
查看答案
单选题

The information security management system preserves the confidentiality,integrity and availability of information by applying a( ).

  • A.technology management process
  • B.resource management process
  • C.quality management process
  • D.risk management process
查看答案
单选题

( )is a decentralized database,ensure that the data will not be tampered with and forged.

  • A.Artificial intelligence
  • B.Blockchain
  • C.Sensing technology
  • D.Big datA
查看答案
单选题

( )puts computer resources on the web,and must meet the requirements of super capacity,super concurrency,super speed and super security.

  • A.Cloud computing
  • B.Big datA
  • C.Blockchain
  • D.Internet of things
查看答案
单选题

分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多于人数,故规定其中有一个人可兼完成两项任务,其余三人每人完成一项。为了花费时间最少,( )应该完成两项任务。

高级信息系统项目管理师,历年真题,2021年下半年《信息系统项目管理师》真题

  • A.甲
  • B.乙
  • C.丙
  • D.丁
查看答案
单选题

已知某公司生产AB两种产品,其中生产1件A产品需要1个单位的甲资源,3个单位的丙资源;生产1件B产品需要2个单位的乙资源和2个单位的丙资源。已知现有甲乙丙三种资源4个单位、12个单位和18个单位。通过市场预测,可知A产品的单位市场利润为2元,B产品的单位市场利润为5元。该公司获得最大的市场利润应生产A产品(68)件,此时(69)资源仍有剩余。

  • A.甲
  • B.乙
  • C.丙
  • D.甲及丙
查看答案
单选题

已知某公司生产AB两种产品,其中生产1件A产品需要1个单位的甲资源,3个单位的丙资源;生产1件B产品需要2个单位的乙资源和2个单位的丙资源。已知现有甲乙丙三种资源4个单位、12个单位和18个单位。通过市场预测,可知A产品的单位市场利润为2元,B产品的单位市场利润为5元。该公司获得最大的市场利润应生产A产品(68)件,此时(69)资源仍有剩余。

  • A.0
  • B.2
  • C.4
  • D.6
查看答案
单选题

某项目2016年投资额12万元,2018年开始取得项目的净收益(产品一原料辅料及公用工程)6万元/年,2018-2021年每年还会产生其他成本(包括人员工资、管理成本、制造成本等)1.1万元/年;増值税0.35万元/年、营业税金及附加0.05万元/年。则该项目的静态投资回收期为(66)年,截止到2021年底该项目的投资收益率是(67)。

  • A.0.25
  • B.0.33
  • C.0.35
  • D.0.6
查看答案
单选题

安全审计的手段主要包括( )。

  • A.①②③
  • B.②③④
  • C.①②④
  • D.①③④
查看答案