2018杭州师范大学计算机825计算机基础真题.pdf

杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 7页 ， 第 1 页 ）杭州师范大学2018年招收攻读硕士研究生入学考试题考 试 科 目 代 码 ： 825考 试 科 目 名 称 ： 计 算 机 基 础说 明 ： 考 生 答 题 时 一 律 写 在 答 题 纸 上 ， 否 则 漏 批 责 任 自 负 。第 一 部 分 ： 程 序 设 计 基 础 （ C 语 言 ）一 、 判 断 题 （ 每 小 题 2 分 ， 共 20分 ）1、 可 执 行 的 C程 序 一 般 应 该 含 有 main函 数 ， 它 是 C程 序 执 行 的 入 口 。 （ ）2、 在 C语 言 中 ， 标 识 符 是 不 区 分 大 小 写 的 。 （ ）3、 C语 言 的 int类 型 数 据 可 以 表 示 任 何 整 数 。 （ ）4、 在 编 译 C源 程 序 时 ， 计 算 机 根 本 不 会 去 识 别 各 个 变 量 名 的 具 体 含 义 。 但 命 名 规范 对 编 写 C程 序 而 言 是 必 要 的 ， 可 以 提 高 程 序 可 读 性 和 可 维 护 性 。 （ ）5、 在 C语 言 中 ， 可 以 给 指 针 变 量 赋 一 个 整 数 作 为 地 址 值 。 （ ）6、 假 设 有 int a10， *p； 则 p= 则 标 识 符 p是 一 个 指 向 有 4个 整 型 元 素 的 一 维 数 组 的 指 针 变量 。 （ ）8、 若 有 定 义 ： int *p; 使 p指 向 类 型 相 同 的 3个 连 续 存 储 单 元 的 语 句 是 ：p=malloc(3*sizeof(int); （ ）9、 用 malloc函 数 动 态 分 配 的 内 存 是 在 栈 中 分 配 的 ， 而 不 是 在 堆 中 分 配 的 。 （ ）10、 对 二 维 数 组 a34， a+1与 a1都 是 数 组 第 二 行 的 首 地 址 。 （ ）二 、 单 项 选 择 题 （ 每 小 题 2 分 ， 共 40分 ）1、 算 法 是 一 个 计 算 过 程 ， 是 程 序 设 计 的 基 础 和 精 髓 。 一 个 有 效 的 算 法 应 该 具 有 如下 特 点 ， 其 中 错 误 的 是 （ ） 。A.零 个 或 多 个 输 入 及 一 个 或 多 个 输 出 B.无 穷 性C.可 行 性 D.确 定 性杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 7页 ， 第 2 页 ）2、 若 有 以 下 语 句 ：int b; char c10;则 正 确 的 输 入 语 句 是 （ ） 。A. scanf(“%d%s“, B. scanf(“%d%s“, C. scanf(“%s%s“, b, c); D. scanf(“%d%s“, b, 3、 设 a为 5， 执 行 下 列 语 句 后 ， b的 值 不 为 2的 是 （ ） 。A. b = a / 2; B. b = 6 - (-a); C. b = a % 2; D. b = a 3 ? 2 : 2;4、 若 有 定 义 ： int a=3, b=4, c=5; 则 以 下 表 达 式 中 值 为 0的 是 （ ） 。A. a int main(void) f();#ifdef N#undef N#endifreturn 0;void f(void) #if defined(N)printf(“N is %dn“, N);#elseprintf(“N is undefinedn“);#endif2、 以 下 程 序 的 输 出 结 果 是 _。#include void swap1(int c) int t;t = c0;c0 = c1;c1 = t;void swap2(int c0,int c1) int t;t = c0;c0 = c1;c1 = t;int main(void) 杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 7页 ， 第 5 页 ）int a2 = 3, 5, b2 = 3, 5;swap1(a);swap2(b0, b1);printf(“%d#%d#%d#%dn“, a0, a1, b0, b1);return 0;3、 以 下 程 序 的 输 出 结 果 是 _。#include struct node int k;struct node *link;int main(void) struct node m5, *p = m, *q = m + 4;int i = 0;while(p != q) p-k = +i;p+;q-k = i+;q-;q-k = i;for(i = 0; i 0; j - -)printf(“%dn“, j);A. O(n) B. (n2) C. O(nlogn) D. O(n3)2.假 设 一 个 循 环 队 列 QmaxSize的 队 头 指 针 为 front， 队 尾 指 针 为 rear， 队 列 的最 大 容 量 为 maxSize， 除 此 之 外 ， 该 队 列 再 没 有 其 他 数 据 成 员 ， 则 该 队 列 的 队 满 条件 是 ( )。A. front = rear B. front + rear = maxSizeC. rear = (front + 1) % maxSize D. front = (rear + 1)%maxSize3. 若 元 素 1、 2、 3依 次 进 栈 ， 允 许 进 栈 和 出 栈 操 作 交 替 进 行 ， 则 下 列 序 列 中 不 可能 得 到 的 出 栈 序 列 是 ( )。A. 1 2 3 B. 3 1 2 C. 1 3 2 D. 3 2 14.若 用 邻 接 矩 阵 表 示 有 向 图 ， 则 其 中 每 一 列 包 含 的 1 的 个 数 代 表 为 ( )。A 图 中 每 个 顶 点 的 出 度 B 图 中 每 个 顶 点 的 入 度C 图 中 弧 的 条 数 D 图 中 连 通 分 量 的 数 目5.如 果 所 有 关 键 字 都 相 等 ， 那 么 插 入 排 序 算 法 的 时 间 复 杂 度 为 ( )。A. O(1) B.O(n) C. O(nlogn) D.O(n2)6.下 列 排 序 算 法 中 ， 平 均 时 间 复 杂 度 为 O(nlogn)且 占 用 额 外 空 间 最 多 的 是( )。A. 堆 排 序 B. 插 入 排 序 C. 归 并 排 序 D. 快 速 排 序7.若 有 向 图 G=（ V, E） 含 有 7 个 顶 点 ， 要 保 证 图 G 都 是 强 连 通 的 ， 则 需 要 的 边 数最 少 是 ( )。A. 6 B. 7 C. 12 D. 148.若 用 数 组 SN(S0 N-1)作 为 两 个 栈 S1和 S2的 共 用 存 储 结 构 ， 对 任 何 一 个 栈 ，只 有 当 S 数 组 全 满 时 才 不 能 入 栈 操 作 。 为 这 两 个 栈 分 配 空 间 的 最 佳 初 始 方 案 是( )。A. S1的 栈 底 位 置 为 -1， S2的 栈 底 位 置 为 N;B. S1的 栈 底 位 置 为 -1， S2的 栈 底 位 置 为 N / 2;C. S1的 栈 底 位 置 为 0， S2的 栈 底 位 置 为 N-1;D. S1的 栈 底 位 置 为 N/2 -1， S2的 栈 底 位 置 为 N/2。杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 7页 ， 第 7 页 ）9. 以 下 排 序 方 法 中 ， 当 输 入 为 已 排 好 序 的 序 列 时 ， ( )算 法 时 间 复 杂 度 最 高 。A.选 择 排 序 B.插 入 排 序 C.冒 泡 排 序 D.快 速 排 序10.下 列 序 列 中 ， ( )不 是 堆 (heap).A. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10B. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20二 、 填 空 题 (每 空 2分 ， 共 20 分 )1. 若 一 棵 二 叉 树 的 中 序 序 遍 历 序 列 和 后 序 遍 历 序 列 分 别 为 ABCDEFG和 BDCAFGE则该 二 叉 树 的 前 序 遍 历 序 列 为 （ 1） ， 层 序 遍 历 结 果 为 （ 2） 。2. 给 定 序 列 25, 40, 11, 97, 59, 30, 87, 73, 21将 其 进 行 升 序 排 列 ,如 使 用 快速 排 序 （ quicksort） ， 第 一 轮 排 序 完 成 后 序 列 为 （ 3） ； 如 使 用 堆 排 序 （ heapsort） ，第 一 轮 完 成 后 （ 建 堆 完 成 后 ） ， 序 列 为 (4) ； 如 使 用 归 并 排 序 （ mergesort） ， 第 一 轮 完 成 后 序 列 为 （ 5） 。3. 用 顺 序 查 找 法 对 具 有 n个 结 点 的 线 性 表 查 找 一 个 结 点 的 时 间 复 杂 度 为 （ 6） 。4. 实 现 折 半 查 找 的 存 储 结 构 仅 限 于 （ 7） 存 储 结 构 ， 且 其 中 元 素 排 列 必 须是 （ 8） 的 。5. 图 的 DFS 遍 历 类 似 于 树 的 （ 9） 遍 历 ， 图 的 BFS 遍 历 类 似 于 树的 （ 10） 遍 历 。三 、 请 写 出 用 数 组 实 现 的 循 环 队 列 的 入 队 列 和 出 队 列 的 算 法 。 （ 20分 ）四 、 请 写 出 快 速 排 序 的 递 归 算 法 。 （ 15分 ）