全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2009 年 下 半 年 程 序 员 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 请 按 下 述 要 求 正 确 填 写 答 题 纸 1. 在 答 题 纸 的 指 定 位 置 填 写 你 所 在 的 省 自 治 区 直 辖 市 计 划 单 列 市 的 名 称 2. 在 答 题 纸 的 指 定 位 置 填 写 准 考 证 号 出 生 年 月 日 和 姓 名 3. 答 题 纸 上 除 填 写 上 述 内 容 外 只 能 写 解 答 4. 本 试 卷 共 6 道 题, 试 题 一 至 试 题 四 是 必 答 题, 试 题 五 至 试 题 六 选 答 1 道 每 题 15 分, 满 分 75 分 试 题 号 一 ~ 四 五 ~ 六 选 择 方 法 必 答 题 选 答 1 题 5. 解 答 时 字 迹 务 必 清 楚, 字 迹 不 清 时, 将 不 评 分 6. 仿 照 下 面 例 题, 将 解 答 写 在 答 题 纸 的 对 应 栏 内 例 题 2009 年 下 半 年 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 日 期 是 (1) 月 (2) 日 因 为 正 确 的 解 答 是 11 月 14 日, 故 在 答 题 纸 的 对 应 栏 内 写 上 11 和 14 ( 参 看 下 表 ) 例 题 解 答 栏 (1) 11 (2) 14 2009 年 下 半 年 程 序 员 下 午 试 卷 第 1 页 ( 共 9 页 )
试 题 一 ( 共 15 分 ) 阅 读 以 下 说 明 和 流 程 图, 填 补 流 程 图 中 的 空 缺 (1)~(5), 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 求 连 续 函 数 f(x) 的 根 ( 方 程 f(x)=0 的 解 ) 的 最 简 单 方 法 是 二 分 法 为 此, 首 先 需 要 在 若 干 点 上 检 查 函 数 值 的 符 号, 如 果 发 现 f(a) 与 f(b) 符 号 相 反 (a<b), 则 在 区 间 (a,b) 中 必 然 存 在 f(x) 的 根 因 为 当 x 从 a 变 到 b 时, 连 续 函 数 的 值 将 从 正 变 到 负 ( 或 从 负 变 到 正 ), 必 然 要 经 过 0 区 间 (a,b) 就 是 根 的 初 始 范 围 取 该 区 间 的 中 点 m, 如 果 f(m)=0, 则 根 就 是 m 如 果 f(a) 与 f(m) 符 号 相 反, 则 根 一 定 在 区 间 (a,m) 中 ; 如 果 f(m) 与 f(b) 符 号 相 反, 则 根 一 定 在 区 间 (m,b) 中 因 此, 根 的 范 围 缩 小 了 一 半 依 此 类 推, 将 区 间 一 半 一 半 地 分 下 去, 当 区 间 的 长 度 很 小 ( 达 到 根 的 精 度 要 求, 例 如 0.001) 时, 或 者 当 区 间 中 点 处 的 函 数 值 几 乎 接 近 于 0( 即 绝 对 值 小 于 预 先 规 定 的 微 小 量, 例 如 0.001) 时, 近 似 计 算 就 可 以 结 束 了 以 下 流 程 图 描 述 了 用 二 分 法 近 似 计 算 区 间 (a,b) 中 f(x) 的 根 的 过 程 流 程 图 f(a) y1, f(b) y2 y1 y2>0? true false. (1) x,. (2) y. (3) < 0.001? true false x. (4). true y y1< 0? false x. (5) y y1 false b-a < 0.001? true 输 出 根 x 输 出 失 败 信 息 2009 年 下 半 年 程 序 员 下 午 试 卷 第 2 页 ( 共 9 页 )
试 题 二 ( 共 15 分 ) 阅 读 以 下 说 明 和 C 函 数, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 1 函 数 Counter(int n, int w[]) 的 功 能 是 计 算 整 数 n 的 二 进 制 表 示 形 式 中 1 的 个 数, 同 时 用 数 组 w 记 录 该 二 进 制 数 中 1 所 在 位 置 的 权 例 如, 十 进 制 数 22 的 二 进 制 表 示 为 10110 对 于 该 二 进 制 数,1 的 个 数 为 3, 在 w[0] 1 2 4 中 存 入 2( 即 2 ) w[1] 中 存 入 4( 即 2 ) w[2] 中 存 入 16( 即 2 ) C 函 数 1 int Counter(int n, int w[]) { int i = 0, k = 1; while ( (1) ) { if (n% 2) w[i++] = k; n = n / 2; (2) ; return i; 说 明 2 函 数 Smove(int A[], int n) 的 功 能 是 将 数 组 中 所 有 的 奇 数 都 放 到 所 有 偶 数 之 前 其 过 程 为 : 设 置 数 组 元 素 下 标 索 引 i( 初 值 为 0) 和 j( 初 值 为 n-1), 从 数 组 的 两 端 开 始 检 查 元 素 的 奇 偶 性 若 A[i] A[j] 都 是 奇 数, 则 从 前 往 后 找 出 一 个 偶 数, 再 与 A[j] 进 行 交 换 ; 若 A[i] A[j] 都 是 偶 数, 则 从 后 往 前 找 出 一 个 奇 数, 再 与 A[i] 进 行 交 换 ; 若 A[i] 是 偶 数 而 A[j] 是 奇 数, 则 交 换 两 者, 直 到 将 所 有 的 奇 数 都 排 在 所 有 偶 数 之 前 为 止 C 函 数 2 void Smove(int A[], int n) { int temp, i = 0, j = n-1; if ( n < 2 ) return; while ( i < j ) { if ( A[i] % 2 == 1 && A[j] % 2 == 1 ) { (3) ; else if ( A[i] % 2 == 0 && A[j] % 2 == 0 ) { (4) ; else { if ( (5) ) { temp = A[i]; A[i] = A[j]; A[j] = temp; i++, j--; 2009 年 下 半 年 程 序 员 下 午 试 卷 第 3 页 ( 共 9 页 )
试 题 三 ( 共 15 分 ) 阅 读 以 下 说 明 C 函 数 和 问 题, 将 解 答 写 入 答 题 纸 的 对 应 栏 内 说 明 1 函 数 test_f1(int m, int n) 对 整 数 m n 进 行 某 种 运 算 后 返 回 一 个 整 数 值 C 函 数 1 int test_f1(int m, int n) { int k; k = m > n? m : n; for(;(k%m!=0) (k%n!=0);k++); return k; 问 题 1 (5 分 ) (1) 请 写 出 发 生 函 数 调 用 test_f1(9,6) 时, 函 数 的 返 回 值 ; (2) 请 说 明 函 数 test_f1 的 功 能 说 明 2 设 在 某 C 系 统 中 为 每 个 字 符 分 配 1 个 字 节, 为 每 个 指 针 分 配 4 个 字 节,sizeof(x) 计 算 为 x 分 配 的 字 节 数 函 数 test_f2() 用 于 测 试 并 输 出 该 C 系 统 为 某 些 数 据 分 配 的 字 节 数 C 函 数 2 void test_f2( ) { char str[] = "NewWorld"; char *p = str; char i = '\0'; void *ptr = malloc(50); printf("%d\t", sizeof(str)); printf("%d\n", sizeof(p)); printf("%d\t", sizeof(i)); printf("%d\n ", sizeof(ptr)); 问 题 2 (4 分 ) 请 写 出 函 数 test_f2() 的 运 行 结 果 说 明 3 函 数 test_f3(char s[]) 的 功 能 是 : 将 给 定 字 符 串 s 中 的 所 有 空 格 字 符 删 除 后 形 成 的 串 保 存 在 字 符 数 组 tstr 中 ( 串 s 的 内 容 不 变 ), 并 返 回 结 果 串 的 首 地 址 C 函 数 3 char *test_f3 (const char s[]) { char tstr[50]={'\0'; unsigned int i, k = 0; for(i=0; i<strlen(s); i++) if (s[i]!= ' ') tstr[k++] = s[i]; return tstr; 问 题 3 (6 分 ) 函 数 test_f3() 对 返 回 值 的 处 理 有 缺 陷, 请 指 出 该 缺 陷 并 说 明 修 改 方 法 2009 年 下 半 年 程 序 员 下 午 试 卷 第 4 页 ( 共 9 页 )
试 题 四 ( 共 15 分 ) 阅 读 以 下 说 明 和 C 函 数, 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 函 数 del_substr(s,t) 的 功 能 是 从 头 至 尾 扫 描 字 符 串 S, 删 除 其 中 与 字 符 串 T 相 同 的 所 有 子 串, 其 处 理 过 程 为 : 首 先 从 串 S 的 第 一 个 字 符 开 始 查 找 子 串 T, 若 找 到, 则 将 后 面 的 字 符 向 前 移 动 将 子 串 T 覆 盖 掉, 然 后 继 续 查 找 子 串 T, 否 则 从 串 S 的 第 二 个 字 符 开 始 查 找, 依 此 类 推, 重 复 该 过 程, 直 到 串 S 的 结 尾 为 止 该 函 数 中 字 符 串 的 存 储 类 型 SString 定 义 如 下 : typedef struct { SString; C 函 数 char *ch; /* 串 空 间 的 首 地 址 */ int length; /* 串 长 */ void del_substr(sstring *S, SString T) { int i, j; if ( S->length < 1 T.length < 1 S->length < T.length ) return; i = 0; /* i 为 串 S 中 字 符 的 下 标 */ for ( ; ; ) { j = 0; /* j 为 串 T 中 字 符 的 下 标 */ while ( i < S->length && j < T.length ) { /* 在 串 S 中 查 找 与 T 相 同 的 子 串 */ if ( S->ch[i]==T.ch[j] ) { i++; j++; else { i = (1) ; j = 0; /* i 值 回 退, 为 继 续 查 找 T 做 准 备 */ if ( (2) ){ /* 在 S 中 找 到 与 T 相 同 的 子 串 */ i = (3) ; /* 计 算 S 中 子 串 T 的 起 始 下 标 */ for(k = i+t.length; k<s->length; k++) /* 通 过 覆 盖 子 串 T 进 行 删 除 */ S->ch[ (4) ] = S->ch[k]; S->length = (5) ; /* 更 新 S 的 长 度 */ else break; /* 串 S 中 不 存 在 子 串 T*/ 2009 年 下 半 年 程 序 员 下 午 试 卷 第 5 页 ( 共 9 页 )
从 下 列 2 道 试 题 ( 试 题 五 至 试 题 六 ) 中 任 选 1 道 解 答 如 果 解 答 的 试 题 数 超 过 1 道, 则 题 号 小 的 1 道 解 答 有 效 试 题 五 ( 共 15 分 ) 阅 读 以 下 说 明 和 C++ 代 码, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 已 知 类 LinkedList 表 示 列 表 类, 该 类 具 有 四 个 方 法 :addelement() lastelement() numberofelement() 以 及 removelastelement() 四 个 方 法 的 含 义 分 别 为 : void addelement(object): 在 列 表 尾 部 添 加 一 个 对 象 ; Object lastelement(): 返 回 列 表 尾 部 对 象 ; int numberofelement(): 返 回 列 表 中 对 象 个 数 ; void removelastelement(): 删 除 列 表 尾 部 的 对 象 现 需 要 借 助 LinkedList 来 实 现 一 个 Stack 栈 类,C++ 代 码 1 和 C++ 代 码 2 分 别 采 用 继 承 和 组 合 的 方 式 实 现 C++ 代 码 1 class Stack :public LinkedList{ public: void push(object o){ addelement(o); ; // 压 栈 Object peek(){ return (1) ; ; // 获 取 栈 顶 元 素 bool isempty(){ // 判 断 栈 是 否 为 空 return numberofelement() == 0; ; Object pop(){ // 弹 栈 Object o = lastelement(); (2) ; return o; ; ; C++ 代 码 2 class Stack { private: (3) ; public: void push(object o){ // 压 栈 list.addelement(o); ; Object peek(){ // 获 取 栈 顶 元 素 return list. (4) ; 2009 年 下 半 年 程 序 员 下 午 试 卷 第 6 页 ( 共 9 页 )
; ; bool isempty(){ // 判 断 栈 是 否 为 空 return list.numberofelement() == 0; ; Object pop(){// 弹 栈 Object o = list.lastelement(); list.removelastelement(); return o; ; 问 题 若 类 LinkedList 新 增 加 了 一 个 公 有 的 方 法 removeelement(int index), 用 于 删 除 列 表 中 第 index 个 元 素, 则 在 用 继 承 和 组 合 两 种 实 现 栈 类 Stack 的 方 式 中, 哪 种 方 式 下 Stack 对 象 可 访 问 方 法 removeelement(int index)? (5) (A. 继 承 B. 组 合 ) 2009 年 下 半 年 程 序 员 下 午 试 卷 第 7 页 ( 共 9 页 )
试 题 六 ( 共 15 分 ) 阅 读 以 下 说 明 和 Java 代 码, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 已 知 类 LinkedList 表 示 列 表 类, 该 类 具 有 四 个 方 法 :addelement() lastelement() numberofelement() 以 及 removelastelement() 四 个 方 法 的 含 义 分 别 为 : void addelement(object): 在 列 表 尾 部 添 加 一 个 对 象 ; Object lastelement(): 返 回 列 表 尾 部 对 象 ; int numberofelement(): 返 回 列 表 中 对 象 个 数 ; void removelastelement(): 删 除 列 表 尾 部 的 对 象 现 需 要 借 助 LinkedList 来 实 现 一 个 Stack 栈 类,Java 代 码 1 和 Java 代 码 2 分 别 采 用 继 承 和 组 合 的 方 式 实 现 Java 代 码 1 public class Stack extends LinkedList{ public void push(object o){ // 压 栈 addelement(o); public Object peek(){ // 获 取 栈 顶 元 素 return (1) ; public boolean isempty(){ // 判 断 栈 是 否 为 空 return numberofelement() == 0; public Object pop(){ // 弹 栈 Object o = lastelement(); (2) ; return o; Java 代 码 2 public class Stack { private (3) ; public Stack(){ list = new LinkedList(); public void push(object o){ list.addelement(o); 2009 年 下 半 年 程 序 员 下 午 试 卷 第 8 页 ( 共 9 页 )
public Object peek(){// 获 取 栈 顶 元 素 return list. (4) ; public boolean isempty(){// 判 断 栈 是 否 为 空 return list.numberofelement() == 0; public Object pop(){ // 弹 栈 Object o = list.lastelement(); list.removelastelement(); return o; 问 题 若 类 LinkedList 新 增 加 了 一 个 公 有 的 方 法 removeelement(int index), 用 于 删 除 列 表 中 第 index 个 元 素, 则 在 用 继 承 和 组 合 两 种 实 现 栈 类 Stack 的 方 式 中, 哪 种 方 式 下 Stack 对 象 可 访 问 方 法 removeelement(int index)? (5) (A. 继 承 B. 组 合 ) 2009 年 下 半 年 程 序 员 下 午 试 卷 第 9 页 ( 共 9 页 )