阅读以下说明和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]”。
( )is that it provides guidance and direction on how quality will be managed and verified throughout the project.
( )the process of determining,documenting,and managing stakeholder needs and requirements to meet Project objectives.
The information security management system preserves the confidentiality,integrity and availability of information by applying a( ).
( )is a decentralized database,ensure that the data will not be tampered with and forged.
( )puts computer resources on the web,and must meet the requirements of super capacity,super concurrency,super speed and super security.
分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多于人数,故规定其中有一个人可兼完成两项任务,其余三人每人完成一项。为了花费时间最少,( )应该完成两项任务。
已知某公司生产AB两种产品,其中生产1件A产品需要1个单位的甲资源,3个单位的丙资源;生产1件B产品需要2个单位的乙资源和2个单位的丙资源。已知现有甲乙丙三种资源4个单位、12个单位和18个单位。通过市场预测,可知A产品的单位市场利润为2元,B产品的单位市场利润为5元。该公司获得最大的市场利润应生产A产品(68)件,此时(69)资源仍有剩余。
已知某公司生产AB两种产品,其中生产1件A产品需要1个单位的甲资源,3个单位的丙资源;生产1件B产品需要2个单位的乙资源和2个单位的丙资源。已知现有甲乙丙三种资源4个单位、12个单位和18个单位。通过市场预测,可知A产品的单位市场利润为2元,B产品的单位市场利润为5元。该公司获得最大的市场利润应生产A产品(68)件,此时(69)资源仍有剩余。
某项目2016年投资额12万元,2018年开始取得项目的净收益(产品一原料辅料及公用工程)6万元/年,2018-2021年每年还会产生其他成本(包括人员工资、管理成本、制造成本等)1.1万元/年;増值税0.35万元/年、营业税金及附加0.05万元/年。则该项目的静态投资回收期为(66)年,截止到2021年底该项目的投资收益率是(67)。
安全审计的手段主要包括( )。