1、中级软件设计师下午试题-143 及答案解析(总分：100.00，做题时间：90 分钟)一、试题一(总题数：2，分数：25.00)1.说明 1 B 树是一种多又平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树。 (1)树中每个节点至多有 m 棵子树。 (2)若根节点不是叶子节点，则它至少有两棵子树。 (3)除根之外的所有非叶子节点至少有m/2棵子树。 (4)所有的非叶子节点中包含下列数据信息：(n，A 0 ，K 1 ，A 1 ，K 2 ，A 2 ，K n ，A n )。其中，K i (i=1，2，n)为关键字，且 K i K i +1(i=1，2，n-1)，A i (i
2、=0，1，n)为指向树根节点的指针，且指针 A i-1 所指子树中所有节点的关键字均小于 k i ，A i+1 所指子树中所有节点的关键字均大于 k i ；n 为节点中关键字的数目。 (5)所有的叶子节点都出现在同一层次上，并且不带信息(可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。 例如，一棵 4 阶 B 树如图 1 所示(节点中关键字的数目省略)。 （分数：12.50）_2.说明 2 在 M 阶 B 树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的“分裂”处
3、理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增 1。 例如，在图 1 所示的 B 树中插入关键字 25 时，需将其插入节点 e 中。由于 e 中已经有 3 个关键字，因此将关键字 24 插入节点 e 的父节点 b 中，并以 24 为分界线将节点 e 分裂为 e1 和 e2 两个节点，结果如图 2所示。 （分数：12.50）_二、试题二(总题数：1，分数：25.00)3.说明 散列文件的存储单位称为桶(Bucket)。假如一个桶能存放 m 个记录，当
4、桶中已有 m 个同义词(散列函数值相同)的记录时，存放第 m+1 个同义词会发生“溢出”。此时需要将第 m+1 个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前 m 个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回；否则沿指针到溢出桶中进行查找。 例如，设散列函数为 Hash(Key)=Key mod 7，记录的关键字序列为15，14，21，87，96，293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如下图所示。 （分数：25.00）
5、_三、试题三(总题数：1，分数：25.00)4.说明 在一公文处理系统中，开发者定义了一个公文结构 OfficeDoc，其中定义了公文应该具有的属性。当系统中的文件内容或状态发生变化时，与之相关联的 DocExplorer 结构的值都需要发生改变。一个 OfficeDoc结构能够关联一组 DocExplorer 结构。当 OfficeDoc 结构的内容或状态发生变化时，所有与之相关联的DocExplorer 结构都将被更新，这种应用被称为观察者模式。以下代码采用 C 语言实现，能够正确编译通过。 C 程序 #includestdio.h #define OBS_MAXNUM 20/*一个 Of
6、ficeDoc 变量最多能够关联的 DocExplorer 结构变量的个数*/ typedef void(_)(struct OfficeDoc*, struct DocExplorer*); struct DocExplorer func update; /*DocExplorer 结构采用的更新函数*/ /*其他的结构字段省略*/ ; Struct OfficeDoc _ myObsOBS_MAXNUM; /*存储所有与 OfficeDoc 相关联的 DocExplorer 结构指针*/ int index; /*与 OfficeDoc 结构变量相关联的 DocExplorer 结构变量的
7、个数*/ ; Void attach (struct OfficeDoc *doc, struct DocExplorer *ob) /*关联 Obersver 结构 ob 与 OfficeDoc 结构 doc*/ int loop = 0; if (docindex =OBS_MAXNUM | ob = NULL) return; for (loop=0; loopdocindex; loop+) if (docmyObs loop = ob) return; docmyObs docindex = ob; docindex+; void detach (struct OfficeDoc *
8、doc, struct DocExplorer *b) /*解除 doc 结构与 ob 结构间的关系*/ int loop; if (ob = NULL) return; for (loop = 0; loop doc index; loop+) if (docmyObs loop = ob) if (loop =docindex-2) docmyObs loop = docmyObs _; docmyObsdocindex-1 = NULL; docindex-一 j break; void update1 (struct OfficeDoc *doc, struct DocExplorer
9、 *ob) /*更新 ob 结构的值，更新代码省略*/ void update2 (struct OfficeDoc *doc, struct DocExplorer *ob) /*更新 ob 结构的值，更新代码省略*/ void notifyObs (struct OfficeDoc *doc) /*当 doc 结构的值发生变化时，通知与之关联的所有 DocExplorer 结构变量*/ int loop; for (loop = 0; loop docindex; loop+) (docmyObs loop)update(_); void main() struct OfficeDoc d
10、oc; /*定义一个 OfficeDoc 变量*/ struct DocExplorer explorer1, explorer2; /*定义两个 DocExplorer 变量*/ /*初始化与 OfficeDoc 变量相关的 DocExplorer 变量个数为 0*/ doc. index=0; explorer1. update = update1; /*设置 explorer1 变量的更新函数*/ explorer2. update = update2; /*设置 explorer2 变量的更新函数*/ attach ( /*关联 explorer1 与 doc 对象*/ attach
11、( /*关联 explorer2 与 doc 对象*/ /*其他代码省略*/ _; /*通知与 OfficeDoc 相关的所有 DocExploer 变量*/ return; （分数：25.00）_四、试题四(总题数：1，分数：25.00)5.说明 本程序的函数 sum(int i int total, int sigma, int rear, int d, int n)用来从已知数组 d 的前 n个元素中找出所有部分元素序列之和等于 total 的元素序列，约定数组 d 的元素都是正整数，且都小于等于 total。 函数 sum 使用递归方法找出全部解答。参数 i 表示递归函数当前考虑元素
12、di，参数 sigma 是调用前已选取的部分序列的元素和，参数 rear 是后面还未考虑的那部分元素的元素和。 函数对元素 di有以下两种可能的选择方案。 (1)考虑元素 di被包含在新的部分元素序列中的可能性。如果在当前部分元素序列之后接上 di，新序列的元素和不超过 total，则函数将 di包含在当前部分元素序列中。如果新的部分元素序列的元素和等于 total，新的部分元素序列就是一个解答，函数将其输出；否则，若继续考虑后面的元素还有可能找到解答时，函数就递归去考虑后面的元素，寻找解答。最后，函数应恢复原来部分元素序列中不包含 di的状态。 (2)考虑元素 di不被包含在新的部分元素序列
13、中的可能性。如果继续向 di之后考虑还是有希望能得到和为 total 的部分元素序列时，函数将新序列(不包含 di)也作为一种可能的选择，并递归去考虑后面的元素，寻找解答。 C 程序 #include stdio. h #define N 100 int aN; int flgN; sum (int i, int total, int sigma, int rear, int d, int t) int j; /* 考虑元素 di被包含在新的部分元素序列中的可能性 */ if (sigma + di =total) /*如果 di与当前序列的和不超过 total*/ flgi=1；/* di被
14、考虑在部分元素序列中 */ if (_=total) /* 输出解 */ for (j=0; flgj = 0; j+) printf (“%4d = %d“, total，dj); for (j+; j =i; j+) if (flgj) printf (“+%d“, dj); printf(“); else if(i n-1 rear+sigma =total) /* 并且继续考虑后面的元素有可能找到解答时 */ sum (i+1, total, _, rear-di, d, n); _; /* 考虑元素 di不被包含在新的部分元素序列中的可能性*/ if (i n-1 rear-di+t
15、igma =total) sum(i+1, total, _, rear-di, d, n); main() int i, j, n, total, s, d; printf (“输入 total! /n“); scanf (“%d“, printf (“输入 n! /n“); scanf (“%d“, n); for (s = i = 0; i n;) printf (“输入第%d 个元素 0 且 = %d)n“, i+1, total); scanf (“%d“, d); if (d 1 | d total) printf (“出错, 清重新输入! n“); continue; s+=(a
16、i+=d); sum (0, total, 0, _, a, n); printf (“nn“); （分数：25.00）_中级软件设计师下午试题-143 答案解析(总分：100.00，做题时间：90 分钟)一、试题一(总题数：2，分数：25.00)1.说明 1 B 树是一种多又平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树。 (1)树中每个节点至多有 m 棵子树。 (2)若根节点不是叶子节点，则它至少有两棵子树。 (3)除根之外的所有非叶子节点至少有m/2棵子树。 (4)所有的非叶子节点中包含下列数据信息：(n，A 0 ，K 1 ，A 1 ，K 2 ，A 2 ，K
17、n ，A n )。其中，K i (i=1，2，n)为关键字，且 K i K i +1(i=1，2，n-1)，A i (i=0，1，n)为指向树根节点的指针，且指针 A i-1 所指子树中所有节点的关键字均小于 k i ，A i+1 所指子树中所有节点的关键字均大于 k i ；n 为节点中关键字的数目。 (5)所有的叶子节点都出现在同一层次上，并且不带信息(可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。 例如，一棵 4 阶 B 树如图 1 所示(节点中关键字的数目省略)。 （分数：12.50）_正确答案：()解析：pnumkeys 或其等价形式 pKmida
18、key 或其等价形式 pAhi或 pAlw-1或其等价形式2.说明 2 在 M 阶 B 树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增 1。 例如，在图 1 所示的 B 树中插入关键字 25 时，需将其插入节点 e 中。由于 e 中已经有 3 个关键字，因此将关键字 24 插入节点 e 的父节点
19、b 中，并以 24 为分界线将节点 e 分裂为 e1 和 e2 两个节点，结果如图 2所示。 （分数：12.50）_正确答案：()解析：root，akey， struct DocExplorer func update; /*DocExplorer 结构采用的更新函数*/ /*其他的结构字段省略*/ ; Struct OfficeDoc _ myObsOBS_MAXNUM; /*存储所有与 OfficeDoc 相关联的 DocExplorer 结构指针*/ int index; /*与 OfficeDoc 结构变量相关联的 DocExplorer 结构变量的个数*/ ; Void attach
20、 (struct OfficeDoc *doc, struct DocExplorer *ob) /*关联 Obersver 结构 ob 与 OfficeDoc 结构 doc*/ int loop = 0; if (docindex =OBS_MAXNUM | ob = NULL) return; for (loop=0; loopdocindex; loop+) if (docmyObs loop = ob) return; docmyObs docindex = ob; docindex+; void detach (struct OfficeDoc *doc, struct DocExp
21、lorer *b) /*解除 doc 结构与 ob 结构间的关系*/ int loop; if (ob = NULL) return; for (loop = 0; loop doc index; loop+) if (docmyObs loop = ob) if (loop =docindex-2) docmyObs loop = docmyObs _; docmyObsdocindex-1 = NULL; docindex-一 j break; void update1 (struct OfficeDoc *doc, struct DocExplorer *ob) /*更新 ob 结构的值
22、，更新代码省略*/ void update2 (struct OfficeDoc *doc, struct DocExplorer *ob) /*更新 ob 结构的值，更新代码省略*/ void notifyObs (struct OfficeDoc *doc) /*当 doc 结构的值发生变化时，通知与之关联的所有 DocExplorer 结构变量*/ int loop; for (loop = 0; loop docindex; loop+) (docmyObs loop)update(_); void main() struct OfficeDoc doc; /*定义一个 OfficeD
23、oc 变量*/ struct DocExplorer explorer1, explorer2; /*定义两个 DocExplorer 变量*/ /*初始化与 OfficeDoc 变量相关的 DocExplorer 变量个数为 0*/ doc. index=0; explorer1. update = update1; /*设置 explorer1 变量的更新函数*/ explorer2. update = update2; /*设置 explorer2 变量的更新函数*/ attach ( /*关联 explorer1 与 doc 对象*/ attach ( /*关联 explorer2 与
24、 doc 对象*/ /*其他代码省略*/ _; /*通知与 OfficeDoc 相关的所有 DocExploer 变量*/ return; （分数：25.00）_正确答案：()解析：*func struct DocExplorer* docindex-1 doc，docmyObsloop notifyObs( int flgN; sum (int i, int total, int sigma, int rear, int d, int t) int j; /* 考虑元素 di被包含在新的部分元素序列中的可能性 */ if (sigma + di =total) /*如果 di与当前序列的和不
25、超过 total*/ flgi=1；/* di被考虑在部分元素序列中 */ if (_=total) /* 输出解 */ for (j=0; flgj = 0; j+) printf (“%4d = %d“, total，dj); for (j+; j =i; j+) if (flgj) printf (“+%d“, dj); printf(“); else if(i n-1 rear+sigma =total) /* 并且继续考虑后面的元素有可能找到解答时 */ sum (i+1, total, _, rear-di, d, n); _; /* 考虑元素 di不被包含在新的部分元素序列中的可
26、能性*/ if (i n-1 rear-di+tigma =total) sum(i+1, total, _, rear-di, d, n); main() int i, j, n, total, s, d; printf (“输入 total! /n“); scanf (“%d“, printf (“输入 n! /n“); scanf (“%d“, n); for (s = i = 0; i n;) printf (“输入第%d 个元素 0 且 = %d)n“, i+1, total); scanf (“%d“, d); if (d 1 | d total) printf (“出错, 清重新输入! n“); continue; s+=(ai+=d); sum (0, total, 0, _, a, n); printf (“nn“); （分数：25.00）_正确答案：()解析：sigma+di sigma+dj figi=0 sigma s
