软件设计师第2部分C语言类
第2部分C语言类
●试题1
阅读下列函数说明和C函数，将应填人(n)处的字句写在答题纸的对应栏内。
【函数说明】
函数TreeDelete(Bitree*root，int e)的功能是：在树根结点指针为root的二叉查找(排序)树上删除键值为value的结点，若删除成功，则函数返回O，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Node{
int data；／*结点的键值*／
struct Node：I：Lchild，木Rchild；／*指向左、右子树的指针*／
}*Bitree；
在二叉查找树上删除一个结点时，有三种情况：
①若待删除的结点P是叶子结点，则直接删除该结点；
②若待删除的结点P只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；
③若待删除的结点P有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点P的值，然后删除结点s，结点s必属于上述①、②情况之一。
【函数】
答案：(1)value 解析：value比P结点的数值小。进入左子树查找。
答案：(2)p→Lchild
解析：s用于在要删除结点的左子树上寻找最大结点。此处为s赋初始值。
答案：(3)PP=s
解析：PP用于指向s的父结点，此处先将pp指向s，然后s指向其右子结点。
答案：(4)p→Lchild
解析：若P的左子结点存在。用它来替换P。
答案：(5)pp→Lchild=c
解析：如果P是pp的左子结点，则pp的左指针指向替换结点c。否则用右指针。
●试题2
阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
图G是一个具有n个顶点的AOE网(加权有向图)，图中顶点从1～n依次编号，函数int To- plogical(LkdWDigh G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。图G的存储结构采用邻接表表示，其数据类型定义如下：
答案：(1)P＝p→nextarc
解析：此处的while循环累加当前顶点的入度，累加的方式是不断使P指向下一个弧。答案：(2)Stack[top一一]
解析：程序执行到此处时，入度为0的结点已被压入栈，此时弹出结点并赋给Wo
答案：(3)indegree[p→adjVex]一一
解析：将邻接到顶点W的各顶点的入度减一。
答案：(4)ve[W]+p→weight>ve[p→adjvex]
解析：判断最长路径长度是否需要更新。
答案：(5)ve[W]
解析：汇点的最早发生时间就是该AOE网络的关键路径长度，而汇点是从栈中弹出的最后一个顶点。
●试题3
阅读以下说明和C程序，将应填人(n)处的字句写在答题纸的对应栏内。
【说明】
并行计算中需要将N个作业分配给N个处理器同时去完成，每个处理器都能承担这N个作业，但耗时不同。下面的程序用回溯法计算总耗时最小的一种作业分配方案，在该方案中为每个处理器分配l个不同的作业。
程序中，N个作业从0开始依次编号，N个处理器也从0开始依次编号，主要的变量说明如下：
C[i][j]：将作业i分配给处理器j的耗时；
job[i]：值为0表示作业i未分配，值为j表示作业i分配给处理器j；
processor[k]：值为0表示处理器k未分配作业，值为
l表示处理器k已分配作业；
mincost：最小总耗时.
【C程序】
答案：(1)K==N或K>=N
解析：当K等于N时。表示分配最后一个任务。其后便不再进入循环。
答案：(2)processor[i]==0
解析：判断当前处理器未分配而且总费用较小时。对处理器i分配作业。
答案：(3)i
解析：表示将作业k分配给处理器i。
答案：(4)k+1
解析：开始分配第k+1个作业。
答案：(5)processor[i]=0
解析：将分配处理器i的作业撤销。以便考察其他方案。
●试题4
阅读以下函数说明、图和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
散列文件是按桶(BUCKET)存放的。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
例如：设散列函数为Hash(Key)=Key mod 6，记录的关键字序列为l2、13、128、75、81、18、14、21、l7、30、44、89、54、5、66、125、59、605，建立的散列文件内容如图2．1所示。
为简化起见，散列文件的存储单位以内存单元表示。
函数Insert(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值0；否则返回值-1。
采用的散列函数为Hash(NewElemKey)=NewElemKey％P，其中P设定的基桶数目。
函数中使用的预定义符号如下：
#define NULLKEY-1 ／*散列桶的空闲单元标识*／
#define P 6 ／*散列文件中基桶的数目*／
#define ITEMS 3 ／*基桶和溢出桶的容量*／
typedef struct BucketNode{ ／*基桶和溢出桶的类型定义*／
int KeyDam[ITEMS]；
struct BucketNode*Link；}BUCKET；
BUCKET Bucket[P]； ／*基桶空间定义*／
答案：(1)i 
答案：(1)i 解析：在基桶内循环查找插入位置，当i等于ITEMS表示查至基桶末尾。跳出for循环。 答案：(2)return 0
解析：i 答案：(3)k==ITEMS
解析：表示当前溢出桶插入不成功，前进到下一个溢出桶。
答案：(4)t==NULL(或!t)
解析：当再无可用的溢出桶时(t==NULL)，需要新申请溢出桶并将元素加入。
答案：(5)t=s
解析：将新生成的溢出桶添加至链表末尾。
●试题5
阅读以下说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
在一图像处理系统中，开发者定义了一个图像结构ImageCon，其中定义了图像应该具有的属性。当图像件的内容或状态发生变化时，与之相关联的ImageView结构的值都需要发生改变。一个ImageCon结构能够关联一组ImageView结构。当ImageCon结构的内容或状态发生变化时，所有与之相关联的ImageView结构都将被更新，这种应用被称为观察者模式。以下代码采用c语言实现，能够正确编译通过。
【c代码】
答案：(1)*func
解析：定义func类型。
答案：(2)struct ImageView*
解析：由myObs的功能可知，它是struct ImageView*类型的。
答案：(3)index-1
解析：将index-1处的值赋给loop处的值。
答案：(4)&im9或img→myObs[100p]
解析：逐个更新ImageView结构变量。
答案：(5)notifyObs(&img)
解析：通知与ImageCon相关的所有ImageView变量。
阅读以下预备知识、函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。【预备知识】
①对给定的信号集合及相应的出现概率，采用哈夫曼编码算法构造最优编码，并用结构数组存
储最优二叉树。例如，给定信号集合{a，b，C}及其出现概率0．1、0．7、O．2，可构造如图2．2所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)(见表2．1)。
●试题6
结构数组Ht的类型定义如下：
#define MAXLEAFNUM 20
struct node{
char signal； ／*当前结点表示的信号，对于非叶子结点，此域不用*／
int frequency； ／*当前结点的出现频率*／
int parent； ／*当前结点的父结点的下标，为0时表示无父结点*／
int lchild，rchild；
／*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*／
}Ht[2*MAXLEAFNUM]；
②用’0’或’1’标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用’
0’(‘1’)标识该分支。
③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由’0’、’1’组成的一个序列，称此序列为该叶子结点的前缀编码。例如图2．10所示的叶子结点a,b、C的前缀编码分别是10、0、11。
【函数说明】
函数void LeafCode(int root，int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。
在构造过程中，将Ht[p]．frequencv域用作被遍历结点的谝历状杰标志．
【函数说明】
函数void Decode(char*buff，int root)的功能是：将前缀编码序列翻译成叶子结点的信号序列并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。
答案：(1)code[cdlen]=’＼0’
解析：设置源串的串结束标志。
答案：(2)Ht[P]．parent
解析：从右子树向父结点退回。
答案：(3)cdlen一一
解析：从右子树向父结点退回，每退回一次，结点的路径长度就会减一。
答案：(4)*buff==’0’
解析：编码序列的当前字符是0，则进入左子树分支。
答案：(1)buff一一
解析：到达一个叶子结点时。超前读入了一个编码序列中的字符，因此此处填入buff一一。
●试题7
阅读下列程序说明和C代码，将应填入(13)处的字句写在答题纸的对应栏内。
【程序说明】
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为s，设有N件物品，其重量分别为w1,w2…．，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于s。
如下程序均能求得“背包问题”的一组解，其中程序5．1是“背包问题”的递归解法，而程序5．2是“背包问题”的非递归解法。
【程序】
【程序5．2】
答案：(1)bag(S—w[ n ]，n一1)
解析：此处含义是。选择一个物品放入背包后，剩余物品和剩余背包空间又构成一个背包问题，如果该问题可
解。则当前物品是可以放入包内的，于是接下来的语句打印当前物品。
答案：(2)bag(S，n一1)
解析：程序执行到此处时。选择一个物品放入背包后。剩余物品和剩余背包空间构成的背包问题不可解。则从
下一个物品开始递归寻找结果。
答案：(3)!k&&rep
(4)X．job=1
(5)stack[++top]
(6)rep=0
解析：结构BAGTP表示经过考查的物品。s表示考查过该物品后，背包所能乘放的物品重量；n表示该物品在数组W中的下标；job表示当前物品的状态：“1”。表示物品可以放入背包；“2”。物品不可以放入背包，在以后的选择中将不再考虑该物品。k为有解标志。等于0表示没有解。等于l表示求得了一组解。rep是一个标志变量，等于0时表示结束当前动作；等于l时表示继续当前动作。所以(3)处填!k＆＆rep。第(4)(5)空完成将物品放入背包的操作，因此(4)处填x．job=1，(5)处stack[＋＋top]将下一个待考虑物品放入栈中。
(6)处while循环表示将物品从背包取出，即释放该物品在背包中所占空间。并标记为不可放入背包(job=2)，再将其放入栈中；然后继续考察数组下一个物品，因此需要将rep置为0结束当前循环。
●试题8
阅读下列程序说明和c程序，把应填入其中(n)处的字句，写在答卷的对应栏内。
【程序说明】
对角线下元素全为0的矩阵称为上三角矩阵，设对于一个n×n的上三角矩阵a，为节约存贮，只将它的上三角元素按行主序连续存放在数组b中。下面的函数trans在不引入工作数组的情况下，实现将a改为按列主序连续存放在数组b中。
b=(1，2，3，4，5，6，7，8，9，10，11，l2，13，14，15)经调用trans函数后，b变为
b=(1，2，6，3，7，10，4，8，11，13，5，9，12，14，15)
函数tans对数组元素的存贮位置作调整。调整过程中存在若干个循环传送链： b(i1)→b(i2)→…→b(ij)→b(il)1≤j 例如，考察调整后的数组元素b(2)(值为6)，与该元素相关的位置调整将形成下面的循环传送链：
b(2)→b(3)→b(6)→…→b(12)→b(9)→b(5)→b(2)
关键是确定循环传送链的下标i1，i2，…，ij，以及在考察调整后的元素b(k)(k；3，4，…)时
能判定b(k)是已被传送过的某传送链上的元素。
函数ctr(k，n)计算调整后的数组b的第k个元素b(k)在原数组b中的位置，该位置作为函数ctr(k，n)的返回值。函数ctr根据k确定它在矩阵中的行号i和列号j(注意行号和列号均从0算起)，然后按矩阵存放原则计算出它在b中的位置。
【程序】
答案：(1)rr!=k&&cc>=k
解析：当rr不等于k而且CC大于等于k时，才对元素位置进行调整。
答案：(2)cc>=k
解析：对CC大于等于k的情况进行处理。
答案：(3)11r!=k
解析：当rr不等于k时。对数组元素进行循环传送。
答案：(4)m一一
解析：缩小调整范围，当m小于等于0时。调整结束。不再进入while循环。
答案：(5)i>i
解析：循环至i大于等于j停止。此时i、j分别是第k个元素的行号和列号。
●试题9
阅读下列程序说明和c程序，把应填入其中(n)处的字句，写在答卷的对应栏内。
【说明】
现在需要用程序实现以下功能：对于正整数n，输出其和等于n且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为 4=4
4＝3+1
4=2+2
4=2+1+1
4=l+1+1+l
程序中给出了分别采用递归和非递归解法的两个函数recursive()和nonrec()。
函数recursive()采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组a[]中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调整用分解和式函数。
函数nonrec()以要分解的数为参数，另开设一个数组r[]，用于存贮当前还未分解的余数。
在求一个解的第k步时，a[k]为第k个和数，r[k]为相应的余数。当找到一个分解后(此步 r[k]等于0)，输出解，并作回溯处理，从当前k退回到第一个不为1的和数，将其减1，并将其余数加l，准备去找另一个解；否则，生成下一步的分解和数与余数。
【c程序】
答案：(1)n 解析：当n小于a[k一1]时，j初始化为n。否则初始化为a[k一1]。
答案：(2)j==n
解析：当j等于n时。表示分解成功。打印输出分解结果。
答案：(3)recursive(n—j，k一1)
解析：当J不等于n时。递归调用函数recursive()对n—j进行分解。
答案：(4)r[k]==0
解析：当r[k]等于0时。打印输出分解结果。
答案：(5)a[k]==1
解析：a[k]等于l时。表示不可再分解。
●试题10
阅读以下程序说明和C程序，将应填人程序中(n)处的字句，写在答卷的对应栏内。 【说明】
下面程序能够实现简单的计算器功能。对任意给定的正确四则运算表达式，程序计算其结果值并输出。表达式中运算分量为无正负号整数，运算符为+、一、*、／，圆括号按常规配对，表达式以字符”=”结束。
函数get_char()为获取表达式的一个合法字符，并将字符存入变量mediacy；函数指针数组func[]是为了统一加减乘除计算而设置的。
【程序】
答案：(1)num*10+mediacy一0′其中0可答成48或Ox30或corch[7]
解析：此处是对数字的处理。将数字字符串转换成有效的数字。例如‘123’转换过程是(1* 10+2)*10+3=123。
答案：(2)(op2>=0)&&(op2<5)或op2<5或op2<=4或!(op2>=5)
解析：op2小于5说明它是运算符，不是括号，进入对运算符的处理。
答案：(3)(*func[opl])(x1，x2)
解析：用x1保存xl和 x2进行opl运算的结果。
答案：(4)op1=op2
解析：将0p2赋值给op1。进入下一次循环。
答案：(5)(木func[op1])
解析：返回对x1和x2进行op1运算的结果。
●试越11
阅读以下程序说明和c程序，将应填入(n)处的字句，写在答卷的对应栏内。
【程序说明】
某网络由n个端点组成，这些端点被物理地分成若干个分离的端点组。同一组内的两件端点 i和j，它们或直接相连，或间接相连(端点i和端点J间接相连是指在这两件端点之间有一个端点相连序列，其中端点i和j分别与这相连序列中的某个端点直接相连)。网络的n个端点被统一编号为0，1，…，n一1。本程序输入所有直接相连的端点号对，分别求出系统各分离端点组中的端点号并输出。
程序根据输入的直接相连的两件端点号，建立n个链表，其中第i个链表的首指针为s[i]，其结点是与端点i直接相连的所有端点号。
程序依次处理各链表。在处理s[i]链表中，用top工作链表重新构造S[i]链表，使s[i]链表对应系统中的一个端点组，其中结点按端点号从小到大连接。
【程序】
答案：(1)s[i]=NULL
解析：将s[i]赋给top，s[i]置为空作为循环的初始条件，循环至top为空。
答案：(2)top=top→1link
解析：用P保存top，用top指向它链接的端点。
答案：(3)s[j]=NULL
解析：此时已经把s[j]结点加到链表中。所以将s[j]置为空作为标志。
答案：(4)y!=NULL&&Y→data 解析：当Y不为空而且Y排在q之前的时候进行for循环。
答案：(5)q→link=Y
解析：当前结点插入重新生成的i链表。
●试题1
阅读下列函数说明和C函数，将应填人(n)处的字句写在答题纸的对应栏内。
【函数说明】
函数TreeDelete(Bitree*root，int e)的功能是：在树根结点指针为root的二叉查找(排序)树上删除键值为value的结点，若删除成功，则函数返回O，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Node{
int data；／*结点的键值*／
struct Node：I：Lchild，木Rchild；／*指向左、右子树的指针*／
}*Bitree；
在二叉查找树上删除一个结点时，有三种情况：
①若待删除的结点P是叶子结点，则直接删除该结点；
②若待删除的结点P只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；
③若待删除的结点P有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点P的值，然后删除结点s，结点s必属于上述①、②情况之一。
【函数】
答案：(1)value
答案：(2)p→Lchild
解析：s用于在要删除结点的左子树上寻找最大结点。此处为s赋初始值。
答案：(3)PP=s
解析：PP用于指向s的父结点，此处先将pp指向s，然后s指向其右子结点。
答案：(4)p→Lchild
解析：若P的左子结点存在。用它来替换P。
答案：(5)pp→Lchild=c
解析：如果P是pp的左子结点，则pp的左指针指向替换结点c。否则用右指针。
●试题2
阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
图G是一个具有n个顶点的AOE网(加权有向图)，图中顶点从1～n依次编号，函数int To- plogical(LkdWDigh G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。图G的存储结构采用邻接表表示，其数据类型定义如下：
答案：(1)P＝p→nextarc
解析：此处的while循环累加当前顶点的入度，累加的方式是不断使P指向下一个弧。答案：(2)Stack[top一一]
解析：程序执行到此处时，入度为0的结点已被压入栈，此时弹出结点并赋给Wo
答案：(3)indegree[p→adjVex]一一
解析：将邻接到顶点W的各顶点的入度减一。
答案：(4)ve[W]+p→weight>ve[p→adjvex]
解析：判断最长路径长度是否需要更新。
答案：(5)ve[W]
解析：汇点的最早发生时间就是该AOE网络的关键路径长度，而汇点是从栈中弹出的最后一个顶点。
●试题3
阅读以下说明和C程序，将应填人(n)处的字句写在答题纸的对应栏内。
【说明】
并行计算中需要将N个作业分配给N个处理器同时去完成，每个处理器都能承担这N个作业，但耗时不同。下面的程序用回溯法计算总耗时最小的一种作业分配方案，在该方案中为每个处理器分配l个不同的作业。
程序中，N个作业从0开始依次编号，N个处理器也从0开始依次编号，主要的变量说明如下：
C[i][j]：将作业i分配给处理器j的耗时；
job[i]：值为0表示作业i未分配，值为j表示作业i分配给处理器j；
processor[k]：值为0表示处理器k未分配作业，值为
l表示处理器k已分配作业；
mincost：最小总耗时.
【C程序】
答案：(1)K==N或K>=N
解析：当K等于N时。表示分配最后一个任务。其后便不再进入循环。
答案：(2)processor[i]==0
解析：判断当前处理器未分配而且总费用较小时。对处理器i分配作业。
答案：(3)i
解析：表示将作业k分配给处理器i。
答案：(4)k+1
解析：开始分配第k+1个作业。
答案：(5)processor[i]=0
解析：将分配处理器i的作业撤销。以便考察其他方案。
●试题4
阅读以下函数说明、图和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
散列文件是按桶(BUCKET)存放的。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
例如：设散列函数为Hash(Key)=Key mod 6，记录的关键字序列为l2、13、128、75、81、18、14、21、l7、30、44、89、54、5、66、125、59、605，建立的散列文件内容如图2．1所示。
为简化起见，散列文件的存储单位以内存单元表示。
函数Insert(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值0；否则返回值-1。
采用的散列函数为Hash(NewElemKey)=NewElemKey％P，其中P设定的基桶数目。
函数中使用的预定义符号如下：
#define NULLKEY-1 ／*散列桶的空闲单元标识*／
#define P 6 ／*散列文件中基桶的数目*／
#define ITEMS 3 ／*基桶和溢出桶的容量*／
typedef struct BucketNode{ ／*基桶和溢出桶的类型定义*／
int KeyDam[ITEMS]；
struct BucketNode*Link；}BUCKET；
BUCKET Bucket[P]； ／*基桶空间定义*／
答案：(1)i
答案：(1)i
解析：i
解析：表示当前溢出桶插入不成功，前进到下一个溢出桶。
答案：(4)t==NULL(或!t)
解析：当再无可用的溢出桶时(t==NULL)，需要新申请溢出桶并将元素加入。
答案：(5)t=s
解析：将新生成的溢出桶添加至链表末尾。
●试题5
阅读以下说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
在一图像处理系统中，开发者定义了一个图像结构ImageCon，其中定义了图像应该具有的属性。当图像件的内容或状态发生变化时，与之相关联的ImageView结构的值都需要发生改变。一个ImageCon结构能够关联一组ImageView结构。当ImageCon结构的内容或状态发生变化时，所有与之相关联的ImageView结构都将被更新，这种应用被称为观察者模式。以下代码采用c语言实现，能够正确编译通过。
【c代码】
答案：(1)*func
解析：定义func类型。
答案：(2)struct ImageView*
解析：由myObs的功能可知，它是struct ImageView*类型的。
答案：(3)index-1
解析：将index-1处的值赋给loop处的值。
答案：(4)&im9或img→myObs[100p]
解析：逐个更新ImageView结构变量。
答案：(5)notifyObs(&img)
解析：通知与ImageCon相关的所有ImageView变量。
阅读以下预备知识、函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。【预备知识】
①对给定的信号集合及相应的出现概率，采用哈夫曼编码算法构造最优编码，并用结构数组存
储最优二叉树。例如，给定信号集合{a，b，C}及其出现概率0．1、0．7、O．2，可构造如图2．2所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)(见表2．1)。
●试题6
结构数组Ht的类型定义如下：
#define MAXLEAFNUM 20
struct node{
char signal； ／*当前结点表示的信号，对于非叶子结点，此域不用*／
int frequency； ／*当前结点的出现频率*／
int parent； ／*当前结点的父结点的下标，为0时表示无父结点*／
int lchild，rchild；
／*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*／
}Ht[2*MAXLEAFNUM]；
②用’0’或’1’标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用’
0’(‘1’)标识该分支。
③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由’0’、’1’组成的一个序列，称此序列为该叶子结点的前缀编码。例如图2．10所示的叶子结点a,b、C的前缀编码分别是10、0、11。
【函数说明】
函数void LeafCode(int root，int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。
在构造过程中，将Ht[p]．frequencv域用作被遍历结点的谝历状杰标志．
【函数说明】
函数void Decode(char*buff，int root)的功能是：将前缀编码序列翻译成叶子结点的信号序列并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。
答案：(1)code[cdlen]=’＼0’
解析：设置源串的串结束标志。
答案：(2)Ht[P]．parent
解析：从右子树向父结点退回。
答案：(3)cdlen一一
解析：从右子树向父结点退回，每退回一次，结点的路径长度就会减一。
答案：(4)*buff==’0’
解析：编码序列的当前字符是0，则进入左子树分支。
答案：(1)buff一一
解析：到达一个叶子结点时。超前读入了一个编码序列中的字符，因此此处填入buff一一。
●试题7
阅读下列程序说明和C代码，将应填入(13)处的字句写在答题纸的对应栏内。
【程序说明】
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为s，设有N件物品，其重量分别为w1,w2…．，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于s。
如下程序均能求得“背包问题”的一组解，其中程序5．1是“背包问题”的递归解法，而程序5．2是“背包问题”的非递归解法。
【程序】
【程序5．2】
答案：(1)bag(S—w[ n ]，n一1)
解析：此处含义是。选择一个物品放入背包后，剩余物品和剩余背包空间又构成一个背包问题，如果该问题可
解。则当前物品是可以放入包内的，于是接下来的语句打印当前物品。
答案：(2)bag(S，n一1)
解析：程序执行到此处时。选择一个物品放入背包后。剩余物品和剩余背包空间构成的背包问题不可解。则从
下一个物品开始递归寻找结果。
答案：(3)!k&&rep
(4)X．job=1
(5)stack[++top]
(6)rep=0
解析：结构BAGTP表示经过考查的物品。s表示考查过该物品后，背包所能乘放的物品重量；n表示该物品在数组W中的下标；job表示当前物品的状态：“1”。表示物品可以放入背包；“2”。物品不可以放入背包，在以后的选择中将不再考虑该物品。k为有解标志。等于0表示没有解。等于l表示求得了一组解。rep是一个标志变量，等于0时表示结束当前动作；等于l时表示继续当前动作。所以(3)处填!k＆＆rep。第(4)(5)空完成将物品放入背包的操作，因此(4)处填x．job=1，(5)处stack[＋＋top]将下一个待考虑物品放入栈中。
(6)处while循环表示将物品从背包取出，即释放该物品在背包中所占空间。并标记为不可放入背包(job=2)，再将其放入栈中；然后继续考察数组下一个物品，因此需要将rep置为0结束当前循环。
●试题8
阅读下列程序说明和c程序，把应填入其中(n)处的字句，写在答卷的对应栏内。
【程序说明】
对角线下元素全为0的矩阵称为上三角矩阵，设对于一个n×n的上三角矩阵a，为节约存贮，只将它的上三角元素按行主序连续存放在数组b中。下面的函数trans在不引入工作数组的情况下，实现将a改为按列主序连续存放在数组b中。
b=(1，2，3，4，5，6，7，8，9，10，11，l2，13，14，15)经调用trans函数后，b变为
b=(1，2，6，3，7，10，4，8，11，13，5，9，12，14，15)
函数tans对数组元素的存贮位置作调整。调整过程中存在若干个循环传送链： b(i1)→b(i2)→…→b(ij)→b(il)1≤j
b(2)→b(3)→b(6)→…→b(12)→b(9)→b(5)→b(2)
关键是确定循环传送链的下标i1，i2，…，ij，以及在考察调整后的元素b(k)(k；3，4，…)时
能判定b(k)是已被传送过的某传送链上的元素。
函数ctr(k，n)计算调整后的数组b的第k个元素b(k)在原数组b中的位置，该位置作为函数ctr(k，n)的返回值。函数ctr根据k确定它在矩阵中的行号i和列号j(注意行号和列号均从0算起)，然后按矩阵存放原则计算出它在b中的位置。
【程序】
答案：(1)rr!=k&&cc>=k
解析：当rr不等于k而且CC大于等于k时，才对元素位置进行调整。
答案：(2)cc>=k
解析：对CC大于等于k的情况进行处理。
答案：(3)11r!=k
解析：当rr不等于k时。对数组元素进行循环传送。
答案：(4)m一一
解析：缩小调整范围，当m小于等于0时。调整结束。不再进入while循环。
答案：(5)i>i
解析：循环至i大于等于j停止。此时i、j分别是第k个元素的行号和列号。
●试题9
阅读下列程序说明和c程序，把应填入其中(n)处的字句，写在答卷的对应栏内。
【说明】
现在需要用程序实现以下功能：对于正整数n，输出其和等于n且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为 4=4
4＝3+1
4=2+2
4=2+1+1
4=l+1+1+l
程序中给出了分别采用递归和非递归解法的两个函数recursive()和nonrec()。
函数recursive()采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组a[]中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调整用分解和式函数。
函数nonrec()以要分解的数为参数，另开设一个数组r[]，用于存贮当前还未分解的余数。
在求一个解的第k步时，a[k]为第k个和数，r[k]为相应的余数。当找到一个分解后(此步 r[k]等于0)，输出解，并作回溯处理，从当前k退回到第一个不为1的和数，将其减1，并将其余数加l，准备去找另一个解；否则，生成下一步的分解和数与余数。
【c程序】
答案：(1)n 解析：当n小于a[k一1]时，j初始化为n。否则初始化为a[k一1]。
答案：(2)j==n
解析：当j等于n时。表示分解成功。打印输出分解结果。
答案：(3)recursive(n—j，k一1)
解析：当J不等于n时。递归调用函数recursive()对n—j进行分解。
答案：(4)r[k]==0
解析：当r[k]等于0时。打印输出分解结果。
答案：(5)a[k]==1
解析：a[k]等于l时。表示不可再分解。
●试题10
阅读以下程序说明和C程序，将应填人程序中(n)处的字句，写在答卷的对应栏内。 【说明】
下面程序能够实现简单的计算器功能。对任意给定的正确四则运算表达式，程序计算其结果值并输出。表达式中运算分量为无正负号整数，运算符为+、一、*、／，圆括号按常规配对，表达式以字符”=”结束。
函数get_char()为获取表达式的一个合法字符，并将字符存入变量mediacy；函数指针数组func[]是为了统一加减乘除计算而设置的。
【程序】
答案：(1)num*10+mediacy一0′其中0可答成48或Ox30或corch[7]
解析：此处是对数字的处理。将数字字符串转换成有效的数字。例如‘123’转换过程是(1* 10+2)*10+3=123。
答案：(2)(op2>=0)&&(op2<5)或op2<5或op2<=4或!(op2>=5)
解析：op2小于5说明它是运算符，不是括号，进入对运算符的处理。
答案：(3)(*func[opl])(x1，x2)
解析：用x1保存xl和 x2进行opl运算的结果。
答案：(4)op1=op2
解析：将0p2赋值给op1。进入下一次循环。
答案：(5)(木func[op1])
解析：返回对x1和x2进行op1运算的结果。
●试越11
阅读以下程序说明和c程序，将应填入(n)处的字句，写在答卷的对应栏内。
【程序说明】
某网络由n个端点组成，这些端点被物理地分成若干个分离的端点组。同一组内的两件端点 i和j，它们或直接相连，或间接相连(端点i和端点J间接相连是指在这两件端点之间有一个端点相连序列，其中端点i和j分别与这相连序列中的某个端点直接相连)。网络的n个端点被统一编号为0，1，…，n一1。本程序输入所有直接相连的端点号对，分别求出系统各分离端点组中的端点号并输出。
程序根据输入的直接相连的两件端点号，建立n个链表，其中第i个链表的首指针为s[i]，其结点是与端点i直接相连的所有端点号。
程序依次处理各链表。在处理s[i]链表中，用top工作链表重新构造S[i]链表，使s[i]链表对应系统中的一个端点组，其中结点按端点号从小到大连接。
【程序】
答案：(1)s[i]=NULL
解析：将s[i]赋给top，s[i]置为空作为循环的初始条件，循环至top为空。
答案：(2)top=top→1link
解析：用P保存top，用top指向它链接的端点。
答案：(3)s[j]=NULL
解析：此时已经把s[j]结点加到链表中。所以将s[j]置为空作为标志。
答案：(4)y!=NULL&&Y→data
答案：(5)q→link=Y
解析：当前结点插入重新生成的i链表。