【计算机类职业资格】中级软件设计师下午试题-130及答案解析.doc

《【计算机类职业资格】中级软件设计师下午试题-130及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】中级软件设计师下午试题-130及答案解析.doc（9页珍藏版）》请在麦多课文档分享上搜索。

1、中级软件设计师下午试题-130 及答案解析(总分：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=0，1，

2、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个记录，当桶中已有 m个同义词(散列函数值相同)的记录时，

4、存放第 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）_三、试题三(总题数：1，分数：25.00)4.说明 在

5、一公文处理系统中，开发者定义了一个公文结构 OfficeDoc，其中定义了公文应该具有的属性。当系统中的文件内容或状态发生变化时，与之相关联的 DocExplorer结构的值都需要发生改变。一个 OfficeDoc结构能够关联一组 DocExplorer结构。当 OfficeDoc结构的内容或状态发生变化时，所有与之相关联的DocExplorer结构都将被更新，这种应用被称为观察者模式。以下代码采用 C语言实现，能够正确编译通过。 C程序 #includestdio.h #define OBS_MAXNUM 20/*一个 OfficeDoc变量最多能够关联的 DocExplorer结构变量的个

6、数*/ typedef void(_)(struct OfficeDoc*, struct DocExplorer*); struct DocExplorer func update; /*DocExplorer结构采用的更新函数*/ /*其他的结构字段省略*/ ; Struct OfficeDoc _ myObsOBS_MAXNUM; /*存储所有与 OfficeDoc相关联的 DocExplorer结构指针*/ int index; /*与 OfficeDoc结构变量相关联的 DocExplorer结构变量的个数*/ ; Void attach (struct OfficeDoc *doc

7、, 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 DocExplorer *b) /*解除 doc结构与 ob结构

8、间的关系*/ 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结构的值，更新代码省略*/ void update2 (struc

9、t 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; /*定义一个 OfficeDoc变量*/ struct DocExplorer explor

10、er1, explorer2; /*定义两个 DocExplorer变量*/ /*初始化与 OfficeDoc变量相关的 DocExplorer变量个数为 0*/ doc. index=0; explorer1. update = update1; /*设置 explorer1 变量的更新函数*/ explorer2. update = update2; /*设置 explorer2 变量的更新函数*/ attach ( /*关联 explorer1与 doc对象*/ attach ( /*关联 explorer2与 doc对象*/ /*其他代码省略*/ _; /*通知与 OfficeDoc相

11、关的所有 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表示递归函数当前考虑元素 di，参数 sigma是调用前已选取的部分序列的元素和，参数 rear是后面还未考虑的那部分元素的元素和。 函数对元素 di有以下

12、两种可能的选择方案。 (1)考虑元素 di被包含在新的部分元素序列中的可能性。如果在当前部分元素序列之后接上 di，新序列的元素和不超过 total，则函数将 di包含在当前部分元素序列中。如果新的部分元素序列的元素和等于 total，新的部分元素序列就是一个解答，函数将其输出；否则，若继续考虑后面的元素还有可能找到解答时，函数就递归去考虑后面的元素，寻找解答。最后，函数应恢复原来部分元素序列中不包含 di的状态。 (2)考虑元素 di不被包含在新的部分元素序列中的可能性。如果继续向 di之后考虑还是有希望能得到和为 total的部分元素序列时，函数将新序列(不包含 di)也作为一种可能的选择

13、，并递归去考虑后面的元素，寻找解答。 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被考虑在部分元素序列中 */ if (_=total) /* 输出解 */ for (j=0; flgj = 0; j+) printf (

14、“%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+tigma =total) sum(i+1, total, _, rear-di, d, n); main() int i, j, n, t

15、otal, 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）_中级软件设计师下

16、午试题-130 答案解析(总分：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=0，1，n)为指向树根节点

17、的指针，且指针 A i-1 所指子树中所有节点的关键字均小于 k i ，A i+1 所指子树中所有节点的关键字均大于 k i ；n 为节点中关键字的数目。 (5)所有的叶子节点都出现在同一层次上，并且不带信息(可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。 例如，一棵 4阶 B树如图 1所示(节点中关键字的数目省略)。 （分数：12.50）_正确答案：()解析：pnumkeys 或其等价形式 pKmidakey 或其等价形式 pAhi或 pAlw-1或其等价形式2.说明 2 在 M阶 B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关

18、键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增 1。 例如，在图 1所示的 B树中插入关键字 25时，需将其插入节点 e中。由于 e中已经有 3个关键字，因此将关键字 24插入节点 e的父节点 b中，并以 24为分界线将节点 e分裂为 e1和 e2两个节点，结果如图 2所示。 （分数：12.50）_正确答案：()解析：root，akey， struct DocExp

19、lorer func update; /*DocExplorer结构采用的更新函数*/ /*其他的结构字段省略*/ ; Struct OfficeDoc _ myObsOBS_MAXNUM; /*存储所有与 OfficeDoc相关联的 DocExplorer结构指针*/ int index; /*与 OfficeDoc结构变量相关联的 DocExplorer结构变量的个数*/ ; Void attach (struct OfficeDoc *doc, struct DocExplorer *ob) /*关联 Obersver结构 ob与 OfficeDoc结构 doc*/ int loop =

20、 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 DocExplorer *b) /*解除 doc结构与 ob结构间的关系*/ int loop; if (ob = NULL) return; for (loop = 0; loop doc index; loo

21、p+) 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结构的值，更新代码省略*/ void update2 (struct OfficeDoc *doc, struct DocExplorer *ob) /*更新 ob结构的值，更新代码省略*/ void notify

22、Obs (struct OfficeDoc *doc) /*当 doc结构的值发生变化时，通知与之关联的所有 DocExplorer结构变量*/ int loop; for (loop = 0; loop docindex; loop+) (docmyObs loop)update(_); void main() struct OfficeDoc doc; /*定义一个 OfficeDoc变量*/ struct DocExplorer explorer1, explorer2; /*定义两个 DocExplorer变量*/ /*初始化与 OfficeDoc变量相关的 DocExplorer变量

23、个数为 0*/ doc. index=0; explorer1. update = update1; /*设置 explorer1 变量的更新函数*/ explorer2. update = update2; /*设置 explorer2 变量的更新函数*/ attach ( /*关联 explorer1与 doc对象*/ attach ( /*关联 explorer2与 doc对象*/ /*其他代码省略*/ _; /*通知与 OfficeDoc相关的所有 DocExploer变量*/ return; （分数：25.00）_正确答案：()解析：*func struct DocExplorer*

24、 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与当前序列的和不超过 total*/ flgi=1；/* di被考虑在部分元素序列中 */ if (_=total) /* 输出解 */ for (j=0; flgj = 0; j+) printf (“%4d = %d“, total，dj);

25、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+tigma =total) sum(i+1, total, _, rear-di, d, n); main() int i, j, n, total, s, d; printf (“输入

26、 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